数据结构-实验报告KMP算法.doc
文本预览下载声明
深 圳 大 学 实 验 报 告
课程名称： 数据结构
实验项目名称： 实验三：Kmp算法
学院： 计算机与软件学院
专业： 计算机
指导教师： 蔡平
报告人： 郑静宏 学号： 班级： 03
实验时间： 2010年11
实验报告提交时间： 2010年11月1
教务处制
一、实验目的与要求：
实验目的：
1．理解串的特性及与线性表的关系。
2．熟悉字符串在顺序存储结构下的基本运算。
3．掌握如何用kmp算法实验字符串的模式匹配。
实验要求：
1．输出界面格式：
实验名称：Kmp算法 实验人： 学号：
按要求完成的输入/输出信息
完成日期 自我评价
2．输入数据应提示输入内容与输入格式。
输出数据要加以说明。
4．程序应注意使用注释语句。
5．注意程序的健壮性和交互性，养成良好的编程习惯。
6．在“网上课程”上提交C源程序。
7．交打印稿（或电子稿）的实验报告（完成日期：11月17日
三．实验内容：(提供每一个实验题目的算法描述、程序代码)
[问题描述]
选做1：
求出子串（模式串）的next，利用kmp算法实验模式与主串的匹配算法。
要求：由键盘输入主串及子串的值，（1）输出子串的next值（注：next的初始值为：next[1]=0）。（2）输出子串在主串中首次出现的位置。
选做2：
实现串的基本运算（求（1）串的长度、（2）串的连接、（3）串的比较）。
要求：（1）由键盘输入一个串的值，输出串的长度。
（2）由键盘输入两个串的值，输出第一个串+第二个串的值。
（3）由键盘输入两个串的值，比较两串是否相等，输出相关提示信息。
[算法描述]
算法提示：
1．生成模式串的next函数
2．从第1个字符开始，进行模式串与主串的比较，
3．如果出现失配，将模式串的第next[j]位置开始，继续与主串进行比较。
[算法实现]（程序代码）
#includestdio.h
#includestring.h
int getnext(char T[100]);
void main()
{
unsigned short KMP,a,b;
char str1[100],str2[100];
printf(please input the main bunch!\n);
scanf(%s,str1);
printf(please input the vice-bunch!\n);
scanf(%s,str2);
int next[100]={getnext(str2)};
a=0;
b=1;
while(a=strlen(str1) b=strlen(str2))
{
if(b==0||str1[a]==str2[b-1])
{
++a;
++b;
}
else b=next[b-1];
}
if(bstrlen(str2))
KMP=a-strlen(str2)+1;
else
KMP=0;
printf(the kmp number is:%d\nd,KMP);
}
int getnext(char T[])
{
int next[100];
int i,j;
i=1;
next[1]=0;
j=0;
while(istrlen(T))
{
if(j==0||T[i]==T[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
printf(the vice-bunch\s number：\n);
for(j=1;j=strlen(T);j++)
printf(%d,next[j]);
return next[j];
}
四、实验结论：（提供实验结果的输出界面拷屏画面。对实验结果自我评价，说明实验是否达到要求，需要哪些改进）
实验结论：这个实验是我这学期做的第三个数据结构的实验，在这个实验上，我感觉我有了明显的进步，对C语言和数据结构也有了一定的认识，在编程序过程中，虽有所错误，但几经修改最终还是达到实验的基本目的和要求。
五、实验体会：
温故而知新，可以知之矣，在这个实验中，我进一步熟悉了大一学的C语言的一些该注意的地方，同
显示全部