数据结构实验报告串Word文档下载推荐.docx
- 文档编号:5179254
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:14
- 大小:16.97KB
数据结构实验报告串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!
!
欢迎您的下载,资料仅供参考!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告