幾種常見(jiàn)的重要數(shù)據(jù)結(jié)構(gòu)總結(jié)

棧的表示

1. 數(shù)組

2. 鏈表（優(yōu)點(diǎn)：無(wú)需指定大小，不存在棧溢出等情況的處理）

隊(duì)列表示

1. 數(shù)組（構(gòu)造成循環(huán)隊(duì)列以提高空間使用效率）

2. 鏈表

二叉樹(shù) （滿二叉樹(shù)、完全二叉樹(shù)、稀疏二叉樹(shù)等）

1. 數(shù)組（二叉樹(shù)按照層次編號(hào)，空缺的孩子結(jié)點(diǎn)也要保留編號(hào)，這使得當(dāng)二叉樹(shù)比較稀疏時(shí)，空間利用率很低）

2. 鏈表（二叉鏈表（三個(gè)域：左孩子，右孩子和結(jié)點(diǎn)的值），三叉鏈表（多一個(gè)父結(jié)點(diǎn)的指針，解決了找祖先結(jié)點(diǎn)困難的問(wèn)題））

樹(shù)

1. 廣義表

廣義表是一個(gè)n個(gè)表元素組成的有限序列，表元素或者是數(shù)據(jù)元素（atom），或者是子表（sublist），一個(gè)廣義表的元素結(jié)構(gòu)可以由3個(gè)域構(gòu)成

第一個(gè)域標(biāo)識(shí)該表結(jié)點(diǎn)是什么類(lèi)型的結(jié)點(diǎn)（type=0，廣義表專(zhuān)用的表頭結(jié)點(diǎn)；type=1，數(shù)據(jù)結(jié)點(diǎn)；type=2，子表結(jié)點(diǎn)），第二個(gè)域是值域（如果是數(shù)據(jù)元素類(lèi)結(jié)點(diǎn)，則是相應(yīng)數(shù)據(jù)值，如果是子表則存放指向子表表頭的指針），第三個(gè)域存放尾指針（type=0，空；type！=0，同一層下一個(gè)結(jié)點(diǎn)的指針）

2. 雙親表示

一個(gè)結(jié)點(diǎn)有兩個(gè)域，data和parent域。可組織成連續(xù)存儲(chǔ)單元形式（數(shù)組），或者鏈表形式。

3. 左子女右兄弟

一個(gè)結(jié)點(diǎn)有三個(gè)域，data，first child，next sibling。當(dāng)然也可以組織成數(shù)組或者鏈表形式。

數(shù)組其實(shí)可以表示任意類(lèi)型的信息，不同的解析方式產(chǎn)生不同的結(jié)果。

霍夫曼樹(shù)、霍夫曼編碼

霍夫曼樹(shù)：帶全路徑長(zhǎng)度最小的二叉樹(shù)應(yīng)是權(quán)值大的外結(jié)點(diǎn)離根節(jié)點(diǎn)最近的擴(kuò)充二叉樹(shù)（n個(gè)葉結(jié)點(diǎn)帶權(quán)值）

Huffman Code是霍夫曼樹(shù)在數(shù)據(jù)編碼中的應(yīng)用，解決數(shù)據(jù)的最小冗余編碼問(wèn)題，是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。

霍夫曼算法：

1. 問(wèn)題：將權(quán)值為{W0，W1，...，Wn}的擴(kuò)充二叉樹(shù)構(gòu)造霍夫曼樹(shù)

2. 算法過(guò)程：

（1）. 由給定的n個(gè)權(quán)值，構(gòu)造具有n棵擴(kuò)充二叉樹(shù)的森林F，其中每棵樹(shù)Ti只有一個(gè)帶有權(quán)值Wi的根結(jié)點(diǎn)，左右子樹(shù)為空。

（2）. 重復(fù)以下步驟，直至F中只剩下一棵擴(kuò)充二叉樹(shù)，此即為霍夫曼樹(shù)

①. 在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的擴(kuò)充二叉樹(shù)，作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。

②. 在F中刪去兩棵二叉樹(shù)

③. 將新二叉樹(shù)加入F

圖

圖的存儲(chǔ)表示

1. 鄰接矩陣

2. 鄰接表

圖的遍歷、連通性

1. 深度優(yōu)先搜索（對(duì)應(yīng)棧）DFS

2. 寬度優(yōu)先搜索（對(duì)應(yīng)隊(duì)列）BFS

最小生成樹(shù)（Minimum-cost Spanning Tree）

1. Kruskal算法（依次往圖中加入最小權(quán)值且兩個(gè)鄰接點(diǎn)位于不同連通分量即不構(gòu)成回路的邊）

2. Prim算法（從某一頂點(diǎn)出發(fā)，選擇與其關(guān)聯(lián)的具有最小權(quán)值的邊，將另一頂點(diǎn)加入到集合U中，以后每步從一個(gè)頂點(diǎn)在U中，另一個(gè)不在U中的各條邊中選擇權(quán)值最小的邊，將其不在U中的頂點(diǎn)加入U(xiǎn)中，直至所有頂點(diǎn)都在U中）

最短路徑問(wèn)題

1. Dijkstra算法 （圖中沒(méi)有負(fù)權(quán)值邊）

2. Bellman-Ford算法（圖中沒(méi)有負(fù)權(quán)值路徑）

活動(dòng)網(wǎng)絡(luò)

1. AOV（用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)，比如學(xué)生課程學(xué)習(xí)工程圖）

拓?fù)渑判騿?wèn)題

2.AOE

關(guān)鍵路徑問(wèn)題