? 3.1 線性結(jié)構(gòu)

? ? ? ? 線性結(jié)構(gòu)：主要用于客觀世界中具有單一前驅(qū)和后繼的數(shù)據(jù)關(guān)系描述

? ? ? ? 3.1.1 線性表

? ? ? ? ? ? ? ? 線性表：是n個元素的有限序列庙洼，存在唯一的一個稱為第一個的元素；存在唯一的稱為最后一個的元素源内；除第一個外每個元素只有一個直接前驅(qū)老厌，除最后一個外瘟则，只有一個直接后繼

? ? ? ? ? ? ? ? 存儲結(jié)構(gòu)：順序存儲和鏈?zhǔn)酱鎯?/p>

? ? ? ? ? ? ? ? 順序存儲：用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素，從而使邏輯上相鄰的兩個元素在物理上也相鄰

? ? ? ? ? ? ? ? 鏈?zhǔn)酱鎯Γ和ㄟ^指針連接起來的結(jié)點(diǎn)來存儲數(shù)據(jù)元素梅桩，結(jié)點(diǎn)由數(shù)據(jù)域和指針域組成壹粟，數(shù)據(jù)域用于存儲數(shù)據(jù)元素的值，指針域則存儲當(dāng)前元素的直接前驅(qū)或直接后繼的位置信息

? ? ? ? 3.1.2 棧和隊列

? ? ? ? ? ? ? ? 棧：后進(jìn)先出的線性表宿百，只能通過訪問它的一端來實(shí)現(xiàn)數(shù)據(jù)存儲和檢索

? ? ? ? ? ? ? ? 棧的基本運(yùn)算：初始化棧趁仙、判棧空垦页、入棧雀费、出棧、讀取棧頂元素

? ? ? ? ? ? ? ? 隊列：先進(jìn)先出的線性表痊焊，隊尾插入元素盏袄，對頭刪除元素

? ? ? ? ? ? ? ? 隊列的基本運(yùn)算：初始化隊列、判隊空薄啥、入隊辕羽、出隊、讀隊頭元素? ? ?

? ? ? ? 3.1.3 串

? ? ? ? ? ? ? ? 串：僅由字符構(gòu)成的有限序列垄惧；

? ? ? ? ? ? ? ? 相關(guān)概念：空串刁愿、空格穿、子串到逊、串相等铣口、串比較

? ? ? ? ? ? ? ? 基本操作：賦值操作滤钱、連接操作、求串長脑题、串比較件缸、求子串

? ? ? ? ? ? ? ? 串的模式匹配：子串的定位操作

????3.2 數(shù)組/矩陣和廣義表

? ? ? ? 3.2.1 數(shù)組

? ? ? ? ? ? ? ? 數(shù)組：定長線性表在維數(shù)上的擴(kuò)展，即線性表中的元素又是一個線性表

? ? ? ? ? ? ? ? 特點(diǎn)：數(shù)目固定叔遂、元素類型相同他炊、上下標(biāo)關(guān)系具有上下界的約束且下標(biāo)有序

? ? ? ? ? ? ? ? 運(yùn)算：給定下標(biāo)存取相應(yīng)的數(shù)據(jù)元素、給定下標(biāo)修改相應(yīng)數(shù)據(jù)值? ? ? ? ? ? ? ??

? ? ? ? 3.2.2 矩陣

? ? ? ? ? ? ? ? 矩陣存儲時掏熬，為0的元素不分配存儲空間佑稠，不為0的元素分配存儲空間

? ? ? ? 3.2.3 廣義表? ? ? ?

? ? ? ? ? ? ? ? 廣義表是線性表的推廣，其元素可以是單元素旗芬，也可以是有結(jié)構(gòu)的表

????3.3 樹

? ? ? ? 3.3.1 樹與二叉樹的定義

? ? ? ? ? ? ? ? 樹的概念：雙親、孩子和兄弟捆蜀；度疮丛；葉子結(jié)點(diǎn)；內(nèi)部結(jié)點(diǎn)辆它；層次誊薄；高度；有序/無序樹

? ? ? ? 3.3.2 二叉樹的性質(zhì)與存儲結(jié)構(gòu)

????????????????二叉樹的性質(zhì)：二叉樹第i層上最多有2（i-1）個結(jié)點(diǎn)锰茉；高度為k的二叉樹最多有2（k）-1個節(jié)點(diǎn)呢蔫；對于任何一棵二叉樹，若其終端節(jié)點(diǎn)數(shù)為n0飒筑，度為2的節(jié)點(diǎn)數(shù)為n2片吊，n0=n2+1；具有n個節(jié)點(diǎn)的完全二叉樹的深度為log2n+1

? ? ? ? ? ? ? ? 二叉樹的存儲：完全二叉樹適用于順序存儲协屡、鏈?zhǔn)酱鎯m用于一般二叉樹

? ? ? ? 3.3.3 二叉樹的遍歷

? ? ? ? ? ? ? ? 遍歷：先序俏脊、中序、后序（以根結(jié)點(diǎn)的遍歷位置來定）

? ? ? ? 3.3.4 線索二叉樹

? ? ? ? 3.3.5 最優(yōu)二叉樹

? ? ? ? ? ? ? ? 最優(yōu)二叉樹：哈夫曼樹肤晓，帶權(quán)路徑長度最短的樹

? ? ? ? ? ? ? ? 樹的路徑長度：樹根到每個葉子結(jié)點(diǎn)的路徑長度之和

? ? ? ? ? ? ? ? 帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和

? ? ? ? ? ? ? ? 哈夫曼編碼：

? ? ? ? 3.3.6 樹與森林

? ? ? ? ? ? ? ? 樹的存儲結(jié)構(gòu)：雙親表示法爷贫、孩子表示法、孩子兄弟表示法

????3.4 圖

? ? ? ? 3.4.1 圖的定義與存儲

? ? ? ? ? ? ? ? 圖：由頂點(diǎn)和邊組成的數(shù)據(jù)結(jié)構(gòu)

? ? ? ? ? ? ? ? 圖的概念：有向圖补憾、無向圖漫萄、完全圖、度盈匾、出度腾务、入度、路徑威酒、子圖窑睁、連通圖與連通分量挺峡、強(qiáng)連通圖與強(qiáng)連通分量、網(wǎng)担钮、有向樹

? ? ? ? ? ? ? ? 圖的存儲：鄰接矩陣表示法橱赠、鄰接鏈表表示法

? ??????????????鄰接矩陣表示法：用一個矩陣來表示圖中頂點(diǎn)之間的關(guān)系

? ? ? ? ? ? ? ? 鄰接鏈表表示法：為圖的頂點(diǎn)建立一個單鏈表，第i個單鏈表的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊

? ? ? ? 3.4.2 圖的遍歷

? ? ? ? ? ? ? ? 圖的遍歷：深度優(yōu)先搜索箫津、廣度優(yōu)先搜索

? ??????????????深度優(yōu)先搜索：設(shè)置指針p指向頂點(diǎn)v狭姨；訪問p所指頂點(diǎn)，并使p指向與其向鄰接的且尚未被訪問的頂點(diǎn)苏遥；若p存在重復(fù)上一步饼拍，若不存在則沿剛才的次序方向回溯到一個未被訪問的頂點(diǎn)，使p指向該頂點(diǎn)田炭，重復(fù)师抄，直到所有的頂點(diǎn)均被訪問

? ??????????????廣度優(yōu)先搜索：從某一頂點(diǎn)出發(fā)，在訪問該頂點(diǎn)后訪問與之相鄰的頂點(diǎn)教硫，直到所有頂點(diǎn)均被訪問

? ? ? ? 3.4.3 生成樹及最小生成樹

? ? ? ? ? ? ? ? 生成樹：對于有n個頂點(diǎn)的連通圖叨吮，至少有n-1條邊，而生成樹中恰好有n-1條邊瞬矩，所以連通圖的生成樹是該圖的極小連通子圖茶鉴，生成樹不唯一

? ? ? ? ? ? ? ? 最小生成樹：對于連通網(wǎng)來說，邊是帶權(quán)值的景用，生成樹的各邊也帶權(quán)值涵叮，因此將生成樹的各邊的權(quán)值總和成為生成樹的權(quán)，把權(quán)值最小的的生成樹成為最小生成樹

? ? ? ? ? ? ? ? 最小生成樹的求解算法：普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法

? ??????????????普里姆（Prim）算法：以一個頂點(diǎn)集合U={u0}作為初態(tài)伞插，不斷尋找與U中頂點(diǎn)相鄰且代價最小的邊的另一個頂點(diǎn)割粮，擴(kuò)充U集合直到U=V時為止。

? ??????????????克魯斯卡爾（Kruskal）算法：假設(shè)連通圖N=(V蜂怎，E)穆刻，另最小生成樹的初始狀態(tài)是只有n個頂點(diǎn)而無邊的非連通圖T=(T,{})，圖中每個頂點(diǎn)自成一個連通分量杠步，在E中選擇代價最小的邊氢伟，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中幽歼，否則舍去此邊而選擇下一條代價最小的邊朵锣，以此類推，直到T中所有的頂點(diǎn)都在同一連通分量上分支

? ? ? ? 3.4.4 拓?fù)渑判蚺c關(guān)鍵路徑

? ? ? ? ? ? ? ? AOV網(wǎng)：在有向圖中甸私，以頂點(diǎn)表示活動诚些，用有向邊表示活動之間的優(yōu)先關(guān)系的網(wǎng)，AOV網(wǎng)中不應(yīng)出現(xiàn)有環(huán)（Activity On Vertex Network）

? ? ? ? ? ? ? ? 拓?fù)渑判颍菏茿OV網(wǎng)中的所有頂點(diǎn)排成一個線性序列的過程，并且該序列滿足：若在AOV網(wǎng)中诬烹，從頂點(diǎn)vi到vj有一條路徑砸烦，則在該線性序列中，頂點(diǎn)vi必然在vj之前

? ? ? ? ? ? ? ? AOE網(wǎng)：若在帶權(quán)有向圖G中以頂點(diǎn)表示時間绞吁，以有向邊表示活動幢痘，一邊上的權(quán)值表示活動持續(xù)的時間(Activity On Edge Network)。

? ? ? ? ? ? ? ? 關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的路徑中家破，長度最長的路徑

? ? ? ? ? ? ? ? 關(guān)鍵活動：關(guān)鍵路徑上的所有活動

? ? ? ? 3.4.5 最短路徑? ? ? ??

? ? ? ? ? ? ? ? 單源點(diǎn)最短路徑：指給定帶權(quán)有向圖G和源點(diǎn)V0颜说，求從v0到G中其余各頂點(diǎn)的最短路徑（迪杰斯特拉算法）

? ? ? ? ? ? ? ? 每隊頂點(diǎn)間的最短路徑：若每次以一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行上述算法n次汰聋，便可得到網(wǎng)中每一對頂點(diǎn)之間的最短路徑（弗洛伊德算法）

????3.5 查找

? ? ? ? 3.5.1 查找的基本概念

? ? ? ? ? ? ? ? 查找表（動態(tài)门粪、靜態(tài)）、關(guān)鍵字烹困、平均查找長度

? ? ? ? 3.5.2 靜態(tài)查找表的查找方法

? ??????????????順序查找：從表的一端開始玄妈、逐個將記錄的關(guān)鍵字和給定值比較，若匹配則查找成功韭邓，若一直未找到措近，則失敗女淑；查找長度：（n+1）/2

????????????????折半查找：對于有序序列，首先將查找元素的關(guān)鍵字值與表中間位置上記錄的關(guān)鍵字進(jìn)行比較辜御，若成功鸭你，則查找成功，若key>中間值擒权，則說明待查記錄只可能在后半個子表中袱巨，下一步應(yīng)該在后半個子表中進(jìn)行查找，key<中間值類似碳抄；查找長度log2(n+1)-1

? ? ? ? ? ? ? ? 分塊查找：首先將表分成若干塊愉老，每一塊的關(guān)鍵字不一定有序，但塊之間是有序的剖效，即后一塊的記錄大于前一塊的記錄嫉入，此外還建立了索引表；查找過程分兩步：第一步在索引表中確定待查記錄所在的快璧尸，第二步在塊中順序查找查找長度（n/s+s）/2+1

? ? ? ? 3.5.3 動態(tài)查找表

? ? ? ? ? ? ? ? 動態(tài)查找表：表格結(jié)構(gòu)本身在查找過程中動態(tài)生成

? ? ? ? ? ? ? ? 二叉排序樹：又稱為二叉查找樹咒林，若左子樹非空，則均小于根結(jié)點(diǎn)爷光，若右子樹非空垫竞，則均大于根結(jié)點(diǎn)，左右子樹本身為二叉排序樹

? ??????????????二叉排序樹查找：二叉排序樹非空時蛀序，將給定值與根結(jié)點(diǎn)的值進(jìn)行比較欢瞪，若成功活烙，這查找成功，若不成功遣鼓，視其與根結(jié)點(diǎn)的比較選擇查找范圍啸盏，若一直未查找成功，則失敗

? ? ? ? ? ? ? ? 平衡二叉樹：左右子樹均為平衡二叉樹譬正；左右子樹的高度差不超過1

? ? ? ? ? ? ? ? m_樹：樹中每個節(jié)點(diǎn)最多有m棵子樹宫补；若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則最少有兩棵子樹曾我；除根結(jié)點(diǎn)外的所有非終端節(jié)點(diǎn)最少有m/2棵子樹粉怕；所有非終端節(jié)點(diǎn)包含指向子樹根結(jié)點(diǎn)的指針，關(guān)鍵字和節(jié)點(diǎn)中關(guān)鍵字的個數(shù)抒巢；所有葉子結(jié)點(diǎn)均出現(xiàn)在同一層贫贝，并且不帶信息。

? ? ? ? 3.5.4 哈希表? ? ? ??

? ? ? ? ? ? ? ? 哈希表比較方式：通過計算一個以記錄的關(guān)鍵字為自變量的函數(shù)蛉谜，來得到該記錄的存儲地址稚晚，所以在哈希表中進(jìn)行查找操作時，需要同一哈希函數(shù)計算得到待查記錄的存儲地址型诚，然后到相應(yīng)的儲存單元去獲得有關(guān)信息再判定查找是否成功

? ? ? ? ? ? ? ? 哈希函數(shù)的構(gòu)造方法：直接定址法客燕、數(shù)據(jù)分析發(fā)、平方取中法狰贯、折疊法也搓、隨機(jī)數(shù)法和除留余數(shù)法

? ? ? ? ? ? ? ? 解決沖突的方法：開放地址法

? ? ? ? ? ? ? ? 哈希表查找：哈希表查找時，用與存入元素時相同的哈希函數(shù)和沖突處理方法計算得到待查記錄的儲存地址涵紊，然后到相應(yīng)的存儲單元獲得有關(guān)信息在判定查找是否成功傍妒；雖然哈希表在關(guān)鍵字和記錄的存儲位置之間監(jiān)理了直接映射，但由于沖突的產(chǎn)生摸柄，該過程仍然是一個給定值和關(guān)鍵字進(jìn)行比較的過程颤练；比較關(guān)鍵字的個數(shù)取決于哈希函數(shù)、處理沖突的方法和哈希表的裝填因子

????3.6 排序

????????3.6.1 排序的基本概念

? ? ? ? ? ? ? ? 內(nèi)部排序：待排記錄全部存在內(nèi)存中進(jìn)行排序的過程

? ? ? ? ? ? ? ? 外部排序：排序過程中需要對外存進(jìn)行訪問的排序過程

????????3.6.2 簡單排序

? ? ? ? ? ? ? ? 直接插入排序：在插入第i個記錄時驱负，原記錄已經(jīng)排好序嗦玖，這時將該記錄插入到對應(yīng)位置上，然后其后的記錄向后移動

? ? ? ? ? ? ? ? 冒泡排序：首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進(jìn)行比較电媳，若出現(xiàn)逆序這交換這兩個記錄的值踏揣，然后比較第二個記錄和第三個記錄的關(guān)鍵字，以此類推匾乓，直到所有的記錄比較完畢為止捞稿，此時最大的記錄被交換到第n個記錄的位置上，然后進(jìn)行第二趟冒泡排序，對前面的n-1個記錄進(jìn)行重復(fù)操作娱局。時間復(fù)雜度n2

? ? ? ? ? ? ? ? 簡單選擇排序：通過n-i在次關(guān)鍵字之間的比較彰亥，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄進(jìn)行交換衰齐，當(dāng)i等于n時所有記錄有序排列

????????3.6.3 希爾排序

? ? ? ? ? ? ? ? 基本思想：現(xiàn)將整個待排記錄序列分割成若干個子序列任斋，然后分別進(jìn)行直接插入排序，待整個序列中的記錄基本有序時耻涛，再對全體記錄進(jìn)行一次直接插入排序

????????3.6.4 快速排序

????????????????基本思想：通過一趟排序?qū)⒋诺挠涗泟澐殖瑟?dú)立的兩部分废酷，成為前半?yún)^(qū)和后半?yún)^(qū)，其中抹缕，前半?yún)^(qū)記錄的關(guān)鍵字均不大于后半?yún)^(qū)記錄的關(guān)鍵字澈蟆，然后分別對著兩部分記錄繼續(xù)進(jìn)行快速排序，從而使整個排列有序? ? ? ? ? ? ? ??

????????3.6.5 堆排序

? ? ? ? ? ? ? ? 基本思想：對一組待排序記錄的關(guān)鍵字卓研，首先按堆的定義排列成一個序列趴俘，從而可以輸出堆頂?shù)淖畲箨P(guān)鍵字，然后將剩余的關(guān)鍵字在調(diào)整成新堆奏赘，便得到次大的關(guān)鍵字寥闪，如此反復(fù)，直到全部關(guān)鍵字排成有序序列為止

????????3.6.6 歸并排序

? ? ? ? ? ? ? ? 歸并：將兩個或兩個以上的有序文件合并成一個新的有序文件

? ? ? ? ? ? ? ? 實(shí)現(xiàn)方法：將一個有n個記錄的無序文件看成是由n個長度為1的有序子文件組成的文件磨淌，然后進(jìn)行兩兩歸并疲憋，得到n/2個長度為2或者1的有序文件，在歸并梁只，重復(fù)柜某，知道最后形成包含n個記錄的有序文件為止?

????????3.6.7 基數(shù)排序

? ? ? ? ? ? ? ? 基本思想：設(shè)立r個隊列，隊列編號分別為0......r-1敛纲，首先按最低有效位的值把n個關(guān)鍵字分配到這r個隊列中，然后按照隊列編號從小到大將各隊列中的關(guān)鍵字依次收集起來剂癌，接著在依次低有效位的值把剛收集起來的關(guān)鍵字分配到r個隊列中淤翔；重復(fù)以上步驟，知道按照最高有效為分配和收集佩谷，這樣就得到一個從小大道有序的關(guān)鍵字序列旁壮。

????????3.6.8 內(nèi)部排序方法小結(jié)

????????????????若排序的記錄數(shù)目n較小，可采用直接插入排序和簡單選擇排序

? ? ? ? ? ? ? ? 若待排序記錄按照關(guān)鍵字基本有序谐檀，宜采用直接插入排序或冒泡【】排序

? ? ? ? ? ? ? ? 若n很大且關(guān)鍵字的位數(shù)較少時抡谐，采用鏈?zhǔn)交鶖?shù)排序較好

? ? ? ? ? ? ? ? 若n較大，則因采用時間復(fù)雜度少的排序方法桐猬，快速排序麦撵、堆排序或歸并排序

? ? ? ? 3.6.9 外部排序

? ? ? ? ? ? ? ? 外部排序就是對大型文件的排序，待排序的記錄存放在外存。在排序過程中內(nèi)存只存儲文件的一部分記錄免胃，整個排序過程需要進(jìn)行多次內(nèi)外存間的數(shù)據(jù)交換

? ? ? ? ? ? ? ? 一般采用歸并排序音五，分兩個階段：第一個階段，把文件中的記錄分段讀入內(nèi)存羔沙，利用某種內(nèi)部排序方法對記錄段進(jìn)行排序并輸出到外存的另一個 文件中躺涝，在新文件中形成許多有序的記錄段，成為歸并段扼雏；第二階段坚嗜，對第一階段形成的歸并段用某種歸并方法進(jìn)行一趟趟的歸并，使文件的有序段逐漸加長诗充，直到將整個文件歸并為一個有序段時為止