《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言-耿國(guó)華版)》復(fù)習(xí)大綱

1、第一章 緒論1.數(shù)據(jù)：人們利用文字符號(hào)、數(shù)字符號(hào)及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)的描述。凡是能被計(jì)算機(jī)輸入、存儲(chǔ)、處理和輸出的一切信息都叫數(shù)據(jù)。2.數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素的組成：一個(gè)數(shù)據(jù)元素通常由一個(gè)或若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)：指具有獨(dú)立含義的最小標(biāo)識(shí)單位。3.數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。4.數(shù)據(jù)結(jié)構(gòu)：研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相互關(guān)系和所定義的算法在計(jì)算機(jī)上運(yùn)行的學(xué)科。5.算法：是對(duì)待定問(wèn)題求解步驟的一種描述，是指令的有限序列。算法應(yīng)滿足以下性質(zhì)：1)輸入性：具有零個(gè)或若干個(gè)輸入量

2、；2)輸出性：至少產(chǎn)生一個(gè)輸出；3)有窮性：每條指令的執(zhí)行次數(shù)是有限的；4)確定性：每條指令的含義明確，無(wú)二義性；5)可行性：每條指令都應(yīng)在有限的時(shí)間內(nèi)完成。6.評(píng)價(jià)算法優(yōu)劣的主要指標(biāo)：1)執(zhí)行算法后，計(jì)算機(jī)運(yùn)行所消耗的時(shí)間，即所需的機(jī)器時(shí)間；2)執(zhí)行算法時(shí)，計(jì)算機(jī)所占存儲(chǔ)量的大小，即所需的存儲(chǔ)空間；3)所設(shè)計(jì)的算法是否易讀、易懂，是否容易轉(zhuǎn)換成其他可運(yùn)行的程序語(yǔ)言。7.會(huì)估算某一算法的總執(zhí)行時(shí)間和時(shí)間復(fù)雜度。8.熟悉習(xí)題P32:3(5)-(9)、4(2)(3)第二章 線性表 1.線性表(P7)：是性質(zhì)相同的一組數(shù)據(jù)元素序列。線性表的特性：1)數(shù)據(jù)元素在線性表中是連續(xù)的，表中數(shù)據(jù)元素的個(gè)數(shù)可以

3、增加或減少，但調(diào)整后數(shù)據(jù)元素仍必須是連續(xù)的，即線性表是一種線性結(jié)構(gòu)。2)數(shù)據(jù)元素在線性表中的位置僅取決于自己在表中的序號(hào)，并由該元素?cái)?shù)據(jù)項(xiàng)中的關(guān)鍵字(key)加以標(biāo)識(shí)。3)線性表中所有數(shù)據(jù)元素的同一數(shù)據(jù)項(xiàng)，其屬性是相同的，數(shù)據(jù)類型也是一致的。線性表的主要運(yùn)算有：插入、刪除、查找、存取、長(zhǎng)度、排序、復(fù)制、合并。線性表的順序存儲(chǔ)結(jié)構(gòu)及特點(diǎn)(就是把表中相鄰的數(shù)據(jù)元素存放在內(nèi)存鄰接的存儲(chǔ)單元，這種存儲(chǔ)方法叫做順序分配，又稱順序映像。其特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素，它們的物理次序也是相鄰的。)，存儲(chǔ)地址的計(jì)算方式(Loc(ai)=Loc(a0)+i*s)。2.線性表的查找、插入和刪除熟悉線性表的查找算法(

4、P38)、插入算法(P39)和刪除算法(P40)。3.理解線性表的順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。4.熟悉線性鏈表的存儲(chǔ)結(jié)構(gòu)(P43)線性鏈表(由若干結(jié)點(diǎn)鏈接而成的一種存儲(chǔ)結(jié)構(gòu)。)、結(jié)點(diǎn)(由存放數(shù)據(jù)元素值的部分?jǐn)?shù)據(jù)域和存放另一元素存儲(chǔ)地址的部分指針域或鏈域兩部分信息組成的存儲(chǔ)結(jié)構(gòu)。)、單鏈表(線性鏈表)的概念。5.熟悉線性鏈表的建立(P45-47)、查找(P47-48)、插入(P49-50)和刪除(P50-51)的算法；6.明了什么是循環(huán)鏈表(鏈表中最后一個(gè)結(jié)點(diǎn)指針域回指向鏈表的第一個(gè)結(jié)點(diǎn)，使得整個(gè)鏈表通過(guò)鏈指針成為一個(gè)環(huán)形，這種形式的鏈表稱為循環(huán)鏈表。)？7.明了雙向鏈表的結(jié)構(gòu)(鏈表中的每個(gè)結(jié)點(diǎn)有兩個(gè)

5、指針域，一個(gè)是向前鏈接的左指針(Lnext或prior)，另一個(gè)是向后鏈接的右指針(Rnext或next)，同時(shí)還有一個(gè)數(shù)據(jù)域(Data)。)；了解雙向鏈表的插入和刪除的算法。8.理解鏈表的優(yōu)缺點(diǎn)(P48)。9.熟悉習(xí)題P68：1、2第三章 限定性線性表-棧和隊(duì)列1.棧和隊(duì)列明確什么是棧及其特點(diǎn)(只允許在一端進(jìn)行插入和刪除的線性表。允許插入和刪除的一端稱為棧頂，不允許插入和刪除的一端稱為棧底。棧的插入為進(jìn)棧，稱棧的刪除為出棧。棧的特性：后進(jìn)先出，所以又稱后進(jìn)先出表，簡(jiǎn)稱LIFO表。)。2. 明了什么是順序棧（用順序存儲(chǔ)結(jié)構(gòu)表示的棧），熟悉順序棧進(jìn)棧算法和出棧算法（?？?，棧滿判定條件，指針移動(dòng)）

6、。3.明了什么是鏈棧(用鏈表表示的棧。)，熟悉鏈棧(進(jìn)棧；出棧)的算法。4.明確什么是隊(duì)列及其特點(diǎn)(所有的插入(進(jìn)隊(duì))均限制在表的一端進(jìn)行，所有的刪除(出隊(duì))被限制在表的另一端。允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)頭(front)。隊(duì)列結(jié)構(gòu)特點(diǎn)：先進(jìn)隊(duì)的元素先出隊(duì)，故也稱為先進(jìn)先出表，簡(jiǎn)稱FIFO表。)。5.了解循環(huán)隊(duì)列及其進(jìn)隊(duì)和出隊(duì)的算法（循環(huán)隊(duì)列隊(duì)空隊(duì)滿判定條件，指針移動(dòng)）。6. 明了什么是鏈隊(duì)列(采用鏈表表示隊(duì)列。)？熟悉鏈隊(duì)列(進(jìn)隊(duì)、出隊(duì))的算法。7.熟悉習(xí)題P102：1、3、12第四章 串 1.掌握串的基本概念：串(是由零個(gè)或多個(gè)字符組成的有限序列。一般記為：s=

7、(n=0)。)、串的長(zhǎng)度(串中字符的數(shù)目n。)、空串(零個(gè)字符的串，其長(zhǎng)度為零。)、空格串(僅含有空格字符的串，它的長(zhǎng)度為串中空格符的個(gè)數(shù)。)、子串(串中任意個(gè)連續(xù)的字符組成的子序列)、主串(包含子串的串)、字符在串中的位置(字符在序列中的序號(hào))、子串在主串的位置(以子串第一個(gè)字符在主串中的位置來(lái)表示)、兩個(gè)串相等(當(dāng)且僅當(dāng)這兩個(gè)串的值相等。也就是說(shuō)，只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各對(duì)應(yīng)位置的字符都相等時(shí)才相等。)2.熟悉串的基本運(yùn)算：串的賦值運(yùn)算(assign(a，b)、串的聯(lián)接運(yùn)算(concat(a，b)、求串長(zhǎng)(length(s)、求子串(substr(s，start，len

8、)、判斷兩個(gè)串是否相等(equal(a，b)；了解求子串在主串中的序號(hào)(index(a，b)、替換運(yùn)算(replace(a，b，c)、插入運(yùn)算(insert(a,i,b)、刪除運(yùn)算(delete(a,i,k)的功能。3.明了串的存儲(chǔ)結(jié)構(gòu)(P81)：串的靜態(tài)存儲(chǔ)結(jié)構(gòu)(是將串定義成字符型數(shù)組，從串名可直接訪問(wèn)到串值，串的存儲(chǔ)空間分配是在編譯時(shí)完成的，不能更改)、串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)（是串的存儲(chǔ)空間分配是在程序運(yùn)行時(shí)動(dòng)態(tài)分配的）；串的靜態(tài)存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)結(jié)構(gòu)；串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)有兩種方式：一種是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，另一種是堆結(jié)構(gòu)的存儲(chǔ)方式。4.熟悉子串定位函數(shù)的算法(P112)。5.熟悉習(xí)題(P119)

9、1。第五章 數(shù)組和廣義表1.數(shù)組(P125)：一維數(shù)組、二維數(shù)組存儲(chǔ)地址的計(jì)算(一維P125公式，或Loc(ai)=Loc(a0)+i*s；二維P125公式，或Loc(aij)= Loc(a00)+(i*n+j) *s)。2.上三角矩陣、下三角矩陣、帶狀矩陣的壓縮存儲(chǔ)，會(huì)求任意元素aij在一維數(shù)組中的位置。3.稀疏矩陣：指大部分元素為零的矩陣。稀疏矩陣的表示方法三元組表中各元素所表示的意義。4.了解廣義表的概念，廣義表的長(zhǎng)度，廣義表的表頭，廣義表的表尾。5.熟悉習(xí)題(P145) 1、3、9。第六章 樹(shù) 1.掌握一般樹(shù)的概念：一般樹(shù)的定義(樹(shù)是n(n=0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)稱為空樹(shù)，否

10、則，在任一棵非空樹(shù)中：有一個(gè)且僅有一個(gè)稱為該樹(shù)根(Root)的結(jié)點(diǎn)；其余結(jié)點(diǎn)可分為m(m=0)個(gè)互不相交的有限集合T1，T2，Tm，且每個(gè)集合本身又是一棵樹(shù)，并稱之為根的子樹(shù)(Subtree)。樹(shù)的定義是一種遞歸定義)；樹(shù)的結(jié)點(diǎn)(指一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。)、結(jié)點(diǎn)的度(指結(jié)點(diǎn)擁有子樹(shù)的數(shù)目。)、葉子結(jié)點(diǎn)(指度為零的結(jié)點(diǎn)。)、分支結(jié)點(diǎn)(指度不為零的結(jié)點(diǎn)。)、樹(shù)的度(指樹(shù)中各結(jié)點(diǎn)度的最大值。)、有序樹(shù)(將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左到右是有次序的，稱為有序樹(shù)，否則稱為無(wú)序樹(shù)。)、森林(m(m=0)棵互不相交的樹(shù)的集合。)樹(shù)的存儲(chǔ)結(jié)構(gòu)：多重鏈表表示法(每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域和若干指針域組成。每

11、個(gè)指針域?qū)⒅赶蛟摻Y(jié)點(diǎn)的一個(gè)孩子。)，多重鏈表又分為：定長(zhǎng)結(jié)點(diǎn)的多重鏈表和不定長(zhǎng)結(jié)點(diǎn)的多重鏈表；二重鏈表示法(即孩子兄弟表示法，樹(shù)中每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域：數(shù)據(jù)域、長(zhǎng)子指針域和次弟指針域。)2.掌握二叉樹(shù)的概念二叉樹(shù)(結(jié)點(diǎn)的有限集合，它或者是空集，或者由一個(gè)根結(jié)點(diǎn)和兩個(gè)互不相交的該根的左子樹(shù)和右子樹(shù)組成，左右子樹(shù)也是一棵二叉樹(shù)，顯然這也是一個(gè)遞歸定義。)；二叉樹(shù)是有序的(二叉樹(shù)中的結(jié)點(diǎn)即使只有一棵子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù))；兩種特殊形態(tài)的二叉樹(shù)：滿二叉樹(shù)(如果一棵深度為K的二叉樹(shù)，共有2K-1結(jié)點(diǎn)，則稱為滿二叉樹(shù)。)、完全二叉樹(shù)(如果深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，能夠與深度為k的順序編號(hào)滿

12、二叉從1到n標(biāo)號(hào)的結(jié)點(diǎn)相對(duì)應(yīng)。)了解二叉樹(shù)的性質(zhì),會(huì)靈活運(yùn)用性質(zhì)：性質(zhì)1 在二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)(i=1)。 性質(zhì)2 高度為h的二叉樹(shù)最多有2h-1個(gè)結(jié)點(diǎn)(h=1)。(可用圖5-7a)解釋)性質(zhì)3 對(duì)任何二叉樹(shù)T，設(shè)n0、n1、n2分別表示度數(shù)為0、1、2的結(jié)點(diǎn)數(shù)，則有n0= n2+1。(葉子結(jié)點(diǎn)數(shù)與度數(shù)為2的結(jié)點(diǎn)數(shù)的關(guān)系)性質(zhì)4 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 +1。(注符號(hào)表示不大于x的最大整數(shù)，則表示不小于x的最小整數(shù)) 性質(zhì)5 如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則對(duì)任一結(jié)點(diǎn)(1=i1，則i的雙親結(jié)點(diǎn)是 。2)若2in，則i無(wú)左孩子。3)若2i+1n，則i無(wú)右孩子。

13、了解二叉樹(shù)的存儲(chǔ)：二叉樹(shù)通常有兩類存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3.掌握二叉樹(shù)的先序遍歷的算法；了解中序遍歷、后序遍歷的算法。給出一棵樹(shù)，會(huì)寫(xiě)出樹(shù)的先序中序后序序列。4.明了結(jié)點(diǎn)間的路徑長(zhǎng)度(從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支個(gè)數(shù)即是結(jié)點(diǎn)間的路徑長(zhǎng)度)、樹(shù)的路徑長(zhǎng)度(從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和稱為樹(shù)的路徑長(zhǎng)度，一般記作pl。)、帶權(quán)路徑長(zhǎng)度(若給二叉樹(shù)的每個(gè)終端結(jié)點(diǎn)賦以權(quán)值，從而構(gòu)成的帶權(quán)路徑長(zhǎng)度。其計(jì)算方法為：wpl=)、哈夫曼樹(shù)(帶權(quán)路徑長(zhǎng)度wpl最小的樹(shù)稱做最優(yōu)二叉樹(shù)或哈夫曼樹(shù))；熟悉哈夫曼樹(shù)的算法，給出數(shù)據(jù)序列，會(huì)構(gòu)造哈夫曼樹(shù)。5.

14、了解一般樹(shù)轉(zhuǎn)化為二叉樹(shù)和二叉還原為一般樹(shù)。6.熟悉習(xí)題(P194) 2、3、4、7、9、11第七章 圖1.熟悉圖的基本術(shù)語(yǔ)：圖(G由頂點(diǎn)的集合V(G)和邊的E(G)集合組成，記做：G = (V，E)，其中V(G)是圖中頂點(diǎn)的非空有限集合，E(G)是圖中邊的有限集合。)、有向圖(如果圖中每條邊都是有方向的，即在圖示時(shí)每條邊都用箭頭表示方向，則稱此圖為有向圖。)、無(wú)向圖(如果圖中每條邊都是頂點(diǎn)無(wú)序?qū)?，則稱為無(wú)向圖。)、無(wú)向完全圖(若一個(gè)無(wú)向圖有n個(gè)頂點(diǎn)，而每一個(gè)頂點(diǎn)與其它n-1個(gè)頂點(diǎn)之間都有邊，這樣的圖稱為無(wú)向完全圖，即共有n(n-1)/2條邊。)、有向完全圖(在有n個(gè)頂點(diǎn)的有向圖中，若有n(n-

15、1)條弧，即任意兩頂點(diǎn)之間都有雙向相反的兩條弧連接，則稱為有向完全圖。)、子圖(設(shè)有兩個(gè)圖G=(V，E)和G=(V，E)，如果VV且EE，則稱G為G的子圖。)、路徑(在圖G中，從頂點(diǎn)Vp到Vq的一條路徑是頂點(diǎn)序列(Vp，Vi1，Vi2，Vin，Vq)且(Vp，Vi1)，(Vi1，Vi2)，(Vin，Vq)是E(G)中的邊，路徑上邊的數(shù)目稱之為該路徑長(zhǎng)度。)、連通圖(在無(wú)向圖G中，若從Vi到Vj有路徑，則稱Vi和Vj是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通，則稱G為連通圖，否則稱為非連通圖。)、強(qiáng)連通圖(在有向圖G中，若任意兩個(gè)頂點(diǎn)Vi和Vj都連通的，即從Vi到Vj和從Vj到Vi都存在路徑，則稱G是

16、強(qiáng)連通圖。)、度(就是依附于該頂點(diǎn)的邊數(shù)。)、入度和出度(在有向圖中，以某頂點(diǎn)為頭，即終止于該結(jié)點(diǎn)的弧的數(shù)目稱為該頂點(diǎn)的入度；以某頂點(diǎn)為尾，即起始該頂點(diǎn)的弧的數(shù)目稱為該頂點(diǎn)的出度。頂點(diǎn)的入度和出度之和稱為頂點(diǎn)的度。)2.熟悉圖的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接鏈表)，了解建立鄰接矩陣或鄰接鏈表的算法：鄰接矩陣(是用一個(gè)二維數(shù)組來(lái)表示圖中頂點(diǎn)的相鄰關(guān)系。設(shè)圖G=V,E有n1個(gè)頂點(diǎn)，則G的鄰接矩陣是按如下定義的n階方陣：costij=)、鄰接鏈表(由鄰接矩陣改進(jìn)而來(lái)的一種鏈接結(jié)構(gòu)，它包含兩個(gè)部分，一部分是向量，另一部分是鏈表。鏈表部分共有n個(gè)鏈表，即每個(gè)頂點(diǎn)一個(gè)鏈表。每個(gè)鏈表由一個(gè)表頭結(jié)點(diǎn)和若干個(gè)表結(jié)點(diǎn)組

17、成。向量部分為一個(gè)數(shù)組，用來(lái)存儲(chǔ)n個(gè)表頭結(jié)點(diǎn)，向量的下標(biāo)指示了頂點(diǎn)的序號(hào)。)3.熟悉遍歷圖的算法:深度優(yōu)先搜索法和廣度優(yōu)先搜索法。4.了解最小生成樹(shù)、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑的概念和用途。5.給出一個(gè)無(wú)向圖，會(huì)用普利姆算法和克魯斯卡爾算法手工構(gòu)造最小生成樹(shù)。6.給出一個(gè)有向圖，會(huì)用迪杰斯特拉算法求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑，用弗洛伊德算法求任意一對(duì)頂點(diǎn)間的最短路徑。7.熟悉習(xí)題(P244)1、4、14、15第八章 查找 1.熟悉查找表(由同一數(shù)據(jù)類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。)、關(guān)鍵字(數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可標(biāo)識(shí)(識(shí)別)一個(gè)數(shù)據(jù)元素(或記錄)。若此關(guān)鍵字可以唯

18、一地標(biāo)識(shí)，則稱此關(guān)鍵字為主關(guān)鍵字。)、查找(根據(jù)給定的某個(gè)關(guān)鍵字的值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素(或記錄)。)的概念。2.熟悉順序查找（P249）、折半查找（P250-251）的算法，及其平均查找長(zhǎng)度。3.了解分塊查找的原理。4.明了二叉排序樹(shù)的概念(二叉排序樹(shù)的定義：它或者是一個(gè)空樹(shù)，或者是一個(gè)具有如下性質(zhì)的二叉樹(shù)：(1)若它有左子樹(shù)，則左子樹(shù)上有所有結(jié)點(diǎn)的數(shù)據(jù)均小于根結(jié)點(diǎn)的數(shù)據(jù)；(2)若它有右子樹(shù)，則右子樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)均大于根結(jié)點(diǎn)的數(shù)據(jù)；(3)左，右子樹(shù)本身又各是一棵二叉樹(shù)排序樹(shù)。)；熟悉二叉排序樹(shù)的算法，給出數(shù)據(jù)序列，會(huì)構(gòu)造二叉排序樹(shù)。5.了解什么是哈希法、哈希表

19、和哈希函數(shù)(存取過(guò)程中需要在記錄存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系H，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系H，就可以找到需要的關(guān)鍵字及其對(duì)應(yīng)的記錄。這種方法稱為哈希法(也稱為散列法、雜湊法)，其存儲(chǔ)空間稱為哈希表(或散列表)，其對(duì)應(yīng)關(guān)系H稱為哈希函數(shù)。)，了解哈希函數(shù)的構(gòu)造方法(構(gòu)造哈希函數(shù)時(shí)應(yīng)遵循的基本原則：1)算法簡(jiǎn)單，運(yùn)算最小；2)均勻分布，減少?zèng)_突。直接定址法、(熟悉)除留余數(shù)法、平方取中法、折迭法、數(shù)字分析法)，了解解決沖突的方法(開(kāi)放地址法和鏈地址法)6.熟悉習(xí)題(P295)1、5(1)、12第九章 排序1.明了排序的分類(根據(jù)待排序記錄數(shù)量的不同分成兩類：a.內(nèi)部排序，指