1、严蔚敏数据结构（ C语言版）习题集答案 第一章 绪论 1.16 void print_descending(int x,int y,int z)/按从大到小顺序输出三个数 scanf(“%d,%d,%d“, if(xy; /为表示交换的双目运算符 ,以下同 if(yz; if(xy; /冒泡排序 printf(“%d %d %d“,x,y,z); /print_descending 1.17 Status fib(int k,int m,int if(ka.length) return INFEASIBLE; for(count=1;i+count-1va.listsize) return E
2、RROR; va.length+; for(i=va.length-1;va.elemixi-) va.elemi+1=va.elemi; va.elemi+1=x; return OK; /Insert_SqList 2.12 int ListComp(SqList A,SqList B)/比较字符表 A和 B,并用返回值表示结果 ,值为 1,表示 AB;值为 -1,表示 AB.elemi?1:-1; if(A.length=B.length) return 0; return A.lengthB.length?1:-1; /当两个字符表可以互相比较的部分完全相同时 ,哪个较长 ,哪个就较大
3、 /ListComp 2.13 LNode* Locate(LinkList L,int x)/链表上的元 素查找 ,返回指针 for(p=l-next;pp=p-next); return p; /Locate 2.14 int Length(LinkList L)/求链表的长度 for(k=0,p=L;p-next;p=p-next,k+); return k; /Length 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList p=ha; while(p-next) p=p-next; p-next=hb; /ListConcat
4、2.16 见书后答案 . 2.17 Status Insert(LinkList q=(LinkList*)malloc(sizeof(LNode); q.data=b; if(i=1) q.next=p;L=q; /插入在链表头部 else while(-i1) p=p-next; q-next=p-next;p-next=q; /插入在第 i个元素的位置 /Insert 2.18 Status Delete(LinkList /删除第一个元素 else p=L; while(-i1) p=p-next; p-next=p-next-next; /删除第 i个元素 /Delete 2.19
5、Status Delete_Between(Linklist while(p-next-datanext; /p是最后一个不大于 mink的元素 if(p-next) /如果还有比 mink更大的元素 q=p-next; while(q-datanext; /q是第一个不小于 maxk的元素 p-next=q; /Delete_Between 2.20 Status Delete_Equal(Linklist q=p-next; /p,q指向相邻两元素 while(p-next) if(p-data!=q-data) p=p-next;q=p-next; /当相邻两元素不相等时 ,p,q都向后
6、推一步 else while(q-data=p-data) free(q); q=q-next; p-next=q;p=q;q=p-next; /当相邻元素相等时删除多余元素 /else /while /Delete_Equal 2.21 void reverse(SqList iA.elemj; /reverse 2.22 void LinkList_reverse(Linklist 为简化算法 ,假设表长大于 2 p=L-next;q=p-next;s=q-next;p-next=NULL; while(s-next) q-next=p;p=q; q=s;s=s-next; /把 L的元素
7、逐个插入新表表头 q-next=p;s-next=q;L-next=s; /LinkList_reverse 分析 :本算法的思想是 ,逐个地把 L的当前元素 q插入新的链表头部 ,p为新表表头 . 2.23 void merge1(LinkList q=B-next;C=A; while(pp-next=q; /将 B的元素插入 if(s) t=q-next;q-next=s; /如 A非空 ,将 A的元素插入 p=s;q=t; /while /merge1 2.24 void reverse_merge(LinkList pb=B-next;pre=NULL; /pa和 pb分别指向 A,
8、B的当前元素 while(pa|pb) if(pa-datadata|!pb) pc=pa;q=pa-next;pa-next=pre;pa=q; /将 A的元素插入新表 else pc=pb;q=pb-next;pb-next=pre;pb=q; /将 B的元素插入新表 pre=pc; C=A;A-next=pc; /构造新表头 /reverse_merge 分析 :本算法的思想是 ,按从小到大的顺序依次把 A和 B的元素插入新表的头部 pc处 ,最后处理A或 B的剩余元素 . 2.25 void SqList_Intersect(SqList A,SqList B,SqList j=1;k
9、=0; while(A.elemi if(A.elemi=B.elemj) C.elem+k=A.elemi; /当发现了一个在 A,B中都存在的元素 , i+;j+; /就添加到 C 中 /while /SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList q=B-next; pc=(LNode*)malloc(sizeof(LNode); C=pc; while(p else if(p-dataq-data) q=q-next; else s=(LNode*)malloc(sizeof(LNode); s-data=p-data; pc-next=s;pc=s; p=p-next;q=q-next; /while /LinkList_Intersect 2.27 void SqList_Intersect_True(SqList j=1;k=0; while(A.elemi else if(A.elemi!=A.elemk) A.elem+k=A.elemi; /当发现了一个在 A,B中都存在的元素 i+;j+; /且 C 中没有 ,就添加到 C 中
