資料結構複習第四章串

第四章串（string）

重點：掌握串的基本概念，掌握串的基本操作；掌握串的三種不同的儲存方式。

難點：掌握串的三種不同的儲存方式。

學習提要:

1. 熟悉串的七種基本操作的定義，並能利用這些基本操作來實現串的其它各種操作的方法。

2. 熟練掌握在串的定長順序儲存結構上實現串的各種操作的方法。

3. 掌握串的堆儲存結構以及在其上實現串操作的基本方法。

4. 了解串操作的應用方法和特點。

4.1 串及操作

一．串的基本概念

1．串串長度：串中字元的數目。

空串：不含任何字元的串，串長度=0

空格串：僅由乙個或多個空格組成的串

例.,——串名，——串值，長度為7。

2．子串

主串：包含子串的串。如：，，為主串，為子串。

位置：字元在序列中的序號。子串在主串中的位置以子串的第乙個字元在主串中的位置來表示。

說明：空串與由空格組成的串是不同的。

空串是任意串的子串。

任意串都是本身的子串，除本身以外的的其它子串稱為的真子串。

3．串相等：只有當兩個串的長度相等，並且各個對應位置的字元都相等時才相等。

* 對於串的操作，往往是針對一組連續的字元（如插入、刪除等），而不是單個的字元，這也是串區別於一般線性表的特點。

串的邏輯結構和線性表極為相似，區別僅在於串的資料物件約束為字符集。然而，串的基本操作和線性表有很大差別。**性表的基本操作中，大多以「單個元素」作為操作物件，如求某個元素，在某個位置上插入乙個元素等，而在串的基本操作中，通常以「串的整體」作為操作物件，如在串中查詢某個子串、求取乙個子串等。

4．串的基本操作

串的基本操作子集為：賦值、比較、求串長、聯接、求子串。

詳見。4.2 串的儲存結構

串既然是線性表的特例，因此線性表的兩種儲存結構對串都是適用的。串有三種機內表示法。

1. 定長順序儲存結構

類似於線性表的順序儲存結構，用一組位址連續的儲存單元儲存串值得字串行。在串的定長順序儲存結構中，按照預定義的大小，為每個定義的串變數分配乙個固定長度的儲存區。

2. 堆分配儲存表示

體現動靜的結合。

在c語言中，存在乙個稱之為「堆」的自由儲存區，並由c語言的動態分配函式malloc()和free()來管理。利用函式malloc()為每個新產生的串分配一塊實際串長所需的儲存空間，若哦分配成功，則返回乙個指向起始位址的指標，作為串的基址，同時，為了以後方便處理，約定串長也作為儲存結構的一部分。

3. 串的塊鏈儲存表示

* 儲存密度大，則占用的儲存量小，儲存密度小，運算方便，但占用空間大。

串值的鏈式儲存結構對某些操作，如聯接操作等有一定的方便之處，但總的說來不如另外兩種儲存結構靈活，它占用儲存量大且操作複雜。