严蔚敏版数据结构C语言版参考答案第五章复习进程.doc

《严蔚敏版数据结构C语言版参考答案第五章复习进程.doc》由会员分享，可在线阅读，更多相关《严蔚敏版数据结构C语言版参考答案第五章复习进程.doc（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Good is good, but better carries it.精益求精，善益求善。严蔚敏版数据结构C语言版参考答案第五章-第四章串4.10voidString_Reverse(Stringtypes,Stringtype&r)/求s的逆串rStrAssign(r,);/初始化r为空串for(i=Strlen(s);i;i-)StrAssign(c,SubString(s,i,1);StrAssign(r,Concat(r,c);/把s的字符从后往前添加到r中/String_Reverse4.11voidString_Subtract(Stringtypes,Stringtypet,S

2、tringtype&r)/求所有包含在串s中而t中没有的字符构成的新串rStrAssign(r,);for(i=1;i=Strlen(s);i+)StrAssign(c,SubString(s,i,1);for(j=1;ji&StrCompare(c,SubString(s,j,1);j+);/判断s的当前字符c是否第一次出现if(i=j)for(k=1;kStrlen(t)StrAssign(r,Concat(r,c);/for/String_Subtract4.12intReplace(Stringtype&S,StringtypeT,StringtypeV);/将串S中所有子串T替换为V

3、,并返回置换次数for(n=0,i=1;i=Strlen(S)-Strlen(T)+1;i+)/注意i的取值范围if(!StrCompare(SubString(S,i,Strlen(T),T)/找到了与T匹配的子串/分别把T的前面和后面部分保存为head和tailStrAssign(head,SubString(S,1,i-1);StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1);StrAssign(S,Concat(head,V);StrAssign(S,Concat(S,tail);/把head,V,tail连接

4、为新串i+=Strlen(V);/当前指针跳到插入串以后n+;/ifreturnn;/Replace分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S=place,T=ace,V=face,则省掉i+=Strlen(V);运行时会出现什么结果?4.13intDelete_SubString(Stringtype&s,Stringtypet)/从串s中删除所有与t相同的子串,并返回删除次数for(n=0,i=1;i=Strlen(s)-Strlen(t)+1;i+)if(!StrCompare

5、(SubString(s,i,Strlen(t),t)StrAssign(head,SubString(S,1,i-1);StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1);StrAssign(S,Concat(head,tail);/把head,tail连接为新串n+;/ifreturnn,/Delete_SubString4.14StatusNiBoLan_to_BoLan(Stringtypestr,Stringtype&new)/把前缀表达式str转换为后缀式newInitstack(s);/s的元素为Stri

6、ngtype类型for(i=1;it时返回正数,s=t时返回0,st时返回负数for(i=1;i=s0&is0&it0)return0;elseif(is0)return-ti;elseif(it0)returnsi;elsereturnsi-ti;/StrCompare4.17intString_Replace(Stringtype&S,StringtypeT,StringtypeV);/将串S中所有子串T替换为V,并返回置换次数for(n=0,i=1;iT0)/找到了与T匹配的子串:分三种情况处理if(T0=V0)for(l=1;l=T0;l+)/新子串长度与原子串相同时:直接替换Si+l

7、-1=Vl;elseif(T0=i+T0;l-)Sl+V0-T0=Sl;for(l=1;l=V0;l+)Si+l-1=Vl;else/新子串长度小于原子串时:先将后部左移for(l=i+V0;l=S0+V0-T0;l+)Sl=Sl-V0+T0;for(l=1;l=V0;l+)Si+l-1=Vl;S0=S0-T0+V0;i+=V0;n+;/if/forreturnn;/String_Replace4.18typedefstructcharch;intnum;mytype;voidStrAnalyze(StringtypeS)/统计串S中字符的种类和个数mytypeTMAXSIZE;/用结构数组T

8、存储统计结果for(i=1;i=S0;i+)c=Si;j=0;while(Tj.ch&Tj.ch!=c)j+;/查找当前字符c是否已记录过if(Tj.ch)Tj.num+;elseTj=c,1;/forfor(j=0;Tj.ch;j+)printf(%c:%dn,Tj.ch,Tj.num);/StrAnalyze4.19voidSubtract_String(Stringtypes,Stringtypet,Stringtype&r)/求所有包含在串s中而t中没有的字符构成的新串rr0=0;for(i=1;i=s0;i+)c=si;for(j=1;ji&sj!=c;j+);/判断s的当前字符c是

9、否第一次出现if(i=j)for(k=1;kt0)r+r0=c;/for/Subtract_String4.20intSubString_Delete(Stringtype&s,Stringtypet)/从串s中删除所有与t相同的子串,并返回删除次数for(n=0,i=1;i=s0-t0+1;i+)for(j=1;jm)/找到了与t匹配的子串for(k=i;knext;p;p=p-next)r=(LStrNode*)malloc(sizeof(LStrNode);r-ch=p-ch;q-next=r;q=r;q-next=NULL;/StringAssignvoidStringCopy(LSt

10、ring&s,LStringt)/把串t复制为串s.与前一个程序的区别在于,串s业已存在.for(p=s-next,q=t-next;p&q;p=p-next,q=q-next)p-ch=q-ch;pre=p;while(q)p=(LStrNode*)malloc(sizeof(LStrNode);p-ch=q-ch;pre-next=p;pre=p;p-next=NULL;/StringCopycharStringCompare(LStrings,LStringt)/串的比较,st时返回正数,s=t时返回0,snext,q=t-next;p&q&p-ch=q-ch;p=p-next,q=q-

11、next);if(!p&!q)return0;elseif(!p)return-(q-ch);elseif(!q)returnp-ch;elsereturnp-ch-q-ch;/StringCompareintStringLen(LStrings)/求串s的长度(元素个数)for(i=0,p=s-next;p;p=p-next,i+);returni;/StringLenLString*Concat(LStrings,LStringt)/连接串s和串t形成新串,并返回指针p=malloc(sizeof(LStrNode);for(q=p,r=s-next;r;r=r-next)q-next=(

12、LStrNode*)malloc(sizeof(LStrNode);q=q-next;q-ch=r-ch;/for/复制串sfor(r=t-next;r;r=r-next)q-next=(LStrNode*)malloc(sizeof(LStrNode);q=q-next;q-ch=r-ch;/for/复制串tq-next=NULL;returnp;/ConcatLString*Sub_String(LStrings,intstart,intlen)/返回一个串,其值等于串s从start位置起长为len的子串p=malloc(sizeof(LStrNode);q=p;for(r=s;start

13、;start-,r=r-next);/找到start所对应的结点指针rfor(i=1;inext)q-next=(LStrNode*)malloc(sizeof(LStrNode);q=q-next;q-ch=r-ch;/复制串tq-next=NULL;returnp;/Sub_String4.22voidLString_Concat(LString&t,LString&s,charc)/用块链存储结构,把串s插入到串t的字符c之后p=t.head;while(p&!(i=Find_Char(p,c)p=p-next;/查找字符cif(!p)/没找到t.tail-next=s.head;t.t

14、ail=s.tail;/把s连接在t的后面elseq=p-next;r=(Chunk*)malloc(sizeof(Chunk);/将包含字符c的节点p分裂为两个for(j=0;jchj=#;/原结点p包含c及其以前的部分for(j=i;jchj=p-chj;p-chj=#;/p的后半部分和r的前半部分的字符改为无效字符#p-next=s.head;s.tail-next=r;r-next=q;/把串s插入到结点p和r之间/elset.curlen+=s.curlen;/修改串长s.curlen=0;/LString_ConcatintFind_Char(Chunk*p,charc)/在某个块

15、中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0for(i=0;ichi!=c;i+);if(i=CHUNKSIZE)return0;elsereturni+1;/Find_Char4.23intLString_Palindrome(LStringL)/判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0InitStack(S);p=S.head;i=0;k=1;/i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始)for(k=1;k=S.curlen;k+)if(kchi);/将前半段的字符入串elseif(k(S.curlen+1)/2)Pop(S,c);

16、/将后半段的字符与栈中的元素相匹配if(p-chi!=c)return0;/失配if(+i=CHUNKSIZE)/转到下一个元素,当为块中最后一个元素时,转到下一块p=p-next;i=0;/forreturn1;/成功匹配/LString_Palindrome4.24voidHString_Concat(HStrings1,HStrings2,HString&t)/将堆结构表示的串s1和s2连接为新串tif(t.ch)free(t.ch);t.ch=malloc(s1.length+s2.length)*sizeof(char);for(i=1;i=s1.length;i+)t.chi-1=

17、s1.chi-1;for(j=1;j=s2.length;j+,i+)t.chi-1=s2.chj-1;t.length=s1.length+s2.length;/HString_Concat4.25intHString_Replace(HString&S,HStringT,HStringV)/堆结构串上的置换操作,返回置换次数for(n=0,i=0;i=S.length-T.length;i+)for(j=i,k=0;kT.length&S.chj=T.chk;j+,k+);if(k=T.length)/找到了与T匹配的子串:分三种情况处理if(T.length=V.length)for(l

18、=1;l=T.length;l+)/新子串长度与原子串相同时:直接替换S.chi+l-1=V.chl-1;elseif(T.length=i+T.length;l-)S.chl+V.length-T.length=S.chl;for(l=0;lV.length;l+)Si+l=Vl;else/新子串长度小于原子串时:先将后部左移for(l=i+V.length;lS.length+V.length-T.length;l+)S.chl=S.chl-V.length+T.length;for(l=0;lV.length;l+)Si+l=Vl;S.length+=V.length-T.length;

19、i+=V.length;n+;/if/forreturnn;/HString_Replace4.26StatusHString_Insert(HString&S,intpos,HStringT)/把T插入堆结构表示的串S的第pos个字符之前if(posS.length)pos=S.length+1;/当插入位置大于串长时,看作添加在串尾S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char);for(i=S.length-1;i=pos-1;i-)S.chi+T.length=S.chi;/后移为插入字符串让出位置for(i=0;iT.length;

20、i+)S.chpos+i-1=T.chpos;/插入串TS.length+=T.length;returnOK;/HString_Insert4.27intIndex_New(Stringtypes,Stringtypet)/改进的定位算法i=1;j=1;while(i=s0&jt0)returni-t0;/Index_New4.28voidLGet_next(LString&T)/链串上的get_next算法p=T-succ;p-next=T;q=T;while(p-succ)if(q=T|p-data=q-data)p=p-succ;q=q-succ;p-next=q;elseq=q-ne

21、xt;/while/LGet_next4.29LStrNode*LIndex_KMP(LStringS,LStringT,LStrNode*pos)/链串上的KMP匹配算法,返回值为匹配的子串首指针p=pos;q=T-succ;while(p&q)if(q=T|p-chdata=q-chdata)p=p-succ;q=q-succ;elseq=q-next;/whileif(!q)for(i=1;inext;returnp;/发现匹配后,要往回找子串的头returnNULL;/LIndex_KMP4.30voidGet_LRepSub(StringtypeS)/求S的最长重复子串的位置和长度f

22、or(maxlen=0,i=1;iS0;i+)/串S2向右移i格for(k=0,j=1;jmaxlen)/发现了比以前发现的更长的重复子串lrs1=j-k+1;lrs2=mrs1+i;maxlen=k;/作记录/for/forif(maxlen)printf(LongestRepeatingSubstringlength:%dn,maxlen);printf(Position1:%dPosition2:%dn,lrs1,lrs2);elseprintf(NoRepeatingSubstringfound!n);/Get_LRepSub分析:i代表错位值.本算法的思想是,依次把串S的一个副本S2

23、向右错位平移1格,2格,3格,.与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明重复子串是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k=T0)StrAssign(A,S);StrAssign(B,T);elseStrAssign(A,T);StrAssign(B,S);/为简化设计,令S和T中较长的那个为A,较短的那个为Bfor(maxlen=0,i=1-B0;iA0;i+)if(iA0-B0)jmin=i;jmax=A0;

24、/B有一部分在A右端的右边elsejmin=i;jmax=i+B0;/B在A左右两端之间./以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.for(k=0,j=jmin;jmaxlen)lps1=j-k+1;lps2=j-i-k+1;maxlen=k;/for/forif(maxlen)if(S0=T0)lpsS=lps1;lpsT=lps2;elselpsS=lps2;lpsT=lps1;/将A,B上的位置映射回S,T上的位置printf(LongestPublicSubstringlength:%dn,maxlen);printf(Posi

25、tioninS:%dPositioninT:%dn,lpsS,lpsT);/ifelseprintf(NoRepeatingSubstringfound!n);/Get_LPubSub分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t）。第五章数组和广义表5.18voidRSh(intAn,intk)/把数组A的元素循环右移k位,只用一个辅助存储空间for(i=1;i=k;i

26、+)if(n%i=0&k%i=0)p=i;/求n和k的最大公约数pfor(i=0;iA6,A6-A12,A12-A3,A3-A9,A9-A0.第二条链:A1-A7,A7-A13,A13-A4,A4-A10,A10-A1.第三条链:A2-A8,A8-A14,A14-A5,A5-A11,A11-A2.恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的.5.19voidGet_Saddle(intAmn)/求矩阵A中的马鞍点for(i=0;im;i+)for(min=Ai0,j=0;jn;j+)if(Aijmin)min=Aij;/求一行中的最小值for(j=0;jn;j+)

27、if(Aij=min)/判断这个(些)最小值是否鞍点for(flag=1,k=0;km;k+)if(minAkj)flag=0;if(flag)printf(Foundasaddleelement!nA%d%d=%d,i,j,Aij);/for/Get_Saddle5.20本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复.5.21voidTSMatrix_Add(TSMatrixA,TSMatrixB,TSMat

28、rix&C)/三元组表示的稀疏矩阵加法C.mu=A.mu;C.nu=A.nu;C.tu=0;pa=1;pb=1;pc=1;for(x=1;x=A.mu;x+)/对矩阵的每一行进行加法while(A.datapa.ix)pa+;while(B.datapb.iB.datapb.j)C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;elseC.datapc.i=x;C.datapc.j=A.datapa.j;C.datapc.e=A.datapa.epa+;pc+;/whilewhile(A.datapa=x)/插入A

29、中剩余的元素(第x行)C.datapc.i=x;C.datapc.j=A.datapa.j;C.datapc.e=A.datapa.epa+;pc+;while(B.datapb=x)/插入B中剩余的元素(第x行)C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;/forC.tu=pc;/TSMatrix_Add5.22voidTSMatrix_Addto(TSMatrix&A,TSMatrixB)/将三元组矩阵B加到A上for(i=1;i=A.tu;i+)A.dataMAXSIZE-A.tu+i=A.datai;/把A的所有元素都移到尾部以腾出位置pa=MAXSIZE-A.tu+1;pb=1;pc=1;for(x=1;x=A.mu;x+)/对矩阵的每一行进行加法while(A.datapa.ix)pa+;while(B.datapb.ix)pb+;while(A.datapa.i=x&B.datapb.i=x)/行列值都相等的元素if(A.datapa.j=B.datapb.j)ne=A.datapa.e+B.datapb.e;if(ne)/和不为0A.datapc.i=x;A.datapc.j=A.datapa.j;A.datapc.e