数据结构-串实验报告

实验报告 化学实验报告单总流体力学实验报告观察种子结构实验报告观察种子结构实验报告单观察种子的结构实验报告单 课程数据结构实验名称实验三串学号姓名实验日期：2011/10/27实验三串实验目的：1.熟悉串类型的实现方法，了解简单文字处理的设计方法；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；并要求设计主函数进行测试。一个测试例子为：S=“Iamastudent”,T=“student”,V=“teacher”。实验结果：4.19（1）SString.h/*静态存储结构*/typedefstruct{ charstr[MaxSize]; intlength;}String;voidInitiate(String*S){S->length=0;}intInsert(String*S,intpos,StringT)/*在串S的pos位置插入子串T*/{ inti; if(pos<0) { printf("参数pos出错！"); return0; } elseif(S->length+T.length>MaxSize) { printf("数组空间不足无法插入！"); return0; } else { for(i=S->length-1;i>=pos;i--) S->str[i+T.length]=S->str[i]; /*为插入做准备*/ for(i=0;i<T.length;i++) S->str[pos+i]=T.str[i]; /*插入*/ S->length+=T.length; /*产生新的元素个数*/ return1; }}intDelete(String*S,intpos,intlen){ inti; if(S->length<=0) { printf("数组中未存放字符无元素可删!\n"); return0; } elseif(pos<0||len<0||pos+len>S->length) { printf("参数pos和len出错"); return0; } else { for(i=pos+len;i<=S->length-1;i++) S->str[i-len]=S->str[i]; /*依次前移*/ S->length-=len; /*产生新的长度值*/ return1; }}intSubString(StringS,intpos,intlen,String*T){ inti; if(pos<0||len<0||pos+len>S.length) { printf("参数pos和len出错"); return0; } else { for(i=0;i<len;i++) T->str[i]=S.str[pos+i]; /*给子串T赋值*/ T->length=len; /*给子串T的长度域赋值*/ return1; }}(2)BFandKMP.h/*查找子串BF(Brute-Force)操作*/intBFIndex(StringS,intstart,StringT){inti=start,j=0,v;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j==T.length)v=i-T.length;elsev=-1;returnv;}intKMPIndexA(StringS,intstart,StringT,intnext[]){inti=start,j=0,v;while(i<S.length&&j<T.length){if(j==-1||S.str[i]==T.str[j]){i++;j++;}elsej=next[j];}if(j==T.length)v=i-T.length;elsev=-1;returnv;}intKMPIndexB(StringS,intstart,StringT,intnext[]){inti=start,j=0,v;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}elseif(j==0)i++;elsej=next[j];}if(j==T.length)v=i-T.length;elsev=-1;returnv;}voidGetNext(StringT,intnext[])/*求子串T的next[j]值并存放于数组next中*/{intj=1,k=0;next[0]=-1;next[1]=0;while(j<T.length){if(T.str[j]=T.str[k]){next[j+1]=k+1;j++;k++;}elseif(k==0){next[j+1]=0;j++;}elsek=next[k];}}/*查找子串BF(Brute-Force)算法累计次数*/intBFIndexC(StringS,intstart,StringT){inti=start,j=0,t=0;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else{i=i-j+1;j=0;}t++;}returnt;}/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/intKMPIndexC(StringS,intstart,StringT,intnext[]){inti=start,j=0,t=0;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}elseif(j==0)i++;elsej=next[j]; t++; }returnt;}（3）测试主函数：#include<stdio.h>#defineMaxSize100#include"SString.h"#include"BFandKMP.h"voidmain(void){StringS={{"cddcdc"},6},T={{"abcde"},5};StringS1={{"aaaaaa"},6},T1={{"aaaab"},5};StringS2={{"aaaaaaaaaaaad"},13},T2={{"aaaab"},5};intnext[20],count;count=BFIndexC(S,0,T);printf("formSfindTBrute-Force'stimes:%d\n",count);GetNext(T,next);count=KMPIndexC(S,0,T,next);printf("formSfindTKMP'stimes:%d\n",count);count=BFIndexC(S1,0,T1);printf("formS1findT1Brute-Force'stimes:%d\n",count);GetNext(T1,next);count=KMPIndexC(S1,0,T1,next);printf("formS1findT1KMP'stimes:%d\n",count);count=BFIndexC(S2,0,T2);printf("formS2findT2Brute-Force'stimes:%d\n",count);GetNext(T2,next);count=KMPIndexC(S2,0,T2,next);printf("formS2findT2KMP'stimes:%d\n",count);printf("Thisprogramismadeby10273206\n");}运行结果为：4.20(1)建立头文件SString.htypedefstruct{ charstr[MaxSize]; intlength;}String;voidInitiate(String*S){S->length=0;}intInsert(String*S,intpos,StringT)/*在串S的pos位置插入子串T*/{ inti; if(pos<0) { printf("参数pos出错！"); return0; } elseif(S->length+T.length>MaxSize) { printf("数组空间不足无法插入！"); return0; } else { for(i=S->length-1;i>=pos;i--) S->str[i+T.length]=S->str[i]; /*为插入做准备*/ for(i=0;i<T.length;i++) S->str[pos+i]=T.str[i]; /*插入*/ S->length+=T.length; /*产生新的元素个数*/ return1; }}intDelete(String*S,intpos,intlen){ inti; if(S->length<=0) { printf("数组中未存放字符无元素可删!\n"); return0; } elseif(pos<0||len<0||pos+len>S->length) { printf("参数pos和len出错"); return0; } else { for(i=pos+len;i<=S->length-1;i++) S->str[i-len]=S->str[i]; /*依次前移*/ S->length-=len; /*产生新的长度值*/ return1; }}intSubString(StringS,intpos,intlen,String*T){ inti; if(pos<0||len<0||pos+len>S.length) { printf("参数pos和len出错"); return0; } else { for(i=0;i<len;i++) T->str[i]=S.str[pos+i]; /*给子串T赋值*/ T->length=len; /*给子串T的长度域赋值*/ return1; }}(2)建立头文件BFandKMP.hintBFIndex(StringS,intstart,StringT){inti=start,j=0,v;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j==T.length)v=i-T.length;elsev=-1;returnv;}intKMPIndexA(StringS,intstart,StringT,intnext[]){inti=start,j=0,v;while(i<S.length&&j<T.length){if(j==-1||S.str[i]==T.str[j]){i++;j++;}elsej=next[j];}if(j==T.length)v=i-T.length;elsev=-1;returnv;}intKMPIndexB(StringS,intstart,StringT,intnext[]){inti=start,j=0,v;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}elseif(j==0)i++;elsej=next[j];}if(j==T.length)v=i-T.length;elsev=-1;returnv;}voidGetNext(StringT,intnext[])/*求子串T的next[j]值并存放于数组next中*/{intj=1,k=0;next[0]=-1;next[1]=0;while(j<T.length){if(T.str[j]=T.str[k]){next[j+1]=k+1;j++;k++;}elseif(k==0){next[j+1]=0;j++;}elsek=next[k];}}/*查找子串BF(Brute-Force)算法累计次数*/intBFIndexC(StringS,intstart,StringT){inti=start,j=0,t=0;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else{i=i-j+1;j=0;}t++;}returnt;}/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/intKMPIndexC(StringS,intstart,StringT,intnext[]){inti=start,j=0,t=0;while(i<S.length&&j<T.length){if(S.str[i]==T.str[j]){i++;j++;}elseif(j==0)i++;elsej=next[j]; t++; }returnt;}（3）主函数#defineMaxSize80#include<stdio.h>#include<string.h>#include"SString.h"#include"BFandKMP.h"intReplace(StringS,intstart,StringT,StringV){inti;Initiate(&S);Initiate(&T);Initiate(&V);for(i=0;i<strlen(S.str);i++)S.length=S.length+1;for(i=0;i<strlen(T.str);i++)T.length=T.length+1;for(i=0;i<strlen(V.str);i++)V.length=V.length+1;i=BFIndex(S,0,T);if(i!=-1){if(Delete(&S,i,T.length))Insert(&S,i,V);for(i=0;i<S.length;i++)printf("%c",S.str[i]);printf("\n");return1;}else {printf("error!\n");return0;}}intmain(void){intv;StringS={"Iamastudent."},T={"student"},V={"teacher"};v=Replace(S,0,T,V);printf("Thisprogramismadeby10273206\n");}运行结果为： 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 与思考KMP算法的主要特点是：消除了Brute-Force算法的主串指针在相当多个字符比较相等后，只要有一个字符不相等便回退，也就是回溯的缺点。所以从两种算法的原理和程序运行的结果来看，KMP算法比Brute-Force算法的效率更高、比较次数更少。