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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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