第一張概論

1.1 引言

兩項(xiàng)基本任務(wù)：數(shù)據(jù)表示，數(shù)據(jù)處理

軟件系統(tǒng)生存期：軟件計(jì)劃，需求分析，軟件設(shè)計(jì)，軟件編碼，軟件測(cè)試，軟件維護(hù)

由一種邏輯結(jié)構(gòu)和一組基本運(yùn)算構(gòu)成的整體是實(shí)際問(wèn)題的一種數(shù)學(xué)模型，這種數(shù)學(xué)模型的建立，選擇和實(shí)現(xiàn)是數(shù)據(jù)結(jié)構(gòu)的核心問(wèn)題。

機(jī)外表示------邏輯結(jié)構(gòu)------存儲(chǔ)結(jié)構(gòu)

處理要求-----基本運(yùn)算和運(yùn)算-------算法

1.2.1 數(shù)據(jù)，邏輯結(jié)構(gòu)和運(yùn)算

數(shù)據(jù)：凡是能夠被計(jì)算機(jī)存儲(chǔ)，加工的對(duì)象通稱為數(shù)據(jù)

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體加以考慮和處理。又稱元素、頂點(diǎn)、結(jié)點(diǎn)、記錄。

數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素，但通常不具有完整確定的實(shí)際意義，或不被當(dāng)作一個(gè)整體對(duì)待。又稱字段或域，是數(shù)據(jù)不可分割的最小標(biāo)示單位。

1.2.2 數(shù)據(jù)的邏輯結(jié)構(gòu)

邏輯關(guān)系：是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式，又稱“鄰接關(guān)系”

邏輯結(jié)構(gòu):數(shù)據(jù)元素之間邏輯關(guān)系的整體稱為邏輯結(jié)構(gòu)。即數(shù)據(jù)的組織形式。

四種基本邏輯結(jié)構(gòu)：

1 集合：任何兩個(gè)結(jié)點(diǎn)間沒(méi)有邏輯關(guān)系，組織形式松散

2 線性結(jié)構(gòu)：結(jié)點(diǎn)按邏輯關(guān)系依次排列成一條“鎖鏈”

3 樹(shù)形結(jié)構(gòu)：具有分支，層次特性，形態(tài)像自然界中的樹(shù)

4. 圖狀結(jié)構(gòu)：各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接。

注意點(diǎn):

1. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式，內(nèi)容無(wú)關(guān)。

2. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)

3. 邏輯結(jié)構(gòu)與所含結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)。

運(yùn)算：運(yùn)算是指在任何邏輯結(jié)構(gòu)上施加的操作，即對(duì)邏輯結(jié)構(gòu)的加工。加工型運(yùn)算：改變了原邏輯結(jié)構(gòu)的“值”，如結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)內(nèi)容等。

引用型運(yùn)算:不改變?cè)壿嫿Y(jié)構(gòu)個(gè)數(shù)和值，只從中提取某些信息作為運(yùn)算的結(jié)果。

引用：查找，讀取

加工：插入，刪除，更新

同一邏輯結(jié)構(gòu)S上的兩個(gè)運(yùn)算A和B, A的實(shí)現(xiàn)需要或可以利用B，而B(niǎo)的實(shí)現(xiàn)不需要利用A，則稱A可以歸約為B。

假如X是S上的一些運(yùn)算的集合，Y是X的一個(gè)子集，使得X中每一運(yùn)算都可以規(guī)約為Y中的一個(gè)或多個(gè)運(yùn)算，而Y中任何運(yùn)算不可規(guī)約為別的運(yùn)算，則稱Y中運(yùn)算（相對(duì)于X）為基本運(yùn)算。

將邏輯結(jié)構(gòu)S和在S上的基本運(yùn)算集X的整體（S,X）稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和處理方式。

1.3 存儲(chǔ)實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)

由于邏輯結(jié)構(gòu)是設(shè)計(jì)人員根據(jù)解題需要選定的數(shù)據(jù)組織形式，因此存儲(chǔ)實(shí)現(xiàn)建立的機(jī)內(nèi)表示應(yīng)遵循選定的邏輯結(jié)構(gòu)。另一方面，由于邏輯結(jié)構(gòu)不包括結(jié)點(diǎn)內(nèi)容即數(shù)據(jù)元素本身的表示，因此存儲(chǔ)實(shí)現(xiàn)的另一主要內(nèi)容是建立數(shù)據(jù)元素的機(jī)內(nèi)表示。按上述思路建立的數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

存儲(chǔ)結(jié)構(gòu)包括三部分：

1. 存儲(chǔ)結(jié)點(diǎn)，每個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素。

2. 數(shù)據(jù)元素之間關(guān)聯(lián)方式的表示，也就是邏輯結(jié)構(gòu)的機(jī)內(nèi)表

示。

3. 附加設(shè)施，如方便運(yùn)算實(shí)現(xiàn)而設(shè)置的“啞結(jié)點(diǎn)”等。

四種基本存儲(chǔ)方式：

1．順序存儲(chǔ)方式：每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)數(shù)據(jù)元素。所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里。用存儲(chǔ)結(jié)點(diǎn)間的位置關(guān)系

表述數(shù)據(jù)元素之間的邏輯關(guān)系。

2．鏈?zhǔn)酱鎯?chǔ)方式：每個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含

一組指針。每個(gè)指針指向一個(gè)與本結(jié)點(diǎn)有邏輯關(guān)系的結(jié)點(diǎn)，即

用附加的指針表示邏輯關(guān)系。

3．索引存儲(chǔ)方式：每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)連續(xù)存放。此外增設(shè)一個(gè)索引表，索引指示各存儲(chǔ)結(jié)點(diǎn)的存

儲(chǔ)位置或位置區(qū)間端點(diǎn)。

4．散列存儲(chǔ)方式：每個(gè)結(jié)點(diǎn)含一個(gè)數(shù)據(jù)元素，各個(gè)結(jié)點(diǎn)均勻分布在存儲(chǔ)區(qū)里，用散列函數(shù)指示各結(jié)點(diǎn)的存儲(chǔ)位置或位置區(qū)間端

點(diǎn)。

1.3.2 運(yùn)算實(shí)現(xiàn)

運(yùn)算只描述處理功能，不包括處理步驟和方法；運(yùn)算實(shí)現(xiàn)的核心是處理步驟的規(guī)定，即算法設(shè)計(jì)。

算法：算法規(guī)定了求解給定問(wèn)題所需的所有處理步驟及其執(zhí)行順序，使得給定類型的任何問(wèn)題能在有限時(shí)間內(nèi)被機(jī)械的求解。

算法分類：

1：運(yùn)行終止的程序可執(zhí)行部分：又稱為程序

2：偽語(yǔ)言算法：不可以直接在計(jì)算機(jī)上運(yùn)行，但容易編寫(xiě)和閱讀。 3：非形式算法：用自然語(yǔ)言，同時(shí)可能還使用了程序設(shè)計(jì)語(yǔ)言或偽語(yǔ)言描述的算法。

1.4 算法分析

算法質(zhì)量評(píng)價(jià)指標(biāo)：

1．正確性：能夠正確實(shí)現(xiàn)處理要求

2．易讀性：易于閱讀和理解，便于調(diào)試，修改和擴(kuò)充

3．健壯性：當(dāng)環(huán)境發(fā)生變化，算法能夠適當(dāng)做出反應(yīng)或處理，不會(huì)產(chǎn)生不需要的運(yùn)行結(jié)果

4．高效率：達(dá)到所需要的時(shí)空性能。

如何確定一個(gè)算法的時(shí)空性能，稱為算法分析

一個(gè)算法的時(shí)空性能是指該算法的時(shí)間性能和空間性能，前者是算法包含的計(jì)算量，后者是算法需要的存儲(chǔ)量。

算法在給定輸入下的計(jì)算量：

1．根據(jù)該問(wèn)題的特點(diǎn)選擇一種或幾種操作作為“標(biāo)準(zhǔn)操作”。

2．確定每個(gè)算法在給定輸入下共執(zhí)行了多少次標(biāo)準(zhǔn)操作，并將此次數(shù)規(guī)定為該算法在給定輸入下的計(jì)算量。

若無(wú)特殊說(shuō)明，將默認(rèn)以賦值語(yǔ)句作為標(biāo)準(zhǔn)操作。

最壞情況時(shí)間復(fù)雜性：算法在所有輸入下的計(jì)算量的最大值作為算法的計(jì)算量

平均時(shí)間復(fù)雜性：算法在所有輸入下的計(jì)算量的加權(quán)平均值作為算法的計(jì)算量。

算法的輸入規(guī)模(問(wèn)題規(guī)模)是指作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)。

常見(jiàn)時(shí)間復(fù)雜性量級(jí)：

1．常數(shù)階：O(1)即算法的時(shí)間復(fù)雜性與輸入規(guī)模N無(wú)關(guān)或N恒為常數(shù)。

2．對(duì)數(shù)階：Olog2 N

3．線性階：O(N)

4．平方階：O(N2)

5．指數(shù)階：O(2N次方)

通常認(rèn)為指數(shù)階量級(jí)的算法實(shí)際是不可計(jì)算的，而量級(jí)低于平方階的算法是高效率的

第二章線性表

2.1 線性表的基本概念

線性結(jié)構(gòu)：線性結(jié)構(gòu)是N（N大于等于0）個(gè)結(jié)點(diǎn)的有窮序列。

Ai稱為Ai+1的直接前驅(qū)，Ai+1稱為Ai的直接后繼。為滿足運(yùn)算的封閉性，通常允許一種邏輯結(jié)構(gòu)出現(xiàn)不含任何結(jié)點(diǎn)的情況。不含任何結(jié)點(diǎn)的線性結(jié)構(gòu)記為（）或

線性結(jié)構(gòu)的基本特征：若至少含有一個(gè)結(jié)點(diǎn)，則除起始節(jié)點(diǎn)沒(méi)有直接前驅(qū)外，其他結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)，除終端結(jié)點(diǎn)沒(méi)有直接后繼外，其他結(jié)點(diǎn)有且只有一個(gè)直接后繼。

2.1.2 線性表

線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。所含結(jié)點(diǎn)個(gè)數(shù)稱為線性表的長(zhǎng)度(表長(zhǎng))。表長(zhǎng)為0的是空表。

線性表的基本運(yùn)算：

1．初始化initiate（L）：加工型運(yùn)算，其作用是建立一個(gè)空表L。

2．求表長(zhǎng)length（L）：引用型運(yùn)算，其結(jié)果是線性表L的長(zhǎng)度。

3．讀表元get（L，i）：引用型運(yùn)算。若i小于等于length（L），其結(jié)果是L的第i個(gè)結(jié)點(diǎn)，否則為一特殊值。

4．定位（按值查找）locate（L，X）：引用型運(yùn)算。若L中存在一個(gè)或多個(gè)值與X相等，結(jié)果為這些結(jié)點(diǎn)的序號(hào)最小值，否

則，運(yùn)算結(jié)果為0。

5．插入insert (L，X，i)：加工型運(yùn)算。在L的第i個(gè)位置上增加一個(gè)值為X的新結(jié)點(diǎn)，參數(shù)i的合法取值范圍是1---L+1。

6．刪除delete（L，i）：加工型運(yùn)算。撤銷L的第i個(gè)結(jié)點(diǎn)Ai, i的合法取值范圍是1---N。

2.2 線性表的順序?qū)崿F(xiàn)

2.2.1 順序表

順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，即按順序存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)。順序表基本思想：

順序表的一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)線性表的一個(gè)結(jié)點(diǎn)的內(nèi)容，即數(shù)據(jù)元素(不含其他信息)，所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列。

順序表的特點(diǎn)：邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰。

順序表的類C語(yǔ)言描述：p17

Const maxsize=順序表的容量

Typedef struct

{ datatype date [maxsize]

Int last;

} sqlist;

Sqlist L;

L表示線性表的長(zhǎng)度，last-1 是終端結(jié)點(diǎn)在順序表中的位置。常數(shù)

maxsize為順序表的容量。

表長(zhǎng)st , 終端結(jié)點(diǎn) L.data[st-1]

2.2.2 基本運(yùn)算在順序表上的實(shí)現(xiàn)

1．插入

Void inset_sqlist (sqlist L,datatype x, int i)

{ if (st == maxsize) error(‘表滿’); /*溢出*/

If (((i<1)!!(i>st+1)) error (‘非法位置’);

For (j=st ; j=I; j--)

L.data[j] = L.data [j-1]; /*依次后移*/

L.data[i-1 ]= x; /*置入*/

st =st+1 /*修改表長(zhǎng)*/

}

2. 刪除

Void delete_sqlist ( sqlist L, int I ) /*刪除順序表L中第i個(gè)位置上的結(jié)點(diǎn)*/

{

If ( ( i<1 ) !! (I >st)) error (‘非法位置’);

For ( j= i+1; j= st; j++)

L.data [j-2 ] = L.data [j-1 ]; /*依次前移，注意第一個(gè)L.data[j-2]存放ai*/

st=st-1 /*修改表長(zhǎng)*/

3．定位

Int locate_sqlist (sqlist L , datatype X)

/*在順序表中從前往后查找第一個(gè)值等于X的結(jié)點(diǎn)。若找到則回傳該結(jié)點(diǎn)序號(hào)，否則回傳0*/

{

I=1 ;

While ( ( i<= st) && (L.data[i-1]!=x) ) /*注意：ai在L.data[i-1]中*/ i++; /*從前往后查找*/

if (i<=st) return (i)

else return (0)

}

2.2.3 順序?qū)崿F(xiàn)的算法分析

插入:平均時(shí)間復(fù)雜性：

=n/2

平均時(shí)間復(fù)雜性量級(jí)為O（n）

刪除：平均時(shí)間復(fù)雜性：n-1/2

平均時(shí)間復(fù)雜性量級(jí)：O（n）

定位：平均時(shí)間復(fù)雜性量級(jí)：O（n）

求表長(zhǎng)，讀表元：量級(jí)O（1）

以上分析得知：順序表的插入，刪除算法的時(shí)間性能方面是不理想的。

2.3 線性表的鏈接實(shí)現(xiàn)

順序表的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：1。無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間。

2．可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)。

缺點(diǎn)：1。插入，刪除運(yùn)算不方便，除表尾位置外，其他位置上進(jìn)行插入和刪除操作都必須移動(dòng)大量結(jié)點(diǎn)，效率較低。

2．由于順序表要求占用連續(xù)的空間，存儲(chǔ)分配職能預(yù)先進(jìn)行（靜態(tài)分配），因此當(dāng)表長(zhǎng)變化較大時(shí)，可能造成空間長(zhǎng)期閑置或空間

不夠而溢出。

鏈表：采用鏈接方式存儲(chǔ)的線性表稱為鏈表

一種數(shù)據(jù)結(jié)構(gòu)的鏈接實(shí)現(xiàn)是指按鏈?zhǔn)酱鎯?chǔ)方式構(gòu)建其存儲(chǔ)結(jié)構(gòu)，并在此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)其基本運(yùn)算。

2.3.1 單鏈表

單鏈表表示法的基本思想：用指針表示結(jié)點(diǎn)間的邏輯關(guān)系。

一個(gè)存儲(chǔ)結(jié)點(diǎn)包含兩部分：

data 部分: 稱為數(shù)據(jù)域，用于存儲(chǔ)線性表的一個(gè)數(shù)據(jù)元素。

Next部分：稱為指針域或鏈域，用于存放一個(gè)指針，指向本結(jié)點(diǎn)所含數(shù)據(jù)元素的直接后繼所在的結(jié)點(diǎn)

終端結(jié)點(diǎn)的指針NULL稱為空指針，不指向任何結(jié)點(diǎn)，只起標(biāo)志作用。Head稱為頭指針變量，指向單鏈表的第一個(gè)結(jié)點(diǎn)的，稱為頭指針。

頭指針具有標(biāo)識(shí)單鏈表的作用，故常用頭指針變量來(lái)命名單鏈表。

單鏈表的類C語(yǔ)言描述:

Typedef struct node *pointer;

Struct node

{ datatype data;

Pointer next;

};

Typedef pointer lklist;

2.3.2 單鏈表的簡(jiǎn)單操作

為了便于實(shí)現(xiàn)各種運(yùn)算，通常在單鏈表第一個(gè)結(jié)點(diǎn)前增設(shè)一個(gè)類型相同的結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。其他結(jié)點(diǎn)稱為表結(jié)點(diǎn)。表結(jié)點(diǎn)中第一個(gè)和最后一個(gè)稱為首結(jié)點(diǎn)和尾結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存放一個(gè)特殊標(biāo)志或表長(zhǎng)。

1 初始化：

Lklist initiate_lklist() /*建立一個(gè)空表*/

{

t = malloc(size);

t - > next = NULL;

return(t); }

此算法說(shuō)明的問(wèn)題：

1．語(yǔ)句 t = malloc(size); 有雙重作用：1 由malloc自動(dòng)生成一個(gè)類型為node的新結(jié)點(diǎn)。2指針型變量t得到一個(gè)值即指針，該指針

指向上述新結(jié)點(diǎn)。

2．要生成新結(jié)點(diǎn)必須通過(guò)調(diào)用malloc才能實(shí)現(xiàn)。

3．語(yǔ)句t - > next=NULL的作用是將頭結(jié)點(diǎn)*t的鏈域置為NULL。

4．為了建立一個(gè)空表，可定義一個(gè)lklist類型的變量head,并通過(guò)調(diào)用head =initiate_lklist( )使head成為指向一個(gè)空表的頭指針。

2 求表長(zhǎng)

Int length_lklist(lklist head) /*求表head的長(zhǎng)度，P是pointer類型的變量*/

{ p=head;

J=0;

While (p ->next!=NULL)

{ p=p->next;

J++; }

Return (j ); }

3 按序號(hào)查找

Pointer find_lklist ( lklist head ,int I ) /*在單鏈表head中查找第i個(gè)結(jié)點(diǎn)。若找到則回傳指向該結(jié)點(diǎn)的指針，否則回傳null*/

{ p= head; j=0;

While ( p->next !=NULL)&&( j

{ p= p->next; j++; }

If (i==j) return (p);

Else return(NULL); }

4 定位

Int locate_lklist ( lklist head, datatype x)

{ p=head ; j= 0;

While ( (p->next!=NULL)&&(p->data!=x))

{ p= p->next; j++;}

If p->data ==x return(j);

Else return (0);

}

5刪除

Void delete_lklist ( lklist head, int i)

{ p= find_lklist (head,i-1); /*調(diào)用按序號(hào)查找算法*/

If ((p!=NULL)&&(p->next!=NULL))

{q=p->next;

p->next = q->next;

free (q); }

else error(‘不存在第i個(gè)結(jié)點(diǎn)’) }

free是庫(kù)函數(shù)，結(jié)果是釋放q所指結(jié)點(diǎn)占用的內(nèi)存空間，同時(shí)q的值變成無(wú)定義。

6 插入

Void insert_lklist( lklist head,datatyped x ,int i)

{

P=find_lklist (head, i-1);

If ( p==NULL)

Error (‘不存在第i個(gè)位置’)

Else

{ s= malloc (size); s->data= x;

s->next=p->next;

p->next =s; }

2.5 其他鏈表

循環(huán)鏈表

尾結(jié)點(diǎn)的鏈域值不是NULL,而是指向頭結(jié)點(diǎn)的指針。優(yōu)點(diǎn)是從任一結(jié)點(diǎn)出發(fā)都能通過(guò)后移操作而掃描整個(gè)循環(huán)鏈表。

但為找到尾結(jié)點(diǎn)，必須從頭指針出發(fā)掃描表中所有結(jié)點(diǎn)。改進(jìn)的方法是不設(shè)頭指針而改設(shè)尾指針。這樣，頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的位置為：rear->next->next 和rear.

雙鏈表：在每個(gè)結(jié)點(diǎn)中增加一個(gè)指針域，所含指針指向前驅(qū)結(jié)點(diǎn)。

雙鏈表的摘除*P的操作：p->prior->next=p->next;

p->next->prior=p->prior;

鏈入操作：P后面鏈入*q: q->prior=p; q->next=p->next; p->next-

>prior=q; p->next =q;

2.6順序?qū)崿F(xiàn)與鏈接實(shí)現(xiàn)的比較

空間性能的比較：

存儲(chǔ)結(jié)點(diǎn)中數(shù)據(jù)域占用的存儲(chǔ)量與整個(gè)存儲(chǔ)結(jié)點(diǎn)占用存儲(chǔ)量之比稱為存儲(chǔ)密度。順序表=1，鏈表<1，所有順序表空間利用率高。但順序表要事先估計(jì)容量，有時(shí)造成浪費(fèi)。

時(shí)間性能的比較：

一種實(shí)現(xiàn)的時(shí)間性能是指該實(shí)現(xiàn)中包含的算法的時(shí)間復(fù)雜性。

定位：順序表和鏈表都是O（n）

讀表元：順序表O（1），鏈表O（n），故當(dāng)需要隨機(jī)存取時(shí)，不宜采用鏈表。

摘除，鏈入：順序表O（n），鏈表O（1），經(jīng)常需要插入刪除時(shí)不宜采用順序表。

2.7串

串是由零個(gè)或多個(gè)字符組成的又窮序列。含零個(gè)字符的串稱為空串。串中所含字符的個(gè)數(shù)稱為該串的長(zhǎng)度。

兩個(gè)串完全一樣時(shí)稱為相等的。串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子竄，該竄稱為主竄。

字符串常量按字符數(shù)組處理，它的值在執(zhí)行過(guò)程中不能改變。串變量與其他變量不一樣，不能由賦值語(yǔ)句賦值。

串的基本運(yùn)算：

1．賦值：ASSIGN(S,T):加工型運(yùn)算。將串變量或串常量的值傳給串變量。

2．判等：EQUAL(S,T)：引用型運(yùn)算，若相等返回1，否則返回0。

3．求長(zhǎng)：LENGTH(S)：引用型運(yùn)算

4．聯(lián)接：CONCAT(S,T)：引用型運(yùn)算。運(yùn)算結(jié)果是聯(lián)接在一起形成的新串。

5．求子串：SUBSTR(S,I,j)：引用型運(yùn)算：結(jié)果是串S中從第i個(gè)字符開(kāi)始，由連續(xù)j個(gè)字符組成的子串。當(dāng)I,j參數(shù)超過(guò)范圍時(shí)，運(yùn)算

不能執(zhí)行，也沒(méi)有結(jié)果。

6．插入：INSERT(S1,I,S2)：加工型運(yùn)算。將串2整個(gè)插到S1的第i個(gè)字符之后從而產(chǎn)生一個(gè)新串。

7．刪除DELETE(S,I,J)加工型運(yùn)算。從串S中刪去第I個(gè)字符開(kāi)始的長(zhǎng)度為J的子串。

8．定位：INDEX(S,T)：引用型運(yùn)算。若串S中存在一個(gè)與T相等的子串。則結(jié)果為S中第一個(gè)這樣的子串的第一個(gè)字符在S中的位

置，否則，結(jié)果為0。（要求T不是空串）

9．替換：REPLACE(S,T,R)加工型運(yùn)算。在S中處處同時(shí)以串R置換T 的所有出現(xiàn)所得的新串。

串的存儲(chǔ)：

1．串的順序存儲(chǔ)：緊縮格式，非緊縮格式

2．串的鏈接存儲(chǔ)：將串中每個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)的字符個(gè)數(shù)稱為結(jié)點(diǎn)大小。結(jié)點(diǎn)為1時(shí)存儲(chǔ)密度低但操作方便，大于1時(shí)存儲(chǔ)密

度高但操作不方便。

第三章棧，隊(duì)列和數(shù)組

3.1 棧

棧是一種特殊的線性表，棧上的插入刪除操作限定在表的某一端進(jìn)行，稱為棧頂。另一端稱為棧底。不含任何元素的棧稱為空棧。

棧又稱為先進(jìn)后出線性表。在棧頂進(jìn)行插入運(yùn)算，被稱為進(jìn)棧，刪除被稱為出棧。

棧的基本運(yùn)算：

1．初始化：InitStack(S):加工型運(yùn)算，設(shè)置一個(gè)空棧S.

2．進(jìn)棧：push（S,X）加工型運(yùn)算，將元素X插入S中，使X稱為棧頂元素。

3．退棧：pop（S）加工型運(yùn)算，當(dāng)棧不空時(shí)，從棧中刪除當(dāng)前棧頂。

4．讀棧頂：top（S）：引用型運(yùn)算，若S不空，由X返回棧頂元素，S為空時(shí)，結(jié)果為一特殊標(biāo)志。

5．判?？誩mpty（S）：引用型運(yùn)算，若S為空棧，結(jié)果為1，否則為0

3.0.2 棧的順序?qū)崿F(xiàn)

順序棧由一個(gè)一維數(shù)組和一個(gè)記錄棧頂位置的變量組成。

空棧中進(jìn)行出棧操作，發(fā)生下溢，滿棧中進(jìn)行入棧操作，發(fā)生上溢。

類C語(yǔ)言定義：

#define sqstack_maxsize 6 /*6是棧的容量*/

Typedef struct sqstack

{ DataType dada[sqstack_maxsize];

Int top;

}SqStackTP;

棧的基本運(yùn)算的實(shí)現(xiàn)：

1．初始化

Int InitStack(InitStackTp *sq)

{sq->top=0;

Return(1); }

2. 進(jìn)棧

Int push(sqstackTp *sq, datatype x)

{ if (s->top == sqstack_maxsize-1)

{error(“棧滿”);return 0;}

Else{sq-top++;

Sq->data[sq->top]=x;

Return(1); }

3 退棧

Int pop(sqstackTp *sq,datatype *x)

{if (sq->top==0)

{error(“下溢”);return(0);}

Else {*x=sq->data[sq->top];

Sq->top--;

Return(1); }

4 判?？?/p>

Int emptystack(stackTp *sq)

{if sq->top==0}

Return(1);

Else return(0); }

5 取棧頂元素

Int gettop( sqstackTp *sq, datatype *x)

{if(sq->top=0) return(0);

Else{*x =sq->data[sq->top];

Return(1); }

3.1.3棧的鏈接實(shí)現(xiàn)

鏈棧由棧頂指針ls唯一確定。棧中其他結(jié)點(diǎn)通過(guò)他們的next域鏈接起來(lái)。棧底結(jié)點(diǎn)的next域?yàn)镹ULL。

因?yàn)殒湕１旧頉](méi)有容量限制，所以不會(huì)出現(xiàn)棧滿情況。

3．1.5 棧的簡(jiǎn)單應(yīng)用和遞歸

棧與函數(shù)調(diào)用:

函數(shù)調(diào)用時(shí)，先保存的位置后返回，后保存的位置先返回。所以每遇到一個(gè)函數(shù)調(diào)用便立刻將相應(yīng)的返回位置進(jìn)棧，調(diào)用結(jié)束時(shí)，棧頂元素正好是此函數(shù)的返回位置。

遞歸與棧：

滿足遞歸的條件：

1．被定義項(xiàng)在定義中的應(yīng)用具有更小的尺度。

2．被定義項(xiàng)在最小尺度上的定義不是遞歸的。

3.1 隊(duì)列

隊(duì)列也可以看成一種受限的線性表，插入限定在表的某一端進(jìn)行（隊(duì)尾），刪除限定在另一端進(jìn)行（隊(duì)頭）

隊(duì)列又稱先進(jìn)先出線性表。

隊(duì)列的基本運(yùn)算：

1．隊(duì)列初始化initQueue(Q) 加工型運(yùn)算，設(shè)置一個(gè)空隊(duì)列Q

2．入隊(duì)列enQueue(Q,X)加工型運(yùn)算，將X插入到隊(duì)列Q的隊(duì)尾。若原隊(duì)列為空，則X為原隊(duì)尾結(jié)點(diǎn)的后繼，同時(shí)是新隊(duì)列的隊(duì)尾

結(jié)點(diǎn)。

3．出隊(duì) outQueue(Q,X)加工型運(yùn)算，若隊(duì)列Q不空，則將隊(duì)頭元素賦給X,并刪除隊(duì)頭結(jié)點(diǎn)，其后繼成為新的隊(duì)頭結(jié)點(diǎn)。

4．判隊(duì)列空emptyQueue(Q) 引用型運(yùn)算，若隊(duì)列Q為空，則返回1，否則為0

5．讀隊(duì)頭gethead(Q,x)引用型運(yùn)算，Q不空時(shí)由參數(shù)X返回隊(duì)頭結(jié)點(diǎn)的值，否則給一特殊標(biāo)志。

隊(duì)列的順序?qū)崿F(xiàn)：

隊(duì)列的順序?qū)崿F(xiàn)由一個(gè)一維數(shù)組及兩個(gè)分別指示隊(duì)頭和隊(duì)尾的變量組成，稱為隊(duì)頭指針和隊(duì)尾指針。約定隊(duì)尾指針指示隊(duì)尾元素在一維數(shù)組中的當(dāng)前位置，隊(duì)頭指針指示隊(duì)頭元素在一維數(shù)組中的當(dāng)前位置的前一個(gè)位置。

如果按sq.rear=sq.rear+1; sq.data[sq.rear]=x和sq.front=sq.front+1分別進(jìn)行入隊(duì)和出隊(duì)操作，則會(huì)造成“假溢出?！?/p>

循環(huán)隊(duì)列的入隊(duì)操作：sq.rear=(sq.rear+1)%maxsize; sq.data[sq.rear]=x 出隊(duì)操作：sq.front=(sq.front+1)%maxsize;

判斷循環(huán)隊(duì)列隊(duì)滿的條件：((sq.rear+1)%maxsize)==sq.front

隊(duì)空的條件：sq.rear==sq.front

3.2 數(shù)組

二維數(shù)組可以看成是一個(gè)被推廣的線性表，這種線性表的每一個(gè)數(shù)據(jù)元素本身也是一個(gè)線性表。

數(shù)組只有兩種基本運(yùn)算：

1．讀：給定一組下標(biāo)，讀取相應(yīng)的數(shù)據(jù)元素

2．寫(xiě)：給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素

數(shù)組元素的存儲(chǔ)位置是下標(biāo)的線性函數(shù)，計(jì)算存儲(chǔ)位置所需的時(shí)間取決于乘法的時(shí)間，因此，存取任一元素的時(shí)間相等。通常將具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)成為隨機(jī)存儲(chǔ)結(jié)構(gòu)。

3.3.3矩陣的壓縮存儲(chǔ)

壓縮存儲(chǔ)的基本思想：值相同的多個(gè)元素只分配一個(gè)存儲(chǔ)空間，零元素不分配空間。

要壓縮的矩陣分為兩種

1．特殊矩陣：對(duì)稱矩陣，三角矩陣。值相同的元素或零元素的分布有一定規(guī)律叫特殊矩陣。

對(duì)稱矩陣通常存儲(chǔ)下三角，n階方陣需要n*(n+1)/2個(gè)存儲(chǔ)單元

三角矩陣需要n*(n+1)/2+1個(gè)存儲(chǔ)單元，最后一個(gè)單元存儲(chǔ)相同

的常數(shù)。

2．稀疏矩陣：零元素遠(yuǎn)多于非零元素，且非零元素的分布沒(méi)有規(guī)律。

用三元組表存儲(chǔ)稀疏矩陣，只存儲(chǔ)非零元素。(I,j,aij)

第四章樹(shù)

4.1 樹(shù)的基本概念

樹(shù)的定義：樹(shù)是n(n>0)個(gè)結(jié)點(diǎn)的有窮集合，滿足：樹(shù)――是n(n>=0)個(gè)結(jié)

點(diǎn)的有限集T，滿足：

(1)有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；

(2)其余的結(jié)點(diǎn)可分為m(m>=0)個(gè)互不相交的子集，T1,T2,T3…Tm，其中每個(gè)子集Ti又是一棵樹(shù)，

并稱其為子樹(shù)。

有關(guān)術(shù)語(yǔ)：

樹(shù)上任一結(jié)點(diǎn)所擁有的子樹(shù)的數(shù)目稱為該結(jié)點(diǎn)的度。度為0的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)。度大于0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支點(diǎn)。一棵樹(shù)中所有結(jié)點(diǎn)度的最大值稱為該樹(shù)的度。

若結(jié)點(diǎn)A是B的直接前驅(qū)，則稱A是B的雙親或父節(jié)點(diǎn)，稱B為A的孩子或子節(jié)點(diǎn)。父節(jié)點(diǎn)相同的結(jié)點(diǎn)互稱為兄弟。

一棵樹(shù)的任何結(jié)點(diǎn)（不包括根節(jié)點(diǎn)）稱為根的子孫，根節(jié)點(diǎn)稱為其他節(jié)點(diǎn)的祖先。

結(jié)點(diǎn)的層數(shù)（或深度）從根開(kāi)始算，根的層數(shù)為1，其他節(jié)點(diǎn)的層數(shù)為其雙親的層數(shù)加1。樹(shù)中結(jié)點(diǎn)層數(shù)的最大值稱為該樹(shù)的高度或深度。

樹(shù)的基本運(yùn)算：

1．求根 ROOT(T) 引用型運(yùn)算，結(jié)果是樹(shù)T的根結(jié)點(diǎn)。

2．求雙親PARENT (T,X) 引用型運(yùn)算，結(jié)果是結(jié)點(diǎn)X在樹(shù)T上的雙親，若X是樹(shù)T的根或X不在T上，則結(jié)果為一特殊標(biāo)志。

3．求孩子CHILD(T,X,I) 引用型運(yùn)算，結(jié)果是樹(shù)T上結(jié)點(diǎn)X的第i個(gè)孩子，若X不在T上或X沒(méi)有第i個(gè)孩子，結(jié)果為一特殊標(biāo)志。

4．建樹(shù)CREATE (X,T1…….，TK) ，K>=1，加工型運(yùn)算，建立一棵以X為根，以T1…….TK為第1……K課子樹(shù)的樹(shù)。

5．剪枝DELETE（T,X,i）加工型運(yùn)算，刪除樹(shù)T上結(jié)點(diǎn)X的第i棵子樹(shù)，若T無(wú)第i棵子樹(shù)，則操作為空。

6．遍歷Traverse Tree(T):遍歷樹(shù)，即訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。

4.2 二叉樹(shù)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭?n=0)，或是由一個(gè)根結(jié)點(diǎn)及最多有兩棵互不相交的左、右

子樹(shù)組成，且每棵子樹(shù)都是二叉樹(shù)，或者同時(shí)滿足下述兩個(gè)條件：1．有且僅有一個(gè)稱為根的結(jié)點(diǎn)。

2．其余結(jié)點(diǎn)分為兩個(gè)互不相交的集合T1,T2，都是二叉樹(shù)，并且T1,T2有順序關(guān)系，T1在T2之前，他們分別稱為根的左子樹(shù)和右

子樹(shù)。

二叉樹(shù)的五種形態(tài)：

空二叉樹(shù)，

只含根的二叉樹(shù)，

只有非空左子樹(shù)的二叉樹(shù)，

只有非空右子樹(shù)的二叉樹(shù)，

同時(shí)有非空左右子樹(shù)的二叉樹(shù)。

二叉樹(shù)的基本運(yùn)算：

1．初始化INITIATE(BT) 加工型運(yùn)算，作用是設(shè)置一棵空二叉樹(shù)

2．求根ROOT(BT)引用型運(yùn)算，結(jié)果是二叉樹(shù)BT的根節(jié)點(diǎn)，若BT 為空二叉樹(shù)，結(jié)果為一特殊標(biāo)志。

3．求雙親PARENT(BT,X) 引用型運(yùn)算，結(jié)果是結(jié)點(diǎn)X在二叉樹(shù)BT上的雙親，若X是根或不在BT上，結(jié)果為一特殊標(biāo)志

4．求左孩子LCHILD(BT,X)右孩子RCHILD(BT,X)引用型運(yùn)算，結(jié)果分別為結(jié)點(diǎn)X在BT上的左，右孩子。若X為BT的葉子或X不在

BT上，結(jié)果為一特殊標(biāo)志。

5．建樹(shù)CREAT(X,LBT,RBT)加工型運(yùn)算，建立一棵X為結(jié)點(diǎn)，LBT,RBT為左右子樹(shù)的二叉樹(shù)。

6．剪枝DELETEFT(BT,X)和DELETEHT(BT,X)加工型運(yùn)算，刪除BT結(jié)點(diǎn)X的左右子樹(shù)，若無(wú)，運(yùn)算為空。

二叉樹(shù)的性質(zhì)：

性質(zhì)1、二叉樹(shù)第i(i>=1)層上至多有2i-1個(gè)結(jié)點(diǎn)。

性質(zhì)2、深度為K（k>=1）的二叉樹(shù)至多有2k -1個(gè)結(jié)點(diǎn)。

性質(zhì)3、對(duì)任何二叉樹(shù)，若2度結(jié)點(diǎn)數(shù)為n2,則葉子數(shù)n=n2+1

深度為K（K>=1）且有2k-1結(jié)點(diǎn)的二叉樹(shù)為滿二叉樹(shù)，在第K層刪去最右邊連續(xù)J個(gè)結(jié)點(diǎn)，得到一棵深度為K的完全二叉樹(shù)。

完全二叉樹(shù)的性質(zhì)：|_x|表示不大于X的最大整數(shù)。

性質(zhì)4、具有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為|_

|+1

性質(zhì)5、將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則對(duì)任一編號(hào)為i的

結(jié)點(diǎn)X有：

若i=1，則結(jié)點(diǎn)X是根，若i>1，則X的雙親parent（X）的編號(hào)

為|_i/2|

若2i>n,則結(jié)點(diǎn)X無(wú)左孩子（且無(wú)右孩子），否則，X的左孩子

LCHILD(X)的編號(hào)為2i.

若2i+1>n,則結(jié)點(diǎn)X無(wú)右孩子，否則,X的右孩子RCHILD(X)的編號(hào)

為2i+1

4.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：

二叉鏈表在做求雙親運(yùn)算時(shí)效率不高，此時(shí)可采用三叉鏈表。

具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，一共有2n個(gè)指針域，其中只有n-1個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的n+1個(gè)指針域?yàn)镹ULL.

P81

4.3.2二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

按層編號(hào)然后存儲(chǔ)。

對(duì)于非完全二叉樹(shù)，可采用增加虛結(jié)點(diǎn)的方式轉(zhuǎn)化成完全二叉樹(shù)再進(jìn)行存儲(chǔ)。虛結(jié)點(diǎn)在數(shù)組中用特殊記號(hào)表示。但同時(shí)會(huì)浪費(fèi)存儲(chǔ)空間。

4.4. 二叉樹(shù)的遍歷

遍歷一棵二叉樹(shù)就是按某種次序系統(tǒng)地“訪問(wèn)”二叉樹(shù)上所有結(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)恰好被訪問(wèn)一次。

先根遍歷：1 訪問(wèn)根結(jié)點(diǎn) 2 先根遍歷左子樹(shù) 3先根遍歷右子樹(shù)

中根遍歷：1中根遍歷左子樹(shù) 2 訪問(wèn)根結(jié)點(diǎn) 3中根遍歷右子樹(shù)

后根遍歷：1后根遍歷左子樹(shù) 2后根遍歷右子樹(shù) 3訪問(wèn)根結(jié)點(diǎn)。

4.6 樹(shù)和林

樹(shù)的存儲(chǔ)結(jié)構(gòu)：P93

1．孩子鏈表示方法：頭結(jié)點(diǎn)分為數(shù)據(jù)域和指針域，表結(jié)點(diǎn)分為孩子域和指針域

可以在頭結(jié)點(diǎn)中增加雙親域，稱為帶雙親的孩子鏈表示方

法。

2．孩子兄弟鏈表示法：存儲(chǔ)結(jié)點(diǎn)均含三個(gè)域：數(shù)據(jù)域，孩子域（存放指向本結(jié)點(diǎn)第一個(gè)孩子的指針），兄弟域（存放指向本

結(jié)點(diǎn)下一個(gè)兄弟的指針）。

3．雙親表示法：數(shù)據(jù)域，指針域（指示本結(jié)點(diǎn)的雙親所在的存儲(chǔ)結(jié)點(diǎn)）

將指針域定義為高級(jí)語(yǔ)言中的指針類型的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)成為“動(dòng)態(tài)鏈表”，相應(yīng)的指針成為動(dòng)態(tài)指針。

將指針域定義為整形，子界型的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)成為靜態(tài)鏈表，相應(yīng)的指針?lè)Q為靜態(tài)指針。

動(dòng)態(tài)鏈表的結(jié)構(gòu)通過(guò)庫(kù)函數(shù)malloc（size）動(dòng)態(tài)生成，無(wú)需事先規(guī)定表的容量。而靜態(tài)鏈表容量須事先說(shuō)明。

4.6.2樹(shù)的遍歷

1．先根遍歷：若樹(shù)非空1 訪問(wèn)根結(jié)點(diǎn) 2依次先根遍歷根的各個(gè)子樹(shù)2．后根遍歷： 1 依次后根遍歷根的各個(gè)子樹(shù)2 訪問(wèn)根結(jié)點(diǎn)

3 層次遍歷： 2 訪問(wèn)根結(jié)點(diǎn) 2從左到右，從上到下依次訪問(wèn)每層。

二叉樹(shù)與樹(shù)，林的關(guān)系 P97

將二叉樹(shù)的二叉鏈表和數(shù)的孩子兄弟鏈表的左孩子指針，右孩子指針和孩子指針，兄弟指針對(duì)應(yīng)起來(lái)。

與樹(shù)對(duì)應(yīng)的二叉樹(shù)的右子樹(shù)一定為空。

判定樹(shù)和哈夫曼樹(shù)

用于描述分類過(guò)程的二叉樹(shù)稱為判定樹(shù)。判定樹(shù)的每個(gè)非終端結(jié)點(diǎn)包含一個(gè)條件，因而對(duì)應(yīng)于一次比較火判斷，每個(gè)終端結(jié)點(diǎn)包含一個(gè)種類標(biāo)記，對(duì)應(yīng)于一種分類結(jié)果。

哈夫曼樹(shù)：

給定一組值p1……pK，如何構(gòu)造一棵有k個(gè)葉子且分別以這些值為權(quán)的判定樹(shù)，使得其平均比較次數(shù)最小。滿足上述條件的判定樹(shù)稱為哈夫曼樹(shù)。的

第五章圖

圖中的小圓圈稱為頂點(diǎn)，連線稱為邊，連線附帶的數(shù)值稱為邊的權(quán)。

任何兩點(diǎn)間相關(guān)聯(lián)的無(wú)向圖稱為無(wú)向完全圖，一個(gè)N個(gè)頂點(diǎn)的完全無(wú)向圖的邊數(shù)為n(n-1)/2.

任何兩頂點(diǎn)間都有弧的有向圖稱為有向完全圖。一個(gè)N個(gè)頂點(diǎn)的有向完全圖弧數(shù)位n(n-1)

每條邊或弧都帶權(quán)的圖稱為帶權(quán)圖或網(wǎng)。

一個(gè)連通圖的生成樹(shù)，是含有該連通圖的全部頂點(diǎn)的一個(gè)極小聯(lián)通子圖。

若連通圖的頂點(diǎn)個(gè)數(shù)位N,則生成樹(shù)的邊數(shù)為N-1,如果它的一個(gè)子圖的邊數(shù)大于N-1,則其中一定有環(huán)，如果小于，則一定不連通。

5.2 圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣

對(duì)于無(wú)向圖，頂點(diǎn)VI的度是矩陣中第I行（或列）的元素之和。

對(duì)于有向圖，行元素之和為出度，列元素之和為入度。

鄰接表

為每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表中每個(gè)結(jié)點(diǎn)稱為表結(jié)點(diǎn)，包括兩個(gè)域，鄰接點(diǎn)域，用以存放與VI相鄰接的頂點(diǎn)序號(hào)，鏈域，用以指向同VI鄰接的下一個(gè)的頂點(diǎn)。

另外，每個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。每個(gè)表頭結(jié)點(diǎn)有兩個(gè)域，一個(gè)存放頂點(diǎn)VI的信息，另一個(gè)指向鄰接表中的第一個(gè)結(jié)點(diǎn)。

若一個(gè)無(wú)向圖有N個(gè)頂點(diǎn)，E條變，則它的鄰接表需要N個(gè)頭結(jié)點(diǎn)和2E個(gè)表結(jié)點(diǎn)，所以在邊稀疏的情況下，用鄰接表比鄰接矩陣更節(jié)省存儲(chǔ)空間。

對(duì)于無(wú)向圖，第I個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)即為VI的度。

對(duì)于有向圖，第I個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是VI的出度，為求入度，必須遍歷整個(gè)鄰接表，所有單鏈表中，鄰接點(diǎn)域的值為I的結(jié)點(diǎn)個(gè)數(shù)即為入度。

有時(shí)為了方便的求入度，可以建立逆鄰接表。

5.3 圖的遍歷

從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，每個(gè)頂點(diǎn)僅訪問(wèn)一次，叫做圖的遍歷。

增設(shè)visited[n]數(shù)組。初值為0,vi被訪問(wèn)后，置為1

遍歷方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。

最小生成樹(shù)問(wèn)題

拓?fù)渑判?/p>

第六章查找表

集合的特點(diǎn)：在集合這種邏輯結(jié)構(gòu)中，任何結(jié)點(diǎn)間都不存在邏輯關(guān)系。用來(lái)標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)稱為關(guān)鍵字，簡(jiǎn)稱鍵，該數(shù)據(jù)項(xiàng)的值稱為鍵值。

靜態(tài)查找表：以集合為邏輯結(jié)構(gòu)，包括三種基本運(yùn)算

1．建表 CREATE(ST) 加工型運(yùn)算，生成一個(gè)由用戶給定的若干數(shù)據(jù)元素組成的靜態(tài)查找表ST.

2．查找 SEARCH(ST,K)引用型運(yùn)算，若ST中存在鍵值等于K，結(jié)果為該鍵在ST中的位置，否則為一特殊標(biāo)志

3．讀表元GET(ST,pos)引用型運(yùn)算，結(jié)果是pos位置上的數(shù)據(jù)元素。動(dòng)態(tài)查找表：包括查找，讀表元（同上）和以下三種基本運(yùn)算。

1．插入INSERT(ST,K)加工型運(yùn)算，若ST中不存在鍵值等于K的數(shù)據(jù)元素，則將一個(gè)鍵值等于K的數(shù)據(jù)元素插入到ST中。

2．刪除DELETE(ST,K)加工型運(yùn)算，刪除ST中鍵值等于K的數(shù)據(jù)元素。

3．初始化INITIATE(ST)加工型運(yùn)算，設(shè)置一個(gè)空的動(dòng)態(tài)查找表。6．2 靜態(tài)查找表的實(shí)現(xiàn)

6.2.1順序表上的查找

順序查找法：從表的第n個(gè)位置開(kāi)始，從后往前依次將各個(gè)位置上的數(shù)據(jù)元素的鍵值與給定值K比較。若相等，回送該位置作為結(jié)果。若不等，查找不成功。

在第0個(gè)單元設(shè)置哨崗，所有當(dāng)查找不成功時(shí)，查找了n+1次。

平均查找長(zhǎng)度ASL=（N+1）/2

6.2.2有序表的查找

二分查找法

當(dāng)N較大時(shí)，ASL約等于6,2,3 索引順序表上的查找

索引順序表由順序表和索引表兩部分組成。

兩個(gè)特點(diǎn)：1 順序表中的數(shù)據(jù)元素按塊有序 2 索引表反映了這些快的有關(guān)特性（塊內(nèi)最大鍵值和塊的起始位置）

分塊查找法

平均查找長(zhǎng)度高于順序查找而低于二分查找。

6,3樹(shù)表

6.3.1 二叉排序樹(shù)

一棵二叉排序樹(shù)或者是一棵空樹(shù)，或者同時(shí)滿足下列三個(gè)條件：1．若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的鍵值均小于它的根結(jié)點(diǎn)的鍵值。

2．若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的鍵值均大于它的根結(jié)點(diǎn)的鍵值。

3．它的左右子樹(shù)也分別是二叉排序樹(shù)。

二叉排序樹(shù)的中根遍歷所得排序是從小到大。

二叉排序樹(shù)的插入，刪除后仍要保持是一棵二叉排序樹(shù)。

刪除時(shí)：設(shè)待刪結(jié)點(diǎn)為P,雙親結(jié)點(diǎn)為F.設(shè)P是F的左孩子。

1．P為葉節(jié)點(diǎn)，直接置F的左指針域?yàn)榭铡?/p>

2．P只有一棵非空子樹(shù)，直接以其根節(jié)點(diǎn)代替P的位置。

3．P有兩顆非空子樹(shù)，可用左子樹(shù)根結(jié)點(diǎn)代替P,然后將右子樹(shù)變?yōu)樾碌母?jié)點(diǎn)的右子樹(shù)。

6.3．2 平衡二叉排序樹(shù)

一棵平衡二叉排序樹(shù)AVL樹(shù)，或者是空樹(shù)，或者是一棵任一結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)的高度至多差1的二叉排序樹(shù)。

調(diào)整方法：

P140

6．4 散列表

散列函數(shù)是一種將鍵值映射為散列表中的存儲(chǔ)位置的函數(shù)。

由散列函數(shù)決定的數(shù)據(jù)元素在散列表中的存儲(chǔ)位置稱為散列地址。

散列的基本思想是通過(guò)散列函數(shù)決定的鍵值與散列地址間的對(duì)應(yīng)關(guān)系實(shí)現(xiàn)存儲(chǔ)組織和查找運(yùn)算。

散列函數(shù)的構(gòu)造法：

1．?dāng)?shù)字分析法（需要事先知道大概的鍵值） 2 除余法 3 平方取中法 4基數(shù)轉(zhuǎn)換法 5隨機(jī)數(shù)法

第八章排序

假定待排序的序列中存在多個(gè)記錄具有相同的鍵值。若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，稱這種排序的方法是穩(wěn)定的，否則是不穩(wěn)定的。

按照排序過(guò)程涉及的存儲(chǔ)設(shè)備的不同，分為內(nèi)部排序和外部排序。內(nèi)部排序指排序過(guò)程中，數(shù)據(jù)全部存放在計(jì)算機(jī)內(nèi)存中，并在內(nèi)存中調(diào)整記錄間的相對(duì)位置。外部排序指排序過(guò)程中，數(shù)據(jù)的主要部分存放在外存中，借助內(nèi)存逐步調(diào)整記錄間的相對(duì)位置。

排序以鍵值比較和記錄移動(dòng)為標(biāo)準(zhǔn)操作。

8.2插入排序

分為直接插入排序，折半插入排序，表插入排序和希爾排序。

直接插入排序，方法是穩(wěn)定的，時(shí)間復(fù)雜性為O(N2),空間來(lái)看，只需要一個(gè)記錄的輔助空間，故空間復(fù)雜度為O（1）。

8.3交換排序

根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來(lái)兌換這兩個(gè)記錄在序列中的位置。特點(diǎn)是，將鍵值較大的記錄向序列尾部移動(dòng)，鍵值較小的記錄向序列前部移動(dòng)。

8.3.1冒泡排序

至多需要進(jìn)行N-1趟起泡。

時(shí)間復(fù)雜性為O（n2），穩(wěn)定的排序方法。