实验4串模式匹配算法的设计与实现.doc

《实验4串模式匹配算法的设计与实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验4：串模式匹配算法的设计与实现实验所需学时数2学时实验目的1)熟悉串类型的实现方法和文本模式匹配方法2)熟悉如何利用模式匹配算法实现一般的文本处理技术实验内容顺序串的模式匹配算法实验所需器材计算机及VC++6.0软件内容要求：1.在串的基本操作中，在主串中查找模式串的模式匹配算法是文本处理中最常用、最重要的操作之一。所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或串匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。2.顺序串的类型定义如下：#defineMaxStrSize256//可根据需

2、要自己定义大小typedefstruct{charch[MaxStrSize];//ch是一个可容纳256个字符的字符数组intlength;}SString;//定义顺序串类型3.测试数据：主串：”ThrougharetrospectivelookatthemathematicsteachingatUSTC,thisarticlesummarizesuniversity’steachingachievementsinpast45years.”子串：teaching输出结果应为：子串teaching出现在主串中的次数为：22次

3、匹配位置分别为：46102；实验结果1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。#include#include#defineMAXL256#defineFALSE0#defineTRUE1typedefunsignedcharSString[MAX

4、L+1];SString&T,char*strs)//生成一个其值等于串常量strs的串T{inti;T[0]=0;//0号单元存储字串长度for(i=0;strs[i];i++)//用数组strs给串T赋值{T[i+1]=strs[i];T[0]=i+1;}}intIndex(SStringS,SStringT,intpos){inti=pos,j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//继续比较后面的字符else{i=i-j+2;j=1;}//指针回退，重新开

5、始匹配}if(j>T[0])returni-T[0];elsereturn0;}intmain(){SStringS,T;intm;charstrs1[MAXL];//建立主串Scharstrs2[MAXL];//建立模式串Tprintf("请输入主串和子串:");printf("主串S:");scanf("%s",strs1);printf("子串T:");scanf("%s",strs2);StrAssign(S,strs1);StrAssign(T,strs2);m=Index(S,T,1);if(m)printf(

6、"S={%s}T={%s}在第%d个位置开始匹配！",strs1,strs2,m);elseprintf("S={%s}T={%s}匹配不成功！",strs1,strs2);return0;}