1. 您所在位置：首页 > 给排水规范 > 设计规范 > 数据结构第一版习题参考答案.doc

数据结构第一版习题参考答案.doc 37页

  • 270.50 KB
  • 2022-04-22 11:52:36 发布

数据结构第一版习题参考答案.doc

  • 37页
  • 当前文档由用户上传发布，收益归属用户
  1. 1、本文档共5页，可阅读全部内容。
  2. 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
  3. 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
  4. 文档侵权举报电话：19940600175。
'数据结构2009年习题参考答案教材数据结构（c语言版）第一版作者李云清等第一章概论概念题从略1.10（1）O(1)(2)O(n)(3)O(n2)第二章线性表的顺序存储2.2intnumber_of_x_sequence_list(sequence_listslt,datatypex){inti,n=0;if(!slt.size){printf("顺序表是空的！");exit(1);}elsefor(i=0;isize){printf("顺序表是空的！");exit(1);}elsefor(i=0;isize/2;i++){temp=slt->a[i];slt->a[i]=slt->a[slt->size-i-1];slt->a[slt->size-i-1]=temp;}}2.4voidinsert_order_sequence_list(sequence_list*slt,datatypex){inti=0;if(slt->size==MAXSIZE){printf("n顺序表是满的!没法插入!");exit(1);}i=find_num_sequence_list(slt,x);insert_pos_sequence_list(slt,i,x);}2.6当rear>=front时，循环队列的元素个数是rear-fornt当rear=1,F(0)=1)具体的完成实现程序如下：#includeintstk[21],out[21];voidgo(intn,intintop,intouttop,intin){inti,t;if(intop==0&&outtop==n){for(i=0;i0){out[outtop]=stk[intop-1];t=stk[intop-1];go(n,intop-1,outtop+1,in);stk[intop-1]=t;}}main(){intn;printf("pleaseinputn:n");scanf("%d",&n);go(n,0,0,0);getch();}第一章线性表的链式存储3.1intcal_link_list(node*head){inti=0;node*q=head; while(q){i++;q=q->next;}printf("nThislistatotal%dofnodes",i);returni;}3.3node*insert_x_before_y(node*head,intx,inty){node*m,*n,*t;m=head;while(m&&m->info!=y){n=m;m=m->next;}t=(node*)malloc(sizeof(node));t->info=x;t->next=m;n->next=t;returnhead;}3.4intjudgement(node*head){node*p=head;if(p&&p->info>=p->next->info){while(p&&p->info>=p->next->info){p=p->next;}}else{while(p&&p->infonext->info){p=p->next;}}if(p->next){ printf("nLinelistisnotarrangeinorder");return0;}else{printf("nLinelistisarrangeinorder");return1;}}3.5node*change(node*head){node*p,*q=0;while(head){p=head->next;head->next=q;q=head;head=p;;}head=q;returnhead;}3.6voidseperate(node*head){node*p1,*p2,*p,*headodd,*headeven,temp;p=head;while(p)/*找到第一个奇数结点，由headodd指向*/{if(p->info%2!=0){headodd=p;break;}elsep=p->next;}p=head;while(p)/*找到第一个偶数结点，由headeven指向*/{if(p->info%2==0){headeven=p;break;}elsep=p->next; }p=head;p1=headodd;p2=headeven;while(p){if(p->info%2!=0&&p==headodd)p=p->next;elseif(p->info%2==0&&p==headeven)p=p->next;elseif(p->info%2!=0){p1->next=p;p1=p;p=p->next;}elseif(p->info%2==0){p2->next=p;p2=p;p=p->next;}}p1->next=p2->next=0;head=headeven;printf("该链表的偶数部分是:");print_link_list(head);printf("n该链表的奇数部分是:");print_link_list(headodd);}3.7node*delete_x_to_y(node*head,intx,inty){node*p=head,*q=head;for(;q;q=q->next){if(q->info>x&&q->info<=y&&q==head)head=q->next;else{if(q->info>x&&q->info<=y){p->next=q->next;}elsep=q;}} returnhead;}第一章字符串、数组和特殊矩阵题4.1#include#defineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;seqstring*init(seqstring*S){S->str[0]="";S->length=0;returnS;}intsign(intr){if(r>0)return1;if(r==0)return0;if(r<0)return-1;}intstrcompare(seqstring*S,seqstring*T){inti=1,j=0;while(!(i=S->str[j]-T->str[j])){j++;if(S->str[j]==""&&T->str[j]=="")break;}returnsign(i);}voidprint(seqstring*S){inti;for(i=0;ilength;i++)printf("%c",S->str[i]);}main(){seqstring*S=init(S),*T=init(T);inta,i=0;clrscr();printf("Thisprogramistocomparetwostrings.npleaseinputfirststringn");while((S->str[i]=getchar())!="n"){i++;}S->str[i]="";S->length=strlen(S->str);printf("pleaseinputsecondsrtingn");i=0;while((T->str[i]=getchar())!="n"){i++;}T->str[i]="";T->length=strlen(T->str); printf("nthefirstyouinput:");print(S);printf("nthesecondyouinput:");print(T);a=strcompare(S,T);printf("naftercompare,returnvalue%d",a);getch();}题4.4#includetypedefstructnode{chardata;structnode*next;}linkstrnode;typedeflinkstrnode*linkstring;linkstring*strcreat(linkstring*S){charch;linkstrnode*p,*r;*S=0;r=0;while((ch=getchar())!="n"){p=(linkstrnode*)malloc(sizeof(linkstrnode));p->data=ch;if(*S==0)*S=p;elser->next=p;r=p;}if(r!=0)r->next=0;returnS;}voidprint(linkstringS){linkstringq=S;for(;q!=0;q=q->next)printf("%c",q->data);}voidstrinsert(linkstring*S,inti,linkstringT){intk;linkstringp,q;p=*S,k=1;if(i==1){q=T;while(q->next)q=q->next;q->next=*S; *S=T;}else{while(p&&knext;k++;}if(!p)printf("Errorn");else{q=T;while(q->next)q=q->next;q->next=p->next;p->next=T;}}}voidstrdelete(linkstring*S,inti,intlen){intk;linkstringp,q,r;p=*S,q=0;k=1;while(p&&knext;k++;}if(!p)printf("Error1n");else{k=1;while(knext;k++;}if(!p)printf("Error2n");else{if(!q){r=*S;*S=p->next;}else{r=q->next;q->next=p->next;}p->next=0;while(r!=0){p=r;r=r->next;free(p);}}}}linkstringsubstring(linkstringS,inti,intlen){intk;linkstringp,q,t,r;p=S,k=1;while(p&&knext;k++;}if(!p) {printf("Errorn");return0;}else{r=(linkstring)malloc(sizeof(linkstrnode));r->data=p->data;r->next=0;k=1;q=r;while(p->next&&knext;k++;t=(linkstring)malloc(sizeof(linkstrnode));t->data=p->data;q->next=t;q=t;}if(knext=0;return(r);}}}/*Creatanewlinkstring=b*/linkstringnewcopy(linkstringx,linkstringy){linkstringq,t=x,new;for(q=y;q;q=q->next){new=(linkstring)malloc(sizeof(linkstrnode));new->data=q->data;if(t==0)x=new;elset->next=new;t=new;}t->next=0;returnx;}voidreplace(linkstring*S,linkstringa,linkstringb)/*4.4*/{linkstringp=*S,q=a,r=b,temp,t;inti,j=0,k=0,l=0;while(p!=0){p=p->next;j++;}while(q!=0){q=q->next;k++;}while(r!=0){r=r->next;l++;}for(i=1;i+kdata!=q->data)break;temp=temp->next;q=q->next;} if(temp==0&&q==0){t=0;t=newcopy(t,b);printf("nHehe%d%d",i,k);strdelete(S,i,k);strinsert(S,i,t);j=j-k+l;i=i+l-1;}}}main(){linkstrnode*S,*T1,*T2;clrscr();printf("TheprogramistoS,T1replacedbyT2.npleaseinputstringS:n");strcreat(&S);printf("pleaseinputstringT1:n");strcreat(&T1);printf("pleaseinputstringT2:n");strcreat(&T2);printf("nS:");print(S);printf("nT1:");print(T1);printf("nT2:");print(T2);replace(&S,T1,T2);printf("nn");print(S);getch();}题4.7分别使用按行优先和按列优先的顺序写出三位数组A[3][2][4]中所有元素在存储器中的存储次序，并计算数组元素A[0][1][2]的地址。解：按行优先：A[0][0][0]A[0][0][1]A[0][0][2]A[0][0][3]A[0][1][0]A[0][1][1]A[0][1][2]A[0][1][3]A[1][0][0]A[1][0][1]A[1][0][2]A[1][0][3]A[1][1][0]A[1][1][1]A[1][1][2]A[1][1][3]A[2][0][0]A[2][0][1]A[2][0][2]A[2][0][3]A[2][1][0]A[2][1][1]A[2][1][2]A[2][1][3]其中：address(A[0][1][2])=address(A[0][0][0])+(1*4+2)*L;按列优先：A[0][0][0]A[1][0][0]A[2][0][0]A[0][1][0]A[1][1][0]A[2][1][0]A[0][0][1]A[1][0][1]A[2][0][1]A[0][1][1]A[1][1][1]A[2][1][1]A[0][0][2]A[1][0][2]A[2][0][2]A[0][1][2]A[1][1][2]A[2][1][2]A[0][0][3]A[1][0][3]A[2][0][3] A[0][1][3]A[1][1][3]A[2][1][3]其中：address(A[0][1][2])=address(A[0][0][0])+(0+1*3+2*2*3)*L;具体的参考程序如下：typedefintdatatype;typedefstruct{datatype*base;intindex[3];intc[3];}array;intinitarray(array*A,intb1,intb2,intb3){intelements;A->index[0]=b1;A->index[1]=b2;A->index[2]=b3;elements=b1*b2*b3;A->base=(datatype*)malloc(elements*sizeof(datatype));if(!(A->base))return(0);A->c[0]=b2*b3;A->c[1]=b3;A->c[2]=1;return(1);}intvalue(arrayA,inti1,inti2,inti3,datatype*x){intoff;if(i1<0||i1>=A.index[0]||i2<0||i2>=A.index[1]||i3<0||i3>=A.index[2])return(0);off=i1*A.c[0]+i2*A.c[1]+i3*A.c[2];*x=*(A.base+off);return(1);}intassign(array*A,datatypee,inti1,inti2,inti3){intoff;if(i1<0||i1>=A->index[0]||i2<0||i2>=A->index[1]||i3<0||i3>=A->index[2])return(0);off=i1*A->c[0]+i2*A->c[1]+i3*A->c[2];*(A->base+off)=e;return(1);}voidprint_in_row(array*A){inti,j,k,l=0;datatypetemp;for(i=0;iindex[0];i++)for(j=0;jindex[1];j++)for(k=0;kindex[2];k++){if(l%4==0)printf("n");l++;value(*A,i,j,k,&temp); printf("A[%d][%d][%d]:%3d",i,j,k,temp);}}voidprint_in_column(array*A){inti,j,k,l=0;datatypetemp;for(i=0;iindex[2];i++)for(j=0;jindex[1];j++)for(k=0;kindex[0];k++){if(l%4==0)printf("n");l++;value(*A,k,j,i,&temp);printf("A[%d][%d][%d]:%3d",k,j,i,temp);}}voidinsert_example(array*A){inti,j,k;datatypex=1;for(i=0;iindex[0];i++)for(j=0;jindex[1];j++)for(k=0;kindex[2];k++,x++){assign(A,x,i,j,k);}}main(){array*A;intaddress;clrscr();initarray(A,3,2,4);insert_example(A);printf("Printbyrown");print_in_row(A);printf("nnPrintbyColumn:n");print_in_column(A);address=A+0+1*4+2;printf("nnTheaddressofA[0][1][2]is:Ox%x",address);getch();}题4.8typedefstruct{intdata[100][100];intm,n;}matrix;typedefintspmatrix[100][3];/*把spmatrix声明为具有100*3个int元素的数组的类型别名*/intmax(intx,inty) {if(x>=y)returnx;elsereturny;}voidprint(spmatrixT){intk;printf("Norowcolumnvalues");for(k=0;kB[k][1]&&A[k][0]==B[k][0]){if(B[k][2]!=0);{C[j][0]=B[k][0];C[j][1]=B[k][1];C[j][2]=B[k][2];j++;}if(A[k][2]!=0){C[j][0]=A[k][0];C[j][1]=A[k][1];C[j][2]=A[k][2];j++;}}else{if(A[k][2]!=0){C[j][0]=A[k][0];C[j][1]=A[k][1];C[j][2]=A[k][2];j++;}if(B[k][2]!=0){C[j][0]=B[k][0];C[j][1]=B[k][1];C[j][2]=B[k][2];j++;}}}else{if(B[k][2]!=0){C[j][0]=B[k][0];C[j][1]=B[k][1];C[j][2]=B[k][2];j++;}if(A[k][2]!=0){C[j][0]=A[k][0];C[j][1]=A[k][1];C[j][2]=A[k][2];j++;}}}}C[0][2]=j-1;return&C;}main(){spmatrixA,B;A[0][0]=3;A[0][1]=3;A[0][2]=2; A[1][0]=1;A[1][1]=2;A[1][2]=35;A[2][0]=3;A[2][1]=1;A[2][2]=38;B[0][0]=3;B[0][1]=3;B[0][2]=2;B[1][0]=1;B[1][1]=2;B[1][2]=35;B[2][0]=3;B[2][1]=2;B[2][2]=99;clrscr();printf("A:n");print(A);printf("nnB:n");print(B);printf("nnA+B:n");print(*add(A,B));getch();}第六章树6.1（1）答：树中A为根节点，E、G、H、I、J、K、L为叶子结点。（2）答：结点B的双亲为A，其子女为E、F。（3）A、B、F为I的祖先，E、F、G、H、I为结点B的子孙。（4）B、C、L为D的兄弟，J为结点K的兄弟。（5）结点J位于第三层，树的高度为4。（6）结点A的度为4，C的度为0，整个树的度为4。（7）以结点B为根的子树的高度为3；（8）①括号表示为：A（B，(E，F(G，H，I))，C，D(J，K)，L）；②层号表示为：1A，2B，3E，3F，5G，5H，5I，2C，2D，4J，4K，2L6.2前序遍历结果：ABEFGHICDJKL后序遍历结果：EGHIFBCJKDLA层次遍历结果：ABCDLEFJKGHI6.3datachild[0]child[1]child[2]child[3]A12311B45-1-1C-1-1-1-1D910-1-1E-1-1-1-1F678-1G-1-1-1-1H-1-1-1-1I-1-1-1-1J-1-1-1-1K-1-1-1-1L-1-1-1-1双亲表示法：数组方式的孩子表示法：DataParent0A-11B02C03D04E15F16G56.5一棵含有n个结点的k度树，可能达到的最大深度和最小深度分别为多少？解：最大深度为n-k+1最小深度为㏒k（1-n（1-k）） 6.9*假设树为有序树*/voidcompare(treea,treeb){inti;if(a!=NULL&&b!=NULL){if(a->data!=b->data)printf("A!=B");for(i=0;ichild[i],b->child[i]);}}第七章二叉树7.1已知一棵二叉树如图7.12所示，试求：（1）该二叉树前序、中序和后序遍历的结果；（2）该二叉树是否是满二叉树？是否是完全二叉树？（3）将它转换成对应的树或森林；（4）这棵二叉树的深度为多少？（5）试对该二叉树进行前序线索化；（6）试对该二叉树进行中序线索化。解：(1)前序遍历：abdgecfh中序遍历：dgbeafhc后序遍历：gdebhfca(2)否，否(3)转化为森林abedgcfh(4)深度为4(5)前序线索化(6)后序线索化 abcdefhgabcdefgh7.4已知一棵二叉树的前序遍历的结果为：ABCEFGHD，后序遍历的结果为：ABFHGEDC,试画出此二叉树。CbbbBbbbAbbbDbbbEbbbGbbbFbbbHbbbAbbbFbbbDbbbBbbbCbbbEbbb7.4题二叉树7.5题二叉树7.5已知一棵二叉树的前序遍历的结果为：ABCDEF，中序遍历的结果为：CBAEDF，试画出此二叉树。7.8试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。解：程序如下：#include"stdio.h"typedefchardatatype;typedefstruct{datatypedata;structnode*lchild,*rchild;}node; node*createtree(){charch;node*t;if((ch=getchar())=="#")t==NULL;else{t=(node*)malloc(sizeof(node));t->data=ch;t->lchild=createtree();t->rchild=createtree();}returnt;}voidprint(node*t){if(t){printf("%c",t->data);print(t->lchild);print(t->rchild);}}voidexchange(node*t){node*p;if(t){p=t->lchild;t->lchild=t->rchild;t->rchild=p;exchange(t->lchild);exchange(t->rchild);}}voidmain(){inti;node*root;printf("请按前序遍历输入各结点的data:n");root=createtree();printf("输出各结点值：n");print(root);exchange(root);printf("n按前序遍历输出互换子女后的树：n"); print(root);getch();}7.13假设二叉树采用链式方式存储，root为其根结点，p指向二叉树中的任意一个结点，编写一个求从根结点到p所指结点之间路径长度的函数。程序：#include"stdio.h"#include#includetypedefchardatatype;typedefstruct{datatypedata;structnode*lchild,*rchild,*parent;}node;node*createtree(){charch;node*t;if((ch=getchar())=="#")t==NULL;else{t=(node*)malloc(sizeof(node));t->data=ch;t->parent=NULL;t->lchild=createtree();t->rchild=createtree();}returnt;}voidget_parent(node*t){if(t){node*p;if(t->lchild){p=t->lchild;p->parent=t;get_parent(t->lchild);}if(t->rchild){p=t->rchild;p->parent=t; get_parent(t->rchild);}}}voidprint(node*t){if(t){printf("%c",t->data);print(t->lchild);print(t->rchild);}}voidfind_target(node*t,int*flag,int*level){if(t&&t->data=="$")*flag=1;if(*flag==1)return;（*level）++;if(*flag==0){if(t){find_target(t->lchild,flag,level);find_target(t->rchild,flag,level);}}if(flag==0)*level--;}voidmain(){intflag=0,level=0;node*root;printf("请按前序遍历输入各结点的data:n");root=createtree();get_parent(root);printf("按前序遍历输出建立的树：n");print(root);find_target(root,&flag,&level);printf("ndata为"$"的结点所在的层数为：%d",level-1);getch();} 7.15假设二叉树采用链式方式存储，设计一个算法求二叉树中指定结点所在的层数。程序：#include"stdio.h"#include#includetypedefchardatatype;typedefstruct{datatypedata;structnode*lchild,*rchild,*parent;}node;node*createtree(){charch;node*t;if((ch=getchar())=="#")t==NULL;else{t=(node*)malloc(sizeof(node));t->data=ch;t->parent=NULL;t->lchild=createtree();t->rchild=createtree();}returnt;}voidget_parent(node*t){if(t){node*p;if(t->lchild){p=t->lchild;p->parent=t;get_parent(t->lchild);}if(t->rchild){p=t->rchild;p->parent=t;get_parent(t->rchild);}} }voidprint(node*t){if(t){printf("%c",t->data);print(t->lchild);print(t->rchild);}}voidfind_target(node*t,int*flag,int*level){if(t&&t->data=="$")*flag=1;if(*flag==1)return;（*level）++;if(*flag==0){if(t){find_target(t->lchild,flag,level);find_target(t->rchild,flag,level);}}if(flag==0)（*level）--;}voidmain(){intflag=0,level=0;node*root;printf("请按前序遍历输入各结点的data:n");root=createtree();get_parent(root);printf("按前序遍历输出建立的树：n");print(root);find_target(root,&flag,&evel);printf("ndata为"$"的结点所在的层数为：%d",level);getch();}另外的方法： #defineNULL0#includetypedefchardatatype;/*结点值的类型*/typedefstructnode{datatypedata;structnode*lchild,*rchild;}bintnode;/*二叉树结点的类型*/typedefbintnode*bintree;bintreeroot;/*指向根结点的指针*//*locate(bintree,datatype);numofnode(bintree);isequal(bintree,bintree);preorder(bintree);inorder(bintree);postorder(bintree);depth(bintree);createbitree(bintree*);destroybitree(t)root(t)leftchild(t)rightchild(t)parent(t,x)isempty(t)numofnode(t)addchild(t,x,t1,b)deletechild(t,x,b)setnull(t)transform(t1,t2)*/voidcreatebintree(bintree*t)/*创建二叉树*/{charch;if((ch=getchar())=="$")*t=NULL;else{*t=(bintnode*)malloc(sizeof(bintnode));/*生成二叉树的根结点*/(*t)->data=ch;createbintree(&(*t)->lchild);/*递归实现左子树的建立*/createbintree(&(*t)->rchild);/*递归实现右子树的建立*/} }bintreelocate(bintreet,datatypex)/*二叉树的查找*/{bintreep;if(t==NULL)returnNULL;elseif(t->data==x)returnt;else{p=locate(t->lchild,x);if(p)returnp;elsereturnlocate(t->rchild,x);}}intnumofnode(bintreet)/*统计二叉树中结点的个数*/{if(t==NULL)return0;elsereturn(numofnode(t->lchild)+numofnode(t->rchild)+1);}intisequal(bintreet1,bintreet2)/*判断二叉树是否等价*/{intt=0;if(t1==NULL&&t2==NULL)t=1;elseif(t1!=NULL&&t2!=NULL)if(t1->data==t2->data)if(isequal(t1->lchild,t2->lchild))t=isequal(t1->rchild,t2->rchild);return(t);}voidpreorder(bintreet)/*前序遍历*/{if(t){printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);}}voidinorder(bintreet)/*中序遍历二叉树的递归算法*/{ if(t){inorder(t->lchild);printf("%c",t->data);inorder(t->rchild);}}voidpostorder(bintreet)/*后序遍历二叉树的递归算法*/{if(t){postorder(t->lchild);postorder(t->rchild);printf("%c",t->data);}}intdepth(bintreet)/*求一棵树的深度*/{inth,lh,rh;if(t==NULL)h=0;else{lh=depth(t->lchild);rh=depth(t->rchild);if(lh>=rh)h=lh+1;elseh=rh+1;}returnh;}intisempty(bintreet)/*判断是否为空*/{if(t==NULL)return1;elsereturn0;}intLeaf_rec(bintreeT)/*7.7a采用递归方式求二叉树T的叶子结点的数目*/{intleaf1,leaf2;if(T==NULL)return0;/*若二叉树是空树，则返回0*/ elseif((T->lchild==NULL)&&(T->rchild==NULL))return1;/*若二叉树的左孩子和右孩子为空，则返回1*/else{/*若二叉树的左孩子或右孩子不为空*/leaf1=Leaf_rec(T->lchild);/*递归求T的左孩子的叶子结点数目*/leaf2=Leaf_rec(T->rchild);/*递归求T的右孩子的叶子结点数目*/return(leaf1+leaf2);/*返回总的叶子结点数目*/}}voidswap(bintreert)/*7.8将所有结点左右子树互换*/{bintreetemp=NULL;if(rt->lchild==NULL&&rt->rchild==NULL)return;else{temp=rt->lchild;rt->lchild=rt->rchild;rt->rchild=temp;}if(rt->lchild)swap(rt->lchild);if(rt->rchild)swap(rt->rchild);}intisfull(bintreet)/*7.9判断是否为完全二叉树*/{inti,j;i=depth(t);j=numofnode(t);if(j==(i*(i+1))/2)return0;/*相等返回0,为完全二叉树*/elsereturn1;/*否者返回，为非完全二叉树*/}bintreeparent(bintreet,datatypex)/*找双亲*/{bintreep; if(t==NULL)returnNULL;elseif(t->lchild->data==x||t->rchild->data==x)returnt;else{p=parent(t->lchild,x);if(p)returnp;elsereturnparent(t->rchild,x);}}introot_to_p(bintreet,datatypep)/*7.13找root到p的路径长度*/{inti;datatypea;printf("Thepathis:%c",a=p);for(i=0;a!=t->data;a=parent(t,a)->data,i++,printf("%c",a));returni;}datatypeAncestor(bintreet,datatypex,datatypey)/*7.14最近共同祖先*/{inti,j;chara[10],b[10],temp;for(i=0,temp=x,a[i]=x;temp!=t->data;a[i]=temp,i++)temp=parent(t,temp)->data;for(j=0,temp=y,b[j]=y;temp!=t->data;b[j]=temp,j++)temp=parent(t,temp)->data;for(i--,j--;a[i]==b[j];i--,j--);returna[i+1];}main(){inti,j,k;chartemp5,temp14,temp161,temp162;printf("pleaseinput(forexample:abd$e$$fg$$$c$$)n");/*请用前序创建一个二叉树,如输入abd$e$$fg$$$c$$*/ createbintree(&root);while(1){printf("nmenu:n0.exit1.preordern2.inorder3.postordern4.numofnode5.locaten6.depth7.rootn8.leftchild9.Rightchildn10.isempty?11.sumofleafn12.swaplandr13.Isfull?n14.findparent15.roottopn16.CommonparentnPleaseselect:");/*提示用户选选择*/scanf("%i",&i);if(i==0)break;/*输入0退出程序*/switch(i){case1:printf("npreorder:");preorder(root);break;case2:printf("ninorder:");inorder(root);break;case3:printf("npostorder:");postorder(root);break;case4:j=numofnode(root);printf("nNumofnodeis:%d",j);break;case5:printf("nPleaseinputthevalueyouwantfind:");fflush(stdin);temp5=getchar();printf("nItsleftchildis:%candrigthchildis:%c",locate(root,temp5)->lchild->data,locate(root,temp5)->rchild->data);break;case6:printf("nTree"sdepthis:%d",depth(root));break;case7:printf("nRootis:%c",root->data);break;case8:printf("nLeftchildare:n");preorder(root->lchild);break;case9:printf("nRightchildare:n");preorder(root->rchild);break;case10:if(isempty(root))printf("nTreeisempty!");elseprintf("nTreeisnotempty");break;case11:printf("nSumofleavesis:%d",Leaf_rec(root));break; case12:printf("nAfterswap,treeis:");swap(root);preorder(root);break;case13:if(isfull(root)==0)printf("Bintreeisfull!!n");elseprintf("Bintreeisn"tfull!!n");break;case14:printf("pleaseinputthenode:");fflush(stdin);temp14=getchar();if(parent(root,temp14)==NULL)printf("Notexist");elseprintf("thenode"sparentis%c",parent(root,temp14)->data);break;case15:printf("Pleaseinputthenode:");fflush(stdin);temp14=getchar();printf("lengthofthepathis:%d",root_to_p(root,temp14));break;case16:printf("Pleaseinputfirstnode:");fflush(stdin);temp161=getchar();printf("Pleaseinputsecondnode:");fflush(stdin);temp162=getchar();printf("Commonparent:");printf("%c",Ancestor(root,temp161,temp162));break;default:printf("Sorry,errorvalue!!!pleaseretry!!!");}}getch();}第八章图8.4图8.32所示的是某个无向图的邻接表，试：（1）画出此图； （2）写出从顶点A开始的DFS遍历结果；（3）写出从顶点A开始的BFS遍历结果；解：（1）(2)ABCFEGD(3)ABCDFGE8.7如图：8.9①ADBECGFIH②ABDECFGIH③DEABCFGIH④DABECGFIH8.10顶点VeVl活动ell-e关键活动V000a(0->1)000√V166a(0->2)022V245a(1->3)660√V31313a(2->3)451V42222a(2->5)451V52525a(3->4)13130√a(3->5)13152a(4->5)22220√8.11无向图采用邻接表作为存储结构，试写出以下算法：（1）求一个顶点的度；（2）往图中插入一个顶点；（3）往图中插入一条边；（4）删去图中某顶点；（5）删去图中某条边；解：#definem20/*预定义图的最大顶点数*/#defineNULL0#includeintvisited[m];typedefchardatatype;/*顶点信息数据类型*/typedefstructnode{/*边表结点*/intadjvex;/*邻接点*/ structnode*next;}edgenode;typedefstructvnode{/*头结点类型*/datatypevertex;/*顶点信息*/edgenode*firstedge;/*邻接链表头指针*/}vertexnode;typedefstruct{/*邻接表类型*/vertexnodeadjlist[m];/*存放头结点的顺序表*/intn,e;/*图的顶点数与边数*/}adjgraph;voidcreateadjgraph(adjgraph*g)/*无向图的邻接表创建算法*/{inti,j,k;edgenode*s;printf("Pleaseinputnande:n");scanf("%d,%d",&g->n,&g->e);/*输入顶点数与边数*/getchar();printf("Pleaseinput%dvertex:n",g->n);for(i=0;in;i++){fflush(stdin);scanf("%c",&g->adjlist[i].vertex);/*读入顶点信息*/g->adjlist[i].firstedge=NULL;/*边表置为空表*/}printf("Pleaseinput%dedges:n",g->e);for(k=0;ke;k++)/*循环e次建立边表*/{scanf("%d,%d",&i,&j);/*输入无序对（i,j）*/s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;/*邻接点序号为j*/s->next=g->adjlist[i].firstedge;g->adjlist[i].firstedge=s;/*将新结点*s插入顶点vi的边表头部*/s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;/*邻接点序号为i*/s->next=g->adjlist[j].firstedge;g->adjlist[j].firstedge=s;/*将新结点*s插入顶点vj的边表头部*/}} print(adjgraph*g)/*打印出邻接表*/{edgenode*temp;inti;printf("nadjgraph:n");for(i=0;in;i++){printf("V[%d]:%c-->",i,g->adjlist[i].vertex);for(temp=g->adjlist[i].firstedge;temp!=NULL;temp=temp->next)printf("%d-->",temp->adjvex);printf("NULLn");}}intdepth(adjgraph*g,datatypea)/*8.11.(1)求一个顶点的度*/{inti,j;edgenode*temp;for(i=0;in;i++)if(g->adjlist[i].vertex==a)break;if(i>=g->n)printf("n%cnotexist!!!",a);for(j=0,temp=g->adjlist[i].firstedge;temp!=NULL;temp=temp->next,j++);returnj;}voidinsert_node(adjgraph*g)/*8.11.(2)往图中插入一个顶点(插在尾部)*/{datatypetemp;printf("Pleaseinputthenode:");fflush(stdin);temp=getchar();g->adjlist[g->n].vertex=temp;g->adjlist[g->n].firstedge=NULL;g->n++;}voidinsert_edge(adjgraph*g)/*8.11(3)往图中插入一条边*/{inti,j;edgenode*s;printf("nPleaseinputtheedge:n"); fflush(stdin);scanf("%d,%d",&i,&j);s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;/*邻接点序号为j*/s->next=g->adjlist[i].firstedge;g->adjlist[i].firstedge=s;/*将新结点*s插入顶点vi的边表头部*/s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;/*邻接点序号为i*/s->next=g->adjlist[j].firstedge;g->adjlist[j].firstedge=s;/*将新结点*s插入顶点vj的边表头部*/g->e++;}voiddelete_vertex(adjgraph*g)/*删除图中某顶点*/{edgenode*temp;datatypea;inth,i,j;printf("nPleaseinputthevertexyouwantdelete:n");fflush(stdin);a=getchar();for(h=0;hn;h++)if(g->adjlist[h].vertex==a){g->adjlist[h].vertex="01";g->adjlist[h].firstedge=NULL;break;}for(i=0;i<=g->n;i++)for(temp=g->adjlist[i].firstedge;temp->next;temp=temp->next){if(temp->adjvex==h)g->adjlist[i].firstedge=temp->next;if(temp->next->adjvex==h)temp->next=temp->next->next;}}voiddelete_edge(adjgraph*g)/*删去图中某条边*/{edgenode*temp;inti,j; printf("nPleaseinputtheedge:n");fflush(stdin);scanf("%d,%d",&i,&j);for(temp=g->adjlist[i].firstedge;temp->next;temp=temp->next)if(temp->next->adjvex==j){temp->next=temp->next->next;break;}for(temp=g->adjlist[j].firstedge;temp->next;temp=temp->next)if(temp->next->adjvex==i){temp->next=temp->next->next;break;}}voiddfs(adjgraphg,inti){/*以vi为出发点深度优先遍历顶点vi所在的连通分量*/edgenode*p;printf("visitvertex:%cn",g.adjlist[i].vertex);/*访问顶点i*/visited[i]=1;p=g.adjlist[i].firstedge;while(p)/*从p的邻接点出发进行深度优先搜索*/{if(!visited[p->adjvex])dfs(g,p->adjvex);/*递归*/p=p->next;}}voiddfstraverse(adjgraphg)/*深度优先遍历图g*/{inti;for(i=0;ihead)/*当队列非空时，执行下列循环体*/{j=queue[++head];/*出队*/p=g.adjlist[j].firstedge;while(p)/*广度优先搜索邻接表*/{if(visited[p->adjvex]==0){printf("%c",g.adjlist[p->adjvex].vertex);queue[++tail]=p->adjvex;visited[p->adjvex]=1;}p=p->next;}}}intbfstraverse(adjgraphg,datatypev)/*广度优先遍历图g*/{inti,count=0;for(i=0;ilchild;}if(top>0)p=s[--top];if(p-key>preval)return0;preval=p-key;p=p->lchild;}while(p||top>0);return1;} 9.109.14'

您可能关注的文档

相关文档

最近下载