2022年数据结构串的操作实验报告 .pdf

实验报告课程数据结构实验名称实验三串学号姓名实验日期：串的操作实验目的：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 的代码：/*静态存储结构*/ typedef struct char 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(posS-length) printf(The parameter pos is error!n); return 0; else if(S-length+T.lengthMaxSize) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - printf(The space of the array is not enough!n); return 0; else for(i=S-length-1; i=pos; i-) S-stri+T.length=S-stri;/* 依次后移数据元素*/ for(i=0; istrpos+i=T.stri; /*插入 */ S-length=S-length+T.length; /*产生新的串长度值*/ return 1; /*删除子串操作*/ int Delete(String *S, int pos, int len) /*删除串 S的从 pos 位置开始长度为len 的子串值 */ int i; if(S-length=0) printf(No elements deleting!n); return 0; else if(pos0|lenS-length) printf(The parameters pos and len are not correct!n); return 0; else for(i=pos+len; ilength-1; i+) S-stri-len=S-stri; /*依次前移数据元素*/ S-length=S-length-len; /*产生新的串长度值*/ return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - /*取子串操作*/ int SubString(String S, int pos, int len, String *T) /*取串 S的从 pos位置开始长度为len 的子串值赋给子串T*/ int i; if(pos0|lenS.length) printf(The parameters pos and len are not correct!n); return 0; else for(i=0; istri=S.strpos+i; /*给子串 T 赋值 */ T-length=len; /*给子串 T 的长度域赋值 */ return 1; /*查找子串BF(Brute-Force) 操作 */ int BFIndex(String S, int start, String T) /*查找主串S 从 start 开始的子串T，找到返回T 在 S 中的开始字符下标，否则返回-1*/ 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - /*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/ int KMPIndex(String S, int start, String T, int next) /*查找主串S 从 start 开始的子串T，找到返回T 在 S 中的首字符下标，*/ /*否则返回 -1*/ /*数组 Next 中存放有模式串T 的 nextj 值*/ 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; /*求模式串nextj 值的操作*/ 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) 算法累计次数*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - int BFIndexC(String S, int start, String T) /*查找主串S 从 start 开始的子串T，找到返回T 在 S 中的开始字符下标，否则返回-1*/ 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) /*查找主串S 从 start 开始的子串T，找到返回T 在 S 中的首字符下标，*/ /*否则返回 -1*/ /*数组 Next 中存放有模式串T 的 nextj 值*/ 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; 测试主函数：#include #define MaxSize 100 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - #includeSString.h #includeBFandKMP.h void main(void) String S=cddcdc,6, T=abcde,5; String S1=aaaaaaaa,8, T1=aaaab,5; String S2=aaaaaaaaaaaaaaaaad,18, T2=aaaab,5; int next20, count; count=BFIndexC(S,0,T); printf(从 S中查找 T 的 Brute-Force 算法比较次数：%dn,count); GetNext(T, next); count=KMPIndexC(S,0,T,next); printf(从 S中查找 T 的 KMP 算法比较次数：%dn,count); count=BFIndexC(S1,0,T1); printf(从 S1 中查找 T1 的 Brute-Force 算法比较次数：%dn,count); GetNext(T1, next); count=KMPIndexC(S1,0,T1,next); printf(从 S1中查找 T1 的 KMP 算法比较次数：%dn,count); count=BFIndexC(S2,0,T2); printf(从 S2 中查找 T2 的 Brute-Force 算法比较次数：%dn,count); GetNext(T2, next); count=KMPIndexC(S2,0,T2,next); printf(从 S2中查找 T2 的 KMP 算法比较次数：%dn,count); 4-20 的部分代码：Replace 函数：/* 从主串 S 中查找字串T，若存在，并用串V 替换串 T 并返回 1，否则，返回0*/ int Replace(String S,int start,String T,String V) int i,v; Initiate(&S); Initiate(&T); Initiate(&V); for(i=0; istrlen(S.str); i+) S.length=S.length+1; for(i=0; istrlen(T.str); i+) T.length=T.length+1; for(i=0; istrlen(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; iS.length; i+) printf(%c, S.stri); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - return v=1; else printf(主串 S 中不存在串Tn); return v=0; 测试主函数：#define MaxSize 80 #include #include #include SString.h int main(void) int v; String S=I am a student., T=student, V=teacher; v=Replace(S,0,T,V); printf(返回 %dn,v); 总结与思考KMP 算法的比较次数比Brute-Force 算法的少。 KMP 算法的主要特点是：消除了Brute-Force 算法的主串指针在相当多个字符比较相等后，只要有一个字符不相等便回退，也就是回溯的缺点。所以从两种算法的原理和程序运行的结果来看， KMP 算法比 Brute-Force 算法的效率更高。谢谢大家下载,本文档下载后可根据实际情况进行编辑修改.再次谢谢大家下载 .翱翔在知识的海洋吧. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -