将串的基本操作C语言实现，实现KMP算法算出NEXT函数和NEXTVAL的值。
SqString.h的基本内容
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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中或者从键盘输入字符串
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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; } |
② 字符串的输出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
//字符串的输出 Status StrOutput(SString S) { int i; for(i=1;i<=S.length;i++) printf("%2c ",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函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
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("%2d ",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("%2d ",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; } |
主函数部分：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
int main(int argc, char* argv[]) { int j,pos=0; SString S,T; printf("----------------徐奕 软件工程 E21614061-------------------\n"); 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; } |
总结：
1. 由于数组是unsigned char类型，如果像书上把S[0]存储数组长度不妥，类型不匹配，建议不使用，建议使用改进的结构体SString类型。
2. 注意每个函数实现时，S.data[0]不作为存储，应该从1开始。
