數(shù)據(jù)結(jié)構(gòu) 串與模式匹配

1、常熟理工學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)與報(bào)告書(shū)_2017-2018_學(xué)年 第_1_ 學(xué)期專 業(yè)： 物聯(lián)網(wǎng)工程 實(shí)驗(yàn)名稱： 串與模式匹配 實(shí)驗(yàn)地點(diǎn)： N6-210 指導(dǎo)教師： 聶盼紅 計(jì)算機(jī)科學(xué)與工程學(xué)院2017實(shí)驗(yàn)四 串與模式匹配【實(shí)驗(yàn)?zāi)康摹?、掌握串的存儲(chǔ)表示及基本操作；2、掌握串的兩種模式匹配算法：BF和KMP。3、了解串的應(yīng)用?！緦?shí)驗(yàn)學(xué)時(shí)】2學(xué)時(shí)【實(shí)驗(yàn)預(yù)習(xí)】回答以下問(wèn)題：1、串和子串的定義串：串是由零個(gè)或多個(gè)任意字符組成的有限序列。子串：串中任意連續(xù)字符組成的子序稱為該串的字串。2、串的模式匹配串的模式匹配是數(shù)據(jù)結(jié)構(gòu)中字符串的一種基本運(yùn)算，給定一個(gè)子串，要求在某個(gè)字符串中找出與該子串相同的所

2、有子串，這就是模式匹配。假設(shè)P是給定的子串，T是待查找的字符串，要求從T中找出與P相同的所有子串，這個(gè)問(wèn)題成為模式匹配問(wèn)題。P稱為模式，T稱為目標(biāo)。如果T中存在一個(gè)或多個(gè)模式為P的子串，就給出該子串在T中的位置，稱為匹配成功；否則匹配失敗【實(shí)1驗(yàn)內(nèi)容和要求】/1、按照要求完成程序exp4_1.c，實(shí)現(xiàn)串的相關(guān)操作。調(diào)試并運(yùn)行如下測(cè)試數(shù)據(jù)給出運(yùn)行結(jié)果： 求“This is a boy”的串長(zhǎng)； 比較”abc3”和“abcde“；表示空格 比較”english”和“student“； 比較”abc”和“abc“； 截取串”white”，起始2，長(zhǎng)度2； 截取串”white”，起始1，長(zhǎng)度7； 截取

3、串”white”，起始6，長(zhǎng)度2； 連接串”asddffgh”和”12344”；實(shí)驗(yàn)代碼：#include#include#define MAXSIZE 100#define ERROR 0#define OK 1/*串的定長(zhǎng)順序存儲(chǔ)表示*/typedef struct char dataMAXSIZE; int length; SqString;int strInit(SqString *s); /*初始化串*/int strCreate(SqString *s); /*生成一個(gè)串*/int strLength(SqString *s); /*求串的長(zhǎng)度*/int strCompare(Sq

4、String *s1,SqString *s2); /*兩個(gè)串的比較*/int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/int strConcat(SqString *t,SqString *s1,SqString *s2); /*兩個(gè)串的連接*/*初始化串*/int strInit(SqString *s) s-length=0; s-data0=0; return OK;/*strInit*/*生成一個(gè)串*/int strCreate(SqString *s) printf(input string :);

5、gets(s-data); s-length=strlen(s-data); return OK;/*strCreate*/*（1）-求串的長(zhǎng)度*/int strLength(SqString *s) return s-length;/*strLength*/*（2）-兩個(gè)串的比較，S1S2返回0，s1s2返回0，s1=s2返回0*/int strCompare(SqString *s1,SqString *s2) int i; for(i=0; ilength & ilength; i+) if(s1-datai != s2-datai) return s1-datai - s2-datai

6、; return s1-length - s2-length;/*strCompare*/*（3）-求子串，sub為返回的子串，pos為子串的起始位置，len為子串的長(zhǎng)度*/int subString(SqString *sub,SqString *s,int pos,int len) int i; if(poss-length | lens-length-pos+1) return ERROR; sub-length = 0; for(i=0; idatai = s-datai+pos-1; sub-length+; sub-datai = 0; return OK;/*subString*

7、/*（4）-兩個(gè)串連接，s2連接在s1后，連接后的結(jié)果串放在t中*/int strConcat(SqString *t,SqString *s1,SqString *s2) int i=0, j=0; while(ilength) t-datai = s1-datai; i+; while(jlength) t-datai+ = s2-dataj+; t-datai = 0; t-length = s1-length + s2-length; return OK;/*strConcat*/int main() system(color 1f); int n,k,pos,len; SqStrin

8、g s,t,x; do printf(n -String- n); printf( 1. strLentghn); printf( 2. strComparen); printf( 3. subStringn); printf( 4. strConcatn); printf( 0. EXITn); printf(n -String-n); printf(ninput choice:); scanf(%d,&n); getchar(); switch(n) case 1: printf(n*show strLength*n); strCreate(&s); printf(strLength is

9、 %dn,strLength(&s); break; case 2: printf(n*show strCompare*n); strCreate(&s); strCreate(&t); k=strCompare(&s, &t); /*（5）-調(diào)用串比較函數(shù)比較s，t*/ if(k=0) printf(two string equal!n); else if(k0) printf(first stringsecond string!n); break; case 3: printf(n*show subString*n); strCreate(&s); printf(input substri

10、ng pos,len:); scanf(%d,%d,&pos,&len); if(subString(&t,&s,pos,len) printf(subString is %sn,t.data); else printf(pos or len ERROR!n); break; case 4: printf(n*show subConcat*n); strCreate(&s); strCreate(&t); if(strConcat(&x, &s, &t) /*（6）-調(diào)用串連接函數(shù)連接s&t*/ printf(Concat string is %s,x.data); else printf(C

11、oncat ERROR!n); break; case 0: exit(0); default: break; while(n); return 0;2、按照要求完成程序exp4_2.c，實(shí)現(xiàn)BF&KMP串的模式匹配算法。調(diào)試及測(cè)試數(shù)據(jù)并給出結(jié)果： 應(yīng)用BF算法求子串”JING”在主串”BEIJING”中的位置，測(cè)試起始位置分別為1和5的情況； 應(yīng)用KMP算法求子串”abaabcac”在主串”acabaabaabcacaabc”中的位置，測(cè)試起始位置分別為1，10的情況，并寫出子串的next值；exp4_2.c部分代碼如下：#include#include#define MAXSIZE 100

12、#define ERROR 0#define OK 1/*串的定長(zhǎng)順序存儲(chǔ)表示*/typedef struct char dataMAXSIZE; int length; SqString;int strCreate(SqString *s);int indexBf(SqString *s,SqString *t,int pos); /*串的模式匹配BF*/void getNext(SqString *t,int next); /*KMP求next值*/int indexKmp(SqString *s,SqString *t,int start,int next); /*串的模式匹配KMP*/

13、*生成一個(gè)串*/int strCreate(SqString *s) printf(input string :); gets(s-data); s-length=strlen(s-data); return OK;/*strCreate*/*（1）-串的模式匹配BF*/int indexBf(SqString *s,SqString *t,int pos) int i = pos-1, j = 0; while(ilength &jlength) if(s-datai = t-dataj) i+; j+; else i = i - j +1; j = 0; if(j = t-length)

14、return i - t-length+1; else return 0;/*index_bf*/*（2）-KMP求next值*/void getNext(SqString *t,int next) int i = 0, j = -1; next0 = -1; while(i length) if(j=-1) | (t-datai=t-dataj) i+; j+; nexti = j; else j = nextj; /*getNext*/*（3）-KMP模式匹配*/int indexKmp(SqString *s,SqString *t,int start,int next) int i =

15、 start - 1, j = 0; while(ilength & jlength) if(j=-1 | s-datai=t-dataj) i+; j+; else j = nextj; if(j = t-length) return i - t-length+1; else return 0;/*index_kmp*/int main() system(color 1f); int n,i,pos,nextMAXSIZE; SqString s,t; do printf(n -String- n); printf( 1. Index_BFn); printf( 2. INdex_KMPn)

16、; printf( 0. EXITn); printf(n -String-n); printf(ninput choice:); scanf(%d,&n); getchar(); switch(n) case 1: printf(n*show Index_BF*n); printf( s:); strCreate(&s); printf( t:); strCreate(&t); printf(input start position:); scanf(%d,&pos); printf(BF:index is %dn,indexBf(&s,&t,pos); break; case 2: printf(n*show Index_KMP*n); printf( s:); strCreate(&s); printf( t:); strCreate(&t); printf(input start position:); scanf(%d,&pos); getNext(&t,next); printf(KMP:n); printf(next:); for(i=0; it.length; i+) printf(%3d,nexti); printf(n); p