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

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

常熟理工學(xué)院

微據(jù)綿嶼算洲實驗指導(dǎo)與報告書

2022-2022學(xué)年第_1―學(xué)期

專業(yè)：__________________物聯(lián)網(wǎng)工程____________________________

實驗名稱：__________________鼓模颯__________________

簿賊吐21°

指導(dǎo)教師聶盼紅

牖蝌?qū)W與工程學(xué)院

2022

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院1

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

實驗四串與模式匹配

【實驗?zāi)康摹?/p>

1、掌握串的存儲表示及基本操作；

2、掌握串的兩種模式匹配算法：BF和KMP。

3、了解串的應(yīng)用。

【實驗學(xué)時】

2學(xué)時

【實驗預(yù)習(xí)】

回答以下問題：

1、串和子串的定義

串：串是由零個或者多個任意字符組成的有限序列。

子串：串中任意連續(xù)字符組成的子序稱為該串的字串。

2、串的模式匹配

串的模式匹配是數(shù)據(jù)結(jié)構(gòu)中字符串的一種基本運算，給定一個子串，要求在某個字符串

中找出與該子串相同的所有子串，這就是模式匹配。假設(shè)是給定的子串，是待查找的字

符串，要求從中找出與相同的所有子串，這個問題成為模式匹配問題。稱為模式，

稱為目標。如果中存在一個或者多個模式為的子串，就給出該子串在中的位置，稱為

匹配成功；否則匹配失敗

【實1

驗內(nèi)容和要求】/

1、按照要求完成程序exp4_1.c,實現(xiàn)串的相關(guān)操作。調(diào)試并運行如下測試數(shù)據(jù)給出運

行結(jié)果：

④求“Thisisaboy”的串長；

inputchoice:1

***showstrLength***

inputstring:Thisisaboy

strLengthis13

④比較”abcI3”和“abcde"：I表示空格

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院2

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

***showstrCompare***

inputstring:abc3

inputstring:abcde

firststring<secondstring!

④比較"english”和“student^

***showstrCompare***

inputstring:english

inputstring:student

firststring<secondstring!

④比較"abc"和"abc”；

***showstrCompare***

inputstring:abc

inputstring:abc

twostringequal!

④截取串，White”，起始2,長度2；

inputchoice:3

***showsubString***

inputstring:white

inputsubstringpos,len:2,2

subStringishi

④截取串，9white”，起始1,長度7；

***showsubString***

inputstring:white

inputsubstringpos,len:1,7

posorlenERROR!

④截取串，1white”，起始6,長度2；

***showsubString***

inputstring：white

inputsubstringpos,len:6,2

posorlenERROR!

④連接串“asddffgh”和"12344”；

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院3

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

竹**showsubConcat***

inputstringzasddffgh

inputstring:12344

Concatstringisasddffghl2344

I--String———

實驗代碼：

#include<stdio.h>

#include<string.h>

#defineMAXSIZE100

#defineERROR0

#defineOK1

/*串的定長順序存儲表示?/

typedefstruct

(

chardata[MAXSIZE];

intlength;

}SqString;

intstrlnit(SqString*s);/*初始化串*/

intstrCreate(SqString*s);/*生成一個串*/

intstrLength(SqString*s);/*求串的長度*/

intstrCompare(SqString*s1,SqString*s2);/*兩個串的比較*/

intsubString(SqString*sub,SqString*s,intposjntlen);/*求子串*/

intstrConcat(SqString*t,SqString*s1.SqString*s2);/*兩個串的連接*/

/*初始化串*/

intstrlnit(SqString*s)

(

s->length=0;

returnOK;

}/*strlnit*/

/*生成一個串*/

intstrCreate(SqString*s)

(

gets(s->data);

s->length=strlen(s->data);

returnOK;

}/*strCreate*/

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院4

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

/*(1)---求串的長度*/

intstrLength(SqString*s)

(

returns->length;

}/*strLength*/

/*(2)-兩個串的比較，S1>S2返回>0,s1vs2返回vO,s1==s2返回07

intstrCompare(SqString*s1,SqString*s2)

(

inti;

for(i=0;i<s1->length&&i<s2->length;i++)

if(s1->data[i]!=s2->data[i])

returns1->data[i]-s2->data[i];

returns1->length-s2->length;

}/*strCompare*/

7*(3)—求子串，sub為返回的子串，pos為子串的起始位置，len為子串的長度*/

intsubString(SqString*sub,SqString*s,intpos,intlen)

(

inti;

if(pos<1||pos>s->length||len<0||len>s->length-pos+1)

returnERROR;

sub->length=0;

for(i=0;i<len;i++){

sub->data[i]=s->data[i+pos-1];

sub->length++;

)

returnOK;

}/*subString*/

/*(4)一兩個串聯(lián)接，s2連接在s1后，連接后的結(jié)果串放在t中*/

intstrConcat(SqString*t,SqString*s1,SqString*s2)

(

inti=0,j=0;

while(i<s1->length){

t->data[i]=s1->data[i];

i++；

)

whileQ<s2->length)

t->data[i++]=s2->data[j++];

t->length=s1->length+s2->length;

returnOK;

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院5

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

}/*strConcat*/

intmain()

(

intn,k,pos,len;

SqStrings,t,x;

do

getchar();

switch(n)

(

case1:

strCreate(&s);

break;

case2:

strCreate(&s);

strCreate(&t);

k=strCompare(&s,&t);/*⑸--調(diào)用串比較函數(shù)比較s,t7

if(k==O)

elseif(k<0)

else

break;

case3:

strCreate(&s);

if(subString(&t,&s,pos,len))

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院6

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

else

break;

case4:

strCreate(&s);

strCreate(&t);

if(strConcat(&x,&s,&t))/*(6)-調(diào)用串聯(lián)接函數(shù)連接s&t7

else

break;

caseO:

exit(O);

default:

break;

while(n);

return0;

)

2、按照要求完成程序exp4_2.c,實現(xiàn)BF&KMP串的模式匹配算法。調(diào)試及測試數(shù)據(jù)

并給出結(jié)果:

④應(yīng)用BF算法求子串"J1NG”在主串”B曰JING”中的位置，測試起始位置分別

為1和5的情況；

***showIndex_BF***

s:inputstring:BEIJING

t:inputstring:JING

inputstartposition:1

BF：indexis4

***showIndex_BF***

s:inputstring:BEIJING

t:inputstring:JING

inputstartposition：5

BF：indexis0

④應(yīng)用KMP算法求子串”abaabcacv在主串"acabaabaabcacaabcn中的位置，測

試起始位置分別為1,10的情況，并寫出子串的next。值；

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院7

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

***showIndex_KMP***

s:inputstring:acabaabaabcacaabc

t:inputstring:abaabcac

inputstartposition:1

KMP:

next[]:-10011201

indexis6

***showIndex_KMP***

s:inputstring:acabaabaabcacaabc

t:inputstring:abaabcac

inputstartposition:10

KMP:

next□:-10011201

indexis0

exp4_2.c部份代碼如下：

#include<stdio.h>

#include<string.h>

#defineMAXSIZE100

#defineERROR0

#defineOK1

/*串的定長順序存儲表示*/

typedefstruct

(

chardata[MAXSIZE];

intlength;

}SqString;

intstrCreate(SqString*s);

intindexBf(SqString*s,SqString*t,intpos);/*串的模式匹配BF7

voidgetNext(SqString*t,intnext[]);/*KMP求next值*/

intindexKmp(SqString*s,SqString*t,intstart,intnext。);/*串的模式匹配KMP7

/*生成一個串*/

intstrCreate(SqString*s)

(

gets(s->data);

s->length=strlen(s->data);

returnOK;

}/*strCreate7

/*(1)一串的模式匹配BF7

intindexBf(SqString*s,SqString*t,intpos)

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院8

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

inti=pos-1,j=0;

while(i<s->length&&j<t->length)

if(s->data[i]==t->data[j]){

i++;

j++;

)

else{

i=i?j+1;

j=0；

)

if(j>=t->length)

returni-t->length+1;

else

return0;

}/*index_bf*/

/*(2)…KMP求next

voidgetNext(SqString*t,intnext[])

(

inti=O,j=-1;

next[0]=-1;

while(i<t->length){

if((j==-1)||(t->data[i]==t->data[j])){

i++;

j++;

next[i]=j;

)

else

j=next[j];

}

}/*getNext7

/*(3)—KMP模式匹配*/

intindexKmp(SqString*s,SqString*t,intstart,intnext[])

(

inti=start-1,j=0;

while(i<s->length&&j<t->length)

if(j==-1||s->data[i]==t->data[j]){

i++；

j++;

)

else

j=next[j];

常熟理工學(xué)院計算機科學(xué)與工程學(xué)院9

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗指導(dǎo)V2022

if(j>=t->length)

returni-t->length+1;

else

return0;

}/*index_kmp*/

intmai