《数据结构习题集答案(c版)(清华大学严蔚敏).docx》由会员分享，可在线阅读，更多相关《数据结构习题集答案(c版)(清华大学严蔚敏).docx（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.16void print_descending(int x,int y,int z)按从大到小顺序输出三个数 (scanf(M%d,%d,%d;&x,&y,&z);if(xvy) xv-y; 为表示交换的双目运算符,以下同if(yz) yz;if(xy; 冒泡排序 printf(H%d %d %dH,x,y,z); /print_descending 1.17Status fib(int k,int m,int &f)求k阶斐波那契序列的第m项的值f ( int tempd;if(k2|m0) return ERROR;if(mk-l)f=0;elseif(m=k-l)f=l;else (
2、 for(i=0;i=k-2;i+) temp=0; tempk-l=l;初始化for(i=k;iv=m;i+) 求出序歹lj第k至第m个元素的值 (sum=0;for(j=i-k;ji;j+) sum4-=tempj;temp=sum;)f=tempm; Ireturn OK;/fib分析:通过保存已经计算出来的结果，此方法的时间复杂度仅为O(m八2).如果采用递归编程(大 多数人都会首先想到递归方法),则时间复杂度将高达O(k八m).1.18typedef struct ( char sport;enum male,female) gender;char schoolname; 校名为或E
3、char *result;int score; resulttype; typedef struct) int malescore; int femalescore; int totalscore; scoretype;void summary(resulttype resull)求各校的男女总分和团体总分,假设结果已经储存在result 数组中scoretype score;i=0;while(result.sport!=NULL)(switch(result.schoolname)(case *A:score 0 .totalscore+=result.score;if(result.ge
4、nder=O) score 0 .malescore+=result.score;else score 0 .femalescore+=result.score;break;case B:score.totalscore+=result.score;if(result.gender=O) score.malescore4-=result.score;else score.femalescore+=result.score;break;99i+;for(i=0;i5;i+)(printf(nSchool %d:nH,i);printf(Total score of male:%dnscore.m
5、alescore);printf(HTotal score of female:%dn,score.femalescore);printfCTotal score of all:%dnnH,score.totalscore);1/summary1.19Status algoll9(int aARRSIZE)求 i!*2Ai 序列的值且不超过 maxint ( last=l;for(i= 1 ;i=ARRSIZE;i+)(ai-l=last*2*i;if(ai-l/last)!=(2*i) reum OVERFLOW;last=ai-l;return OK;1/algol19分析:当某一项的结果
6、超过了 maxint时,它除以前面一项的商会发生异常. 1.20void polyvalue() (float ad;float *p=a;printfC4nput number of terms:0);scanf(n%dn,&n);printf(HInput the %d coefficients from aO to a%d:nn,n);for(i=0;i=n;i+) scanf(n%f;p+);printf(Input value of x:n);scanf(M%f;&x);p=a;xp= 1 ;sum=0; /xp用于存放x的i次方fdr(i=0;i=n;i+)(sum+=xp*(*p
7、+)；xp*=x;)printf(oValue is:%f,sum);/polyvalue2.10Status DeleteK(SqList &a,int i,int k)删除线性表a中第i个元素起的k个元素 (if(il|ka.length) return INFEASIBLE;for(count= 1 ;i+count-1 v二a.length-k;counl+) 注意循环结束的条件a.elemi+count-l =a.elemi+count4-k-1 ;a.length-=k;return OK;/DeleteK2.11Status Insert_SqList(SqList &va,in
8、t x)把 x 插入递增有序表 va 中 if(va.length4-1 va.listsize) return ERROR;va.length+;for(i=va.length-l ;va.elemx&i=0;i)va.elemi+l =va.elem;va.elemi+l=x;return OK;/Insert_SqList2.12int ListComp(SqList A,SqList B)比较字符表A和B,并用返回值表示结果，值为正，表示AB; 值为负，表示Anext;p&p-data!=x;p=p-next);return p;/Locate2.14int Length(LinkLi
9、st L)求链表的长度 (for(k=0,p=L;p-next;p=p-nextk+);return k;/Length2.15void ListConcat(LinkList ha,LinkList hb,LinkList &hc)把链表 hb 接在 ha 后面形成链表 he (hc=ha;p=ha;while(p-next) p=p-next;p-next=hb;/ListConcat2.16见书后答案.2.17Status Insert(LinkList &L,int i,int b)在无头结点链表L的第i个元素之前插入元素b(p=L;q=(LinkList*)malloc(sizeof
10、(LNode);q.dala=b;if(i=l)(q.next二p;L=q; 插入在链表头部)else(while(il) p=p-next;q-next=p-next;p-nexl=q; 插入在第i个元素的位置 )/Insert2.18Status Delete(LinkList &L,im i)在无头结点链表L中删除第i个元素if(i=l) L=L-nexl; 删除第一个元素 else p=L;while(il) p=p-next;pnext二pnextnext; /删除第i个元素 /Delete2.19Status Delete_Between(Linklist &L,int mink,
11、int maxk)删除元素递增排列的链表 L 中值大于 mink且小于maxk的所有元素 (P 二 L;while(p-next-datanext; /p 是最后一个不大于 mink 的元素 if(p-next) 如果还有比mink更大的元素 (q=p-next;while(q-datanext; /q 是第一个不小于 maxk 的元素 p-next=q;1/Delete_Between2.20Status Delete_Equal(Linklist &L)删除元素递增排列的链表L中所有值相同的元素 (p=L-next;q=p-next; /p,q 指向相邻两元素 while(p-next)
12、(if(p-data! =q-data) (p=p-next;q=p-next; 当相邻两元素不相等时,p,q都向后推一步 else(while(q-data=p-data) (free(q);q=q-next;p-next=q;p=q;q=p-next; 当相邻元素相等时删除多余元素 /else/while /DeIete_Equal 2.21void reverse(SqList &A)顺序表的就地逆置 ( for(i=l,j=A.length;ij;i+,j) A.elemA.elemj;/reverse2.22void LinkList_reverse(Linklist &L)链表的就
13、地逆置;为简化算法,假设表长大于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的元素逐个插入新表表头 ) q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是，逐个地把L的当前元素q插入新的链表头部,p为新表表头. 2.23void mergel(LinkList &A,LinkList &B,LinkList &。把链表 A 和 B 合并为 C,A 和 B 的元素间 隔排列，且使用原存储空间 ( p=A-n
14、ext;q=B-next;C=A;while(p&q) (s=p-next;p-next=q; 将 B 的元素插入 if(s) (t=q-next;q-next=s; A 非空，将 A 的元素插入 1 p=s;q=t; /while /merge 1 2.24void reverse_merge(LinkList &A,LinkList &B,LinkList &C)把元素递增排列的链表 A 和 B 合 并为C,且C中元素递减排列，使用原空间 (pa=A-next;pb=B-next;pre=NULL; /pa 和 pb 分别指向 A,B 的当前元素 while(pa|pb) ( if(pa-
15、datadata|!pb) (pc=pa;q=pa-next;pa-next=pre;pa=q; 将 A 的元素插入新表 ) elsepc=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.25void SqList_Intersect(SqList A,SqList B,SqList &C)求元素递增排列的线性表 A 和 B 的元素 的交集并存入C中 ( i
16、=l；j=l；k=O;while(A.elem&B.elemj) ( if(A.elemB.elemj) j+; if(A.elem=B.elem|j) (C.elem+k=A.elem; 当发现了一个在A,B中都存在的元素， i+；j+； 就添加到C中 1 /while /SqList_Intersect 2.26 void LinkListntersect(LinkList A,LinkList B,LinkList &C)在链表结构上重做上题 ( p=A-next;q=B-next;pc=(LNode*)malloc(sizeof(LNode); while(p&q) !if(p-dat
17、adata) p=p-next;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;1 /while C=pc; LinkListnlersecl2.27void SqList_Intersect_True(SqList &A,SqList B)求元素递增排列的线性表A和B的元素的交 集并存回A中(i=l；j=l；k=O；while(A.elem&B.elemj)(if(A.elemB.elemj) j+;else
18、 if(A.elem!=A.elemk)(A.elem+k=A.elem; 当发现了 一个在A,B中都存在的元素i+；j+； 且C中没有，就添加到C中)/whilewhile(A.elemk) A.elemk+=0;/SqList_Intersect_True2.28void LinkList_Intersect_True(LinkList &A,LinkList B)在链表结构上重做上题(p=A-next;q=B-next;pc=A;while(p&q)(if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else if(p-data
19、! =pc-data)(pc=pc-next;pc-data=p-data;p=p-next;q=q-next;1/while/LinkList_Intersect_True2.29void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)!i=0;j=0;k=0;m=0; /i指示A中元素原来的位置,m为移动后的位置while(iA.length&jB.length& kC.length)(if(B.elemjC.elemk) k+;else same=B.elem|j; 找到了 相同元素 same while(B.elemj=same
20、) j+;while(C.elemk=same) k+; /小k 后移到新的元素while(iA.length&A.elemsame)A.elemm+=A.elemi+; 需保留的元素移动到新位置 while(iA.length&A.elem=same) i+; 跳过相同的元素 /while while(inext;q=C-next;r=A-next;while(p&q&r)(if(p-datadata) p=p-next;else if(p-dataq-data) q=q-next;else (u=p-data; 确定待删除元素uwhile(r-next-datanext; 确定最后一个小于
21、u的元素指针rif(r-next-data=u) (s=r-next;while(s-data=u) (t=s;s=s-next;free(t); 确定第一个大于u的元素指针s /whiler-next=s; 删除i和s之间的元素 /ifwhile(p-data=u) p=p-next;while(q-data=u) q=q-next;/else/while/LinkList_Intersect_Delete2.31Status Delete_Pre(CiLNode *s)删除单循环链表中结点s的直接前驱 (p=s；while(p-next-next!=s) p=pnext; 找到 s 的前驱
22、的前驱 pp-next=s; return OK; /Delete_Pre2.32Status DuLNode_Pre(DuLinkList &L)完成双向循环链表结点的pre域 ( for(p=L;!p-next-pre;p=p-next) p-next-pre=p;return OK;/DuLNode_Pre2.33Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)把单链表 L 的元素按类 型分为三个循环链表CiList为带头结点的单循环链表类型.(s=L-next;A=(CiList*)malloc(size
23、of(CiLNode);p=A;B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(CiList*)maHoc(sizeof(CiLNode);r=C; 建立头结点 while(s) (if(isalphabet(s-data) (p-next=s;p=s;1 else if(isdigit(s-data) (q-next=s;q=s;1 else (r-next=s;r=s;1 /while pnext=A;qnext=B;rnext=C; 完成循环链表 /LinkList_Divide2.34 void Print_XorLinkedList(XorLinke
24、dList L)从左向右输出异或链表的元素值 (p=L.left;pre=NULL; while(p) (printf(H%d,p-data);q=XorP(p-LRPtr,pre);pre=p;p=q; 任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针/Print_XorLinkedList2.35Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)在异或链表 L 的第 i 个元素前插入元 素x(p=L.left;pre=NULL;r=(XorNode*)malloc(sizeof(XorNode);r-d
25、ata=x;if(i=l) 当插入点在最左边的情况(p-LRPtr=XorP(p.LRPtr,r);r-LRPtr=p;L.left=r;return OK;1j=l;q=p-LRPtr; 当插入点在中间的情况while(+jLRPtr,pre);pre=p;p=q;/while 在p,q两结点之间插入if(!q) return INFEASIBLE; /i 不可以超过表长p-LRPtr=XorP(XorP(p-LRPtr,q),r);q-LRPtr=XorP(XorP(q-LRPtr,p),r);r-LRPtr=XorP(p,q); 修改指针return OK;/Insert_XorLink
26、edList2.36Status Delete_XorLinkedList(XorlinkedList &L,int i)删除异或链表 L 的第 i 个元素(p=L.left;pre=NULL;if(i=l) /删除最左结点的情况(q=p-LRPtr;q-LRPtr=XorP(q-LRPtr,p);L.left=q;free(p);return OK;j=l;q=p-LRPtr;while(+jLRPtr,pre);pre=p;p=q;while 找到待删结点qif(!q) return INFEASIBLE; /i 不可以超过表长 if(L.right=q) q为最右结点的情况 (p-LRP
27、tr=XorP(p-LRPtr,q);L.right=p;free(q);return OK;r=XorP(q-LRPtr,p); /q为中间结点的情况，此时p,r分别为其左右结点 p-LRPtr=XorP(XorP(p-LRPtr,q),r);r-LRPtr=XorP(XorP(r-LRPtr,q),p); 修改指针 free(q);return OK;/Delete_XorLinkedList2.37void OEReform(DuLinkedList &L)按1,3,5,.4,2的顺序重排双向循环链表L中的所有结点 (p=L.next;while(p-next!=L&p-next-nex
28、t!=L) (p-next=p-next-next;p=p-next;) 此时p指向最后一个奇数结点if(p-next=L) p-next=L-pre-pre;else p-next=l-pre;p=p-next; 此时p指向最后一个偶数结点while(p-pre-pre !=L) (p-next=p-pre-pre;p=p-next;)pnext=L; 按题目要求调整了 next链的结构，此时pre链仍为原状 for(p=L;p-next!=L;p=p-next) p-next-pre=p;Lpre=p; 调整pre链的结构，同2.32方法/OEReform分析:next链和pre链的调整只
29、能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点 的指针，否则将会破坏链表结构，造成结点丢失.2.38DuLNode * Locate_DuList(DuLinkedList &L,int x)带 freq 域的双向循环链表上的查找 (p=L.next;while(p.data!=x&p!=L) p=p-next;if(p=L) return NULL; 没找到p-freq+;q=p-pre;while(q-freqfreq) q=q-pre; 查找插入位置if(q!=p-pre) (p-pre-next=p-next;p-next-pre=p-pre;q-next-pre=p;p-n
30、ext=q-next;qnext=p;ppre=q; 调整位置 return p;/Locate_DuList2.39noat GetValue_SqPoly(SqPoly Bint x0)求升幕顺序存储的稀疏多项式的值 (PolyTerm *q;xp= 1 ;q=P.data;sum=0;ex=0;while(q-coef) (while(exexp) xp*=xO;sum+=q-coef*xp;q+；)return sum;/GetValue_SqPoly2.40void Subtract_SqPoly(SqPoly Pl,SqPoly P2,SqPoly & 3)求稀疏多项式 Pl 减
31、P2 的差式 P3 (PolyTerm *p,*q,*r;Create_SqPoly(P3); 建立空多项式 P3p=Pl .data;q=P2.data;r=P3,data;while(p-coef&q-coef)(if(p-expexp)(r-coef=p-coef;r-exp=p-exp;p+;r+;)else if(p-expexp)(r-coef=-q-coef;r-exp=q-exp;q+;r+;else if(p,coef-q-coef)!=0) 只有同次项相减不为零时才需要存入P3中 (r-coef=p-coef-q-coef;r-exp=p-exp;r+;/ifp+；q+；/
32、else/whilewhile(p-coef) 处理Pl或P2的剩余项 r-coef=p-coef;r-exp=p-exp;p+;r+;)while(q-coef)(r-coef=-q-coef;r-exp=q-exp;q+;r+;)/Subtract_SqPoly2.41void QiuDao_LinkedPoly(LinkedPoly &L)对有头结点循环链表结构存储的稀疏多项式L求 导(p=L-next;if(!p-data.exp)(Lnexttpnext;p二pnext; 跳过常数项)while(p!=L)!p-data.coef*=p-data.exp; 对 每一项求导p=p-ne
33、xt;)/QiuDao_LinkedPoly2.42void Divide_LinkedPoly(LinkedPoly &L,&A,&B)把循环链表存储的稀疏多项式L拆成只含 奇次项的A和只含偶次项的B(p=L-next;A=(PolyNode*)malloc(sizeof(PolyNode);B=(PolyNode*)malloc(sizeof(PolyNode);pa=A;pb=B;while(p!=L)(if(p-data.exp!=2*(p-data.exp/2) (pa-next=p;pa=p;else(pb-next=p;pb=p;)p=p-next;/whilepa-next=A
34、;pb-next=B;/Divide_LinkedPoly3. 15 typedef structElemtype *base2;Elemtype *top2;BDStacktype; 双向栈类型Status Init_Stack (BDStacktype &tws, int m)初始化一个大小为 m 的双向栈 tws (tws. base0 = (Elemtype*)malloc(sizeof(Elemtype);tws. basel=tws. base0+m;tws. top0=tws. base0;tws. topl=tws. basel；return OK;/Init_StackSta
35、tus push (BDStacktype &tws, int i, Elemtype x)x 入栈,i=0 表示低端 栈,i=l表示高端栈 if (tws. top0tws. topl) return OVERFLOW; /注意此时的栈满条件if (i=0) *tws. top0+=x;else if (i=l) *tws. topl-=x;else return ERROR;return OK;/pushStatus pop(BDStacktype &tws, int i, Elemtype &x)x 出栈，i=0 表示低端 栈,i=l表示高端栈if(i=0)if(tws. top0=tw
36、s. baseO) return OVERFLOW;x=*tws. top0;)else if(i=l)(if(tws. topl=tws. basel) return OVERFLOW;x=*+tws. topl;)else return ERROR;return OK：/pop3. 16void Train arrange (char *train)这里用字符串train表示火车，H表示硬 席,S表示毓席(p=train;q=train;InitStack(s);while(*p)(if(*p=H) push(s, *p); 把H存入栈中else *(q+)=*p; 把S调到前部p+；)w
37、hile(!StackEmpty (s)pop(s, c);*(q+)=c; 把H接在后部)/Train_arrange3. 17int IsReverse()判断输入的字符串中前和后部分是否为逆串，是则返回1,否则返回0InitStack(s);while (e=getchar () !=&)push(s, e);while (e=getchar () != )(if(StackEmpty(s) return 0;pop(s, c);if(e!=c) return 0;if(!StackEmpty(s) return 0;return 1;/IsReverse3. 18Status Brac
38、ket_Test (char *str)判别表达式中小括号是否匹配(count=0;for (p=str;*p;p+)if (*p=，() count+;else if(*p二二)count;if (count |*p二=，I l*p=，) push(s, *p);else if (*p=，)J | | *p=，Y *p=,，)(if(StackEmpty (s) return ERROR;pop(s, c);if(*p=)&c!= () return ERROR;if(*p= *&! = C) return ERROR;if (*p=&c!= ) return ERROR; 必须与当前栈顶括
39、号匹配 )/forif(!StackEmpty(s) return ERROR;return OK;/AllBrackets_Test3. 20typedef struct .int x;int y; coordinate;void Repaint_Color (int gm n, int i, int j, int color)把点(i, j)相邻区 域的颜色置换为colorold=gj;InitQueue(Q);EnQueue(Q, I,j);while(!QueueEmpty(Q)(DeQueue(Q, a);x=a. x; y=a. y;if(xl)if(gx-ly=old)gx-ly
40、=color：EnQueue(Q, xT,y); 修改左邻点的颜色 )if(yl)if(gx y-l=old)(gxy-l=color;EnQueue(Q, x, y-1); 修改上邻点的颜色 )if(xm)if(gx+ly=old)(gx+ly=color;EnQueue(Q, x+l,y); 修改右邻点的颜色 )if(yn)if(gxy+l=old) (gxy+l=color;EnQueue(Q, x, y+1); 修改下邻点的颜色 )/while/Repaint_Color分析:本算法采用了类似于图的广度优先遍历的思想，用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢？3.21void NiBoLan (char *str, char Mew) 把中缀表达式str转换成逆波兰式new (p=str;q=new; 为方便起见，设str的两端都加上