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(\ return 0; } else {
for(i=pos+len; i<=S->length-1; i++) S->str[i-len]=S->str[i]; S->length=S->length-len; return 1; } }
int SubString(String S, int pos, int len, String *T) {
int i;
if(pos<0||len<0||pos+len>S.length) {
printf(\ return 0; } else {
for(i=0; i<=len; i++)
T->str[i]=S.str[pos+i]; T->length=len;
return 1; } }
int BFIndex(String S, int start, String T) {
int i= start, j=0, v;
while(i if(S.str[i]==T.str[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j==T.length) v=i-T.length; else v=-1; return v; } void GetNext(String T, int next[]) { int j=1, k=0; next[0]=-1; next[1]=0; while(j if(T.str[j]==T.str[k]) { next[j+1]=k+1; j++; k++; } else if(k==0) { next[j+1]=0; j++; } else k=next[k]; } } int KMPIndex(String S, int start, String T, int next[]) { int i= start, j=0, v; while(i if(j==-1||S.str[i]==T.str[j]) { i++; j++; } else j=next[j]; } if(j==T.length) v=i-T.length; else v=-1; return v; } /*RepFun.c*/ #include int Replace(String *S,int start,String T,String V) { int i,a; if(S->length Delete(S,a,T.length); Insert(S,a,V); return 1; } else return 0; } void main(void) { int start=0,b; String S={{\ b=Replace(&S,start,T,V); printf(\ printf(\} 实验结果： 4-19 4-20 总结与思考 本次试验对串类型的实现方法有所了解，同时也对简单文字处理的设计方法有了初步的了解， 熟悉C语言的字符和把字符串处理的原理和方法，C语言把字符串字面量作为字符数组来处理。当C语言编译器在程序中遇到长度为n的字符串字面量时，它会为字符串字面量分配长度为n+1的内存空间，在末尾增加一个额外的字符——空字符(\\0)。 了解实践了模式匹配算法。 BF算法的基本思想是： 从目标串T的起始比较位置pos开始（在后面的案例中，我们默认pos = 0），和模式串P的第一个字符比较之，若匹配，则继续逐个比较后继字符，否则从串T的下一个字符起再重新和串P的字符比较之。依此类推，直至串P中的每个字符依次和串T中的一个连续的字符序列（即匹配子串）相等，则称匹配成功，返回该匹配子串的首字符下标；否则成匹配不成功，返回-1。BF算法的思想很直接，也很容易理解，其时间复杂度为O（lenT*lenP），其中lenT和lenP分别为串T和串P的长度。 KMP算法： 这是三个人提出的算法，三人的姓氏首字母命名。其思想很简单，却很有效。这种思想同时也是后面三种算法的基础。KMP算法的基本思想是：若某趟匹配过程中T[i]和P[j]不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，文本串T不动，即指针i不回溯，让P[k]与T[i]继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串S无关，因此K可以事先确定。若定义函数next(j)=K，则next函数的定义应为： next(j)=Max{k| P[1..K-1]=P[j-k+1.. j-1] } 本次试验过程中，最重要的是看书，通过看书再实践，对知识点有更多的了解。