实验报告课程数据结构实验名称实验三串学号姓名实验日期:实验三串实验目的:1.熟悉串类型的实现
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
，了解简单文字处理的设计方法;2.熟悉C语言的字符和把字符串处理的原理和方法;3.熟悉并掌握模式匹配算法。实验原理:顺序存储结构下的关于字符串操作的基本算法。模式匹配算法BF、KMP实验内容:4-19.在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。4-20.设串采用静态数组存储结构，编写函数实现串的替换Replace(S，start，T，V)，即要求在主串S中，从位置start开始查找是否存在字串T。若主串S中存在子串T，则用子串V替换子串T，且函数返回1;若主串S中不存在子串T，则函数返回0;并要求设计Iamastudent”,T=“student”,V=“teacher”。主函数进行测试。一个测试例子为:S=“程序代码:4-19的代码:/*静态存储结构*/typedefstruct{charstr[MaxSize];intlength;}String;/*初始化操作*/voidInitiate(String*S){S->length=0;}/*插入子串操作*/intInsert(String*S,intpos,StringT)/*在串S的pos位置插入子串T*/{inti;if(pos<0||pos>S->length){printf("Theparameterposiserror!\n");return0;}elseif(S->lengthT.length>MaxSize){printf("Thespaceofthearrayisnotenough!\n");return0;}else{for(i=S->length-1;i>=pos;i--)S->str[iT.length]=S->str[i];/*依次后移数据元素*/for(i=0;i
str[posi]=T.str[i];/*插入*/S->length=S->lengthT.length;/*产生新的串长度值*/return1;}}/*删除子串操作*/intDelete(String*S,intpos,intlen)/*删除串S的从pos位置开始长度为len的子串值*/{inti;if(S->length<=0){printf("Noelementsdeleting!\n");return0;}elseif(pos<0||len<0||poslen>S->length){printf("Theparametersposandlenarenotcorrect!\n");return0;}else{for(i=poslen;i<=S->length-1;i)S->str[i-len]=S->str[i];/*依次前移数据元素*/S->length=S->length-len;/*产生新的串长度值*/return1;}}/*取子串操作*/intSubString(StringS,intpos,intlen,String*T)/*取串S的从pos位置开始长度为len的子串值赋给子串T*/{inti;if(pos<0||len<0||poslen>S.length){printf("Theparametersposandlenarenotcorrect!\n");return0;}else{for(i=0;i<=len;i)T->str[i]=S.str[posi];/*给子串T赋值*/T->length=len;/*给子串T的长度域赋值*/return1;}}/*查找子串BF(Brute-Force)操作*/intBFIndex(StringS,intstart,StringT)/*查找主串S从start开始的子串T，找到返回T在S中的开始字符下标，否则返回-1*/{inti=start,j=0,v;while(i#defineMaxSize100#include"SString.h"#include"BFandKMP.h"voidmain(void){StringS={{"cddcdc"},6},T={{"abcde"},5};StringS1={{"aaaaaaaa"},8},T1={{"aaaab"},5};StringS2={{"aaaaaaaaaaaaaaaaad"},18},T2={{"aaaab"},5};intnext[20],count;count=BFIndexC(S,0,T);printf("从S中查找T的Brute-Force算法比较次数:%d\n",count);GetNext(T,next);count=KMPIndexC(S,0,T,next);printf("从S中查找T的KMP算法比较次数:%d\n",count);count=BFIndexC(S1,0,T1);printf("从S1中查找T1的Brute-Force算法比较次数:%d\n",count);GetNext(T1,next);count=KMPIndexC(S1,0,T1,next);printf("从S1中查找T1的KMP算法比较次数:%d\n",count);count=BFIndexC(S2,0,T2);printf("从S2中查找T2的Brute-Force算法比较次数:%d\n",count);GetNext(T2,next);count=KMPIndexC(S2,0,T2,next);printf("从S2中查找T2的KMP算法比较次数:%d\n",count);}4-20的部分代码:Replace函数:/*从主串S中查找字串T，若存在，并用串V替换串T并返回1，否则，返回0*/intReplace(StringS,intstart,StringT,StringV){inti,v;Initiate(&S);Initiate(&T);Initiate(&V);for(i=0;i#include#include"SString.h"intmain(void){intv;StringS={"Iamastudent."},T={"student"},V={"teacher"};v=Replace(S,0,T,V);printf("返回%d\n",v);}实验结果:4-19.程序调式结果:4-20.程序调式结果:总结与思考KMP算法的比较次数比Brute-Force算法的少。KMP算法的主要特点是:消除了Brute-Force算法的主串指针在相当多个字符比较相等后，只要有一个字符不相等便回退，也就是回溯的缺点。所以从两种算法的原理和程序运行的结果来看，KMP算法比Brute-Force算法的效率更高。
浙公网安备 33021202002483