一、引入

---

? ? ? ? 在計算機中的處理的數據內容大致可分為以整形、浮點型等的數值處理和字符、字符串等的非數值處理。

? ? ? ? 今天我們主要學習的就是字符串數據。本章主要圍繞“串的定義、串的類型、串的結構及其運算”來進行串介紹與學習。

二、串的定義

---

2.1、串的基本定義

---

? ? ? ? 串（string）是由零個或多個字符組成的有限序列，也是一種內容受限的線性表。其特殊性體現在數據元素是一個字符。一般表示為：

S="abcdefg";

????????其中，S是串的名，雙引號內元素的個數為串的長度，0個元素的串被稱為空串，其長度為0；

Tips：字符串中的“空格”也算是串的一個元素，當一個串的元素只有空格時，這個串稱為“空格串”

2.2、子串以及串相等的條件

---

? ? ? ? 在一個串中，任意幾個連續字符所組成的序列稱之為該串的子串，包含子串的串叫做主串。子串在主串中的位置通常用子串的第一個字符在主串中的位置表示。

????????例如下圖的四個串：

?

? ? ? ? 它們的長度分別為3、4、7、8.且a、吧、都是c和d的子串。其中a在c、d中的位置都是1.而b在c中的位置為4，在d中的位置為5。

? ? ? ? 那么，怎么判斷兩個串是否相等呢？一般來說，只有當兩個串的長度相等且各個位置對應的字符都相等時才相等。像上圖中的a、b、c、d彼此都不相等。

三、串的類型定義和儲存結構

---

3.1、串的類型定義與基本操作

---

? ? ? ? 串的邏輯結構與先信標相似，但其基本操作的對象卻有較大的區別。串的操作主要集中在“子串”這樣的一個部分整體而不是單個元素。

其常見的基本操作如下：

函數	初始條件	操作結果
StrAssign(&T,chars)	chars是字符串常量	生成一個其值等于chars的串T
StrCopy(&T,S)	串S存在	由串S復制得到串T
StrEmpty(S)	串S存在	判斷串S是否為空串
StrCompare(S,T)	串S、T存在	比較S、T的大小。分別返回>0、=1、<0的值
StrLength	串S存在	返回串S的長度（元素個數）
ClearString	串S存在	將S清為空串
Concat(&T,s1,s2)	串s1、s2存在	將s1、s2拼接并由T返回
SubString(&Sub,S,pos,len)	串S存在，1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1	用sub返回串S的第pos個字符起長度為len的子串
Index(S,T,pos)	串S、T存在，T非空串，1<=pos<=StrLength(S).	若S、T中有相同的子串，則返回它在主串S中的第pos個字符后第一次出現的位置，否則返回0
Replace(&s,T,V)	串S、T存在，T非空串	用V替換主串S中出現的所有與T相等的不重疊子串
StrInsert(&S,pos,T)	串S、T存在，1<=pos<=StrLength(S)+1.	在串S的第pos個字符前插入串T
StrDelete(&S,pos,len)	串S存在，1<=pos<=StrLength(S)-len+1	從S中刪除第pos個字符起長度為len的子串
DestoryString(&S)	串S存在	銷毀串S

3.2、串的儲存結構?

---

? ? ? ? 同其他數據結構一樣，串也是有著最為常見的兩種儲存結構——順序和鏈式。但考慮到存儲效率和算法方便性，串多采用鏈式存儲。

3.2.1、順序存儲

---

1、定長順序存儲：

? ? ? ? 類似于線性表，用一組地址連續的存儲單元存儲串值的字符序列，按照預定義的大小，為每個串變量分配一個固定長度的存儲區。則可用定長數組如下表示：

#define MAXLEN 255    //定義串的最大長度
typedef struct{char ch[MAXLEN+1];    //存儲串的一維數組int length;            //記錄串的長度
} SSting;

? ? ? ? 但這種存儲方式如同它的名字一樣，是存儲長度是固定的。串的實際長度只能小于等于MAXLEN，超過預定義長度的串值會被舍去，稱為截斷。串長有兩種表示方法: 一是如上述定義描述的那樣，用一個額外的變量len來存放串的長度;二是在串值后面加一一個不計入串長的結束標記字符“\0”，此時的串長為隱含值。

? ? ? ? 但是現實生活中所遇到的數據長度都是不固定的。這時候內存的動態分布就顯得格外重要。這時候就印出了一個新的順序存儲結構——堆分配存儲。

2、堆分配存儲：

????????在c語言中存在一個稱之為堆（Heap）的自由存儲區，可以為每個新產生的串動態分配一塊實際串長所需要的存儲空間，若分配成功，則返回指向起始地址的指針作為串的基址，同時為了方便處理，約定串長也作為存儲結構的一部分。定義如下：

typedef struct{char *ch;    //若是非空串，則按串長分配存儲區，否則ch為NULLint length;
}HString;

?3.2.2、鏈式存儲

---

? ? ? ? 在順序串中，我們發現，如果對其進行插入或者刪除操作就顯得十分麻煩。而鏈表結構在這方面就剛好能彌補這個弊端。但由于串的特殊性——結構中的每一個數據元素是一個字符，所以存在一個問題——每個結點中可以只存放一個字符，也可以存放多個字符。如圖所示

?

? ? ? ? 所以，當結點大小大于1時，由于串長不一定是結點大小的整數倍，所以鏈表中最后一個結點不一定全被串值占滿。此時通常補上“#”或其他非串值字符。

? ? ? ? 為了操作方便，當以鏈表存儲串值的時候，除頭指針外，還可附設一個尾指針指示鏈表中的最后一個結點，并給出當前串的長度。說明如下：

#define CHUNKSIZE 80        //定義塊大小//定義結點結構
typedef struct Chunk{char ch[CHUNKSIZE];struct Chunk *next;
}Chunk;typedef struct{Chunk *head,*tail;    //串的頭尾指針int length;        //串的長度
}LString

? ? ? ? 串值的鏈式存儲結構對某些串操作有一定的方便之處，但總體來說，不如順序結構靈活。它占用存儲量大且操作復雜。

四、小結?

---

? ? ? ? 本文主要介紹了串的定義及其存儲結構。涉及到的串的匹配算法相對比較重要，所以將單獨發布來學習。

????????如果我的內容對你有幫助，在下就厚著臉皮討個點贊關注。如果你有更好的想法，還望留在評論區讓我來參考學習。我將不勝感激并努力創作出更好的內容。? ? ? ? ?

?

?