目錄

12.串

12.1 基本操作

12.2 串的存儲結(jié)構(gòu)

12.3 字符串的模式匹配算法

（1）.樸素模式匹配算法

（2）.KMP算法

        i.next[]數(shù)組的求解

        ii.next[]數(shù)組的優(yōu)化——nextval數(shù)組

        iii.手算nextval數(shù)組

        iiii.機算nextval數(shù)組 + KMP函數(shù)

---

12.串

        串，即字符串（string），由零個或多個字符組成的有限序列。串也是線性表。

        子串，串中任意個連續(xù)的字符組成的序列。

        主串，包含子串的串。

        空串，沒有字符的串，空格串不是空串。

        字符在串中位置的描述，S = "a1a2a3..."，其編號由1開始，另外，一般都是指的該字符首次出現(xiàn)的位置，另外的另外，空格也算作字符。

        子串在主串中的位置，以子串第一個字符在主串中的位置來代替。

12.1 基本操作

        串的操作一般作用于子串，而非單個的字符。

        StrAssign(&T, chars)：賦值，把chars 賦值給T.

        StrCopy(&T, S)：復制，把S 復制給T.

        StrEmpty(S)：判空，判斷S 是否為空串，為空，返回true；未空，返回false.

        StrLength(S)：求串長。

        ClearString(&S)：清空，將S串變?yōu)榭沾?。（?nèi)存空間并沒有收回）（所以直接length = 0，在邏輯上清除就可以了）

        DestoryString(&S)：銷毀，回收串的存儲內(nèi)存空間。

        Concat(&T, S1, S2)：串的聯(lián)接，用T 返回S1與S2 聯(lián)接成的新串。

        SubString(&Sub, S, pos, len)：求子串，用Sub返回S串的從第pos個字符起往后len個的字符子串。

        Index(S, T)：定位，嘗試尋找子串T在主串S中的位置，返回首次出現(xiàn)的位置，若沒有，則返回0.

        StrCompare(S, T)：比較大小，從各串的第一個字符開始依次比較，字符的ASCll碼值，值相同，則比較各串的下一位字符，先出現(xiàn)更大的字符的串，更大。

        當串中含有空格字符，且串中非空格字符都相等，則更長的串更大，比較時是先忽略空格的。

        只有當串的字符、長度都相等時，串才相等。

12.2 串的存儲結(jié)構(gòu)

        以下代碼是串的存儲結(jié)構(gòu)以及一些重要的基本操作

//順序
#define MAXSIZE 255		//預先定義的最大串長
class SString
{
public:char ch[MAXSIZE];	//對字符的儲存int length;			//記錄串的實際長度//也可以省去此變量，用ch[0]儲存長度//為了使下標統(tǒng)一和變量分離，所以之后會將ch[0]廢棄不用，并繼續(xù)使用length
};
//順序（動態(tài)分配）（堆分配存儲）
class HString
{
public://構(gòu)造函數(shù)HString(){ch = new char();length = 0;}char* ch;int length;
};
//鏈式
class StringNode
{
public:char ch[4];				//如果只是ch ，不是數(shù)組的話，單個節(jié)點的儲存密度非常低，為了提高內(nèi)存利用率，所以采用每個結(jié)點都存儲一個小數(shù)組的方法StringNode* next;
};
using LString = StringNode*;//求串長
int StrLength(SString S)
{return S.leng