數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)

《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》課程回顧與總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第1頁。第一章緒論A數(shù)據(jù)結(jié)構(gòu)研究對象信息數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對象數(shù)據(jù)類型B數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)分類C數(shù)據(jù)結(jié)構(gòu)發(fā)展概況D抽象數(shù)據(jù)型(ADT)

數(shù)據(jù)型、數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)型抽象數(shù)據(jù)型的規(guī)格描述（語法、語義）抽象數(shù)據(jù)型的實現(xiàn)抽象數(shù)據(jù)型的優(yōu)點多層次抽象技術(shù)E算法什么叫算法？算法的特征“好”的算法的評價標(biāo)準(zhǔn)對算法的正確性的要求算法的描述類語言F算法分析算法的時間特性時間復(fù)雜度T(n)空間復(fù)雜度S(n)數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第2頁。①Insert(x,p,L)②Locate(x,L)③Retrieve(p,L)④Delete(p,L)⑤Previous(p,L),Next(p,L)⑥MakeNull(L)⑦First(L)①MakeNull(S)②Top(S)③Pop(S)④Push(x,S)⑤Empty(S)①MakeNull(Q)②Front(Q)③EnQueue(x,Q)④DeQueue(Q)⑤Empty(Q)①Empty(BT);②IsEmpty(BT);③CeeateBT(V,LT,RT);④Lchild(BT);⑤Rchild(BT);⑥D(zhuǎn)ata(BT);①NodeNewNode(G,v)②VoidDelNode(G,v)③VoidSetSucc(G,v1,v2)④VoidDelSucc(G,v1,v2)⑤ListofnodeSucc(G,v)⑥LisyofnodePred(G,v)⑦IntIsEdge(G,v1,v2)⑧NodeFirstAdjVex(G,v)⑨NodeNextAdjVex(G,v,w)①stringNULL();②booleanIsNull(S);③VoidIn(S,a);④intLen(S);⑤VoidConcat(S1,S2);⑥stringSubstr(S,m,n);⑦booleanIndex(S,S1);①Create（）；建立一個空數(shù)組②Retrieve（array，index）；返回第index個元素③

Store（array，index，value）；在數(shù)組array中，為第index個元素賦值value數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第3頁。第二章線性表A線性表的概念什么叫線性表抽象數(shù)據(jù)型線性表B線性表的實現(xiàn)靜態(tài)數(shù)據(jù)結(jié)構(gòu)動態(tài)數(shù)據(jù)結(jié)構(gòu)順序存儲（數(shù)組實現(xiàn)）鏈?zhǔn)酱鎯Γㄖ羔槪┯螛?biāo)（靜態(tài)鏈表）C線性鏈表表頭結(jié)點單向鏈表雙向鏈表單向循環(huán)量表雙向循環(huán)鏈表D限定性數(shù)據(jù)結(jié)構(gòu)：棧&隊列E棧棧的概念A(yù)DT棧棧的存儲結(jié)構(gòu)棧的應(yīng)用:棧與遞歸迷宮求解表達(dá)式轉(zhuǎn)換與求值F隊列隊列的概念A(yù)DT隊列隊列的存儲結(jié)構(gòu)循環(huán)隊列G線性表的應(yīng)用：多項式的表示多項式相加運算數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第4頁。H串串的基本概念A(yù)DT串串的存儲結(jié)構(gòu)存儲密度I數(shù)組數(shù)組的概念A(yù)DT數(shù)組數(shù)組的存儲結(jié)構(gòu)數(shù)組的壓縮存儲：特殊矩陣、對角或帶狀矩陣、稀疏矩陣J廣義表基本概念廣義表的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第5頁。第三章樹與二叉樹A樹的基本術(shù)語樹子樹結(jié)點分支度路葉子非終結(jié)（端）結(jié)點終結(jié)（端）結(jié)點兒子父親兄弟堂兄弟祖先子孫結(jié)點；層高度（深度）結(jié)點的順序?qū)有蛴行驑錈o序樹森林B二叉樹二叉樹的定義，ADT二叉樹，滿二叉樹，完全二叉樹二叉樹的遍歷：先序遍歷、中序遍歷和后序遍歷，層序遍歷二叉樹遍歷的非遞歸算法（先序、中序和后序）二叉樹的性質(zhì)：（1～5）二叉樹的存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)酱鎯Γǘ骀湵恚┚€索二叉樹：基本概念，先序、中序與后序線索求線索二叉樹的（先序、中序、后序）前驅(qū)與后繼結(jié)點線索二叉樹的遍歷線索二叉樹中插入、刪除結(jié)點的討論性質(zhì)1：在二叉樹中的第i層的結(jié)點數(shù)最多為：2i-1。性質(zhì)2：高度為k的二叉樹其結(jié)點總數(shù)最多為2k－1(k≥1)

。性質(zhì)3：對任意的非空二叉樹T

，如果葉結(jié)點的個數(shù)為n0，而其度為2

的結(jié)點數(shù)為n2，則：n0=n2+1

。性質(zhì)4：具有n

個結(jié)點的完全二叉樹的深度為log2n+1。性質(zhì)5：如果對一棵有n個結(jié)點的二叉樹的結(jié)點按層序編號，則對任一結(jié)點i有：

⑴如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i＞1，則其雙親結(jié)點是i/2；

⑵如果2i＞n，則結(jié)點i無左孩子結(jié)點，否則其左孩子結(jié)點是2i；

⑶如果2i+1＞n，則結(jié)點i無右孩子結(jié)點，否則其右孩子結(jié)點是2i+1。數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第6頁。D樹

ADT樹樹的存儲結(jié)構(gòu)：雙親表示法，孩子表示法（鄰接表），樹的左右鏈表示樹與二叉樹的轉(zhuǎn)換，森林與二叉樹的轉(zhuǎn)換樹的遍歷：先序、中序和后序遍歷樹E樹的應(yīng)用用樹表示集合、判定樹、哈夫曼樹及其應(yīng)用、最優(yōu)編碼C二叉樹的相似與等價，二叉樹的復(fù)制算法數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第7頁。第四章圖以及與圖有關(guān)的算法A圖的基本概念圖的定義ADT圖有向圖無向圖弧邊頂點鄰接點相鄰依附環(huán)路權(quán)子圖帶標(biāo)號的圖（網(wǎng)）路徑簡單路徑連通圖強(qiáng)連通圖連通分量強(qiáng)連通分量完全圖稀疏圖稠密圖度入度出度生成樹B圖的表示（存儲結(jié)構(gòu)）：鄰接矩陣鄰接表C圖的遍歷（搜索）算法：先深搜索（DFS）先廣搜索（BFS）D圖與樹的關(guān)系生成樹先深生成森林先廣生成森林樹邊與回退邊開放樹最小生成樹及其算法（MST性質(zhì)、Prim、Kruskal算法）E無向圖的雙連通性關(guān)結(jié)點雙連通圖雙連通分量F有向圖的搜索生成樹生成森林如何區(qū)別樹邊、向前邊、回退邊和橫邊G強(qiáng)連通性：強(qiáng)連通分量，歸約圖，圖的中心點的概念及求解方法數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第8頁。H拓?fù)浞诸愑邢驘o環(huán)圖及其應(yīng)用拓?fù)浞诸愅負(fù)浞诸愃惴↖關(guān)鍵路徑

AOE網(wǎng)AOV網(wǎng)事件活動路徑長度關(guān)鍵活動關(guān)鍵路徑

AOE網(wǎng)問題：(1)完成整個工程至少需要多少時間？

(2)哪些活動是影響工程進(jìn)度的關(guān)鍵活動？關(guān)鍵路徑算法中的關(guān)鍵變量：①事件Vj

的最早可能發(fā)生時間VE(j)；②活動ai

的最早可能開始時間E(k)；③事件Vk的最遲發(fā)生時間VL(k)；④活動ai

的最遲允許開始時間L(i)；⑤時間余量L(i)-E(i)。J最短路徑問題單源最短路徑：Dijkstra算法任意頂點間的最短路徑：Floyd算法、Warshall算法數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第9頁。B線性查找C折半查找：條件D分快查找EAVL樹FB-樹B+樹G二叉查找樹：什么叫二叉查找樹、插入結(jié)點、刪除結(jié)點、查找結(jié)點H散列法：哈稀函數(shù)沖突哈希表的長度哈希函數(shù)：直接定址法質(zhì)數(shù)除余法平方取中法折疊法數(shù)字分析法隨機(jī)法處理沖突：開放定址法（線性探測、二次探測）再散列法鏈地址法建立公共溢出區(qū)第五章查找A基本概念查找（檢索）查找表關(guān)鍵字靜態(tài)查找動態(tài)查找平均查找長度數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第10頁。二次探測法再散列法鏈地址法線性探測法查找失敗（插入記錄）查找成功處理沖突方法L幾種處理沖突方法的平均查找長度裝填因子α標(biāo)志著哈希表的裝滿程度，α越小，發(fā)生沖突的可能性越小，反之，發(fā)生沖突的可能性越大。J成功查找平均查找長度：ASLs

查找到散列表中已存在結(jié)點的平均比較次數(shù)。K失敗查找平均查找長度：ASLu

查找失敗，但找到插入位置的平均比較次數(shù)。I裝填因子：α=表中裝入的記錄數(shù)哈希表的長度數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第11頁。查找分塊查找折半查找線性查找地址散列法/哈希表檢索平衡二叉樹/AVL樹減小二叉樹的高度，提高查找效率m-路查找樹增加寬度，減小高度，減少讀盤次數(shù)平衡樹B-/B+樹平衡m-路查找樹/BalancedTree二叉查找樹/二叉排序樹/二叉檢索樹動態(tài)查找理解概念掌握結(jié)構(gòu)閱讀算法數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第12頁?！?14112114522525824828^………5112522828^5522^數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第13頁。redis和levelDB都是用了它；他在有序鏈表的基礎(chǔ)上進(jìn)行擴(kuò)展；解決了有序鏈表結(jié)構(gòu)查找特定值困難的問題；查找特定值的時間復(fù)雜度為O(logn)；一種可以代替平衡樹的數(shù)據(jù)結(jié)構(gòu)；SkipList又稱跳躍表簡稱跳表數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第14頁。C簡單的分類算法：氣泡排序插入排序冒泡（選擇）排序

O(n2)DShell分類：縮小增量法E快速分類:快速分類的遞歸算法與非遞歸算法F歸并分類G堆分類：堆的概念整理堆的算法H基數(shù)分類（多關(guān)鍵字）第六章內(nèi)部排序（分類）A排序（分類）排序內(nèi)部排序外部排序穩(wěn)定與不穩(wěn)定的排序方法B影響分類性能的因素：比較關(guān)鍵字的次數(shù)—當(dāng)關(guān)鍵字是字符串時，是主要因素；交換記錄位置和移動記錄的次數(shù)—當(dāng)記錄很大時，是主要因素。數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第15頁。各種排序的比較排序方法平均時間最好情況最壞情況輔助空間穩(wěn)定性簡單排序O(n2)O（n）O(n2)O(1)穩(wěn)定希爾排序O（n1.3）------O(1)不穩(wěn)定快速排序O(n·log2n)O(n·log2n)O(n2)O(1)不穩(wěn)定堆排序O(n·log2n)O(n·log2n)O(n·log2n)O(1)不穩(wěn)定歸并排序O(n·log2n)O(n·log2n)O(n·log2n)O(n)穩(wěn)定基數(shù)排序O(d·(n+r·d))O(d·(n+r·d))O(d·(n+r·d))O(n+r·d)穩(wěn)定分析：(1)平均時間性能；(2)當(dāng)序列“基本有序”時，簡單排序中的插入排序最佳；(3)基數(shù)排序適用于n值很大而關(guān)鍵字較小的序列；(4)穩(wěn)定性以基數(shù)排序為最佳；數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第16頁。算法簡單性比較：從算法簡單性看，一類是簡單算法，包括直接插入排序、直接選擇排序和起泡排序；另一類是改進(jìn)后的算法，包括希爾排序、堆排序、快速排序和歸并排序，這些算法都很復(fù)雜。待排序的記錄個數(shù)比較：從待排序的記錄個數(shù)n的大小看n越小，采用簡單排序方法越合適；n越大，采用改進(jìn)的排序方法越合適。因為n越小，O(n2)同O(nlog2n)的差距越小，并且輸入和調(diào)試簡單算法比輸入和調(diào)試改進(jìn)算法要少用許多時間。關(guān)鍵字值的分布情況比較當(dāng)待排序記錄按關(guān)鍵的值有序時，插入排序和起泡排序能達(dá)到O(n)的時間復(fù)雜度；對于快速排序而言，這是最壞的情況，此時的時間性能蛻化為O(n2)；選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第17頁。不同條件下，排序方法的選擇：

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。

當(dāng)記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。

(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序為宜；且以直接插入排序最佳。

(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時，快速排序的平均時間最短；堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞況。這兩種排序都是不穩(wěn)定的?；鶖?shù)排序適用于n值很大而關(guān)鍵字較小的序列。若要求排序穩(wěn)定，則可選用歸并排序，基數(shù)排序穩(wěn)定性最佳。數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第18頁。第七章外部排序（分類）B磁盤文件的歸并分類

(1)多路歸并——減少歸并遍數(shù)

(2)并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可能重疊

(3)初始?xì)w并段的生成

m個初始段進(jìn)行2路歸并，需要log2m

遍歸并；一般地，m個初始段，采用k路歸并，需要logkm

遍歸并。顯然，k越大，歸并遍數(shù)越少，可提高歸并的效率。

在k

路歸并時，從k個關(guān)鍵字中選擇最小記錄時，要比較K-1次。若記錄總數(shù)為n，每遍要比較的次數(shù)為：n*(k-1)[log2m/log2k]

選擇樹或敗者樹，k路歸并時間O(n·log2m)，與k無關(guān)。A歸并方法：首先將文件中的數(shù)據(jù)輸入到內(nèi)存，采用內(nèi)部分類方法進(jìn)行分類（歸并段），然后將有序段寫回外存；對多歸并段（已有序）進(jìn)行多遍合并（歸并），最后形成一個有序序列。C磁帶文件的歸并分類：k路平衡歸并分類。數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第19頁。第八章文件A文件及文件操作文件的概念關(guān)鍵字主關(guān)鍵字次關(guān)鍵字文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)文件的操作：InsertDeleteModifyRetrieve

檢索方式：實時or成批更新方式：實時or成批查詢方式：Q1:簡單查詢，Q2:范圍查詢，Q3:函數(shù)查詢，Q4:布爾查詢B文件的組織順序方式，索引方式，散列方式，鏈接方式，倒排方式數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁，當(dāng)前為第20頁。復(fù)習(xí)時注意幾個問題知識的連貫性：認(rèn)真讀書、尊重教材、要注意參考其它教材注意基本概念：名詞的理解、問題的研究對象算法：（1）遍歷算法（線性表、樹與二叉樹、圖）；（