编写对串求逆的递推算法

1、第四章 串1 编写对串求逆的递推算法。void String_Reverse(Stringtype s,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中  /Str

2、ing_Reverse 2编写一个实现串和置换操作Replace(&S,T,V)的算法。int String_Replace(Stringtype &S,Stringtype T,Stringtype V);/将串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匹配的子串:分三种情

3、况处理          if(T0=V0)        for(l=1;l<=T0;l+) /新子串长度与原子串相同时:直接替换          Si+l-1=Vl;      else if(T0<V0) /新子串长度大于原子串时:先将后部

4、右移              for(l=S0;l>=i+T0;l-)          Sl+V0-T0=Sl;        for(l=1;l<=V0;l+)        

5、60; Si+l-1=Vl;            else /新子串长度小于原子串时:先将后部左移              for(l=i+V0;l<=S0+V0-T0;l+)          Sl=Sl-V0+T0;

6、        for(l=1;l<=V0;l+)          Si+l-1=Vl;            S0=S0-T0+V0;      i+=V0;n+;    /if 

7、 /for  return n;/String_Replace 3编写算法，从串S中删除所有和串T相同的子串。int Delete_SubString(Stringtype &s,Stringtype t)/从串s中删除所有与t相同的子串,并返回删除次数  for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i+)    if(!StrCompare(SubString(s,i,Strlen(t),t)     

8、0;    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+;   

9、 /if  return n,/Delete_SubString 4 编写算法，实现串和基本操作StrCompare(S,T).char StrCompare(Stringtype s,Stringtype t)/串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数  for(i=1;i<=s0&&i<=t0&&si=ti;i+);  if(i>s0&&i>t0) return 0;  else if(i>s

10、0) return -ti;  else if(i>t0) return si;  else return si-ti;/StrCompare 5 编写算法，求串S所含不同字符的总数和每种字符的个数。typedef struct                  char ch;         

11、60;       int num;               mytype;void StrAnalyze(Stringtype S)/统计串S中字符的种类和个数  mytype TMAXSIZE; /用结构数组T存储统计结果  for(i=1;i<=S0;i+)      c=Si;j=

12、0;    while(Tj.ch&&Tj.ch!=c) j+; /查找当前字符c是否已记录过    if(Tj.ch) Tj.num+;    else Tj=c,1;  /for  for(j=0;Tj.ch;j+)    printf("%c:  %dn",Tj.ch,Tj.num);/StrAnalyze 6试写一算法，在串的堆存储结

13、构上实现串基本操作Comcat(&T,s1,s2).void HString_Concat(HString s1,HString s2,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.c

14、hi-1=s2.chj-1;  t.length=s1.length+s2.length;/HString_Concat 7 试写一算法，实现堆存储结构的串的插入操作StrInsert(&S,pos,T).Status HString_Insert(HString &S,int pos,HString T)/把T插入堆结构表示的串S的第pos个字符之前  if(pos<1) return ERROR;  if(pos>S.length) pos=S.length+1;/当插入位置大于串长时,看作添加在串尾&

15、#160; 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;  retur

16、n OK;/HString_Insert 8假设以块链结构表示串，试编写将串S插入到串T中某个字符之后的算法（若串T中不存在此字符，则将串S联接在串T的末尾）。void LString_Concat(LString &t,LString &s,char c)/用块链存储结构,把串s插入到串t的字符c之后  p=t.head;  while(p&&!(i=Find_Char(p,c) p=p->next; /查找字符c  if(!p) /没找到    

17、0; 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包

18、含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之间