数据结构综合实验报告必威体育精装版.docVIP

综合性、设计性实验报告 姓名 _全威 _ 学号_201408003201_ 专业 软件工程 班级2014级软件X班 实验课程名称 数据结构 指导教师及职称 黎明 副高 开课学期 2015至 2016学年 第一学期 上课时间 2015年 11 月 湖南科技学院教务处编 实验设计方案 实验名称：串的操作实验时间：2015-11-4 ~ 2015-11-18小组合作：是○否●成绩：教师评语： 1、实验目的： 熟练掌握串的概念，熟知串的基本操作，掌握BM算法求模式匹配的基本过程，掌握在模式匹配中求next和nextval的意义和重要性，完全掌握KMP算法的应用，能够在KMP算法基础上进行改进。2、实验设备及材料： 联想电脑一体机，操作系统MacOSX，开发平台 XCode3、实验内容： 问题描述：第一课时完成简单模式匹配算法求模式串t在主串s的位置,第二课时完成对模式串求next数组值和nextval,第三课时完成KMP算法求t在s中位置,第四课时完成修正后的KMP算法4、实验方法步骤及注意事项：（请自行填写，不得雷同，各位同学的实验报告应有所区别，不要照抄！如果表格的长度不够，可以自行拉伸！） ①实验步骤： ②设计思路： 5．实验数据处理方法： ① 数据输入 ②结果输出  6．程序代码： #includestdio.h #includestring.h #includemalloc.h #define MaxSize 100 typedef struct { char data[MaxSize]; //定义可容纳MaxSize个字符的空间 int length; //标记当前实际串长 }SqString; void StrAssign(SqString str,char cstr[]){ //由串常量cstr创建串str int i; for(i=0;cstr[i]!=\0;i++) str.data[i]=cstr[i]; str.length=i; } void DispStr(SqString s){ //输出串s的所有元素 int i; if(s.length0){ for(i=0;is.length;i++) printf(%c,s.data[i]); printf(\n); } } int Index(SqString s,SqString t){ //简单匹配算法 int i=0,j=0,k; while(is.length jt.length){ if(s.data[i]==t.data[j]){ //继续匹配下一个字符 i++; j++; }else{ //主串、子串指针回溯重新开始下一次匹配 i=i-j+1; j=0; } } if(j=t.length) k=i-t.length; //返回匹配的第一个字符的下标 else k=-1; //模式匹配不成功 return k; } void GetNext(SqString t,int next[]){ //由模式串t求出next值 int j,k; j=0; k=-1;next[0]=-1; while(jt.length-1){ if(k==-1 || t.data[j]==t.data[k]){ j++; k++; next[j]=k; }else k=next[k]; } } void GetNextval(SqString t,int nextval[]){ //由模式串t求出nextval值 int j=0,k=-1; nextval[0]=-1; while(jt.length){ if(k==-1 || t.data[j]==t.data[k]){ j++; k++; if(t.data[j]!=t.data[k])