數(shù)據(jù)結(jié)構(gòu)讀書(shū)精彩筆記(正式版)

1、數(shù)據(jù)結(jié)構(gòu)讀書(shū)筆記第一章是緒論部分，因?yàn)榇蠹叶际莿倓偨佑|這門(mén)課，所以還有很多不 是很多的了解，隨著計(jì)算機(jī)的迅速發(fā)展，計(jì)算機(jī)的應(yīng)用領(lǐng)域已經(jīng)不再 只是科學(xué)計(jì)算領(lǐng)域，而更多的應(yīng)用于控制管理以及數(shù)據(jù)處理等非數(shù)值 計(jì)算的處理工作，與此對(duì)應(yīng)，計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā) 展到字符，表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)， 這就給程序設(shè)計(jì) 帶來(lái)了一些新的問(wèn)題，為了編寫(xiě)出一個(gè)好的程序，必須分析待處理的 對(duì)象的特性以及各處理對(duì)象之間存在的關(guān)系。 所以在這種環(huán)境下，數(shù) 據(jù)結(jié)構(gòu)這門(mén)課就誕生了。第二章.線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長(zhǎng)、空表、首元 結(jié)點(diǎn)，頭結(jié)點(diǎn)，頭指針等概念。2. 線性表的結(jié)構(gòu)特點(diǎn)，主要是指

2、:除第一及最后一個(gè)元素外，每個(gè)結(jié)點(diǎn) 都只有一個(gè)前趨和只有一個(gè)后繼。3線性表的順序存儲(chǔ)方式及其在具體語(yǔ)言環(huán)境下的兩種不同實(shí)現(xiàn)：表 空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處4. 線性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算 ：?jiǎn)捂湵怼?循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循 環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都 是較為常見(jiàn)的考查方式。此外，近年來(lái)在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單 鏈表輸出（可能是順序也可能是倒序）的問(wèn)題。5. 線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下，其不同的優(yōu)缺點(diǎn)比較，即其 各自適用的場(chǎng)合。單鏈表中設(shè)置頭指針

3、、循環(huán)鏈表中設(shè)置尾指針而不 設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。第三章本章主要重點(diǎn)是1.棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念， 包括:順序棧，鏈棧，共享?xiàng)Ｑh(huán)隊(duì)列，鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)（請(qǐng)注意包括：存和取兩部分）的特點(diǎn)。2.遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng) 典算法:n!階乘問(wèn)題，fib數(shù)列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，3棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號(hào)的配對(duì)等的原理4循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。第四章1串的基本概念，串與線性表的關(guān)系（串是其元素均為字符型 數(shù)據(jù)的特殊線性表），空串與空格串的區(qū)別，串相等的條件2串的基本操作，以及這些基本

4、函數(shù)的使用，包括 ：取子串，串連接, 串替換，求串長(zhǎng)等等。運(yùn)用串的基本操作去完成特定的算法是很多學(xué) 校在基本操作上的考查重點(diǎn)。3順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系，實(shí)現(xiàn)方式。4.KMP算法思想。KMP中next數(shù)組以及nextval數(shù)組的求法。明確 傳統(tǒng)模式匹配算法的不足，明確 n ext數(shù)組需要改進(jìn)之外。其中，理 解算法是核心，會(huì)求數(shù)組是得分點(diǎn)。查方式是：求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運(yùn)用KMP算法進(jìn)行匹配的匹配過(guò)程。第五章廣義表的概念，是數(shù)據(jù)結(jié)構(gòu)里第一次出現(xiàn)的。它是線性表或表 元素的有限序列，構(gòu)成該結(jié)構(gòu)的每個(gè)子表或元素也是線性結(jié)構(gòu)1多維數(shù)組中某

5、數(shù)組元素的position求解。一般是給出數(shù)組元素的首 元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。2明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系3. 將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。 這些矩陣包括： 對(duì)稱(chēng)矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的 三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。4. 廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點(diǎn)，是理解 整個(gè)廣義表一節(jié)算法的基礎(chǔ)。5. 與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，

6、與廣義表有關(guān)的算法也常是遞歸形式的。比如：求表深度，復(fù)制廣義 表等。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運(yùn)用兩種不同的方式解答：一是把一個(gè)廣義表看作是表頭和表尾兩部分，分別對(duì)表頭和表尾進(jìn)行 操作；二是把一個(gè)廣義表看作是若干個(gè)子表， 分別對(duì)每個(gè)子表進(jìn)行操 作。第六章1二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu) 考查方法可有：直接考查二叉樹(shù)的定義，讓你說(shuō)明二叉樹(shù)與普通雙分 支樹(shù)的區(qū)別；考查滿二叉樹(shù)和完全二叉樹(shù)的性質(zhì)， 普通二叉樹(shù)的五個(gè) 性質(zhì):第 i層的最多結(jié)點(diǎn)數(shù)，深度為k的二叉樹(shù)的最多結(jié)點(diǎn)數(shù)，n0二n2+1 的性質(zhì)，n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度，順序存儲(chǔ)二叉樹(shù)時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換 算關(guān)系（左為：2*i

7、，右為:2*i+1 ）。2.二叉樹(shù)的三種遍歷算法二叉樹(shù)的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其 每個(gè)算法中對(duì)根結(jié)點(diǎn)數(shù)據(jù)的訪問(wèn)順序而定。 不僅要熟練掌握三種遍歷 的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的 非遞歸算法。由于二叉樹(shù)一章的很多算法，可以直接根據(jù)三 種遞歸算法改造而來(lái)（比如：求葉子個(gè)數(shù)），所以，掌握了三種遍歷的 非遞歸算法后，對(duì)付諸如：利用非遞歸算法求二叉樹(shù)葉子個(gè)數(shù)” 3可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹(shù)算法 ： 求葉子個(gè)數(shù)，求二叉樹(shù)結(jié)點(diǎn)總數(shù)，求度為1或度為2的結(jié)點(diǎn)總數(shù)，復(fù)制 二叉樹(shù)，建立二叉樹(shù)，交換左右子樹(shù)，查找值為 n的某個(gè)指定結(jié)點(diǎn)， 刪除

8、值為n的某個(gè)指定結(jié)點(diǎn)，諸如此類(lèi)等等等等。如果你可以熟練掌 握二叉樹(shù)的遞歸和非遞歸遍歷算法，那么解決以上問(wèn)題就是小菜一碟了。4. 線索二叉樹(shù)：線索二叉樹(shù)的引出，是為避免如二叉樹(shù)遍歷時(shí)的遞歸求解。 對(duì)于線索 二叉樹(shù)，應(yīng)該掌握：線索化的實(shí)質(zhì)，三種線索化的算法，線索化后二 叉樹(shù)的遍歷算法，基本線索二叉樹(shù)的其它算法問(wèn)題（如：查找某一類(lèi) 線索二叉樹(shù)中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)就是一類(lèi)?？碱}）。5. 最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）：最優(yōu)二叉樹(shù)是為了解決特定問(wèn)題引出的特殊二叉樹(shù)結(jié)構(gòu)， 它的前提是 給二叉樹(shù)的每條邊賦予了權(quán)值，這樣形成的二叉樹(shù)按權(quán)相加之和是最 小的。6.樹(shù)與森林：二叉樹(shù)是一種特殊的樹(shù)，這種特殊不僅僅在于其

9、分支最多為 2以及其 它特征，一個(gè)最重要的特殊之處是在于：二叉樹(shù)是有序的！即：二叉樹(shù) 的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹(shù)， 這樣 交換之后的二叉樹(shù)與原二叉樹(shù)我們認(rèn)為是不相同的兩棵二叉樹(shù)。但 是，對(duì)于普通的雙分支樹(shù)而言，不具有這種性質(zhì)。樹(shù)與森林的遍歷，不像二叉樹(shù)那樣豐富，他們只有兩種遍歷算法：先根與后根（對(duì)于森林而言稱(chēng)作：先序與后序遍歷）。在難度比較大的考 試中，也有基于此種算法的基礎(chǔ)上再進(jìn)行擴(kuò)展要求你利用這兩種算法 設(shè)計(jì)其它算法的，但一般院校很少有這種考法，最多只是要求你根據(jù) 先根或后根寫(xiě)出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹(shù) 中的遍歷算法是有對(duì)應(yīng)關(guān)系的：先根遍歷

10、對(duì)應(yīng)二叉樹(shù)的先序遍歷，而 后根遍歷對(duì)應(yīng)二叉樹(shù)的中序遍歷。第七章圖圖這一章的特點(diǎn)是：概念繁多，與離散數(shù)學(xué)中圖的概念聯(lián)系緊密，算 法復(fù)雜與圖兩章的知識(shí)這一章的重點(diǎn)是：圖的定義和特點(diǎn)， 無(wú)向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長(zhǎng)度，回路， 連通圖，（強(qiáng)）連通分量等概念。2圖的幾種存儲(chǔ)形式：圖的存儲(chǔ)形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。3圖的兩種遍歷算法：深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個(gè)算法對(duì)圖一章的重要性等同于 先序、中序、后序遍歷”對(duì)于二叉樹(shù)一章的重要性。 在考查時(shí)，圖一章的算法設(shè)計(jì)題常常是基于這兩種基本的遍歷算法而 設(shè)計(jì)的，比如：求

11、最長(zhǎng)的最短路徑問(wèn)題”和 判斷兩頂點(diǎn)間是否存在長(zhǎng) 為K的簡(jiǎn)單路徑問(wèn)題”就分別用到了廣度遍歷和深度遍歷算法。4.生成樹(shù)、最小生成樹(shù)的概念以及最小生成樹(shù)的構(gòu)造RIM算法和KRUSKAL7最短路徑問(wèn)題：最短路徑問(wèn)題分為兩種：一是求從某一點(diǎn)出發(fā)到其余各點(diǎn)的最短路徑；二是求圖中每一對(duì)頂點(diǎn)之間的最短路徑。主要還是體現(xiàn)在平時(shí)做實(shí)驗(yàn)的時(shí)候，因?yàn)樽銎渌n的實(shí)驗(yàn)最起碼會(huì)知 道一些基本的做法，但是遇到數(shù)據(jù)結(jié)構(gòu)就會(huì)發(fā)現(xiàn)真的很難， 有時(shí)真的 什么都不會(huì)，看也看不懂，感覺(jué)很吃力，就感覺(jué)數(shù)據(jù)結(jié)構(gòu)這個(gè)模塊不 簡(jiǎn)單，有點(diǎn)復(fù)雜，總體感覺(jué)學(xué)不好，但是上次期中考試時(shí)候，發(fā)現(xiàn)也 不是傳說(shuō)中的那么難，有些題真的很死，可以用固定的方法去寫(xiě)，但 是那種題不多，大部分的題還是要自己去構(gòu)造一種思想， 并用代碼實(shí) 現(xiàn)它！感覺(jué)這樣的題不好做，有點(diǎn)難度！其實(shí)，剛開(kāi)始講的時(shí)候，因 為課下沒(méi)有預(yù)習(xí)，上課節(jié)奏也沒(méi)有跟上，所以就失去信心了。這幾天，因