第一章：緒論
一、概念：
數(shù)據(jù)結(jié)構(gòu)：是一門研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。
數(shù)據(jù)：是描述額觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序加工處理的信息的集合。
數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。（一個(gè)數(shù)據(jù)項(xiàng)或多個(gè)數(shù)據(jù)項(xiàng)（域）。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。結(jié)點(diǎn)、頂點(diǎn)、記錄。
數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合。
數(shù)據(jù)結(jié)構(gòu)：研究是是數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存貯表示，并對(duì)每種結(jié)構(gòu)定義各自的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且經(jīng)過(guò)運(yùn)算后所得的新結(jié)構(gòu)一般仍然是原來(lái)的結(jié)構(gòu)類型。
數(shù)據(jù)類型：是指程序設(shè)計(jì)語(yǔ)言中各變量可取的數(shù)據(jù)種類。
算法：是執(zhí)行特定計(jì)算的有窮過(guò)程。特點(diǎn)：
·動(dòng)態(tài)有窮·確定性·輸入·輸出·可行性。
第二章 線性表和數(shù)組
概念：
一、線性表：是N個(gè)元素構(gòu)成的有限序列。
順序存貯結(jié)構(gòu)：地址計(jì)算，插入、刪除。
鏈?zhǔn)酱尜A結(jié)構(gòu)：?jiǎn)捂湵恚檎?、插入、刪除。
循環(huán)鏈表：
雙向鏈表：
二、數(shù)組：
以行為主；
以列為主；計(jì)算地址：
三、棧：是一種特殊的線性表，這種表只能在固定的一端進(jìn)行插入與刪除運(yùn)算。
隊(duì)列：是另一種特殊的線性表，刪除運(yùn)算限定在表的一端進(jìn)行，而插入運(yùn)算在另一端進(jìn)行。
第三章：串
概念：是由N個(gè)字符組成的有限序列。
存貯結(jié)構(gòu)：
順序表示法：
1、緊縮格式 2、非緊縮格式 3、以單字節(jié)為單位的存貯方式
鏈?zhǔn)奖硎痉ǎ?BR> 串名的存貯映象：
第四章：樹(shù)
一、概念：
樹(shù)：是一個(gè)或多個(gè)結(jié)點(diǎn)的有窮集合T，且滿足以下條件：
1、有且僅有一個(gè)指定的稱作樹(shù)根的結(jié)點(diǎn)；
2、除根以外的其余結(jié)點(diǎn)被分成m個(gè)不相交的集合，這些集合的每一個(gè)又都是樹(shù)，并且稱為根的子樹(shù)。
結(jié)點(diǎn)的度：結(jié)點(diǎn)N的子樹(shù)數(shù)稱為結(jié)點(diǎn)的度。
樹(shù)的度：樹(shù)T中各結(jié)點(diǎn)的度的值稱的樹(shù)T的度。
葉子：樹(shù)中度為0的結(jié)點(diǎn)稱為葉子（終端結(jié)點(diǎn)）。
分枝結(jié)點(diǎn)：樹(shù)中度不為0的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)（非終端結(jié)點(diǎn)）。
雙親和孩子：若樹(shù)中結(jié)點(diǎn)P的一棵子樹(shù)的根是結(jié)點(diǎn)C，則我們稱P是C的雙親或父母，反之稱C是P的孩子。
結(jié)點(diǎn)的層數(shù)：樹(shù)的層數(shù)為1，其余任一結(jié)點(diǎn)的層數(shù)等于它的雙親的層數(shù)加1.
樹(shù)的深度：樹(shù)中各結(jié)點(diǎn)的層數(shù)的值稱為T的深度（高度）。
兄弟和堂兄弟：同一雙親的孩子之間互稱為兄弟，其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。
祖先和子孫：一個(gè)點(diǎn)的祖先是指從樹(shù)的根到該結(jié)點(diǎn)所經(jīng)分枝上的所有結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。
有序樹(shù)和無(wú)序樹(shù)：如果樹(shù)中結(jié)點(diǎn)各棵子樹(shù)規(guī)定從左至右是有次序的，則稱樹(shù)為有序樹(shù)，否則為無(wú)序樹(shù)。
森林：N棵互不相交的樹(shù)的集合稱為森林。
二、樹(shù)的存貯表示：
1、雙親數(shù)組表示：記錄型一維數(shù)組：data，parent
2、孩子鏈表表示法：
·多重鏈表表示法： data，degree，link1，link2…
·單鏈表表示法：data，likn
3、左孩子右兄弟鏈表示法：lchild，data，rsibling
三、二叉樹(shù)：
1、概念：是有限個(gè)結(jié)點(diǎn)的集合，它或者為空集，或者是由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的且分別稱為根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。五種形態(tài)：空，根，左，右，左右 2、性質(zhì)：
·位于二叉樹(shù)第I層上的結(jié)點(diǎn)，最多為2I-1；（I）=1
·深度為K的二叉樹(shù)的結(jié)點(diǎn)總數(shù)，最多為2K-1（K）=1
·N0=N2+1
滿二叉樹(shù)：一棵深度為K的具有2K-1個(gè)結(jié)點(diǎn)的二叉樹(shù)
完全二叉樹(shù)：在一棵二叉樹(shù)中，若所有結(jié)點(diǎn)的度為0或?yàn)?的二叉樹(shù)
順序二叉樹(shù)：如果深度為K的具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，它的每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中順序編號(hào)是1到N的結(jié)點(diǎn)相對(duì)應(yīng)的二叉樹(shù)。
三、二叉樹(shù)的存貯表示：
1、順序存貯：
2、鏈表表示：lchild，data，rchlid
3、遍歷：
·前序：根—左—右
·中序：左—根—右
·后序：左—右—根
四、線索二叉樹(shù)：
五、樹(shù)的二叉樹(shù)表示，森林與二叉樹(shù)的轉(zhuǎn)換。
六、路徑長(zhǎng)度：樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之關(guān)的路徑由這兩個(gè)結(jié)點(diǎn)之間的分枝所構(gòu)成，路徑上的分枝數(shù)目稱為它的路徑長(zhǎng)度。
哈夫曼樹(shù)：WPL，哈夫曼碼
第五章：圖
概念：一個(gè)圖G由兩個(gè)集合V和E組成，V是有限的非空頂點(diǎn)集，E是用頂點(diǎn)對(duì)表示的邊集。
無(wú)向圖，有向圖；
鄰接，關(guān)聯(lián)，鄰接到（于），關(guān)聯(lián)于，孤立頂點(diǎn)。
頂點(diǎn)的度：圖G中關(guān)聯(lián)于頂點(diǎn)V的邊的數(shù)目稱為V的度。
所有頂點(diǎn)的度等于邊的兩倍。
子圖
完全圖：每對(duì)頂點(diǎn)之間都有一條邊相連的圖。在有向圖中，每對(duì)頂點(diǎn)之間都有兩條有向邊相互關(guān)聯(lián)的圖。
在無(wú)向完全圖中，邊的總數(shù)為Cn2=n（n-1）/2
在有向完全圖中，邊的總數(shù)為Pn2=n（n-1）
路徑：由邊組成。
回路
連通圖：對(duì)于無(wú)向圖，如果圖中任何兩頂點(diǎn)都是可達(dá)的，則稱此圖為連能圖。
對(duì)于有向圖，如果圖中任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，則此有向圖是強(qiáng)連通的，如果圖中任何兩頂點(diǎn)至少有一個(gè)頂點(diǎn)另一個(gè)頂點(diǎn)可達(dá)，則稱此有向圖是單向連通的。
強(qiáng)連通分量：有向圖的強(qiáng)連通子圖稱為它的強(qiáng)連通分量。 樹(shù)圖：其本質(zhì)特征是連通性和無(wú)圈性，把不含圈的無(wú)向連通圖稱為樹(shù)圖。
網(wǎng)絡(luò)：是每條邊上帶有數(shù)量指標(biāo)的連通圖。
鄰接矩陣，鄰接表
第六章 查找
查找：就是確定一個(gè)已給的數(shù)據(jù)是否出現(xiàn)在某個(gè)數(shù)據(jù)表中。
域（字段）：組成記錄的每個(gè)數(shù)據(jù)項(xiàng)。
關(guān)鍵字：通常記錄中總存在某個(gè)或某組數(shù)據(jù)項(xiàng)，它們的值能標(biāo)識(shí)一個(gè)記錄，這個(gè)（組）數(shù)據(jù)項(xiàng)稱為關(guān)鍵字。
方法：順序
二分
線性插值
分區(qū)
二叉排序樹(shù)：如果將記錄的鍵碼按二叉樹(shù)的結(jié)構(gòu)來(lái)組織，并且假定樹(shù)中任意非葉子結(jié)點(diǎn)的鍵碼大于其左子樹(shù)所有結(jié)點(diǎn)的鍵碼（若左子樹(shù)存在的話），而小于其右子樹(shù)所有結(jié)點(diǎn)的鍵碼（如右子樹(shù)存在的話），這樣的二叉樹(shù)叫二叉排序樹(shù)（二叉查找樹(shù)）。 哈 希查找：
哈希函數(shù)：能把關(guān)鍵字映射成記錄存貯地址的函數(shù)。
哈希表：假定數(shù)組HT[0··m-1]為存貯記錄的地址空間，哈希函數(shù)H以每個(gè)記錄的關(guān)鍵字值K作為輸入，產(chǎn)生一個(gè)落在[0··m-1]內(nèi)的整數(shù)H（K），并以它作為K所標(biāo)識(shí)的記錄在表HT中的地址或索引號(hào)，這樣產(chǎn)生的記錄表H（K）叫做 ··]
構(gòu)造哈希函數(shù)的方法：
直接定址法
除留余數(shù)法
平方取中法
折疊法與移位法
數(shù)字分析法
沖突處理：
開(kāi)放定址法： 1、線性探測(cè)法 2、偽隨機(jī)探測(cè)法
鏈地址法
第七章：排序
內(nèi)部排序：
外部排序：
內(nèi)部：冒泡 選擇 插入 歸并 堆排序 快速排序 基數(shù)
堆：每個(gè)非終端結(jié)點(diǎn)的關(guān)鍵字大于等于它的孩子結(jié)點(diǎn)的關(guān)鍵字
第八章：文件
基本概念
一、概念：
數(shù)據(jù)結(jié)構(gòu)：是一門研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。
數(shù)據(jù)：是描述額觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序加工處理的信息的集合。
數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。（一個(gè)數(shù)據(jù)項(xiàng)或多個(gè)數(shù)據(jù)項(xiàng)（域）。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。結(jié)點(diǎn)、頂點(diǎn)、記錄。
數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合。
數(shù)據(jù)結(jié)構(gòu)：研究是是數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存貯表示，并對(duì)每種結(jié)構(gòu)定義各自的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且經(jīng)過(guò)運(yùn)算后所得的新結(jié)構(gòu)一般仍然是原來(lái)的結(jié)構(gòu)類型。
數(shù)據(jù)類型：是指程序設(shè)計(jì)語(yǔ)言中各變量可取的數(shù)據(jù)種類。
算法：是執(zhí)行特定計(jì)算的有窮過(guò)程。特點(diǎn)：
·動(dòng)態(tài)有窮·確定性·輸入·輸出·可行性。
第二章 線性表和數(shù)組
概念：
一、線性表：是N個(gè)元素構(gòu)成的有限序列。
順序存貯結(jié)構(gòu)：地址計(jì)算，插入、刪除。
鏈?zhǔn)酱尜A結(jié)構(gòu)：?jiǎn)捂湵恚檎?、插入、刪除。
循環(huán)鏈表：
雙向鏈表：
二、數(shù)組：
以行為主；
以列為主；計(jì)算地址：
三、棧：是一種特殊的線性表，這種表只能在固定的一端進(jìn)行插入與刪除運(yùn)算。
隊(duì)列：是另一種特殊的線性表，刪除運(yùn)算限定在表的一端進(jìn)行，而插入運(yùn)算在另一端進(jìn)行。
第三章：串
概念：是由N個(gè)字符組成的有限序列。
存貯結(jié)構(gòu)：
順序表示法：
1、緊縮格式 2、非緊縮格式 3、以單字節(jié)為單位的存貯方式
鏈?zhǔn)奖硎痉ǎ?BR> 串名的存貯映象：
第四章：樹(shù)
一、概念：
樹(shù)：是一個(gè)或多個(gè)結(jié)點(diǎn)的有窮集合T，且滿足以下條件：
1、有且僅有一個(gè)指定的稱作樹(shù)根的結(jié)點(diǎn)；
2、除根以外的其余結(jié)點(diǎn)被分成m個(gè)不相交的集合，這些集合的每一個(gè)又都是樹(shù)，并且稱為根的子樹(shù)。
結(jié)點(diǎn)的度：結(jié)點(diǎn)N的子樹(shù)數(shù)稱為結(jié)點(diǎn)的度。
樹(shù)的度：樹(shù)T中各結(jié)點(diǎn)的度的值稱的樹(shù)T的度。
葉子：樹(shù)中度為0的結(jié)點(diǎn)稱為葉子（終端結(jié)點(diǎn)）。
分枝結(jié)點(diǎn)：樹(shù)中度不為0的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)（非終端結(jié)點(diǎn)）。
雙親和孩子：若樹(shù)中結(jié)點(diǎn)P的一棵子樹(shù)的根是結(jié)點(diǎn)C，則我們稱P是C的雙親或父母，反之稱C是P的孩子。
結(jié)點(diǎn)的層數(shù)：樹(shù)的層數(shù)為1，其余任一結(jié)點(diǎn)的層數(shù)等于它的雙親的層數(shù)加1.
樹(shù)的深度：樹(shù)中各結(jié)點(diǎn)的層數(shù)的值稱為T的深度（高度）。
兄弟和堂兄弟：同一雙親的孩子之間互稱為兄弟，其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。
祖先和子孫：一個(gè)點(diǎn)的祖先是指從樹(shù)的根到該結(jié)點(diǎn)所經(jīng)分枝上的所有結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。
有序樹(shù)和無(wú)序樹(shù)：如果樹(shù)中結(jié)點(diǎn)各棵子樹(shù)規(guī)定從左至右是有次序的，則稱樹(shù)為有序樹(shù)，否則為無(wú)序樹(shù)。
森林：N棵互不相交的樹(shù)的集合稱為森林。
二、樹(shù)的存貯表示：
1、雙親數(shù)組表示：記錄型一維數(shù)組：data，parent
2、孩子鏈表表示法：
·多重鏈表表示法： data，degree，link1，link2…
·單鏈表表示法：data，likn
3、左孩子右兄弟鏈表示法：lchild，data，rsibling
三、二叉樹(shù)：
1、概念：是有限個(gè)結(jié)點(diǎn)的集合，它或者為空集，或者是由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的且分別稱為根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。五種形態(tài)：空，根，左，右，左右 2、性質(zhì)：
·位于二叉樹(shù)第I層上的結(jié)點(diǎn)，最多為2I-1；（I）=1
·深度為K的二叉樹(shù)的結(jié)點(diǎn)總數(shù)，最多為2K-1（K）=1
·N0=N2+1
滿二叉樹(shù)：一棵深度為K的具有2K-1個(gè)結(jié)點(diǎn)的二叉樹(shù)
完全二叉樹(shù)：在一棵二叉樹(shù)中，若所有結(jié)點(diǎn)的度為0或?yàn)?的二叉樹(shù)
順序二叉樹(shù)：如果深度為K的具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，它的每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中順序編號(hào)是1到N的結(jié)點(diǎn)相對(duì)應(yīng)的二叉樹(shù)。
三、二叉樹(shù)的存貯表示：
1、順序存貯：
2、鏈表表示：lchild，data，rchlid
3、遍歷：
·前序：根—左—右
·中序：左—根—右
·后序：左—右—根
四、線索二叉樹(shù)：
五、樹(shù)的二叉樹(shù)表示，森林與二叉樹(shù)的轉(zhuǎn)換。
六、路徑長(zhǎng)度：樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之關(guān)的路徑由這兩個(gè)結(jié)點(diǎn)之間的分枝所構(gòu)成，路徑上的分枝數(shù)目稱為它的路徑長(zhǎng)度。
哈夫曼樹(shù)：WPL，哈夫曼碼
第五章：圖
概念：一個(gè)圖G由兩個(gè)集合V和E組成，V是有限的非空頂點(diǎn)集，E是用頂點(diǎn)對(duì)表示的邊集。
無(wú)向圖，有向圖；
鄰接，關(guān)聯(lián)，鄰接到（于），關(guān)聯(lián)于，孤立頂點(diǎn)。
頂點(diǎn)的度：圖G中關(guān)聯(lián)于頂點(diǎn)V的邊的數(shù)目稱為V的度。
所有頂點(diǎn)的度等于邊的兩倍。
子圖
完全圖：每對(duì)頂點(diǎn)之間都有一條邊相連的圖。在有向圖中，每對(duì)頂點(diǎn)之間都有兩條有向邊相互關(guān)聯(lián)的圖。
在無(wú)向完全圖中，邊的總數(shù)為Cn2=n（n-1）/2
在有向完全圖中，邊的總數(shù)為Pn2=n（n-1）
路徑：由邊組成。
回路
連通圖：對(duì)于無(wú)向圖，如果圖中任何兩頂點(diǎn)都是可達(dá)的，則稱此圖為連能圖。
對(duì)于有向圖，如果圖中任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，則此有向圖是強(qiáng)連通的，如果圖中任何兩頂點(diǎn)至少有一個(gè)頂點(diǎn)另一個(gè)頂點(diǎn)可達(dá)，則稱此有向圖是單向連通的。
強(qiáng)連通分量：有向圖的強(qiáng)連通子圖稱為它的強(qiáng)連通分量。 樹(shù)圖：其本質(zhì)特征是連通性和無(wú)圈性，把不含圈的無(wú)向連通圖稱為樹(shù)圖。
網(wǎng)絡(luò)：是每條邊上帶有數(shù)量指標(biāo)的連通圖。
鄰接矩陣，鄰接表
第六章 查找
查找：就是確定一個(gè)已給的數(shù)據(jù)是否出現(xiàn)在某個(gè)數(shù)據(jù)表中。
域（字段）：組成記錄的每個(gè)數(shù)據(jù)項(xiàng)。
關(guān)鍵字：通常記錄中總存在某個(gè)或某組數(shù)據(jù)項(xiàng)，它們的值能標(biāo)識(shí)一個(gè)記錄，這個(gè)（組）數(shù)據(jù)項(xiàng)稱為關(guān)鍵字。
方法：順序
二分
線性插值
分區(qū)
二叉排序樹(shù)：如果將記錄的鍵碼按二叉樹(shù)的結(jié)構(gòu)來(lái)組織，并且假定樹(shù)中任意非葉子結(jié)點(diǎn)的鍵碼大于其左子樹(shù)所有結(jié)點(diǎn)的鍵碼（若左子樹(shù)存在的話），而小于其右子樹(shù)所有結(jié)點(diǎn)的鍵碼（如右子樹(shù)存在的話），這樣的二叉樹(shù)叫二叉排序樹(shù)（二叉查找樹(shù)）。 哈 希查找：
哈希函數(shù)：能把關(guān)鍵字映射成記錄存貯地址的函數(shù)。
哈希表：假定數(shù)組HT[0··m-1]為存貯記錄的地址空間，哈希函數(shù)H以每個(gè)記錄的關(guān)鍵字值K作為輸入，產(chǎn)生一個(gè)落在[0··m-1]內(nèi)的整數(shù)H（K），并以它作為K所標(biāo)識(shí)的記錄在表HT中的地址或索引號(hào)，這樣產(chǎn)生的記錄表H（K）叫做 ··]
構(gòu)造哈希函數(shù)的方法：
直接定址法
除留余數(shù)法
平方取中法
折疊法與移位法
數(shù)字分析法
沖突處理：
開(kāi)放定址法： 1、線性探測(cè)法 2、偽隨機(jī)探測(cè)法
鏈地址法
第七章：排序
內(nèi)部排序：
外部排序：
內(nèi)部：冒泡 選擇 插入 歸并 堆排序 快速排序 基數(shù)
堆：每個(gè)非終端結(jié)點(diǎn)的關(guān)鍵字大于等于它的孩子結(jié)點(diǎn)的關(guān)鍵字
第八章：文件
基本概念