文章目錄

• • • 串的定義（153）
    • • 空串 null string（153）
      • 子串與主串（153）
    • 串的比較（154）
    • 串的抽象數據類型（156）
    • • 查找子串第一個實現方法（157）
    • 串的順序存儲結構（157）
    • 串的鏈式存儲結構（159）
    • 樸素的模式匹配算法（160）（查找效率可能低下，最嚴重可達O(n^2)）
    • • 串的模式匹配：子串的定位操作（160）
    • KMP模式匹配算法（克努特——莫里斯——普拉特算法）（163）
    • KMP模式匹配算法實現（169）
    • KMP模式匹配算法改進（170）
    • nextval數組值推導（172）
    • 本章配套代碼
    • • 串
      • 模式匹配

串的定義（153）

串（string）是由零個或多個字符組成的有限序列，又名叫字符串

空串 null string（153）

零個字符的串

子串與主串（153）

串中任意個數的連續字符組成的子序列稱為該串的子串，包含這個子序列的稱為主串

串的比較（154）

串的比較是通過組成串的字符之間的編碼來進行的，而字符的編碼指的是字符在對應字符集中的序號

串的抽象數據類型（156）

查找子串第一個實現方法（157）

串的順序存儲結構（157）

串的鏈式存儲結構（159）

樸素的模式匹配算法（160）（查找效率可能低下，最嚴重可達O(n^2)）

串的模式匹配：子串的定位操作（160）

檢驗：

沒啥問題，而且程序設計很精妙！比157那個代碼量少多了！

KMP模式匹配算法（克努特——莫里斯——普拉特算法）（163）

看不太懂（166）

我大概想了一下，這種字符串遍歷算法的優化，假設S是主字符串，T是要遍歷的子字符串，那么我們可以把S想象得很長很長，那么我們只需要根據需遍歷的子字符串T，根據它自身建立一套遍歷規則，那么就可以按照這套規則，決定哪個字符需要比較，哪里不需要比較，規則只需建立一次，但收益終身（整個S內）

ok，我們來看它那套規則，對子字符串T使用前綴后綴規則計算j變化（有點懵，不知道為什么用這套規則）（對每個j求前面字符串前綴與后綴的最大重復串，在其基礎上加一）（168）

KMP模式匹配算法實現（169）

KMP模式匹配算法改進（170）

即使是使用了KMP模式匹配算法，仍然有不足的情況，需要對T的next[j]數組進行改良，之后的next數組用nextval數組替代

nextval數組值推導（172）

計算方式還是很好理解的，實際細節，還得自己敲代碼后才能完全吃透

本章配套代碼

串

#include "string.h" #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXSIZE 40 /* 存儲空間初始分配量 */typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */ typedef int ElemType; /* ElemType類型根據實際情況而定，這里假設為int */typedef char String[MAXSIZE + 1]; /* 0號單元存放串的長度 *//* 生成一個其值等于chars的串T */ Status StrAssign(String T, const char* chars) {int i;if (strlen(chars) > MAXSIZE)return ERROR;else{T[0] = strlen(chars);for (i = 1; i <= T[0]; i++)T[i] = *(chars + i - 1);return OK;} }/* 由串S復制得串T */ Status StrCopy(String T, String S) {int i;for (i = 0; i <= S[0]; i++)T[i] = S[i];return OK; }/* 若S為空串,則返回TRUE,否則返回FALSE */ Status StrEmpty(String S) {if (S[0] == 0)return TRUE;elsereturn FALSE; }/* 初始條件: 串S和T存在 */ /* 操作結果: 若S>T,則返回值>0;若S=T,則返回值=0;若S<T,則返回值<0 */ int StrCompare(String S, String T) {int i;for (i = 1; i <= S[0] && i <= T[0]; ++i)if (S[i] != T[i])return S[i] - T[i];return S[0] - T[0]; }/* 返回串的元素個數 */ int StrLength(String S) {return S[0]; }/* 初始條件:串S存在。操作結果:將S清為空串 */ Status ClearString(String S) {S[0] = 0;/* 令串長為零 */return OK; }/* 用T返回S1和S2聯接而成的新串。若未截斷，則返回TRUE，否則FALSE */ Status Concat(String T, String S1, String S2) {int i;if (S1[0] + S2[0] <= MAXSIZE){ /* 未截斷 */for (i = 1; i <= S1[0]; i++)T[i] = S1[i];for (i = 1; i <= S2[0]; i++)T[S1[0] + i] = S2[i];T[0] = S1[0] + S2[0];return TRUE;}else{ /* 截斷S2 */for (i = 1; i <= S1[0]; i++)T[i] = S1[i];for (i = 1; i <= MAXSIZE - S1[0]; i++)T[S1[0] + i] = S2[i];T[0] = MAXSIZE;return FALSE;} }/* 用Sub返回串S的第pos個字符起長度為len的子串。 */ Status SubString(String Sub, String S, int pos, int len) {int i;if (pos<1 || pos>S[0] || len<0 || len>S[0] - pos + 1)return ERROR;for (i = 1; i <= len; i++)Sub[i] = S[pos + i - 1];Sub[0] = len;return OK; }/* 返回子串T在主串S中第pos個字符之后的位置。若不存在,則函數返回值為0。 */ /* 其中,T非空,1≤pos≤StrLength(S)。 */ int Index(String S, String T, int pos) {int i = pos; /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */int j = 1; /* j用于子串T中當前位置下標值 */while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環繼續 */{if (S[i] == T[j]) /* 兩字母相等則繼續 */{++i;++j;}else /* 指針后退重新開始匹配 */{i = i - j + 2; /* i退回到上次匹配首位的下一位 */j = 1; /* j退回到子串T的首位 */}}if (j > T[0])return i - T[0];elsereturn 0; }/* T為非空串。若主串S中第pos個字符之后存在與T相等的子串， */ /* 則返回第一個這樣的子串在S中的位置，否則返回0 */ int Index2(String S, String T, int pos) {int n, m, i;String sub;if (pos > 0){n = StrLength(S); /* 得到主串S的長度 */m = StrLength(T); /* 得到子串T的長度 */i = pos;while (i <= n - m + 1){SubString(sub, S, i, m); /* 取主串中第i個位置長度與T相等的子串給sub */if (StrCompare(sub, T) != 0) /* 如果兩串不相等 */++i;else /* 如果兩串相等 */return i; /* 則返回i值 */}}return 0; /* 若無子串與T相等，返回0 */ }/* 初始條件: 串S和T存在,1≤pos≤StrLength(S)+1 */ /* 操作結果: 在串S的第pos個字符之前插入串T。完全插入返回TRUE,部分插入返回FALSE */ Status StrInsert(String S, int pos, String T) {int i;if (pos<1 || pos>S[0] + 1)return ERROR;if (S[0] + T[0] <= MAXSIZE){ /* 完全插入 */for (i = S[0]; i >= pos; i--)S[i + T[0]] = S[i];for (i = pos; i < pos + T[0]; i++)S[i] = T[i - pos + 1];S[0] = S[0] + T[0];return TRUE;}else{ /* 部分插入 */for (i = MAXSIZE; i <= pos; i--)S[i] = S[i - T[0]];for (i = pos; i < pos + T[0]; i++)S[i] = T[i - pos + 1];S[0] = MAXSIZE;return FALSE;} }/* 初始條件: 串S存在,1≤pos≤StrLength(S)-len+1 */ /* 操作結果: 從串S中刪除第pos個字符起長度為len的子串 */ Status StrDelete(String S, int pos, int len) {int i;if (pos<1 || pos>S[0] - len + 1 || len < 0)return ERROR;for (i = pos + len; i <= S[0]; i++)S[i - len] = S[i];S[0] -= len;return OK; }/* 初始條件: 串S,T和V存在,T是非空串（此函數與串的存儲結構無關） */ /* 操作結果: 用V替換主串S中出現的所有與T相等的不重疊的子串 */ Status Replace(String S, String T, String V) {int i = 1; /* 從串S的第一個字符起查找串T */if (StrEmpty(T)) /* T是空串 */return ERROR;do{i = Index(S, T, i); /* 結果i為從上一個i之后找到的子串T的位置 */if (i) /* 串S中存在串T */{StrDelete(S, i, StrLength(T)); /* 刪除該串T */StrInsert(S, i, V); /* 在原串T的位置插入串V */i += StrLength(V); /* 在插入的串V后面繼續查找串T */}} while (i);return OK; }/* 輸出字符串T */ void StrPrint(String T) {int i;for (i = 1; i <= T[0]; i++)printf("%c", T[i]);printf("\n"); }int main() {int i, j;Status k;char s;String t, s1, s2;printf("請輸入串s1: ");k = StrAssign(s1, "abcd");if (!k){printf("串長超過MAXSIZE(=%d)\n", MAXSIZE);exit(0);}printf("串長為%d 串空否？%d(1:是 0:否)\n", StrLength(s1), StrEmpty(s1));StrCopy(s2, s1);printf("拷貝s1生成的串為: ");StrPrint(s2);printf("請輸入串s2: ");k = StrAssign(s2, "efghijk");if (!k){printf("串長超過MAXSIZE(%d)\n", MAXSIZE);exit(0);}i = StrCompare(s1, s2);if (i < 0)s = '<';else if (i == 0)s = '=';elses = '>';printf("串s1%c串s2\n", s);k = Concat(t, s1, s2);printf("串s1聯接串s2得到的串t為: ");StrPrint(t);if (k == FALSE)printf("串t有截斷\n");ClearString(s1);printf("清為空串后,串s1為: ");StrPrint(s1);printf("串長為%d 串空否？%d(1:是 0:否)\n", StrLength(s1), StrEmpty(s1));printf("求串t的子串,請輸入子串的起始位置,子串長度: ");i = 2;j = 3;printf("%d,%d \n", i, j);k = SubString(s2, t, i, j);if (k){printf("子串s2為: ");StrPrint(s2);}printf("從串t的第pos個字符起,刪除len個字符，請輸入pos,len: ");i = 4;j = 2;printf("%d,%d \n", i, j);StrDelete(t, i, j);printf("刪除后的串t為: ");StrPrint(t);i = StrLength(s2) / 2;StrInsert(s2, i, t);printf("在串s2的第%d個字符之前插入串t后,串s2為:\n", i);StrPrint(s2);i = Index(s2, t, 1);printf("s2的第%d個字母起和t第一次匹配\n", i);SubString(t, s2, 1, 1);printf("串t為：");StrPrint(t);Concat(s1, t, t);printf("串s1為：");StrPrint(s1);Replace(s2, t, s1);printf("用串s1取代串s2中和串t相同的不重疊的串后,串s2為: ");StrPrint(s2);return 0; } 請輸入串s1: 串長為4 串空否？0(1:是 0:否) 拷貝s1生成的串為: abcd 請輸入串s2: 串s1<串s2 串s1聯接串s2得到的串t為: abcdefghijk 清為空串后,串s1為: 串長為0 串空否？1(1:是 0:否) 求串t的子串,請輸入子串的起始位置,子串長度: 2,3 子串s2為: bcd 從串t的第pos個字符起,刪除len個字符，請輸入pos,len: 4,2 刪除后的串t為: abcfghijk 在串s2的第1個字符之前插入串t后,串s2為: abcfghijkbcd s2的第1個字母起和t第一次匹配 串t為：a 串s1為：aa 用串s1取代串s2中和串t相同的不重疊的串后,串s2為: aabcfghijkbcd

模式匹配

#include "string.h" #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 /* 存儲空間初始分配量 */typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */ typedef int ElemType; /* ElemType類型根據實際情況而定，這里假設為int */typedef char String[MAXSIZE + 1]; /* 0號單元存放串的長度 *//* 生成一個其值等于chars的串T */ Status StrAssign(String T, const char* chars) {int i;if (strlen(chars) > MAXSIZE)return ERROR;else{T[0] = strlen(chars);for (i = 1; i <= T[0]; i++)T[i] = *(chars + i - 1);return OK;} }Status ClearString(String S) {S[0] = 0;/* 令串長為零 */return OK; }/* 輸出字符串T。 */ void StrPrint(String T) {int i;for (i = 1; i <= T[0]; i++)printf("%c", T[i]);printf("\n"); }/* 輸出Next數組值。 */ void NextPrint(int next[], int length) {int i;for (i = 1; i <= length; i++)printf("%d", next[i]);printf("\n"); }/* 返回串的元素個數 */ int StrLength(String S) {return S[0]; }/* 樸素的模式匹配法 */ int Index(String S, String T, int pos) {int i = pos; /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */int j = 1; /* j用于子串T中當前位置下標值 */while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環繼續 */{if (S[i] == T[j]) /* 兩字母相等則繼續 */{++i;++j;}else /* 指針后退重新開始匹配 */{i = i - j + 2; /* i退回到上次匹配首位的下一位 */j = 1; /* j退回到子串T的首位 */}}if (j > T[0])return i - T[0];elsereturn 0; }/* 通過計算返回子串T的next數組。 */ void get_next(String T, int* next) {int i, j;i = 1;j = 0;next[1] = 0;while (i < T[0]) /* 此處T[0]表示串T的長度 */{if (j == 0 || T[i] == T[j]) /* T[i]表示后綴的單個字符，T[j]表示前綴的單個字符 */{++i;++j;next[i] = j;}elsej = next[j]; /* 若字符不相同，則j值回溯 */} }/* 返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數返回值為0。 */ /* T非空，1≤pos≤StrLength(S)。 */ int Index_KMP(String S, String T, int pos) {int i = pos; /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */int j = 1; /* j用于子串T中當前位置下標值 */int next[255]; /* 定義一next數組 */get_next(T, next); /* 對串T作分析，得到next數組 */while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環繼續 */{if (j == 0 || S[i] == T[j]) /* 兩字母相等則繼續，與樸素算法增加了j=0判斷 */{++i;++j;}else /* 指針后退重新開始匹配 */j = next[j];/* j退回合適的位置，i值不變 */}if (j > T[0])return i - T[0];elsereturn 0; }/* 求模式串T的next函數修正值并存入數組nextval */ void get_nextval(String T, int* nextval) {int i, j;i = 1;j = 0;nextval[1] = 0;while (i < T[0]) /* 此處T[0]表示串T的長度 */{if (j == 0 || T[i] == T[j]) /* T[i]表示后綴的單個字符，T[j]表示前綴的單個字符 */{++i;++j;if (T[i] != T[j]) /* 若當前字符與前綴字符不同 */nextval[i] = j; /* 則當前的j為nextval在i位置的值 */elsenextval[i] = nextval[j]; /* 如果與前綴字符相同，則將前綴字符的 *//* nextval值賦值給nextval在i位置的值 */}elsej = nextval[j]; /* 若字符不相同，則j值回溯 */} }int Index_KMP1(String S, String T, int pos) {int i = pos; /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */int j = 1; /* j用于子串T中當前位置下標值 */int next[255]; /* 定義一next數組 */get_nextval(T, next); /* 對串T作分析，得到next數組 */while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環繼續 */{if (j == 0 || S[i] == T[j]) /* 兩字母相等則繼續，與樸素算法增加了j=0判斷 */{++i;++j;}else /* 指針后退重新開始匹配 */j = next[j];/* j退回合適的位置，i值不變 */}if (j > T[0])return i - T[0];elsereturn 0; }int main() {int i, * p;String s1, s2;StrAssign(s1, "abcdex");printf("子串為: ");StrPrint(s1);i = StrLength(s1);p = (int*)malloc((i + 1) * sizeof(int));get_next(s1, p);printf("Next為: ");NextPrint(p, StrLength(s1));printf("\n");StrAssign(s1, "abcabx");printf("子串為: ");StrPrint(s1);i = StrLength(s1);p = (int*)malloc((i + 1) * sizeof(int));get_next(s1, p);printf("Next為: ");NextPrint(p, StrLength(s1));printf("\n");StrAssign(s1, "ababaaaba");printf("子串為: ");StrPrint(s1);i = StrLength(s1);p = (int*)malloc((i + 1) * sizeof(int));get_next(s1, p);printf("Next為: ");NextPrint(p, StrLength(s1));printf("\n");StrAssign(s1, "aaaaaaaab");printf("子串為: ");StrPrint(s1);i = StrLength(s1);p = (int*)malloc((i + 1) * sizeof(int));get_next(s1, p);printf("Next為: ");NextPrint(p, StrLength(s1));printf("\n");StrAssign(s1, "ababaaaba");printf(" 子串為: ");StrPrint(s1);i = StrLength(s1);p = (int*)malloc((i + 1) * sizeof(int));get_next(s1, p);printf(" Next為: ");NextPrint(p, StrLength(s1));get_nextval(s1, p);printf("NextVal為: ");NextPrint(p, StrLength(s1));printf("\n");StrAssign(s1, "aaaaaaaab");printf(" 子串為: ");StrPrint(s1);i = StrLength(s1);p = (int*)malloc((i + 1) * sizeof(int));get_next(s1, p);printf(" Next為: ");NextPrint(p, StrLength(s1));get_nextval(s1, p);printf("NextVal為: ");NextPrint(p, StrLength(s1));printf("\n");StrAssign(s1, "00000000000000000000000000000000000000000000000001");printf("主串為: ");StrPrint(s1);StrAssign(s2, "0000000001");printf("子串為: ");StrPrint(s2);printf("\n");printf("主串和子串在第%d個字符處首次匹配（樸素模式匹配算法）\n", Index(s1, s2, 1));printf("主串和子串在第%d個字符處首次匹配（KMP算法） \n", Index_KMP(s1, s2, 1));printf("主串和子串在第%d個字符處首次匹配（KMP改良算法） \n", Index_KMP1(s1, s2, 1));return 0; } 子串為: abcdex Next為: 011111子串為: abcabx Next為: 011123子串為: ababaaaba Next為: 011234223子串為: aaaaaaaab Next為: 012345678子串為: ababaaabaNext為: 011234223 NextVal為: 010104210子串為: aaaaaaaabNext為: 012345678 NextVal為: 000000008主串為: 00000000000000000000000000000000000000000000000001 子串為: 0000000001主串和子串在第41個字符處首次匹配（樸素模式匹配算法） 主串和子串在第41個字符處首次匹配（KMP算法） 主串和子串在第41個字符處首次匹配（KMP改良算法）

總結

以上是生活随笔為你收集整理的C语言数据结构（大话数据结构——笔记3）第五章：串（字符串）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。