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

实验报告课程数据结构实验名称实验三 串学号姓名实验日期：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=“I am a student”,T=“student”,V=“teacher”。实验结果：4.19（1）SString.h/*静态存储结构*/typedef structchar strMaxSize;int length; String;void Initiate(String *S) S-length=0;int Insert(String *S, int pos, String T)/*在串S的pos位置插入子串T*/int i;if(pos length + T.length MaxSize)printf(数组空间不足无法插入！);return 0;elsefor(i = S-length-1; i = pos; i-)S-stri+T.length = S-stri;/*为插入做准备*/for(i = 0; i strpos+i = T.stri;/*插入*/S-length += T.length;/*产生新的元素个数*/return 1;int Delete(String *S, int pos, int len)int i;if(S-length = 0)printf(数组中未存放字符无元素可删! n);return 0;else if(pos 0 | len S-length)printf(参数pos和len出错);return 0;elsefor(i = pos+len; i length-1; i+)S-stri-len = S-stri;/*依次前移*/S-length -= len;/*产生新的长度值*/return 1;int SubString(String S, int pos, int len, String *T)int i;if(pos 0 | len S.length)printf(参数pos和len出错);return 0;else for(i = 0; i stri = S.strpos+i;/*给子串T赋值*/T-length = len;/*给子串T的长度域赋值*/return 1; (2) BFandKMP.h /*查找子串BF(Brute-Force)操作*/int BFIndex(String S,int start,String T) int i=start,j=0,v; while(iS.length&jT.length) if(S.stri=T.strj) i+; j+; else i=i-j+1; j=0; if(j=T.length) v=i-T.length; else v=-1; return v;int KMPIndexA(String S,int start,String T,int next) int i=start,j=0,v; while(iS.length&jT.length) if(j=-1|S.stri=T.strj) i+; j+; else j=nextj; if(j=T.length) v=i-T.length; else v=-1; return v;int KMPIndexB(String S,int start,String T,int next) int i=start,j=0,v; while(iS.length&jT.length) if(S.stri=T.strj) i+; j+; else if(j=0)i+; else j=nextj; if(j=T.length) v=i-T.length; else v=-1; return v;void GetNext(String T, int next)/*求子串T的nextj值并存放于数组next中*/ int j=1, k=0; next0=-1; next1=0; while(jT.length) if(T.strj=T.strk) nextj+1=k+1; j+; k+; else if(k=0) nextj+1=0; j+; else k=nextk; /*查找子串BF(Brute-Force)算法累计次数 */int BFIndexC(String S, int start, String T) int i= start, j=0, t=0; while(iS.length & jT.length) if(S.stri=T.strj) i+; j+; else i=i-j+1; j=0; t+; return t;/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作 */int KMPIndexC(String S, int start, String T, int next) int i= start, j=0, t=0; while(iS.length & jT.length) if(S.stri=T.strj) i+; j+; else if(j=0) i+; else j=nextj; t+; return t; （3）测试主函数：#include#define MaxSize 100#includeSString.h#includeBFandKMP.hvoid main(void) String S=cddcdc,6, T=abcde,5; String S1=aaaaaa,6, T1=aaaab,5; String S2=aaaaaaaaaaaad,13, T2=aaaab,5; int next20, count; count=BFIndexC(S,0,T); printf(form S find T Brute-Forces times: %dn,count); GetNext(T, next); count=KMPIndexC(S,0,T,next); printf(form S find T KMPs times: %dn,count); count=BFIndexC(S1,0,T1); printf(form S1 find T1 Brute-Forces times: %dn,count); GetNext(T1, next); count=KMPIndexC(S1,0,T1,next); printf(form S1 find T1 KMPs times: %dn,count); count=BFIndexC(S2,0,T2); printf(form S2 find T2 Brute-Forces times: %dn,count); GetNext(T2, next); count=KMPIndexC(S2,0,T2,next); printf(form S2 find T2 KMPs times: %dn,count); printf(This program is made by 10273206n); 运行结果为：4.20(1) 建立头文件SString.h typedef structchar strMaxSize;int length; String;void Initiate(String *S) S-length=0;int Insert(String *S, int pos, String T)/*在串S的pos位置插入子串T*/int i;if(pos length + T.length MaxSize)printf(数组空间不足无法插入！);return 0;elsefor(i = S-length-1; i = pos; i-)S-stri+T.length = S-stri;/*为插入做准备*/for(i = 0; i strpos+i = T.stri;/*插入*/S-length += T.length;/*产生新的元素个数*/return 1;int Delete(String *S, int pos, int len)int i;if(S-length = 0)printf(数组中未存放字符无元素可删! n);return 0;else if(pos 0 | len S-length)printf(参数pos和len出错);return 0;elsefor(i = pos+len; i length-1; i+)S-stri-len = S-stri;/*依次前移*/S-length -= len;/*产生新的长度值*/return 1;int SubString(String S, int pos, int len, String *T)int i;if(pos 0 | len S.length)printf(参数pos和len出错);return 0;else for(i = 0; i stri = S.strpos+i;/*给子串T赋值*/T-length = len;/*给子串T的长度域赋值*/return 1;(2) 建立头文件BFandKMP.hint BFIndex(String S,int start,String T) int i=start,j=0,v; while(iS.length&jT.length) if(S.stri=T.strj) i+; j+; else i=i-j+1; j=0; if(j=T.length) v=i-T.length; else v=-1; return v;int KMPIndexA(String S,int start,String T,int next) int i=start,j=0,v; while(iS.length&jT.length) if(j=-1|S.stri=T.strj) i+; j+; else j=nextj; if(j=T.length) v=i-T.length; else v=-1; return v;int KMPIndexB(String S,int start,String T,int next) int i=start,j=0,v; while(iS.length&jT.length) if(S.stri=T.strj) i+; j+; else if(j=0)i+; else j=nextj; if(j=T.length) v=i-T.length; else v=-1; return v;void GetNext(String T, int next)/*求子串T的nextj值并存放于数组next中*/ int j=1, k=0; next0=-1; next1=0; while(jT.length) if(T.strj=T.strk) nextj+1=k+1; j+; k+; else if(k=0) nextj+1=0; j+; else k=nextk; /*查找子串BF(Brute-Force)算法累计次数 */int BFIndexC(String S, int start, String T) int i= start, j=0, t=0; while(iS.length & jT.length) if(S.stri=T.strj) i+; j+; else i=i-j+1; j=0; t+; return t;/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作 */int KMPIndexC(String S, int start, String T, int next) int i= start, j=0, t=0; while(iS.length & jT.length) if(S.stri=T.strj) i+; j+; else if(j=0) i+; else j=nextj; t+; return t;（3）主函数#define MaxSize 80#include#include#include SString.h#includeBFandKMP.hint Replace(String S,int start,String T,String V) int i; Initiate(&S); Initiate(&T); I