20122058-张伟-串练习题.doc

第四章 串练习题 编程题 9. 编写对串求逆的算法。 程序如下： #include stdio.h #include string.h main() { char str[100],c; int i,j; printf(请输入一个字符串:); gets(str); for(i=0,j=strlen(str)-1;ij;i++,j--) { c=str[i]; str[i]=str[j]; str[j]=c; } printf(逆序排序的结果为:); printf(%s\n,str); } 8.编写模式匹配算法 运算结果见右图，程序如下： #include stdio.h #include string.h int index_KMP(char *s,char *t,int pos); void get_next(char *t,int *); char s[100],t[20]; int next[20],pos=0; //主函数 main() { printf(------------------------模式匹配算法----------------------\n); printf(0---匹配失败，i---匹配成功,i--指主串中第一个字符出现的位置\n); int n; printf(请输入主串s:\n); gets(s); printf(请输入模式串t:\n); gets(t); get_next(t,next); n=index_KMP(s,t,pos); printf(匹配的结果:%d\n,n); } //KMP模式匹配算法 int index_KMP(char *s,char *t,int pos) { int i=pos,j=1; while (i=(int)strlen(s)j=(int)strlen(t)) { if (j==0||s[i]==t[j-1]) { i++; j++; } else j=next[j]; } if(j(int)strlen(t)) return i-strlen(t)+1; else return 0; } void get_next(char *t,int *next) { int i=1,j=0; next[0]=next[1]=0; while (i(int)strlen(t)) { if (j==0||t[i]==t[j]) { i++; j++; next[i]=j; } else j=next[j]; } } 7.已知主串 s = ADBADABBAABADABBADADA,　模式串 pat = ADABBADADA,　写出模式串的 nextval 函数值，并由此画出 KMP 算法匹配的全过程。 结果如右、程序如下：（借鉴网上） #includestdio.h #includestring.h //定义串的结构体 typedef struct seqstring { char string[100]; int length; }seqstring; void getnext(seqstring p,int next[]) { int i,j; next[0]=-1;//next[0]放上-1 i=0;//指向字符串每个字符的指针 j=-1; while(ip.length){//没有到达结尾的话 if(j==-1||p.string[i]==p.string[j]) {//如果是第一个字符或遇到相同的字符 i++;j++;next[i]=j; } else j=next[j]; } for(i=0;ip.length;i++){//输出next[]值 printf(%d,next[i]); } } //KMP算法 int kmp(seqstring t,seqstring p,int next[]) { int i,j; i=j=0; while(it.lengthjp.length) { if(j==-1||t.string[i]==p.string[j]) { i++;j+