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

Good is good, but better carries it.精益求精，善益求善。严蔚敏版数据结构C语言版参考答案第五章-第四章串4.10voidString_Reverse(Stringtypes,Stringtype&r)/求s的逆串r  StrAssign(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,Stringtype&r)/求所有包含在串s中而t中没有的字符构成的新串r  StrAssign(r,'');  for(i=1;i<=Strlen(s);i+)      StrAssign(c,SubString(s,i,1);    for(j=1;j<i&&StrCompare(c,SubString(s,j,1);j+);/判断s的当前字符c是否第一次出现    if(i=j)          for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1);k+);/判断当前字符是否包含在t中      if(k>Strlen(t)StrAssign(r,Concat(r,c);      /for/String_Subtract4.12intReplace(Stringtype&S,StringtypeT,StringtypeV);/将串S中所有子串T替换为V,并返回置换次数  for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i+)/注意i的取值范围    if(!StrCompare(SubString(S,i,Strlen(T),T)/找到了与T匹配的子串    /分别把T的前面和后面部分保存为head和tail      StrAssign(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连接为新串      i+=Strlen(V);/当前指针跳到插入串以后      n+;    /if  returnn;/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(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+;    /if  returnn,/Delete_SubString4.14StatusNiBoLan_to_BoLan(Stringtypestr,Stringtype&new)/把前缀表达式str转换为后缀式new  Initstack(s);/s的元素为Stringtype类型  for(i=1;i<=Strlen(str);i+)      r=SubString(str,i,1);    if(r为字母)push(s,r);    else          if(StackEmpty(s)returnERROR;      pop(s,a);      if(StackEmpty(s)returnERROR;      pop(s,b);      StrAssign(t,Concat(r,b);      StrAssign(c,Concat(t,a);/把算符r,子前缀表达式a,b连接为新子前缀表达式c      push(s,c);      /for  pop(s,new);  if(!StackEmpty(s)returnERROR;  returnOK;/NiBoLan_to_BoLan分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.4.15voidStrAssign(Stringtype&T,charchars&#;)/用字符数组chars给串T赋值,Stringtype的定义见课本  for(i=0,T0=0;charsi;T0+,i+)Ti+1=charsi;/StrAssign4.16charStrCompare(Stringtypes,Stringtypet)/串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数  for(i=1;i<=s0&&i<=t0&&si=ti;i+);  if(i>s0&&i>t0)return0;  elseif(i>s0)return-ti;  elseif(i>t0)returnsi;  elsereturnsi-ti;/StrCompare4.17intString_Replace(Stringtype&S,StringtypeT,StringtypeV);/将串S中所有子串T替换为V,并返回置换次数  for(n=0,i=1;i<=S0-T0+1;i+)      for(j=i,k=1;Tk&&Sj=Tk;j+,k+);    if(k>T0)/找到了与T匹配的子串:分三种情况处理          if(T0=V0)        for(l=1;l<=T0;l+)/新子串长度与原子串相同时:直接替换          Si+l-1=Vl;      elseif(T0<V0)/新子串长度大于原子串时:先将后部右移              for(l=S0;l>=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  /for  returnn;/String_Replace4.18typedefstruct                charch;                intnum;              mytype;voidStrAnalyze(StringtypeS)/统计串S中字符的种类和个数  mytypeTMAXSIZE;/用结构数组T存储统计结果  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;  /for  for(j=0;Tj.ch;j+)    printf("%c:  %dn",Tj.ch,Tj.num);/StrAnalyze4.19voidSubtract_String(Stringtypes,Stringtypet,Stringtype&r)/求所有包含在串s中而t中没有的字符构成的新串r  r0=0;  for(i=1;i<=s0;i+)      c=si;    for(j=1;j<i&&sj!=c;j+);/判断s的当前字符c是否第一次出现    if(i=j)          for(k=1;k<=t0&&tk!=c;k+);/判断当前字符是否包含在t中      if(k>t0)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;j<=t0&&si+j-1=ti;j+);    if(j>m)/找到了与t匹配的子串          for(k=i;k<=s0-t0;k+)sk=sk+t0;/左移删除      s0-=t0;n+;      /for  returnn;/Delete_SubString4.21typedefstruct                charch;                LStrNode*next;              LStrNode,*LString;/链串结构voidStringAssign(LString&s,LStringt)/把串t赋值给串s  s=malloc(sizeof(LStrNode);  for(q=s,p=t->next;p;p=p->next)      r=(LStrNode*)malloc(sizeof(LStrNode);    r->ch=p->ch;    q->next=r;q=r;    q->next=NULL;/StringAssignvoidStringCopy(LString&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)/串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数  for(p=s->next,q=t->next;p&&q&&p->ch=q->ch;p=p->next,q=q->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=(LStrNode*)malloc(sizeof(LStrNode);    q=q->next;    q->ch=r->ch;  /for/复制串s  for(r=t->next;r;r=r->next)      q->next=(LStrNode*)malloc(sizeof(LStrNode);    q=q->next;    q->ch=r->ch;  /for/复制串t  q->next=NULL;  returnp;/ConcatLString*Sub_String(LStrings,intstart,intlen)/返回一个串,其值等于串s从start位置起长为len的子串  p=malloc(sizeof(LStrNode);q=p;  for(r=s;start;start-,r=r->next);/找到start所对应的结点指针r  for(i=1;i<=len;i+,r=r->next)      q->next=(LStrNode*)malloc(sizeof(LStrNode);    q=q->next;    q->ch=r->ch;  /复制串t  q->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;/查找字符c  if(!p)/没找到      t.tail->next=s.head;    t.tail=s.tail;/把s连接在t的后面    else      q=p->next;    r=(Chunk*)malloc(sizeof(Chunk);/将包含字符c的节点p分裂为两个    for(j=0;j<i;j+)r->chj='#'/原结点p包含c及其以前的部分    for(j=i;j<CHUNKSIZE;j+)/新结点r包含c以后的部分          r->chj=p->chj;      p->chj='#'/p的后半部分和r的前半部分的字符改为无效字符'#'        p->next=s.head;    s.tail->next=r;    r->next=q;/把串s插入到结点p和r之间  /else  t.curlen+=s.curlen;/修改串长  s.curlen=0;/LString_ConcatintFind_Char(Chunk*p,charc)/在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0  for(i=0;i<CHUNKSIZE&&p->chi!=c;i+);  if(i=CHUNKSIZE)return0;  elsereturni+1;/Find_Char4.23intLString_Palindrome(LStringL)/判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0  InitStack(S);  p=S.head;i=0;k=1;/i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始)  for(k=1;k<=S.curlen;k+)      if(k<=S.curlen/2)Push(S,p->chi);/将前半段的字符入串    elseif(k>(S.curlen+1)/2)          Pop(S,c);/将后半段的字符与栈中的元素相匹配      if(p->chi!=c)return0;/失配        if(+i=CHUNKSIZE)/转到下一个元素,当为块中最后一个元素时,转到下一块          p=p->next;      i=0;      /for  return1;/成功匹配/LString_Palindrome4.24voidHString_Concat(HStrings1,HStrings2,HString&t)/将堆结构表示的串s1和s2连接为新串t  if(t.ch)free(t.ch);  t.ch=malloc(s1.length+s2.length)*sizeof(char);  for(i=1;i<=s1.length;i+)t.chi-1=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;k<T.length&&S.chj=T.chk;j+,k+);    if(k=T.length)/找到了与T匹配的子串:分三种情况处理          if(T.length=V.length)        for(l=1;l<=T.length;l+)/新子串长度与原子串相同时:直接替换          S.chi+l-1=V.chl-1;      elseif(T.length<V.length)/新子串长度大于原子串时:先将后部右移              for(l=S.length-1;l>=i+T.length;l-)          S.chl+V.length-T.length=S.chl;        for(l=0;l<V.length;l+)          Si+l=Vl;            else/新子串长度小于原子串时:先将后部左移              for(l=i+V.length;l<S.length+V.length-T.length;l+)          S.chl=S.chl-V.length+T.length;        for(l=0;l<V.length;l+)          Si+l=Vl;            S.length+=V.length-T.length;      i+=V.length;n+;    /if  /for  returnn;/HString_Replace4.26StatusHString_Insert(HString&S,intpos,HStringT)/把T插入堆结构表示的串S的第pos个字符之前  if(pos<1)returnERROR;  if(pos>S.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;i<T.length;i+)    S.chpos+i-1=T.chpos;/插入串T  S.length+=T.length;  returnOK;/HString_Insert4.27intIndex_New(Stringtypes,Stringtypet)/改进的定位算法  i=1;j=1;  while(i<=s0&&j<=t0)      if(j!=1&&si=tj)|(j=1&&si=tj&&si+t0-1=tt0)    /当j=1即匹配模式串的第一个字符时,需同时匹配其最后一个      i=i+j-2;      j=1;        else          i+;j+;      /while  if(j>t0)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->next;  /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;  /while  if(!q)      for(i=1;i<=Strlen(T);i+)      p=p->next;    returnp;  /发现匹配后,要往回找子串的头  returnNULL;/LIndex_KMP4.30voidGet_LRepSub(StringtypeS)/求S的最长重复子串的位置和长度  for(maxlen=0,i=1;i<S0;i+)/串S2向右移i格      for(k=0,j=1;j<=S0-i;j+)/j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动          if(Sj=Sj+i)k+;/用k记录连续相同的字符数      elsek=0;/失配时k归零      if(k>maxlen)/发现了比以前发现的更长的重复子串              lrs1=j-k+1;lrs2=mrs1+i;maxlen=k;/作记录          /for  /for  if(maxlen)      printf("LongestRepeatingSubstringlength:%dn",maxlen);    printf("Position1:%d  Position2:%dn",lrs1,lrs2);    elseprintf("NoRepeatingSubstringfound!n");/Get_LRepSub分析:i代表"错位值".本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,.与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)2).4.31voidGet_LPubSub(StringtypeS,StringtypeT)/求串S和串T的最长公共子串位置和长度  if(S0>=T0)      StrAssign(A,S);StrAssign(B,T);    else      StrAssign(A,T);StrAssign(B,S);  /为简化设计,令S和T中较长的那个为A,较短的那个为B  for(maxlen=0,i=1-B0;i<A0;i+)      if(i<0)/i为B相对于A的错位值,向左为负,左端对齐为0,向右为正          jmin=1;jmax=i+B0;    /B有一部分在A左端的左边    elseif(i>A0-B0)          jmin=i;jmax=A0;    /B有一部分在A右端的右边    else          jmin=i;jmax=i+B0;    /B在A左右两端之间.    /以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.    for(k=0,j=jmin;j<=jmax;j+)          if(Aj=Bj-i)k+;      elsek=0;      if(k>maxlen)              lps1=j-k+1;lps2=j-i-k+1;maxlen=k;          /for  /for  if(maxlen)      if(S0>=T0)          lpsS=lps1;lpsT=lps2;        else          lpsS=lps2;lpsT=lps1;    /将A,B上的位置映射回S,T上的位置    printf("LongestPublicSubstringlength:%dn",maxlen);    printf("PositioninS:%d  PositioninT:%dn",lpsS,lpsT);  /if  elseprintf("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+)    if(n%i=0&&k%i=0)p=i;/求n和k的最大公约数p  for(i=0;i<p;i+)      j=i;l=(i+k)%n;temp=Ai;    while(l!=i)          Aj=temp;      temp=Al;      Al=Aj;      j=l;l=(j+k)%n;    /循环右移一步    Ai=temp;  /for/RSh分析:要把A的元素循环右移k位,则A0移至Ak,Ak移至A2k.直到最终回到A0.然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A0,A1,.Ap-1为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:n=15,k=6,则p=3.第一条链:A0->A6,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;i<m;i+)      for(min=Ai0,j=0;j<n;j+)      if(Aij<min)min=Aij;/求一行中的最小值    for(j=0;j<n;j+)      if(Aij=min)/判断这个(些)最小值是否鞍点              for(flag=1,k=0;k<m;k+)          if(min<Akj)flag=0;        if(flag)          printf("Foundasaddleelement!nA%d%d=%d",i,j,Aij);        /for/Get_Saddle5.20本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复.5.21voidTSMatrix_Add(TSMatrixA,TSMatrixB,TSMatrix&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.i<x)pa+;    while(B.datapb.i<x)pb+;    while(A.datapa.i=x&&B.datapb.i=x)/行列值都相等的元素          if(A.datapa.j=B.datapb.j)              ce=A.datapa.e+B.datapb.e;        if(ce)/和不为0                  C.datapc.i=x;          C.datapc.j=A.datapa.j;          C.datapc.e=ce;          pa+;pb+;pc+;              /if      elseif(A.datapa.j>B.datapb.j)              C.datapc.i=x;        C.datapc.j=B.datapb.j;        C.datapc.e=B.datapb.e;        pb+;pc+;            else              C.datapc.i=x;        C.datapc.j=A.datapa.j;        C.datapc.e=A.datapa.e        pa+;pc+;          /while    while(A.datapa=x)/插入A中剩余的元素(第x行)          C.datapc.i=x;      C.datapc.j=A.datapa.j;      C.datapc.e=A.datapa.e      pa+;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+;      /for  C.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.i<x)pa+;    while(B.datapb.i<x)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)/和不为0                  A.datapc.i=x;          A.datapc.j=A.datapa.j;          A.datapc.e