数据结构串和模式匹配.docx
《数据结构串和模式匹配.docx》由会员分享，可在线阅读，更多相关《数据结构串和模式匹配.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构串和模式匹配
常熟理工学院
《数据结构与算法》实验指导与报告书
_2017-2018_____学年第__1__学期
专业：
物联网工程
实验名称：
串与模式匹配
实验地点：
N6-210
指导教师：
聂盼红
计算机科学与工程学院
2017
实验四串与模式匹配
【实验目的】
1、掌握串的存储表示及基本操作；
2、掌握串的两种模式匹配算法：
BF和KMP。
3、了解串的应用。
【实验学时】
2学时
【实验预习】
回答以下问题：
1、串和子串的定义
串：
串是由零个或多个任意字符组成的有限序列。
子串：
串中任意连续字符组成的子序称为该串的字串。
2、串的模式匹配
串的模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。
假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。
P称为模式，T称为目标。
如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败
【实1
验内容和要求】/
1、按照要求完成程序exp4_1.c，实现串的相关操作。
调试并运行如下测试数据给出运行结果：
•求“Thisisaboy”的串长；
•比较”abc3”和“abcde“；表示空格
•比较”english”和“student“；
•比较”abc”和“abc“；
•截取串”white”，起始2，长度2；
•截取串”white”，起始1，长度7；
•截取串”white”，起始6，长度2；
•连接串”asddffgh”和”12344”；
实验代码：
#include
#include
#defineMAXSIZE100
#defineERROR0
#defineOK1
/*串的定长顺序存储表示*/
typedefstruct
{
chardata[MAXSIZE];
intlength;
}SqString;
intstrInit（SqString*s）;/*初始化串*/
intstrCreate（SqString*s）;/*生成一个串*/
intstrLength（SqString*s）;/*求串的长度*/
intstrCompare（SqString*s1,SqString*s2）;/*两个串的比较*/
intsubString（SqString*sub,SqString*s,intpos,intlen）;/*求子串*/
intstrConcat（SqString*t,SqString*s1,SqString*s2）;/*两个串的连接*/
/*初始化串*/
intstrInit（SqString*s）
{
s->length=0;
s->data[0]='\0';
returnOK;
}/*strInit*/
/*生成一个串*/
intstrCreate（SqString*s）
{
printf（"inputstring:
"）;
gets（s->data）;
s->length=strlen（s->data）;
returnOK;
}/*strCreate*/
/*
（1）---求串的长度*/
intstrLength（SqString*s）
{
returns->length;
}/*strLength*/
/*
（2）---两个串的比较，S1>S2返回>0，s1intstrCompare（SqString*s1,SqString*s2）
{
inti;
for（i=0;ilength&&ilength;i++）
if（s1->data[i]!
=s2->data[i]）
returns1->data[i]-s2->data[i];
returns1->length-s2->length;
}/*strCompare*/
/*（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;isub->data[i]=s->data[i+pos-1];
sub->length++;
}
sub->data[i]='\0';
returnOK;
}/*subString*/
/*（4）---两个串连接，s2连接在s1后，连接后的结果串放在t中*/
intstrConcat（SqString*t,SqString*s1,SqString*s2）
{
inti=0,j=0;
while（ilength）{
t->data[i]=s1->data[i];
i++;
}
while（jlength）
t->data[i++]=s2->data[j++];
t->data[i]='\0';
t->length=s1->length+s2->length;
returnOK;
}/*strConcat*/
intmain（）
{
system（"color1f"）;
intn,k,pos,len;
SqStrings,t,x;
do
{
printf（"\n---String---\n"）;
printf（"1.strLentgh\n"）;
printf（"2.strCompare\n"）;
printf（"3.subString\n"）;
printf（"4.strConcat\n"）;
printf（"0.EXIT\n"）;
printf（"\n---String---\n"）;
printf（"\ninputchoice:
"）;
scanf（"%d",&n）;
getchar（）;
switch（n）
{
case1:
printf（"\n***showstrLength***\n"）;
strCreate（&s）;
printf（"strLengthis%d\n",strLength（&s））;
break;
case2:
printf（"\n***showstrCompare***\n"）;
strCreate（&s）;
strCreate（&t）;
k=strCompare（&s,&t）;/*（5）---调用串比较函数比较s，t*/
if（k==0）
printf（"twostringequal!
\n"）;
elseif（k<0）
printf（"firststring\n"）;
else
printf（"firststring>secondstring!
\n"）;
break;
case3:
printf（"\n***showsubString***\n"）;
strCreate（&s）;
printf（"inputsubstringpos,len:
"）;
scanf（"%d,%d",&pos,&len）;
if（subString（&t,&s,pos,len））
printf（"subStringis%s\n",t.data）;
else
printf（"posorlenERROR!
\n"）;
break;
case4:
printf（"\n***showsubConcat***\n"）;
strCreate（&s）;
strCreate（&t）;
if（strConcat（&x,&s,&t））/*（6）---调用串连接函数连接s&t*/
printf（"Concatstringis%s",x.data）;
else
printf（"ConcatERROR!
\n"）;
break;
case0:
exit（0）;
default:
break;
}
}
while（n）;
return0;
}
2、按照要求完成程序exp4_2.c，实现BF&KMP串的模式匹配算法。
调试及测试数据并给出结果：
•应用BF算法求子串”JING”在主串”BEIJING”中的位置，测试起始位置分别为1和5的情况；
•应用KMP算法求子串”abaabcac”在主串”acabaabaabcacaabc”中的位置，测试起始位置分别为1，10的情况，并写出子串的next[]值；
exp4_2.c部分代码如下：
#include
#include
#defineMAXSIZE100
#defineERROR0
#defineOK1
/*串的定长顺序存储表示*/
typedefstruct
{
chardata[MAXSIZE];
intlength;
}SqString;
intstrCreate（SqString*s）;
intindexBf（SqString*s,SqString*t,intpos）;/*串的模式匹配BF*/
voidgetNext（SqString*t,intnext[]）;/*KMP求next值*/
intindexKmp（SqString*s,SqString*t,intstart,intnext[]）;/*串的模式匹配KMP*/
/*生成一个串*/
intstrCreate（SqString*s）
{
printf（"inputstring:
"）;
gets（s->data）;
s->length=strlen（s->data）;
returnOK;
}/*strCreate*/
/*
（1）---串的模式匹配BF*/
intindexBf（SqString*s,SqString*t,intpos）
{
inti=pos-1,j=0;
while（ilength&&jlength）
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=0,j=-1;
next[0]=-1;
while（ilength）{
if（（j==-1）||（t->data[i]==t->data[j]））{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}/*getNext*/
/*（3）---KMP模式匹配*/
intindexKmp（SqString*s,SqString*t,intstart,intnext[]）
{
inti=start-1,j=0;
while（ilength&&jlength）
if（j==-1||s->data[i]==t->data[j]）{
i++;
j++;
}
else
j=next[j];
if（j>=t->length）
returni-t->length+1;
else
return0;
}/*index_kmp*/
intmain（）
{
system（"color1f"）;
intn,i,pos,next[MAXSIZE];
SqStrings,t;
do
{
printf（"\n---String---\n"）;
printf（"1.Index_BF\n"）;
printf（"2.INdex_KMP\n"）;
printf（"0.EXIT\n"）;
printf（"\n---String---\n"）;
printf（"\ninputchoice:
"）;
scanf（"%d",&n）;
getchar（）;
switch（n）
{
case1:
printf（"\n***showIndex_BF***\n"）;
printf（"s:
"）;
strCreate（&s）;
printf（"t:
"）;
strCreate（&t）;
printf（"inputstartposition:
"）;
scanf（"%d",&pos）;
printf（"BF:
indexis%d\n",indexBf（&s,&t,pos））;
break;
case2:
printf（"\n***showIndex_KMP***\n"）;
printf（"s:
"）;
strCreate（&s）;
printf（"t:
"）;
strCreate（&t）;
printf（"inputstartposition:
"）;
scanf（"%d",&pos）;
getNext（&t,next）;
printf（"KMP:
\n"）;
printf（"next[]:
"）;
for（i=0;iprintf（"%3d",next[i]）;
printf（"\n"）;
printf（"indexis%d\n",indexKmp（&s,&t,pos,next））;
break;
case0:
exit（0）;
default:
break;
}
}
while（n）;
return0;
}
【实验小结】
通过这次实验，我在其中遇到了很多问题。
比如掌握了串的存储表示及基本操作，认识到事情的解决有很多方式。
比如求next的值就BF算法以及KMP算法。
两种算法时间复杂度一个是线性的一个是非线性的，运行起的效率就会明显不一样。
所以认识问题要全面，就觉问题要多考虑。
并且还了解了串的应用，对这种结构有了更深一步的认识。
升级会员 