数据结构实验报告串Word文档下载推荐.docx
《数据结构实验报告串Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告串Word文档下载推荐.docx（14页珍藏版）》请在冰点文库上搜索。
•比较”abc”和“abc“；
•截取串”white”，起始2，长度2；
•截取串”white”，起始1，长度7；
•截取串”white”，起始6，长度2；
•连接串”asddffgh”和”12344”；
#include<
stdio.h>
string.h>
#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;
data[0]='
\0'
;
returnOK;
}/*strInit*/
/*生成一个串*/
intstrCreate（SqString*s）
printf（"
inputstring:
"
）;
gets（s->
data）;
length=strlen（s->
}/*strCreate*/
/*
（1）---求串的长度*/
intstrLength（SqString*s）
returns->
length;
}/*strLength*/
/*
（2）---两个串的比较，S1>
S2返回>
0，s1<
s2返回<
0，s1==s2返回0*/
intstrCompare（SqString*s1,SqString*s2）
inti;
for（i=0;
i<
s1->
length&
&
s2->
i++）
{
if（s1->
data[i]>
data[i]）
return1;
}
data[i]<
return-1;
return0;
}/*strCompare*/
/*（3）---求子串，sub为返回的子串，pos为子串的起始位置，len为子串的长度*/
intsubString（SqString*sub,SqString*s,intpos,intlen）
if（pos<
1||pos>
s->
length||len<
0||len>
length-pos+1）
returnERROR;
sub->
len;
data[i]=s->
data[i+pos-1];
length++;
data[i]='
}/*subString*/
/*（4）---两个串连接，s2连接在s1后，连接后的结果串放在t中*/
intstrConcat（SqString*t,SqString*s1,SqString*s2）
inti=0,j=0;
while（i<
length）
t->
data[i]=s1->
data[i];
i++;
while（j<
data[i++]=s2->
data[j++];
length=s1->
length+s2->
}/*strConcat*/
intmain（）
intn,k,pos,len;
SqStrings,t,x;
do
\n---String---\n"
1.strLentgh\n"
2.strCompare\n"
3.subString\n"
4.strConcat\n"
0.EXIT\n"
\n---String---\n"
\ninputchoice:
scanf（"
%d"
&
n）;
getchar（）;
switch（n）
case1:
\n***showstrLength***\n"
strCreate（&
s）;
strLengthis%d\n"
strLength（&
s））;
break;
case2:
\n***showstrCompare***\n"
t）;
k=strCompare（&
s,&
/*（5）---调用串比较函数比较s，t*/
if（k==0）
twostringequal!
\n"
elseif（k<
0）
firststring<
secondstring!
else
firststring>
case3:
\n***showsubString***\n"
inputsubstringpos,len:
%d,%d"
pos,&
len）;
if（subString（&
t,&
s,pos,len））
subStringis%s\n"
t.data）;
posorlenERROR!
case4:
\n***showsubConcat***\n"
if（strConcat（&
x,&
t））/*（6）---调用串连接函数连接s&
t*/
Concatstringis%s"
x.data）;
ConcatERROR!
case0:
exit（0）;
default:
while（n）;
}2、按照要求完成程序exp4_2.c，实现BF&
KMP串的模式匹配算法。
调试及测试数据并给出结果：
•应用BF算法求子串”JING”在主串”BEIJING”中的位置，测试起始位置分别为1和5的情况；
•应用KMP算法求子串”abaabcac”在主串”acabaabaabcacaabc”中的位置，测试起始位置分别为1，10的情况，并写出子串的next[]值；
exp4_2.c部分代码如下：
intindexBf（SqString*s,SqString*t,intpos）;
/*串的模式匹配BF*/
voidgetNext（SqString*t,intnext[]）;
/*KMP求next值*/
intindexKmp（SqString*s,SqString*t,intstart,intnext[]）;
/*串的模式匹配KMP*/
/*
（1）---串的模式匹配BF*/
intindexBf（SqString*s,SqString*t,intpos）
inti=pos-1,j=0;
j<
t->
if（s->
data[i]==t->
data[j]）
j++;
i=i-j+1;
j=0;
if（j>
=t->
returni-t->
length+1;
}/*index_bf*/
/*
（2）---KMP求next值*/
voidgetNext（SqString*t,intnext[]）
inti=0,j=-1;
next[0]=-1;
if（（j==-1）||（t->
data[j]））
next[i]=j;
j=next[j];
}/*getNext*/
/*（3）---KMP模式匹配*/
intindexKmp（SqString*s,SqString*t,intstart,intnext[]）
inti=start-1,j=0;
if（j==-1||s->
}/*index_kmp*/
intn,i,pos,next[MAXSIZE];
SqStrings,t;
1.Index_BF\n"
2.INdex_KMP\n"
\n***showIndex_BF***\n"
s:
t:
inputstartposition:
pos）;
BF:
indexis%d\n"
indexBf（&
t,pos））;
\n***showIndex_KMP***\n"
getNext（&
t,next）;
KMP:
next[]:
i<
t.length;
i++）
%3d"
next[i]+1）;
indexKmp（&
t,pos,next））;
}
【实验小结】
WelcomeTo
Download!
!
欢迎您的下载，资料仅供参考！
升级会员 