数据结构编程题.doc

invsl(n,a)int n;ET a;int k;ET t;for (k=1; knext=P-next;(1) P-next=S;(11) P=L;(8) while(P-next!=Q)P=P-next;(10) P=Q;(4) S-next=P-next;P-next=S;3. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。 注：统计结点个数是【省统考样题】的要求，也是教材P60 4-6计算链表长度的要求，编程又简单，很容易作为考题。解：编写C程序如下(已上机通过)：全局变量及函数提前说明：-#include#includetypedef struct liuyuint data;struct liuyu*link;test;liuyu *p,*q,*r,*head;int m=sizeof(test);void main () /*第一步，从键盘输入整数，不断添加到链表*/int i;head=(test*)malloc(m); /*m=sizeof(test);*/p=head; i=0;while (i!=-9999) printf(/ninput an integer stop by -9999:);scanf(%d,&i);p-data=i; /* input data is saved */p-link=(test*)malloc(m); /*m=sizeof(test);*/q=p;p=p-link;q-link=NULL; /*原先用p-link=NULL似乎太晚！*/ p=head; i=0; /*统计链表结点的个数并打印出来*/while (p-link!=NULL)printf(%d,p-data);p=p-link;i+;printf(n node number=%dn, i-1); /*结点的个数不包括-9999*/4. 请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。答：#include /*全局变量及函数提前说明：*/#includetypedef struct liuyuchar data;struct liuyu*link;test;liuyu *p,*q,*r,*head;int L; /*元素的个数*/int m=sizeof(test);void build(); /* 主函数中会被调用的函数应当预先说明 */void display();int insert_char(char,char); /*插入一个字母，在第字母Y之前，若无字母则加到末尾*/int delet_char(char); /* 删除元素X，注意保存X的前趋元素指针！ */*-*/void build() /*字母链表的生成*/int i;head=(test*)malloc(m); /*m=sizeof(test);*/p=head;for(i=1;idata=i+a-1; /* a也可用其ASCII码97来表示 */p-link=(test*)malloc(m); /*m=sizeof(test);*/p=p-link; p-data=i+a-1;p-link=NULL;/*-*/void display() /*字母链表的输出*/p=head;while (p-link!=NULL) printf(%c,p-data);p=p-link; printf(%cn,p-data);/*-*/int insert_char(char X,char Y) /*插入一个字母X在某个字母Y之前，若找不到Y字母则加到末尾*/p=head;r=(test*)malloc(m);r-data=X;if(head-data=Y) head=r; r-link=p; else while(p-data!=Y)&(p-link!=NULL) q=p; p=p-link; if(p-data=Y) q-link=r; r-link=p; elsep-link=r;r-link=NULL; L+;return(0);/*-*/int delet_char(char X) /* 删除元素X，注意保存X的前趋元素指针！ */ p=head;if(head-data=X)head=head-link;free(p);else while(p-data!=X)&(p-link!=NULL)q=p; p=p-link;if(p-data=X) q-link=p-link; free(p); else return(-1);L-;return(0);/*-*/void main(void) /*字母线性表的生成和输出*/ L=26; build();display();printf(insert return value=%dn,insert_char(L,W);display();printf(delete return value=%dn,delet_char(z);display();附：屏幕上显示的执行结果是：a b c d e f g h i j k l m n o p q r s t u v w x y zinsert return value=0a b c d 9 e f g h i j k l m n o p q r s t u v w x y z Ldelete return value=0a b c d e f g h i j k l m n o p q r s t u v w x y L 1. 假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量（可理解为每个字符占用一个数组元素），表示被判别的表达式，tag为布尔型变量。答：用堆栈st进行判定，将 ( 、 或 入栈，当遇到 、 或 ) 时，检查当前栈顶元素是否是对应的( 、 或 ，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时，若栈为空表示括号正确配对，否则不配对。编程后的整个函数如下（李书P3132）#define m0 100 /*m0为算术表达式中最多字符个数*/correct(exp,tag)char expm0;int tag;char stm0;int top=0, i=1;tag=1;while (i0)tag=0; /*若栈不空，则不配对*/严题集对应答案：3.19 Status AllBrackets_Test(char *str)/判别表达式中三种括号是否匹配 InitStack(s); for(p=str;*p;p+) if(*p=(|*p=|*p=) push(s,*p); else if(*p=)|*p=|*p=) if(StackEmpty(s) return ERROR; pop(s,c); if(*p=)&c!=() return ERROR; if(*p=&c!=) return ERROR; if(*p=&c!=) return ERROR; /必须与当前栈顶括号匹配 /for if(!StackEmpty(s) return ERROR; return OK; /AllBrackets_Test 答案（已上机通过）#include#includevoid push(char x);void pop();void correct(enum Boolean &tag);/原来的定义是void correct(struct Stack* head,enum Boolean &tag);typedef struct Stackchar data;struct Stack *next;struct Stack *head,*p;enum BooleanFALSE,TRUEtag;void main()head=(struct Stack*)malloc(sizeof(struct Stack);head-data=S;head-next=NULL;/ heads data has not been initialized! correct(tag);if(tag)printf(Right!);elseprintf(Wrong!);void push(char x)p=(struct Stack*)malloc(sizeof(struct Stack);if(!p)printf(Theres no space.n);elsep-data=x;p-next=head;head=p;/ if you define the Correct function like that/Debug will show that the Push action doesnt take effectionvoid pop()if(head-next=NULL)printf(The stack is empty.n);elsep=head;head=head-next;free(p);/void correct(struct Stack* head,enum Boolean &tag)void correct(enum Boolean &tag)int i;char y;printf(Please enter a bds:);for(i=0;y!=n;i+)scanf(%c,&y);if(y=)&head-data=()|(y=&head-data=)|(y=&head-data=)pop();else if(y=()|(y=)|(y=)push(y);/*调试程序显示，y并没有被推入堆栈中。即head-data的值在Push中显示为y的值，但是出Push函数。马上变成Null。*/elsecontinue;if(head-next=NULL) /原来的程序是if(head =NULL)tag=TRUE;tag=TRUE;elsetag=FALSE;/*总结： 由于head为全局变量，所以不应该将其再次作为函数的变量。因为C语言的函数变量是传值机制，所以在函数中对参数进行了拷贝复本，所以不能改变head的数值。*/2.假设一个数组squm存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。解：这就是解决队满队空的三种办法之 设置一个布尔变量以区别队满还是队空（其他两种见简答题）；思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1；若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。3.试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。答：编程如下：int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test 1.编写递归算法，计算二叉树中叶子结点的数目。解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。法一：核心部分为：DLR(liuyu *root) /*中序遍历 递归函数*/if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)sum+; printf(%dn,root-data); DLR(root-lchild); DLR(root-rchild); return(0);法二：int LeafCount_BiTree(Bitree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; /叶子结点 else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree 注：上机时要先建树！例如实验二的方案一。 打印叶子结点值（并求总数）思路：先建树，再从遍历过程中打印结点值并统计。步骤1 键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。叶子结点值应该是4，9, 13, 21, 总数应该是4. 127 17 2 11 16 21 4 9 13编程： 生成二叉树排序树之后，再中序遍历排序查找结点的完整程序如下： 说明部分为：#include #include typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排序树的适当位置*/ q=p;if(p-data=x)printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild; if(xdata)q-lchild=s;else q-rchild=s;DLR(liuyu *root) /*中序遍历 递归函数*/if(root!=NULL) if(root-lchild=NULL)&(root-rchild=NULL)sum+; printf(%dn,root-data); DLR(root-lchild); DLR(root-rchild); return(0); main() /*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/int i,x;i=1; root=NULL; /*千万别忘了赋初值给root!*/doprintf(please input data%d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) DLR(root); printf(nNow output count value:%dn,sum); return(0); else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999); return(0);执行结果：若一开始运行就输入-9999，则无叶子输出，sum=0。2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。 （）编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。答；设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。但注意，递归时应当从叶子开始向上计数，否则不易确定层数。 int depth(liuyu*root) /*统计层数*/int d,p; /*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root=NULL)return(p); /*找到叶子之后才开始统计*/else d=depth(root-lchild);if(dp) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/d=depth(root-rchild);if(dp)p=d;p=p+1;return(p);法二：int Get_Sub_Depth(Bitree T,int x)/求二叉树中以值为x的结点为根的子树深度 if(T-data=x) printf(%dn,Get_Depth(T); /找到了值为x的结点,求其深度 exit 1; else if(T-lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找 /Get_Sub_Depth int Get_Depth(Bitree T)/求子树深度的递归算法 if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; /Get_Depth 附：上机调试过程步骤1 键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。层数应当为4 12 8 17 2 11 16 21 4 9 13 步骤2： 执行求深度的函数，并打印统计出来的深度值。完整程序如下：#include #include typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排序树的适当位置*/ q=p;if(p-data=x)printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild; if(xdata)q-lchild=s;else q-rchild=s;int depth(liuyu*root) /*统计层数*/int d,p; /*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root=NULL)return(p); /*找到叶子之后才开始统计*/else d=depth(root-lchild);if(dp) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/d=depth(root-rchild);if(dp)p=d;p=p+1;return(p);void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/int i,x;i=1; root=NULL; /*千万别忘了赋初值给root!*/doprintf(please input data%d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) printf(nNow output depth value=%dn, depth (root); return; else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999); return;执行结果：3.编写按层次顺序（同一层自左至右）遍历二叉树的算法。或：按层次输出二叉树中所有结点；解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。level(liuyu*T)/* liuyu *T,*p,*q100; 假设max已知*/int f,r;f=0; r=0; /*置空队*/r=(r+1)%max;qr=T; /*根结点进队*/while(f!=r) /*队列不空*/f=(f+1%max);p=qf; /*出队*/printf(%d,p-data); /*打印根结点*/if(p-lchild)r=(r+1)%max; qr=p-lchild; /*若左子树不空，则左子树进队*/ if(p-rchild)r=(r+1)%max; qr=p-rchild; /*若右子树不空，则右子树进队*/ return(0);法二：void LayerOrder(Bitree T)/层序遍历二叉树 InitQueue(Q); /建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /LayerOrder 可以用前面的函数建树，然后调用这个函数来输出。完整程序如下（已上机通过）#include #include #define max 50typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root,*p,*qmax;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排序树的适当位置*/ q=p;if(p-data=x)printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild; if(xdata)q-lchild=s;else q-rchild=s;level(liuyu*T)/* liuyu *T,*p,*q100; 假设max已知*/int f,r;f=0; r=0; /*置空队*/r=(r+1)%max;qr=T; /*根结点进队*/while(f!=r) /*队列不空*/f=(f+1%max);p=qf; /*出队*/printf(%d,p-data); /*打印根结点*/if(p-lchild)r=(r+1)%max; qr=p-lchild; /*若左子树不空，则左子树进队*/ if(p-rchild)r=(r+1)%max; qr=p-rchild; /*若右子树不空，则右子树进队*/ return(0);void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/int i,x;i=1; root=NULL; /*千万别忘了赋初值给root!*/doprintf(please input data%d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) printf(nNow output data value:n, level(root); return; else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999); return;4. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。答：首先，由于是完全二叉树，不必担心中途会出现孩子为null的情况。其次分析：结点i的左孩子为2i，右孩子为2i+1;直接打印即可。Printf(“Left_child=”, %d, v2*i.data; “Right_child=”, %d, v2*i+1.data;);但其双亲是i/2，需先判断i为奇数还是偶数。若i为奇数，则应当先i- ，然后再除以2。If(i/2!=0)i-;Printf(“Parents=”, %d, vi/2.data;);5.编写算法判别给定二叉树是否为完全二叉树。答：int IsFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是则返回1,否则返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作队列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); /不管孩子是否为空,都入队列 /while return 1; /IsFull_Bitree 分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点 是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空 指针的序列.反之,则序列中会含有空指针. 6. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比较：字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码1.编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。解：Status Build_AdjList(ALGraph &G) /输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 InitALGraph(G); scanf(%d,&v); if(v0) return ERROR; /顶点数不能为负 G.vexnum=v; scanf(%d,&a); if(a0) return ERROR; /边数不能为负 G.arcnum=a; for(m=0;mv;m+) G.verticesm.data=getchar(); /输入各顶点的符号 for(m=1;m=a;m+) t=getchar();h=getchar(); /t为弧尾,h为弧头 if(i=LocateVex(G,t)0) return ERROR; if(j=LocateVex(G,h)nextarc;q=q-nextarc); q-nextarc=p; p-adjvex=j;p-nextarc=NULL; /while return OK; /Build_AdjList 2.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ）解：/本题中的图G均为有向无权图。 Status Delete_Arc(MGraph &G,char v,char w)/在邻接矩阵表示的图G上删除边(v,w) if(i=LocateVex(G,v)0) return ERROR; if(j=LocateVex(G,w)nextarc) k=p-adjvex; if(!visitedk&exist_path(k,j) return 1;/i下游的顶点到j有路径 /for /else /exist_path_DFS 解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。）int visitedMAXSIZE; /指示顶点是否在当前路径上 int level1;/递归进行的层数int exist_path_DFS(ALGraph G,int i,int j)/深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 if(i=j) return 1; /i就是j else visitedi=1; for(p=G.verticesi.firstarc;p;p=p-nextarc，level-) level+; k=p-adjvex; if(!visitedk&exist_path(k,j) return 1;/i下游的顶点到j有路径 /for /else if (level=1) return 0;/exist_path_DFS 附加题：采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）int visitedMAXSIZE; int exist_path_len(ALGraph G,int i,int j,int k)/判断邻接表方式存储的有向图G 的顶点i到j是否存在长度为k的简单路径 if(i=j&k=0) return 1; /找到了一条路径,且长度符合要求 else if(k0) visitedi=1; for(p