还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
常熟理工学院《数据绑屿算涉实验指导与报告书学年第学期2022-2022_1—专业__________________物联网工程^佥名称_________________SSfiS实触点N6-210指导教师聂盼红计新科学与工程学院2022ifj=t-lengthreturn i-t-length+1;elsereturn0;}/*index_kmp*/int mainintn,i,pos,next[MAXSIZE];SqString s,t;dogetcharQ;switchn easel:strCreates;strCreatet;break;case2:strCreates;strCreatet;getNextt,next;fori=0;it.length;i++break;caseO:exitO;default:break;whilen;return0;【实验小结】通过这次实验,我在其中遇到了不少问题比如掌握了串的存储表示及基本操作,认识到事情的解决有不少方式比如求的值就算法以及算法两种算法时间复杂度一个是线性next BFKMP的一个是非线性的,运行起的效率就会明显不一样所以认识问题要全面,就觉问题要多考虑并且还了解了串的应用,对这种结构有了更深一步的认识实验四串与模式匹配【实验目的】、掌握串的存储表示及基本操作;
1、掌握串的两种模式匹配算法和2BF KMPO、了解串的应用3【实验学时】学时2【实验预习】回答以下问题、串和子串的定义1串串是由零个或者多个任意字符组成的有限序列子串串中任意连续字符组成的子序称为该串的字串、串的模式匹配2串的模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配假设是给定的子串,是待查找的字符串,要求从中找出与相同的所有子串,这个问题成为模式匹配问题称为模式,称为目标如果中存在一个或者多个模式为的子串,就给出该子串在中的位置,称为匹配成功;否则匹配失败【实1验内容和要求】/、按照要求完成程序实现串的相关操作调试并运行如下测试数据给出运行结果1exp4_
1.c,
④求的串长;“This isa boy”input choice:1***show strLength***input string:This isa boystrLength is13
④比较和;「表示空格abcTT3”“abcde“***show strCompare***input stringabc3input string:abcdefirst stringsecond string!
④比较和;english”“student***show strCompare***input stringenglish inputstring:student firststringsecondstring!
④比较和;abc”“abc“***show strCompare***input string:abc input string:abc twostringequal!
④截取串,,起始2,长度;White”2input choice:3***show subString***input string:white inputsubstring pos,len:2,2subString ishi
④截取串,训,起始长度;hite”1,7***show subString***input stringwhite inputsubstringpos,len1,7pos orlen ERROR!
④截取串,,起始长度;Mhite”6,2***show subString***input string:white inputsubstringpos,len:6,2pos orlen ERROR!
④连接串”和;asddffgh”12344”***show subConcat***input string:asddffgh inputstring:12344Concat stringis asddffghl2344String实验代码#includestdio.h#includestring.h#define MAXSIZE100#define ERROR0#define OK1/*串的定长顺序存储表示*/typedef structchar data[MAXSIZE];int length;}SqString;int strlnitSqString*s;/*初始化串*/int strCreateSqString*s;/*生成一个串*/int strLengthSqString*s;/*求串的长度*/int strCompareSqString*s1,SqString*s2;/*两个串的比较*/int subStringSqString*sub,SqString*s,int posjntlen;/*求子串*/int strConcatSqString*t,SqString*s1,SqString*s2;/*两个串的连接*//*初始化串*/int strlnitSqString*s s-length=0;return OK;}/*strlnit*//*生成一个串*/int strCreateSqString*sgetss-data;s-length=strlens-data;return OK;}/*strCreate7…求串的长度*//*1int strLengthSqString*s{return s-length;}/*strLength*/---两个串的比较,返回返回返回/*2S1S20,s1vs2vO,s1==s207int strCompareSqString*s1,SqString*s2int i;fori=0;is1-lengthis2-length;i++ifs1-data[i]!=s2-data[i]return s1-data[i]-s2-data[i];return s1-length-s2-length;}/*strCompare*/—求子串,为返回的子串,为子串的起始位置,为子串的长度*//*3sub poslen intsubStringSqString*sub,SqString*s,int pos,int lenint i;ifpos1||poss-length||len0||lens-length-pos+1return ERROR;sub-length=0;fori=0;ivlen;i++{sub-data[i]=s-data[i+pos-1];sub-length++;return OK;}/*subString*/―两个串联接,连接在后,连接后的结果串放在中*//*4s2s1tint strConcatSqString*t,SqString*s1,SqString*s2int i=0,j=0;whileis1-length{;t-data[i]=s1-data[i];i++}whilejs2-lengtht-data[i++]=s2-data[j++];t-length=s1-length+s2-length;return OK;}/*strConcat*/int mainintn,k,pos,len;SqString s,t,x;dogetchar;switchn strCreates;break;strCreates;strCreatet;—调用串比较函数比较k=strCompares,t;/*5s,t*/ifk==Oelse ifk0elsebreak;strCreates;ifsubStringt,s,pos,lenelse break;strCreates;strCreatet;一调用串联接函数连接ifstrConcatx,s,t/*6st*/elsebreak;caseO:exitO;default:break;whilen;return0;、按照要求完成程序实现串的模式匹配算法调试及测试数据2exp4_
2.c,BFKMP并给出结果:
④应用算法求子串在主串”曰中的位置,测试起始位置分别为和BF JING”B JING”15的情况;***show Index-BF***s:input string:BEIJIXG t:inputstring:JING inputstart position:1BF:index is4***show Index_BF***s:input string:BEIJIXG t:inputstring:JINGinput startposition:5BF:index is0
④应用算法求子串”在主串“中的位置,测试起始KMP abaabcacvacabaabaabcacaabcv位置分别为的情况,并写出子串的口值;1,10next***show Index_KMP***s:input string:acabaabaabcacaabct:input stringabaabcacinput startposition:1KMP:next[]:-10011201index is6***show Index_KMP***s:input string:acabaabaabcacaabc t:inputstring:abaabcacinput startposition:10KMP:next[]:-10011201index is0部份代码如下exp4_
2.c#includestdio.h#includestring.h#define MAXSIZE100#define ERROR0#define OK1/*串的定长顺序存储表示*/typedef structchar data[MAXSIZE];int length;}SqString;int strCreateSqString*s;/*串的模式匹配int indexBfSqString*s,SqString*t,int pos;BF*/求值*/void getNextSqString*t,int next[];/*KMP next;/*串的模式匹配int indexKmpSqString*s,SqString*t,int start,int nextKMPV/*生成一个串*/int strCreateSqString*s getss-data;s-length=strlens-data;return OK;}/*strCreate7串的模式匹配/*1-BF7int indexBfSqString*s,SqString*t,int posinti=pos-1,j=0;;;whileis-length jt-length ifs-data[i]==t-data[j]{i++j++}else{;i=i-j+1j=0;}ifj=t-lengthreturn i-t-length+1;elsereturn0;}/*index_bf*/求值*//*2—KMP nextvoid getNextSqString*t,int next[]int i=0,j=-1;next
[0]=-1;whileit-length{;;ifj==-1||t-data[i]==t-data[j]{i++j++next[i]=j;elsej=next[j];}}/*getNext*/模式匹配*//*3—KMPint indexKmpSqString*s,SqString*t,int start,int next[]inti=start-1,j=0;whileis-lengthjt-length;;ifj==-1||s-data[i]==t-data[j]{i++j++elsej=next[j];。