数据结构串的基本操作及KMP算法

将串的基本操作C语言实现，实现KMP算法算出NEXT函数和NEXTVAL的值。

SqString.h的基本内容

typedef int Status; typedef struct { unsigned char data[MAXSTRLEN+1]; int length; }SString; Status StrInput(SString &S); void StrAssign(SString &s,char cstr[]); Status StrOutput(SString S); Status Concat(SString &T, SString S1, SString S2); Status SubString(SString &Sub, SString S, int pos, int len); Status GetStrLength(SString S); Status ClearStr(SString &S); Status StrIsEmpty(SString S); Status StrCopy(SString &T, SString S); Status StrIndex(SString S, SString T, int pos); bool StrCompare(SString S, SString T); Status StrInsert(SString &S, int pos, SString T); Status StrDelete(SString &S, int pos, int len); Status DestroyStr(SString &S); void get_next(SString S, int *next); int KMP(SString S, SString T, int pos);

函数具体实现

① 初始化串（本文给了两种方法） 将所给字符串放入串S中或者从键盘输入字符串

void StrAssign(SString &s,char cstr[]) { int i; for (i=1;cstr[i-1]!='\0';i++) s.data[i]=cstr[i-1]; s.length=i-1; } Status StrInput(SString &S) { printf("请输入要输入的数量：\n"); int n; scanf("%d",&n); int i; printf("请输入%d个字符：\n"); getchar(); for(i=0;i<n;i++) scanf("%c",&S.data[i+1]); S.length=n; return OK; }

② 字符串的输出

//字符串的输出 Status StrOutput(SString S) { int i; for(i=1;i<=S.length;i++) printf(", ",S.data[i]); printf("\n"); return OK; } // 符串的拼接 Status Concat(SString &T, SString S1, SString S2) { int i; bool uncut; if (S1.length + S2.length <= MAXSTRLEN) { for (i = 0; i <= S1.length; i++) T.data[i] = S1.data[i]; for (i = S1.length + 1; i <= S1.length + S2.length; i++) T.data[i] = S2.data[i - S1.length]; T.length = S1.length + S2.length; uncut = TRUE; } else if (S1.length<MAXSTRLEN) { for (i = 0; i <= S1.length; i++) T.data[i] = S1.data[i]; for (i = S1.length + 1; i <= MAXSTRLEN; i++) T.data[i] = S2.data[i - S1.length]; T.length = MAXSTRLEN; uncut = FALSE; } else { for (i = 0; i <= MAXSTRLEN; i++) T.data[i] = S1.data[i]; uncut = FALSE; } return uncut; } // 返回需要的子字符串 Status SubString(SString &Sub, SString S, int pos, int len) { int i; if (pos<1 || pos>S.length || len<0 || len>S.length - pos + 1) return ERROR; for (i = 1; i <= len; i++) Sub.data[i] = S.data[pos + i - 1]; Sub.length = len; return OK; } // 询长度 Status GetStrLength(SString S) { return S.length; } // 清除串 Status ClearStr(SString &S) { int i; for (i = 1; i <= S.length; i++) S.data[i] = '\0'; S.length = 0; return OK; } // 判断串是否为空 Status StrIsEmpty(SString S) { if (S.length = 0) return 1; else return ERROR; } // 将串S复制给T Status StrCopy(SString &T, SString S) { int i; for (i = 0; i <= S.length; i++) { T.data[i] = S.data[i]; } return OK; } // 搞复杂度查询子串 Status StrIndex(SString S, SString T, int pos) { int i=pos+1,j=1; while(i<=S.length&&j<=T.length) { if(S.data[i]==T.data[j]) { ++i;++j; } else { i=i-j+2;j=1; } } if(j>T.length)return i-T.length; else return FALSE; } //判断串是否相等 bool StrCompare(SString S, SString T) { bool cmp=TRUE;; if (T.length != S.length) cmp=FALSE; else { int i; for(i=1;i<=T.length;i++) { if(T.data[i]!=S.data[i]) { cmp=FALSE;break; } } } return cmp; } //串的插入 Status StrInsert(SString &S, int pos, SString T) { int i; if (S.length + T.length > MAXSTRLEN || pos<=0 || pos>S.length) return ERROR; for (i = T.length + S.length; i >= S.length; i--) S.data[i] = S.data[i - T.length]; for (i = 1; i <= T.length; i++) S.data[pos+i-1] = T.data[i]; S.length+=T.length; return OK; } //串的删除 Status StrDelete(SString &S, int pos, int len) { int i; if (pos<1 || pos>S.length || len<0 || len>S.length - pos + 1) return ERROR; for (i = pos; i <= pos+len; i++) S.data[i] = S.data[i + 1]; S.length = S.length - len; return OK; }//销毁串 Status DestroyStr(SString &S) { int i; for (i = MAXSTRLEN; i >= 0; i--) free(S.data + i); return OK; }

KMP算法部分，包括next函数和修正的nextval函数

void get_next(SString S, int *next) { int i=1,j=0; next[1] = 0; while (i < S.length) { if (j == 0 || S.data[i] == S.data[j]) { ++i; ++j; next[i] = j; } else{ j = next[j]; } } for(i=1;i<=S.length;i++) printf("- ",next[i]); } void get_nextval(SString T,int *nextval) { int i=1;nextval[1]=0; int j=0; while(i<T.length) { if(j==0||T.data[i]==T.data[j]) { ++i;++j; if(T.data[i]!=T.data[j])nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } for(i=1;i<=T.length;i++) printf("- ",nextval[i]); } int KMP(SString S,SString T,int pos) { int i = pos; int j = 1; int next[MAXSTRLEN]; get_next(T, next); while (i <= S.length && j <= T.length){ if (j == 1 || S.data[i] == T.data[j]){ ++i; ++j; } else{ j = next[j]; } } if (j>T.length) return i - T.length; else return 0; } int KMPval(SString S,SString T,int pos) { int i = pos; int j = 1; int nextval[MAXSTRLEN]; get_nextval(T, nextval); while (i <= S.length && j <= T.length){ if (j == 0 || S.data[i] == T.data[j]){ ++i; ++j; } else{ j = nextval[j]; } } if (j>T.length){ return i - T.length; } else return 0; }

主函数部分：

int main(int argc, char* argv[]) { int j,pos=0; SString S,T; printf("----------------------------------------------------------\n"); StrAssign(S,"ILOVEGOOGLENOW!"); StrAssign(T,"GOOGLE"); printf("S为:\n");StrOutput(S); printf("串S长度 %d ",GetStrLength(S)); printf("\n"); printf("T为:\n");StrOutput(T); printf("串S长度 %d ",GetStrLength(T)); printf("\n"); printf("----------------------------------------------------------\n"); printf("简单匹配算法:\n"); printf("t在s中的位置=%d\n",StrIndex(S,T,0)); printf("----------------------------------------------------------\n"); printf(" T "); StrOutput(T); printf(" next ");KMP(S,T,0); printf("\n"); printf(" nextval");KMPval(S,T,0); printf("\n"); printf("----------------------------------------------------------\n"); printf("KMP算法:\nnext的值 "); printf(" \nt在s中的位置=%d\n",KMP(S,T,0)); printf("----------------------------------------------------------\n"); printf("修正KMP算法:\nnextval的值"); printf(" \nt在s中的位置=%d\n",KMPval(S,T,0)); printf("----------------------------------------------------------\n"); return 0; }

总结：

由于数组是unsigned char类型，如果像书上把S[0]存储数组长度不妥，类型不匹配，建议不使用，建议使用改进的结构体SString类型。注意每个函数实现时，S.data[0]不作为存储，应该从1开始。 欢迎关注我的博客：omegaxyz.com