數據結構實驗報告-串與模式匹配

1、數據結構實驗報告實驗名稱串班級0901姓名髙傲學號20091185015日期2011 12 8實驗目的：（1）掌握順序串的各種基本運算（2）掌握模式匹配算法實驗內容：2.1編寫一個程序algo3-l.cpp,實現順序串的各種基本運算，并在此基礎上設訃一個主函數 完成如下功能：（1）建立串 s=wabcdefghefghijklmnw和串 sWxyz；（2）輸出串s：（3）輸出串s的長度：（4）在串s的第9個字符位置插入串si而產生串s2：（5）輸出串s2：（6）刪除串s第2個字符開始的5個字符而產生串s2：（7）輸出串s2：（8）將串s第2個字符開始的5個字符替換成串si而產生串s2：（9）輸

2、出和串s2.（10）提取串s的第2個字符開始的10個字符而產生串S3：（11）輸出串S3：（22）將串si和串s2連接起來而產生串s4：（13）輸出串s4.程序源代碼：2. 1的源程序：Sinclude Sdefine MAXSIZE 256 /char sMAXSIZE;/求串長int StrLength(char *s) int i二0;while(si != 0)i+；return (i);/串聯(lián)接int StrConcat(char *si, char *s2, char *s)int i二0, j, lenlF len2;lenl= StrLength(sl);len2= StrLe

3、ngth(s2);if(lenl+len2 MAXSIZE-1)return (0);j 二0；wh 訂 e(slj!= or)si=slj;i+；j+;j 二0； while(s2j!= 0F)si=s2j;i+；j+;si二P;return (1);/求子串int StrSub(char *tf char *s, int i, int len) int slen,j; slen=StrLength(s);if(islen lenslen-i+l) printf(-參數不對0; return (0); for(j=0; jlen; j+)tj=si+j-l;tj= 0;return (1);

4、/串比較int StrCmp(char *sl, char *s2)int i二0;while(sli = s2i & sli!=0) i+；return (sli二二 s2i);/輸岀串void Disp_Str(char *s)int i;for(i=0;iStrLength(s);i+)printfsi); printf(n);插入串并保存到新串中int Strinsert (char *s, char * si, int i, char *s2) int j二0, k, lensl, lens; lens=StrLength(s);lensl=StrLength(si);for(k=0

5、; ki-l; k+) s2j=sk;j+；for(int 1=0; Klensl; 1+)s2j=sll;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-l); klens; k+)s2i=sk;i+；s2i= 0;return (1);用一個串替代另一個串中部分

6、字符并保存到新串中int TiDaiStr(char *s, char *si, char *s2, int a, int b) int i二0, lens, lensl; lens=StrLength(s); lensl=StrLength(si);for (int j二0; ja-l; j+)s2i=sj;i+；for(int k=0; klensl; k+)s2i=slk;i+；for(int l=(a+b-1); Klens; 1+) s2i=sl;i+；s2i= 0;return (1);int main(void)printf C (1)建立串 s=abcdefghefghi jk

7、lmn 和 sl=xyzn?，);char sMAXSIZE =，zabcdefghefghijklmn;char siMAXSIZE二xyz;printf C (2)輸出串 s二);Disp_Str (s);printf (，z (3)輸出串 s 的長度:%dn* StrLength(s);printf C (4)在串s的第9個字符位置插入串si而產生s2n);char s2MAXSIZE;Strinsert (s, si, 9, s2);printf C (5)輸出串 s2二);Disp_Str (s2);printf C (6)刪除串s第2個字符開始的5個字符而產生串s2n);StrDe

8、lete(s, s2, 2, 5);printf (，? (7)輸出串 s2:);Disp_Str (s2);printf (8)將串s第2個字符開始的5個字符替換成串si而產生串s2n);TiDaiStr (s, si, s2, 2, 5);printf C (9)輸出 s2二);Disp_Str (s2);printf (w (10)提取串s的第2個字符開始的10個字符而產生串s3n);printf (* (11)輸岀 s3二)；char s3MAXSIZE;StrSub (s3, s, 2, 10);Disp_Str (s3);printf C (12)將串si和串s2連接起來而產生串s

9、4n);char s4MAXSIZE;StrConcat(si, s2t s4);printf C (13)輸岀串 s4O;Disp_Str (s4);getchar0;return(0);2.2#include#define maxsize 256 char 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+l=si;s0=Str

10、Length (s);return (1);/簡單模式匹配int StrIndex_Bf(char *s, char *t)int i=l, j=l;while(i=sO&j=tO)if (si=tjj)i+；j卄；elsei=i-j+2;j二 1;辻 Gto)return (i-t.O);elsereturn T;/輸岀next值int Dis_next (int next, char *t)int i;for(i=l;i=t0;i+)printf (z/%dz，, next ZiJ)；printf(n);return nexti;/模式串求next值void Getnext(char *t

11、,int next)int i=l, j=0;nextl=0;wh訂e(it0)if (j=0+i；+J；next LiJ =j;elsej=nextj;采用KMP算法求t在s中的位苣int SerIndex_KMP(char *s, char *t,int pos,int next) int i=pos, j=l;while (i=sO&jtO)returnelsereturn T;int main(void)printf C (1)建立 abcabcdabcdeabcdefabcdefg 目標串 s 和 abcdeabcdefab 模式串 tn);char s 匚=/，abcabcdabc

12、deabcdefabcdefg/;char t=?/abcdeabcdefabz，;Change (s);Change (t);printf (2)簡單模式匹配求 t 在 s 中的位置:%dn, StrIndex_Bf (s, t);printf (，z (3)由模式串 t 求出 next 值 next二);int nextmaxsize；Getnext(t, next);Dis_next(next, t);printf C (4)采用 KMP 算法求 t 在 s 中的位置:%dn, Serlndex.KMP(s, t, 1, next);2. 2源程序：#include#define max

13、size 256char smaxsize;char t100;int nextmaxsize;/求串長int StrLength(char *s)int i二0;wh訂e(si != 0)i+；return (i);int Change(char *s)int i;for(i=StrLength (s)-1; i=0; i)si+l=si;s E0=StrLength (s);return (1);/簡單模式匹配int StrIndex_Bf(char *s, char *t)int i=l, j=l;while(i=s0&jtO)return (i-t0); elsereturn -1;/

14、輸岀next值int Dis_next (int next, char *t) int i;for(i=l;i=t0;i+)printf (，z%d/z, next Li);printf(n); return nexti;/模式串求next值void Getnext(char *t,int next) int i=l, j=0;nextl=0; while(it 0)if(j=O ti=tj)+i；+J；nexti=j;else j=nextj; /采用KMP算法求t在s中的位置 int SerIndex_KMP(char *s, char *t,int pos,int next)int i=

15、pos,j=l;while(i=s0&jtol)return i-t;elsereturn -1;int main(void)printf C (1)建立 abcabcdabcdeabcdefabcdefg 目標串 s 和 abcdeabcdefab 模式串 tn);char s abcabcdabcdeabcdefabcdefg;char 二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 C (4)采用 KMP算法求 t 在 s 中的位置:%dn?z, SerIndex_KMP(s, t, 1, next) ;char getchar0;return(0);運行結果: H振結溝實驗c huana Igo2-l.exe建?7 串cdief uhi/iklmn 和 si2啪出串r ：-二j z小一 3鐘出串3的長度:： #Ss的第9個宇符位畫插入串而產生s2 錨亠 6製瞬吳第2個字符開始的5個字符而產生串