数据结构-串实验报告.doc

《数据结构-串实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程数据结构实验名称实验三串学号姓名实验日期：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），即要求在主串

2、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(Str

3、ing*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;istr[pos+i]=T.

4、str[i];/*插入*/S->length+=T.length;/*产生新的元素个数*/return1;}}intDelete(String*S,intpos,intlen){inti;if(S->length<=0){printf("数组中未存放字符无元素可删!");return0;}elseif(pos<0

5、

6、len<0

7、

8、pos+len>S->length){printf("参数pos和len出错");return0;}else{for(i=pos+len;i<=S->length-1;i++)S->st

9、r[i-len]=S->str[i];/*依次前移*/S->length-=len;/*产生新的长度值*/return1;}}intSubString(StringS,intpos,intlen,String*T){inti;if(pos<0

10、

11、len<0

12、

13、pos+len>S.length){printf("参数pos和len出错");return0;}else{for(i=0;istr[i]=S.str[pos+i];/*给子串T赋值*/T->length=len;/*给子串T的长度域赋值

14、*/return1;}}(2)BFandKMP.h/*查找子串BF(Brute-Force)操作*/intBFIndex(StringS,intstart,StringT){inti=start,j=0,v;while(i

15、StringT,intnext[]){inti=start,j=0,v;while(i

16、

17、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

18、{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