数据结构实验报告-串与模式匹配.docx

数据结构实验报告实验名称串班级0901姓名高傲学号20091185015日期2011 12 8实验目的：（1）掌握顺序串的各种基本运算（2）掌握模式匹配算法实验内容：2.1 编写一个程序algo3-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个主函数完成如下功能：（1）建立串s=”abcdefghefghijklmn”和串s1=”xyz”；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出和串s2.（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。程序源代码：2.1的源程序：#include #define maxsize 256/char smaxsize;/求串长int strlength(char *s)int i=0;while(si!=0)i+;return(i);/串联接int strconcat(char *s1, char *s2, char *s)int i=0, j, len1, len2;len1= strlength(s1);len2= strlength(s2);if(len1+len2 maxsize-1)return (0);j=0;while(s1j!=0)si=s1j;i+;j+;j=0;while(s2j!=0)si=s2j;i+;j+;si=0;return (1);/求子串int strsub(char *t, char *s, int i, int len)int slen,j;slen=strlength(s);if(islen | lenslen-i+1)printf(参数不对);return (0);for(j=0; jlen; j+)tj=si+j-1;tj=0;return (1);/串比较int strcmp(char *s1, char *s2)int i=0;while(s1i = s2i & s1i!=0)i+;return (s1i = s2i);/输出串void disp_str(char *s)int i;for(i=0;istrlength(s);i+)printf(%c,si);printf(n);/插入串并保存到新串中int strinsert(char *s, char *s1, int i, char *s2)int j=0,k,lens1, lens;lens=strlength(s);lens1=strlength(s1);for(k=0; ki-1; k+)s2j=sk;j+;for(int l=0; llens1; l+)s2j=s1l;j+;for(int m=k; mlens; m+)s2j=sm;j+;s2j=0;return (1);/删除串中元素并保存到新串中int strdelete(char *s, char *s2, int a, int b)int i=0, lens=strlength(s);for(int j=0; j(a-1); j+)s2i=sj;i+;for(int k=(a+b-1); klens; k+)s2i=sk;i+;s2i=0;return (1);/用一个串替代另一个串中部分字符并保存到新串中int tidaistr(char *s, char *s1, char *s2, int a, int b)int i=0, lens, lens1;lens=strlength(s);lens1=strlength(s1);for(int j=0; ja-1; j+)s2i=sj;i+;for(int k=0; klens1; k+)s2i=s1k;i+;for(int l=(a+b-1); llens; l+)s2i=sl;i+;s2i=0;return (1);int main(void)printf(1)建立串s=abcdefghefghijklmn和s1=xyzn);char smaxsize=abcdefghefghijklmn;char s1maxsize=xyz;printf(2)输出串s=);disp_str(s);printf(3)输出串s的长度:%dn,strlength(s);printf(4)在串s的第9个字符位置插入串s1而产生s2n);char s2maxsize;strinsert(s, s1, 9, s2);printf(5)输出串s2=);disp_str(s2);printf(6)删除串s第2个字符开始的5个字符而产生串s2n);strdelete(s, s2, 2, 5);printf(7)输出串s2:);disp_str(s2);printf(8)将串s第2个字符开始的5个字符替换成串s1而产生串s2n);tidaistr(s, s1, s2, 2, 5);printf(9)输出s2=);disp_str(s2);printf(10)提取串s的第2个字符开始的10个字符而产生串s3n);printf(11)输出s3=);char s3maxsize;strsub(s3, s, 2, 10);disp_str(s3);printf(12)将串s1和串s2连接起来而产生串s4n);char s4maxsize; strconcat(s1, s2, s4);printf(13)输出串s4=);disp_str(s4);getchar();return(0);2.2#include#define maxsize 256char smaxsize;char t100;int nextmaxsize;/求串长int strlength(char *s)int i=0;while(si!=0)i+;return(i);int change(char *s)int i;for(i=strlength(s)-1; i=0; i-)si+1=si;s0=strlength(s);return (1);/简单模式匹配int strindex_bf(char *s,char *t)int i=1,j=1;while(i=s0&jt0) return (i-t0); elsereturn -1;/输出next值int dis_next(int next,char *t) int i; for(i=1;i=t0;i+) printf(%d,nexti); printf(n); return nexti;/模式串求next值void getnext(char *t,int next) int i=1,j=0; next1=0; while(it0) if(j=0|ti=tj) +i; +j; nexti=j;elsej=nextj; /采用kmp算法求t在s中的位置int serindex_kmp(char *s,char *t,int pos,int next) int i=pos,j=1; while(i=s0&jt0)return i-t0;elsereturn -1; int main(void)printf(1)建立abcabcdabcdeabcdefabcdefg目标串s和abcdeabcdefab模式串tn); char s=abcabcdabcdeabcdefabcdefg;char t=abcdeabcdefab; change(s); change(t);printf(2)简单模式匹配求t在s中的位置:%dn,strindex_bf(s,t); printf(3)由模式串t求出next值next=);int nextmaxsize; getnext(t,next);dis_next(next,t); printf(4)采用kmp算法求t在s中的位置:%dn,serindex_kmp(s,t,1,next);2.2源程序：#include#define maxsize 256char smaxsize;char t100;int nextmaxsize;/求串长int strlength(char *s)int i=0;while(si!=0)i+;return(i);int change(char *s)int i;for(i=strlength(s)-1; i=0; i-)si+1=si;s0=strlength(s);return (1);/简单模式匹配int strindex_bf(char *s,char *t)int i=1,j=1;while(i=s0&jt0) return (i-t0); elsereturn -1;/输出next值int dis_next(int next,char *t) int i; for(i=1;i=t0;i+) printf(%d,nexti); printf(n); return nexti;/模式串求next值void getnext(char *t,int next) int i=1,j=0; next1=0; while(it0) if(j=0|ti=tj) +i; +j; nexti=j;elsej=nextj; /采用kmp算法求t在s中的位置int serindex_kmp(char *s,char *t,int pos,int next) int i=pos,j=1; while(i=s0&jt0)return i-t0;elsereturn -1; int main(void)printf(1)建立abcabcdabcdeabcdefabcdefg目标串s和abcdeabcdefab模式串tn); char s=abcabcdabcdeabcdefabcdefg;char t=abcdeabcdefab; change(s); change