实验六 串的应用
一、【实验目的】
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开始的值也相应做出改变。
