当前位置: 首页> 汽车> 新车 > 福州seo技术培训_物流公司网站怎么做_抖音代运营公司_网络营销品牌推广公司

福州seo技术培训_物流公司网站怎么做_抖音代运营公司_网络营销品牌推广公司

时间:2025/7/10 12:38:14来源:https://blog.csdn.net/2301_76979886/article/details/142853497 浏览次数: 0次
福州seo技术培训_物流公司网站怎么做_抖音代运营公司_网络营销品牌推广公司

实验六 串的应用

一、【实验目的】
1、掌握串的顺序存储结构
2、掌握顺序串的基本操作方法(插入、删除等)。
3、掌握串的链式存储结构。
4、掌握链式串的几种基本操作(插入、删除等)。
5、掌握Brute-Force算法

二、【实验内容】
1、编写函数BFIndex(String S, int start, String T),实现Brute-Force算法,其中S为主串,start为子串在主串中的查找位置,T为子串。程序可参考书本例子。(鼓励使用KMP算法)。

2、设串采用静态数组存储结构,编写函数实现串的替换Replace(S,start,T,V),即要求在主串S中,从位置start开始查找是否存在子串T。若主串S中存在子串T,则用子串V替换子串T,且函数返回1;若主串S中不存在子串T,则函数返回0。并要求设计主函数进行测试。

三、【实验源代码】

//SString.h#include<stdio.h>
#define MaxSize 100typedef struct
{char str[MaxSize];int length;} String;int Insert(String *S,int pos,String T){int i;if(pos<0){printf("参数pos出错!");return 0;}else if(S->length +T.length>MaxSize){printf("数组空间不足无法插入!");return 0; }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;return 1; }}int Delete(String *S,int pos,int len){int i;if(S->length<=0){printf("数组中未存放字符无元素可删!");return 0; }else if(pos<0||len<0||pos+len>S->length ){printf("参数pos和len出错");return 0; }else{for(i=pos+len;i<=S->length-1;i++){S->str[i-len]=S->str[i]; /*依次前移*/}S->length-=len; /*产生新的长度值*/ return 1;}}
//主程序
#include<stdio.h>
#include<string.h>
#define Maxlength 100
#include"SString.h"int next[100];void get_next(String t,int next[])
{int i=0;int j=-1;next[0]=-1;while(i<t.length){if(j==-1||t.str[i]==t.str[j]){i++;j++;next[i]=j;}		else{j=next[j];}}
}int Index_KMP(String s,int pos,String t)
{int i=pos;int j=0;while(i<s.length&&j<t.length){if(j==-1||s.str[i]==t.str[j]){i++;j++;}else j=next[j];}if(j>=t.length){return i-t.length;}else{return 0;}
}int Replace(String *s,int start,String t,String v)
{int index;index=Index_KMP(*s,start,t);//if(index==0){return 0;}else{if(Delete(s,index,t.length)==0)//strlen(t.str)?{return 0;}else{if(Insert(s,index,v)==0){return 0;}else{return 1;}}}}void main(void){String myString1,myString2,myString3;int i,start=0;printf("请输入主串myString1:");scanf("%s",myString1.str);printf("请输入子串myString2:");scanf("%s",myString2.str);printf("请输入子串myString3:");scanf("%s",myString3.str);myString1.length=strlen(myString1.str);myString2.length=strlen(myString2.str);myString3.length=strlen(myString3.str);get_next(myString2,next);if(Replace(&myString1,start,myString2,myString3)==0){printf("不成功"); }else{for(i=0;i<myString1.length;i++)printf("%c",myString1.str[i]);}}

四、【实验结果】
在这里插入图片描述
在这里插入图片描述

五、【实验心得】
1、本章的难点在于kmp函数,相比于朴素的模式匹配算法,kmp避免了主串比较位置(变量i)的回溯,通过让子串右滑(重新确定子串的比较位置),提高算法效率。
想理解kmp算法,先要知道j的值只和子串有关,分三种情况:①当j=1时(子串在位置1失配),next【j】=0(然后再i++,j++,让主串和子串的比较位置进行比较);②当出现“以t1字符开头的字符串”与“以tk-1字符结尾的的字符串”相同时,next【j】=k(k为相同的字符串的长度);③其他情况时,j=1,注意,kmp算法的if判断条件中增加了j==0的判断,因此此时的j需要与上一次的i相等才能进入if语句进行i++j++,进行下一个位置的判断;
接着,需要一个算法求子串next【j】的值,课本上,先规定next【1】=0,i从1开始,j从0开始,j和i一旦相同就i++j++比较下一位,一旦不同则j值回溯(除第一位外,回溯是先回溯到第一位比较是否与i一样,不一样再回溯到0),这样就能得到子串每一位相应的next【j】的值,将其存入数组next中,kmp算法就完整了。

2、课本主串和子串都是从1开始存储,所以if语句的判断条件是j==0,本次提交的代码中字符是从0开始存储,所以两个函数的判断条件都要改成j==-1,i和j开始的值也相应做出改变。

关键字:福州seo技术培训_物流公司网站怎么做_抖音代运营公司_网络营销品牌推广公司

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: