严蔚敏《数据结构习题集》全答案.docx
严蔚敏数据结构习题集全答案- Page 1-说明: 1.本文是对严蔚敏数据结构(c语言版)习题集一书中所有算法 voidsummary(resulttype result)/求各校的男女总分和团体总分, 设计题目的解决方案,主要作者为计算机版版主一具.以下网 假设结果已经储存在result 数组中 友:siice,龙抬头,iamkent,zames,birdthinking等为答案的修订和完善 工作提出了宝贵意见,在此表示感谢; scoretype score; 2.本解答中的所有算法均采用类c语言描述,设计原则为面向交流、面向 i=0; 阅读,作者不保证程序能够上机正常运行(这种保证实际上也没有任何意 while(resulti.sport!=NULL) 义); 3. 本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思 switch(resulti.schoolname) 路特殊的题目将给出简要的分析说明,对于作者无法解决的题目将给出必 要的讨论.目前尚未解决的题目有:5.20, 10.40; case 'A': 4. 请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考 score 0 .totalscore+=resulti.score; 本解答,以保证复习效果; if(resulti.gender=0) score 0 5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不 .malescore+=resulti.score; 足,希望读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出 else score 0 .femalescore+=resulti.score; 更好的算法来.请将你发现的错误或其它值得改进之处向作者报告: yi- break; ju case 'B': 第一章 绪论 score.totalscore+=resulti.score; if(resulti.gender=0) score.malescore+=resulti.score; else score.femalescore+=resulti.score; 1.16 break; voidprint_descending(int x,int y,int z)/按从大到小顺序输出三 个数 i+； scanf("%d,%d,%d",&x,&y,&z); for(i=0;i<5;i+) if(x<y) x<->y; /<->为表示交换的双目运算符,以下同 if(y<z) y<->z; printf("School %d:n",i); if(x<y) x<->y; /冒泡排序 printf("Total score of male:%dn",scorei.malescore); printf("%d %d %d",x,y,z); printf("Total score of female:%dn",scorei.femalescore); /print_descending printf("Total score of all:%dnn",scorei.totalscore); 1.17 /summary Status fib(int k,intm,int &f)/求k阶斐波那契序列的第m项的值f 1.19 inttempd; Status algo119(int aARRSIZE)/求i!*2i序列的值且不超过maxint if(k<2|m<0) return ERROR; if(m<k-1) f=0; last=1; else if(m=k-1) f=1; for(i=1;i<=ARRSIZE;i+) else ai-1=last*2*i; for(i=0;i<=k-2;i+) tempi=0; if(ai-1/last)!=(2*i) reurn OVERFLOW; tempk-1=1; /初始化 last=ai-1; for(i=k;i<=m;i+) /求出序列第k至第m个元素的值 return OK; sum=0; /algo119 for(j=i-k;j<i;j+) sum+=tempj; 分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. tempi=sum; 1.20 f=tempm; return OK; voidpolyvalue /fib 分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m2).如 float ad; 果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达 float *p=a; O(km). printf("Input numberof terms:"); scanf("%d",&n); 1.18 printf("Input the%dcoefficients froma0 toa%d:n",n,n); for(i=0;i<=n;i+) scanf("%f",p+); printf("Input value of x:"); typedef struct scanf("%f",&x); char *sport; p=a;xp=1;sum=0; /xp用于存放x的i次方 enummale,female gender; for(i=0;i<=n;i+) char schoolname; /校名为'A','B','C','D'或'E' char *result; sum+=xp*(*p+); int score; xp*=x; resulttype; printf("Value is:%f",sum); typedef struct /polyvalue int malescore; int femalescore; 第二章 线性表 int totalscore; scoretype; 2.10 - Page 2-Status DeleteK(SqList &a,int i,int k)/删除线性表a中第i个元素 if(i=1) 起的k个元素 q.next=p;L=q; /插入在链表头部 if(i<1|k<0|i+k-1>a.length) return INFEASIBLE; for(count=1;i+count-1<=a.length-k;count+) /注意循环结束的条 else 件 a.elemi+count-1=a.elemi+count+k-1; while(-i>1) p=p->next; a.length-=k; q->next=p->next;p->next=q; /插入在第i个元素的位置 return OK; /DeleteK /Insert 2.11 2.18 Status Insert_SqList(SqList &va,int x)/把x插入递增有序表va中 Status Delete(LinkList &L,int i)/在无头结点链表L中删除第i个元 素 if(va.length+1>va.listsize) return ERROR; va.length+; if(i=1) L=L->next; /删除第一个元素 for(i=va.length-1;va.elemi>x&&i>=0;i-) else va.elemi+1=va.elemi; va.elemi+1=x; p=L; return OK; while(-i>1) p=p->next; /Insert_SqList p->next=p->next->next; /删除第i个元素 /Delete 2.12 intListComp(SqList A,SqList B)/比较字符表A和B,并用返回值表示 2.19 结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B Status Delete_Between(Linklist &L,int mink,int maxk)/删除元素 for(i=1;A.elemi|B.elemi;i+) 递增排列的链表L中值大于mink且小于maxk的所有元素 if(A.elemi!=B.elemi) return A.elemi-B.elemi; return 0; p=L; /ListComp while(p->next->data<=mink) p=p->next; /p是最后一个不大于mink 的元素 2.13 if(p->next) /如果还有比mink更大的元素 q=p->next; LNode* Locate(LinkList L,int x)/链表上的元素查找,返回指针 while(q->data<maxk) q=q->next; /q是第一个不小于maxk的元素 p->next=q; for(p=l->next;p&&p->data!=x;p=p->next); return p; /Delete_Between /Locate 2.20 2.14 Status Delete_Equal(Linklist &L)/删除元素递增排列的链表L中所有 intLength(LinkList L)/求链表的长度 值相同的元素 for(k=0,p=L;p->next;p=p->next,k+); p=L->next;q=p->next; /p,q指向相邻两元素 return k; while(p->next) /Length if(p->data!=q->data) 2.15 p=p->next;q=p->next; /当相邻两元素不相等时,p,q都向后推一步 voidListConcat(LinkList ha,LinkList hb,LinkList &hc)/把链表hb else 接在ha后面形成链表hc while(q->data=p->data) hc=ha;p=ha; while(p->next) p=p->next; free(q); p->next=hb; /ListConcat q=q->next; p->next=q;p=q;q=p->next; /当相邻元素相等时删除多余元素 2.16 /else /while 见书后答案. /Delete_Equal 2.17 2.21 Status Insert(LinkList &L,int i,int b)/在无头结点链表L的第i个 voidreverse(SqList &A)/顺序表的就地逆置 元素之前插入元素b for(i=1,j=A.length;i<j;i+,j-) p=L;q=(LinkList*)malloc(sizeof(LNode); A.elemi<->A.elemj; q.data=b; /reverse - Page 3-2.22 2.26 voidLinkList_reverse(Linklist &L)/链表的就地逆置;为简化算法, voidLinkList_Intersect(LinkList A,LinkList B,LinkList &C)/在 假设表长大于2 链表结构上重做上题 p=L->next;q=p->next;s=q->next;p->next=NULL; p=A->next;q=B->next; while(s->next) pc=(LNode*)malloc(sizeof(LNode); while(p&&q) q->next=p;p=q; q=s;s=s->next; /把L的元素逐个插入新表表头 if(p->data<q->data) p=p->next; else if(p->data>q->data) q=q->next; q->next=p;s->next=q;L->next=s; else /LinkList_reverse 分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新 s=(LNode*)malloc(sizeof(LNode); 表表头. s->data=p->data; pc->next=s;pc=s; 2.23 p=p->next;q=q->next; /while voidmerge1(LinkList &A,LinkList &B,LinkList &C)/把链表A和B合 C=pc; 并为C,A和B的元素间隔排列,且使用原存储空间 /LinkList_Intersect p=A->next;q=B->next;C=A; while(p&&q) 2.27 s=p->next;p->next=q; /将B的元素插入 voidSqList_Intersect_True(SqList &A,SqList B)/求元素递增排列 if(s) 的线性表A和B的元素的交集并存回A中 t=q->next;q->next=s; /如A非空,将A的元素插入 i=1;j=1;k=0; while(A.elemi&&B.elemj) p=s;q=t; /while if(A.elemi<B.elemj) i+; /merge1 else if(A.elemi>B.elemj) j+; else if(A.elemi!=A.elemk) 2.24 A.elem+k=A.elemi; /当发现了一个在A,B中都存在的元素 i+;j+; /且C中没有,就添加到C中 voidreverse_merge(LinkList &A,LinkList &B,LinkList &C)/把元素 递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间 /while while(A.elemk) A.elemk+=0; pa=A->next;pb=B->next;pre=NULL; /pa和pb分别指向A,B的当前元素 /SqList_Intersect_True while(pa|pb) if(pa->data<pb->data|!pb) 2.28 pc=pa;q=pa->next;pa->next=pre;pa=q;/将A的元素插入新表 voidLinkList_Intersect_True(LinkList &A,LinkList B)/在链表结 构上重做上题 else p=A->next;q=B->next;pc=A; pc=pb;q=pb->next;pb->next=pre;pb=q; /将B的元素插入新表 while(p&&q) pre=pc; if(p->data<q->data) p=p->next; else if(p->data>q->data) q=q->next; C=A;A->next=pc; /构造新表头 else if(p->data!=pc->data) /reverse_merge 分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的 pc=pc->next; 头部pc处,最后处理A或B的剩余元素. pc->data=p->data; p=p->next;q=q->next; 2.25 /while /LinkList_Intersect_True voidSqList_Intersect(SqList A,SqList B,SqList &C)/求元素递增 排列的线性表A和B的元素的交集并存入C中 2.29 i=1;j=1;k=0; while(A.elemi&&B.elemj) voidSqList_Intersect_Delete(SqList &A,SqList B,SqList C) if(A.elemi<B.elemj) i+; i=0;j=0;k=0;m=0; /i指示A中元素原来的位置,m为移动后的位置 if(A.elemi>B.elemj) j+; while(i<A.length&&j<B.length&& k<C.length) if(A.elemi=B.elemj)
