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

数据结构2009年习题参考答案教材 数据结构（c语言版）第一版 作者 李云清等第一章 概论概念题从略1.10（1）O(1) (2)O(n) (3)O(n2) 第二章 线性表的顺序存储2.2int number_of_x_sequence_list(sequence_list slt,datatype x) int i,n=0; if(!slt.size) printf(顺序表是空的！);exit(1); else for(i=0;isize) printf(顺序表是空的！);exit(1); else for(i=0;isize/2;i+) temp=slt-ai;slt-ai=slt-aslt-size-i-1;slt-aslt-size-i-1=temp;2.4void insert_order_sequence_list(sequence_list *slt,datatype x) int i=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)具体的完成实现程序如下：#include int stk21,out21;void go(int n,int intop,int outtop,int in) int i,t; if(intop=0 & outtop=n) for(i=0;in;i+) printf(%d,outi); if(i=n-1) printf(n); return; if(intopn & in0) outouttop=stkintop-1; t=stkintop-1; go(n,intop-1,outtop+1,in); stkintop-1=t; main() int n; printf(please input n:n); scanf(%d,&n); go(n,0,0,0); getch(); 第三章 线性表的链式存储3.1int cal_link_list(node *head) int i=0; node *q=head; while(q) i+;q=q-next; printf(nThis list a total %d of nodes,i); return i;3.3 node *insert_x_before_y(node *head,int x,int y) 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; return head;3.4 int judgement(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(nLine list is not arrange in order); return 0; else printf(nLine list is arrange in order); return 1; 3.5 node *change(node *head) node *p,*q=0; while(head) p=head-next; head-next=q; q=head; head=p; head=q; return head;3.6void seperate(node *head) node *p1,*p2,*p,*headodd,*headeven,temp; p=head; while(p) /*找到第一个奇数结点，由headodd指向*/ if(p-info%2!=0) headodd=p;break; else p=p-next; p=head; while(p) /*找到第一个偶数结点，由headeven指向*/ if(p-info%2=0) headeven=p;break; else p=p-next; p=head; p1=headodd; p2=headeven; while(p) if(p-info%2!=0&p=headodd) p=p-next; else if(p-info%2=0&p=headeven) p=p-next; else if(p-info%2!=0) p1-next=p;p1=p;p=p-next; else if(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.7 node *delete_x_to_y(node *head,int x,int y) node *p=head,*q=head; for(;q;q=q-next) if(q-infox&q-infonext; else if(q-infox&q-infonext=q-next; else p=q; return head;第四章 字符串、数组和特殊矩阵题4.1# include # define MAXSIZE 100 typedef struct char strMAXSIZE; int length;seqstring; seqstring *init(seqstring *S) S-str0=0; S-length=0; return S; int sign(int r) if(r0) return 1; if(r=0) return 0; if(rstrj-T-strj) j+; if(S-strj=0&T-strj=0) break; return sign(i); void print(seqstring *S) int i; for(i=0;ilength;i+) printf(%c,S-stri); main() seqstring *S=init(S),*T=init(T); int a,i=0; clrscr(); printf(This program is to compare two strings.nplease input first stringn); while(S-stri=getchar()!=n)i+; S-stri=0; S-length=strlen(S-str); printf(please input second srtingn); i=0; while(T-stri=getchar()!=n)i+; T-stri=0; T-length=strlen(T-str); printf(nthe first you input :); print(S); printf(nthe second you input :); print(T); a=strcompare(S,T); printf(nafter compare,return value %d,a); getch();题4.4#include typedef struct node char data; struct node *next;linkstrnode; typedef linkstrnode *linkstring; linkstring *strcreat(linkstring *S) char ch; linkstrnode *p,*r; *S=0; r=0; while(ch=getchar()!=n) p=(linkstrnode *)malloc(sizeof(linkstrnode); p-data=ch; if(*S=0) *S=p; else r-next=p; r=p; if(r!=0) r-next=0; return S; void print(linkstring S) linkstring q=S; for(;q!=0;q=q-next) printf(%c,q-data); void strinsert(linkstring *S,int i,linkstring T) int k; linkstring p,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; void strdelete(linkstring *S,int i,int len) int k; linkstring p,q,r; p=*S,q=0;k=1; while(p&knext; k+; if(!p) printf(Error 1n); else k=1; while(knext; k+; if(!p) printf(Error 2n); else if(!q) r=*S;*S=p-next; elser=q-next;q-next=p-next; p-next=0; while(r!=0)p=r;r=r-next;free(p); linkstring substring(linkstring S,int i,int len) int k; linkstring p,q,t,r; p=S,k=1; while(p&knext;k+; if(!p) printf(Errorn);return 0; 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); /*Creat a new linkstring=b*/ linkstring newcopy(linkstring x,linkstring y) linkstring q,t=x,new; for(q=y;q;q=q-next) new=(linkstring)malloc(sizeof(linkstrnode); new-data=q-data; if(t=0) x=new; else t-next=new; t=new; t-next=0; return x; void replace(linkstring *S,linkstring a,linkstring b) /*4.4*/ linkstring p=*S,q=a,r=b,temp,t; int i,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(The program is to S,T1 replaced by T2.nplease input string S:n); strcreat(&S); printf(please input string T1:n); strcreat(&T1); printf(please input string T2: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分别使用按行优先和按列优先的顺序写出三位数组A324中所有元素在存储器中的存储次序，并计算数组元素A012的地址。解：按行优先：A000 A001 A002 A003A010 A011 A012 A013A100 A101 A102 A103A110 A111 A112 A113A200 A201 A202 A203A210 A211 A212 A213其中：address(A012)=address(A000)+(1*4+2)*L;按列优先：A000 A100 A200 A010 A110 A210 A001 A101 A201 A011 A111 A211 A002 A102 A202 A012 A112 A212 A003 A103 A203 A013 A113 A213 其中：address(A012)=address(A000)+(0+1*3+2*2*3)*L;具体的参考程序如下：typedef int datatype;typedef struct datatype *base; int index3; int c3;array; int initarray(array *A,int b1,int b2,int b3) int elements; A-index0=b1;A-index1=b2;A-index2=b3; elements=b1*b2*b3; A-base=(datatype *)malloc(elements*sizeof(datatype); if(!(A-base) return (0); A-c0=b2*b3; A-c1=b3;A-c2=1; return (1); int value(array A,int i1,int i2,int i3,datatype *x) int off; if(i1=A.index0|i2=A.index1|i3=A.index2) return (0); off=i1*A.c0+i2*A.c1+i3*A.c2; *x=*(A.base+off); return (1); int assign(array *A,datatype e,int i1,int i2,int i3) int off; if(i1=A-index0|i2=A-index1|i3=A-index2) return (0); off=i1*A-c0+i2*A-c1+i3*A-c2; *(A-base+off)=e; return (1); void print_in_row(array *A) int i,j,k,l=0; datatype temp; for(i=0;iindex0;i+) for(j=0;jindex1;j+) for(k=0;kindex2;k+) if(l%4=0) printf(n);l+; value(*A,i,j,k,&temp); printf(A%d%d%d:%3d ,i,j,k,temp); void print_in_column(array *A) int i,j,k,l=0; datatype temp; for(i=0;iindex2;i+) for(j=0;jindex1;j+) for(k=0;kindex0;k+) if(l%4=0) printf(n);l+; value(*A,k,j,i,&temp); printf(A%d%d%d:%3d ,k,j,i,temp); void insert_example(array *A) int i,j,k; datatype x=1; for(i=0;iindex0;i+) for(j=0;jindex1;j+) for(k=0;kindex2;k+,x+) assign(A,x,i,j,k); main() array *A; int address; clrscr(); initarray(A,3,2,4); insert_example(A); printf(Print by rown); print_in_row(A); printf(nnPrint by Column:n); print_in_column(A); address=A+0+1*4+2; printf(nnThe address of A012 is: Ox%x,address); getch();题4.8typedef struct int data100100; int m,n;matrix;typedef int spmatrix1003; /*把spmatrix声明为具有100*3个int元素的数组的类型别名*/int max(int x,int y) if(x=y) return x; else return y; void print(spmatrix T) int k; printf(No row column values); for(k=0;kT02+1;k+) printf(n%-4d%-10d%-10d%-10d,k,Tk0,Tk1,Tk2); spmatrix *add(spmatrix A,spmatrix B)/*4.8*/ int k,j=1; spmatrix C; if(A00!=B00|A01!=B01) printf(Error,A cant add to B); C00=A00;C01=A01; for(k=1;k=max(A02,B02);k+) if(Ak0=Bk0&Ak1=Bk1&Ak2!=0)Cj0=Ak0;Cj1=Ak1;Cj2=Ak2+Bk2; j+; else if(Ak0Bk1&Ak0=Bk0) if(Bk2!=0); Cj0=Bk0;Cj1=Bk1;Cj2=Bk2; j+; if(Ak2!=0) Cj0=Ak0;Cj1=Ak1;Cj2=Ak2; j+; else if(Ak2!=0) Cj0=Ak0;Cj1=Ak1;Cj2=Ak2; j+; if(Bk2!=0) Cj0=Bk0;Cj1=Bk1;Cj2=Bk2; j+; else if(Bk2!=0) Cj0=Bk0;Cj1=Bk1;Cj2=Bk2; j+; if(Ak2!=0) Cj0=Ak0;Cj1=Ak1;Cj2=Ak2; j+; C02=j-1; return &C; main() spmatrix A,B; A00=3;A01=3;A02=2; A10=1;A11=2;A12=35; A20=3;A21=1;A22=38; B00=3;B01=3;B02=2; B10=1;B11=2;B12=35; B20=3;B21=2;B22=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.3datachild0child1child2child3A12311B45-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*假设树为有序树*/void compare(tree a,tree b) int i; if(a!=NULL&b!=NULL) if(a-data!=b-data) printf(A!=B); for(i=0;ichildi,b-childi); 第七章 二叉树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,试画出此二叉树。CbbbBbbbAbbbDbbbEbbbGbbbFbbbHbbbAbbbFbbbDbbbBbbbCbbbEbbb 7.4题二叉树 7.5题二叉树7.5已知一棵二叉树的前序遍历的结果为：ABCDEF，中序遍历的结果为：CBAEDF，试画出此二叉树。7.8试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。解：程序如下：#include stdio.htypedef char datatype;typedef struct datatype data; struct node*lchild,*rchild; node;node*createtree() char ch; node*t; if(ch=getchar()=#)t=NULL;else t=(node*)malloc(sizeof(node);t-data=ch;t-lchild=createtree();t-rchild=createtree();return t;void print(node*t)if(t)printf(%c,t-data);print(t-lchild);print(t-rchild);void exchange(node*t)node*p; if(t) p=t-lchild; t-lchild=t-rchild; t-rchild=p; exchange(t-lchild); exchange(t-rchild); void main() int i; 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#includetypedef char datatype;typedef struct datatype data; struct node*lchild,*rchild,*parent; node;node*createtree() char ch; 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();return t;void get_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);void print(node*t)if(t)printf(%c,t-data);print(t-lchild);print(t-rchild);void find_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-;void main() int flag=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#includetypedef char datatype;typedef struct datatype data; struct node*lchild,*rchild,*parent; node;node*createtree() char ch; 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();return t;void get_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);void print(node*t)if(t)printf(%c,t-data);print(t-lchild);print(t-rchild);void find_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,leve