P94 例4-7 编程比较Brute-Force算法和KMP算法的实际比较次数。两个测试例子为： （1）S=”cddcdc”,T=”abcde” （2）S=”aaaaaaaa”,T=”aaaab”
头文件：DString.h
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct { char* str; int maxLength; int length; }DString; void Initiate(DString* S, int max, char* string) { int i; int size = max + 1; S->str = (char*)malloc(sizeof(char) * size); if (S->str != NULL) { S->maxLength = max; S->length = (int)strlen(string); for (i = 0; i < S->length; i++) S->str[i] = string[i]; S->str[i] = '\0'; } } int Insert(DString* S, int pos, DString T) { if (pos < 0) { printf("参数pos出错！"); return 0; } else { int i; char* buffer = (char*)malloc(sizeof(char) * (S->length + 1)); buffer[S->length] = '\0'; for (i = 0; i < S->length; i++) { buffer[i] = S->str[i]; } if (S->length + T.length > S->maxLength) { free(S->str); int size = S->length + T.length + 1; S->str = (char*)malloc(sizeof(char) * size); S->str[size - 1] = '\0'; S->maxLength = S->length + T.length; } for (i = S->length - 1; i >= pos; i--) S->str[i + T.length] = buffer[i]; for (i = 0; i < T.length; i++) S->str[pos + i] = T.str[i]; S->length += T.length; S->str[S->length + T.length] = '\0'; free(buffer); return 1; } } int Delete(DString* S, int pos, int len) { int i; if (S->length <= 0) { printf("数组中未存放字符无元素可删！\n"); return 0; } else if (pos < 0 || len<0 || pos + len>S->length) { printf("参数pos和len不合法！\n"); 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(DString* S, int pos, int len, DString* T) { int i; if (pos < 0 || len<0 || pos + len>S->length) { printf("参数pos和len出错!\n"); return 0; } if (len > T->maxLength) { T->str = (char*)malloc((len + 1) * sizeof(char)); T->maxLength = len; } for (i = 0; i < len; i++) T->str[i] = S->str[pos + i]; T->length = len; T->str[i] = '\0'; return 1; } void Destroy(DString* S) { free(S->str); S->maxLength = 0; S->length = 0; }源文件：例4-7.c
#include<stdio.h> #include<stdlib.h> #include<string.h> #include"DString.h" int BFIndexCount(DString S,int start,DString T) { int i=start,j=0,v=0; while(i<S.length && j<T.length) { if(S.str[i]==T.str[j]) { i++; j++; } else { i=i-j+1; j=0; } v++; } return v; } void GetNext(DString T,int next[]) { int j=1,k=0; next[0]=-1; next[1]=0; while(j<T.length-1) { 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 KMPIndexCount(DString S,int start,DString T,int next[]) { int i=start,j=0,v=0; while(i<S.length&&j<T.length) { if(S.str[i]==T.str[j]) { i++; j++; } else if(j==0) i++; else j=next[j]; v++; } return v; } int main() { DString myString1,myString2; int max1=6,max2=5; int next[6]; int count; Initiate(&myString1,max1,"cddcdc"); Initiate(&myString2,max2,"abcde"); printf("测试例子1:\n"); count=BFIndexCount(myString1,0,myString2); printf("Brute-Force算法比较次数:%d\n",count); GetNext(myString2,next); count=KMPIndexCount(myString1,0,myString2,next); printf("KMP算法比较次数:%d\n",count); DString myString3,myString4; int max3=8,max4=3; Initiate(&myString3,max3,"aaaaaaaa"); Initiate(&myString4,max2,"aaaab"); printf("测试例子2:\n"); count=BFIndexCount(myString3,0,myString4); printf("Brute-Force算法比较次数:%d\n",count); GetNext(myString2,next); count=KMPIndexCount(myString3,0,myString4,next); printf("KMP算法比较次数:%d\n",count); return 0; }