数据结构 串与模式匹配

《数据结构与算法》实验指导V2022

常熟理工学院

微据绵屿算洲实验指导与报告书

2022-2022学年第_1―学期

专业：__________________物联网工程____________________________

实验名称：__________________鼓模飒__________________

簿贼吐21°

指导教师聂盼红

牖蝌学与工程学院

2022

常熟理工学院计算机科学与工程学院1

《数据结构与算法》实验指导V2022

实验四串与模式匹配

【实验目的】

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

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

3、了解串的应用。

【实验学时】

2学时

【实验预习】

回答以下问题：

1、串和子串的定义

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

子串：串中任意连续字符组成的子序称为该串的字串。

2、串的模式匹配

串的模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串

中找出与该子串相同的所有子串，这就是模式匹配。假设是给定的子串，是待查找的字

符串，要求从中找出与相同的所有子串，这个问题成为模式匹配问题。称为模式，

称为目标。如果中存在一个或者多个模式为的子串，就给出该子串在中的位置，称为

匹配成功；否则匹配失败

【实1

验内容和要求】/

1、按照要求完成程序exp4_1.c,实现串的相关操作。调试并运行如下测试数据给出运

行结果：

④求“Thisisaboy”的串长；

inputchoice:1

***showstrLength***

inputstring:Thisisaboy

strLengthis13

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

常熟理工学院计算机科学与工程学院2

《数据结构与算法》实验指导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”；

常熟理工学院计算机科学与工程学院3

《数据结构与算法》实验指导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*/

常熟理工学院计算机科学与工程学院4

《数据结构与算法》实验指导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)一两个串联接，s2连接在s1后，连接后的结果串放在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;

常熟理工学院计算机科学与工程学院5

《数据结构与算法》实验指导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);/*⑸--调用串比较函数比较s,t7

if(k==O)

elseif(k<0)

else

break;

case3:

strCreate(&s);

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

常熟理工学院计算机科学与工程学院6

《数据结构与算法》实验指导V2022

else

break;

case4:

strCreate(&s);

strCreate(&t);

if(strConcat(&x,&s,&t))/*(6)-调用串联接函数连接s&t7

else

break;

caseO:

exit(O);

default:

break;

while(n);

return0;

)

2、按照要求完成程序exp4_2.c,实现BF&KMP串的模式匹配算法。调试及测试数据

并给出结果:

④应用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

④应用KMP算法求子串”abaabcacv在主串"acabaabaabcacaabcn中的位置，测

试起始位置分别为1,10的情况，并写出子串的next。值；

常熟理工学院计算机科学与工程学院7

《数据结构与算法》实验指导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)

常熟理工学院计算机科学与工程学院8

《数据结构与算法》实验指导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];

常熟理工学院计算机科学与工程学院9

《数据结构与算法》实验指导V2022

if(j>=t->length)

returni-t->length+1;

else

return0;

}/*index_kmp*/

intmai