数据结构实验报告——KMP算法.doc

《数据结构实验报告——KMP算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、深圳大学实验报告课程名称：数据结构实验项目名称：实验三：Kmp算法学院：计算机与软件学院专业：计算机指导教师：蔡平报告人：郑静宏学号：班级：03实验时间：2010年11月3日实验报告提交时间：2010年11月17日前教务处制一、实验目的与要求：实验目的：1．理解串的特性及与线性表的关系。2．熟悉字符串在顺序存储结构下的基本运算。3．掌握如何用kmp算法实验字符串的模式匹配。实验要求：1．输出界面格式：实验名称：Kmp算法实验人：学号：按要求完成的输入/输出信息完成日期自我评价2．输入数据应提示输入内容与输入格式。3．输出数据要加以说明

2、。4．程序应注意使用注释语句。5．注意程序的健壮性和交互性，养成良好的编程习惯。6．在“网上课程”上提交C源程序。7．交打印稿（或电子稿）的实验报告（完成日期：11月17日）。三．实验内容：(提供每一个实验题目的算法描述、程序代码)[问题描述]选做1：求出子串（模式串）的next，利用kmp算法实验模式与主串的匹配算法。要求：由键盘输入主串及子串的值，（1）输出子串的next值（注：next的初始值为：next[1]=0）。（2）输出子串在主串中首次出现的位置。选做2：实现串的基本运算（求（1）串的长度、（2）串的连接、（3）串的比较

3、）。要求：（1）由键盘输入一个串的值，输出串的长度。（2）由键盘输入两个串的值，输出第一个串+第二个串的值。（3）由键盘输入两个串的值，比较两串是否相等，输出相关提示信息。[算法描述]算法提示：1．生成模式串的next函数2．从第1个字符开始，进行模式串与主串的比较，3．如果出现失配，将模式串的第next[j]位置开始，继续与主串进行比较。[算法实现]（程序代码）#include#includeintgetnext(charT[100]);voidmain(){unsignedshortKMP,a

4、,b;charstr1[100],str2[100];printf("pleaseinputthemainbunch!");scanf("%s",str1);printf("pleaseinputthevice-bunch!");scanf("%s",str2);intnext[100]={getnext(str2)};a=0;b=1;while(a<=strlen(str1)&&b<=strlen(str2)){if(b==0

5、

6、str1[a]==str2[b-1]){++a;++b;}elseb=next[b-1];}if

7、(b>strlen(str2))KMP=a-strlen(str2)+1;elseKMP=0;printf("thekmpnumberis:%dd",KMP);}intgetnext(charT[]){intnext[100];inti,j;i=1;next[1]=0;j=0;while(i

8、

9、T[i]==T[j]){i++;j++;next[i]=j;}elsej=next[j];}printf("thevice-bunch'snumber：");for(j=1;j<=strlen(T

10、);j++)printf("%d",next[j]);returnnext[j];}四、实验结论：（提供实验结果的输出界面拷屏画面。对实验结果自我评价，说明实验是否达到要求，需要哪些改进）实验结论：这个实验是我这学期做的第三个数据结构的实验，在这个实验上，我感觉我有了明显的进步，对C语言和数据结构也有了一定的认识，在编程序过程中，虽有所错误，但几经修改最终还是达到实验的基本目的和要求。五、实验体会：温故而知新，可以知之矣，在这个实验中，我进一步熟悉了大一学的C语言的一些该注意的地方，同时对数据结构中字符串有了一定的认识。对KMP算法，

11、我是靠自己看书的，虽然花了很多时间，但觉得自己的思维还是不错，我没去上课所以自己看书，虽然浪费了很多时间自己去学习，但最后我靠自己看书里的内容，很成功的退出来了，真的有一种超越感，成就感，哈哈。指导教师批阅意见：成绩评定：指导教师签字：年月日备注：