河北大学：《数据结构》课程教学资源（习题解答）第四章 串

1.利用c的库函数 strlen, strcpy和 strcat写一个算法 void strIngent(char+s,char T,inti),将串哩插入到s的第i个位置上。若i大于s的长度,则插入不执行。 void strinsert(char *s, char *t, int 1) if(i>strlen(s) return strcopy (s+i, r); s[i]-0 strcat(s strcat(s 2利用c的库函数 strlen, strcpy(或 strncpy)写一个算法 void str Delete(char*s,int i,intm),删除串s中从位置ⅰ开始的连续的m个字符。若i≥ strlen(S),则没有字符被删除 i+m≥ strlen(s),则将s中从位置辶开始直至末尾的字符均被删去。 void strdelete(char *s, int m) if(i>=strlen(s) return if (i+m>strlen(s) s[i]-"0 els for(k=+m; s[ k]!=0, k++) s[k-m=s[k] s[k]=0’ return 3采用顺序结构存储串,编写一个函数,求串s和串t的一个最长的公共子串。 typedef struct( char *data int len Astring: void maxsubstr(char *s, char *t, char *r) /*求S和T的最长公共子串* int i,j, k, num, maxnum=0, index=0

⒈利用 C 的库函数 strlen,strcpy 和 strcat 写一个算法 void StrInsert(char *S,char *T,int i)，将串 T 插入到 S 的第 i 个位置上。若 i 大于 S 的长度，则插入不执行。 void strinsert(char *s,char *t, int i) { if (i>strlen(s)) return; strcopy(s+i,r); s[i]='\0'; strcat(s,t); strcat(s,r); } ⒉利用 C 的库函数 strlen，strcpy（或 strncpy）写一个算法 void StrDelete(char *S,int i,int m) ，删除串 S 中从位置 i 开始的连续的 m 个字符。若 i≥strlen(S)，则没有字符被删除；若 i+m≥strlen(S)，则将 S 中从位置 i 开始直至末尾的字符均被删去。 void strdelete(char *s, int m) { if (i>=strlen(s)) return; if (i+m>=strlen(s)) s[i]='\0'; else { for (k=i+m;s[k]!='\0';k++) s[k-m]=s[k]; s[k]='\0'; } return; } ⒊采用顺序结构存储串，编写一个函数，求串 s 和串 t 的一个最长的公共子串。 typedef struct{ char *data; int len; }string; void maxsubstr(char *s,char *t,char *r) /*求 S 和 T 的最长公共子串*/ { int i,j,k,num,maxnum=0,index=0;

1=0 while(ilen) whilelen) if(s->data[]==t->dataD num=I for(k-l; S->datai+k]==t->data[j+k]; k++) num=num+l if(num>maxnum) ndex-1, maxnum-num J+-num H+十 for(i-index j =0; i data[j=s->data[i] return: 4.采用顺序存储结构存储串,编写一个函数计算一个子串在一个字符串中出现的次数,如果该子串不 出现则为0 int count(char *s, char * t) int 1=0, c=0.j while(i<strlen(s) j=strindex KMP(s,t, i, next)

i=0; while (ilen) { j=0; while(jlen) { if (s->data[i]==t->data[j]) { num=1; for (k=1;s->data[i+k]==t->data[j+k];k++) num=num+1; if (num>maxnum) { index=i; maxnum=num; } j+=num; i=0; } else j++; } i++; } for (i=index,j=0;idata[j]=s->data[i]; return; } ⒋采用顺序存储结构存储串，编写一个函数计算一个子串在一个字符串中出现的次数，如果该子串不 出现则为 0。 int count(char *s,char *t) { int i=0,c=0,j; while (i<strlen(s)) { j=strindex_KMP(s,t,i,next);

if(!=0) c++ i=i+strlen(t) return(c)

if (j!=0) c++; i=i+strlen(t); } return(c); }