數(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頁(yè)，當(dāng)前為第1頁(yè)。第一章緒論A數(shù)據(jù)結(jié)構(gòu)研究對(duì)象信息數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對(duì)象數(shù)據(jù)類型B數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(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ī)格描述（語(yǔ)法、語(yǔ)義）抽象數(shù)據(jù)型的實(shí)現(xiàn)抽象數(shù)據(jù)型的優(yōu)點(diǎn)多層次抽象技術(shù)E算法什么叫算法？算法的特征“好”的算法的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)算法的正確性的要求算法的描述類語(yǔ)言F算法分析算法的時(shí)間特性時(shí)間復(fù)雜度T(n)空間復(fù)雜度S(n)數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁(yè)，當(dāng)前為第2頁(yè)。①Insert(x,p,L)②Locate(x,L)③Retrieve(p,L)④Delete(p,L)⑤Previous(p,L),Next(p,L)⑥MakeNull(L)⑦First(L)①M(fèi)akeNull(S)②Top(S)③Pop(S)④Push(x,S)⑤Empty(S)①M(fèi)akeNull(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（）；建立一個(gè)空數(shù)組②Retrieve（array，index）；返回第index個(gè)元素③

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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ù)—當(dāng)記錄很大時(shí)，是主要因素。數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁(yè)，當(dāng)前為第15頁(yè)。各種排序的比較排序方法平均時(shí)間最好情況最壞情況輔助空間穩(wěn)定性簡(jiǎ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)平均時(shí)間性能；(2)當(dāng)序列“基本有序”時(shí)，簡(jiǎn)單排序中的插入排序最佳；(3)基數(shù)排序適用于n值很大而關(guān)鍵字較小的序列；(4)穩(wěn)定性以基數(shù)排序?yàn)樽罴眩粩?shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁(yè)，當(dāng)前為第16頁(yè)。算法簡(jiǎn)單性比較：從算法簡(jiǎn)單性看，一類是簡(jiǎn)單算法，包括直接插入排序、直接選擇排序和起泡排序；另一類是改進(jìn)后的算法，包括希爾排序、堆排序、快速排序和歸并排序，這些算法都很復(fù)雜。待排序的記錄個(gè)數(shù)比較：從待排序的記錄個(gè)數(shù)n的大小看n越小，采用簡(jiǎn)單排序方法越合適；n越大，采用改進(jìn)的排序方法越合適。因?yàn)閚越小，O(n2)同O(nlog2n)的差距越小，并且輸入和調(diào)試簡(jiǎn)單算法比輸入和調(diào)試改進(jìn)算法要少用許多時(shí)間。關(guān)鍵字值的分布情況比較當(dāng)待排序記錄按關(guān)鍵的值有序時(shí)，插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度；對(duì)于快速排序而言，這是最壞的情況，此時(shí)的時(shí)間性能蛻化為O(n2)；選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)據(jù)結(jié)構(gòu)-總結(jié)全文共23頁(yè)，當(dāng)前為第17頁(yè)。不同條件下，排序方法的選擇：

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

當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序?yàn)橐恕?/p>

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

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

快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(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頁(yè)，當(dāng)前為第18頁(yè)。第七章外部排序（分類）B磁盤文件的歸并分類

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

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

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

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

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

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

在k

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

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

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