數據結構與演算法圖

Ⅰ 數據結構中圖的建立及演算法實現

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 20
struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
};
struct Vnode
{
int data;
struct ArcNode *firstarc;
};
struct Vnode AdjList[MaxSize];
int m,n,v,cord;
void main()
{
void creatgraph(struct Vnode A[MaxSize]);
void dfs(struct Vnode A[MaxSize]);
do
{
printf("\n 主菜單");
printf("\n 1 建立無向圖的鄰接表");
printf("\n 2 按深度遍歷圖");
printf("\n 3 結束程序運行");
printf("\n-----------------------------------");
printf("\n 請輸入您的選擇 1, 2, 3 -->");
scanf("%d",&cord);
switch(cord)
{
case 1:
creatgraph(AdjList);
break;
case 2:
dfs(AdjList);
break;
case 3:
exit(0);
}
}while(cord<=3);
}//main end
void creatgraph(struct Vnode A[MaxSize])
{
int i,j,k;
struct ArcNode *p;
printf("input arces and vexes:");
scanf("%d %d",&m,&n);
for(k=0;k<n;k++)
{
printf("\ninput arc:");
scanf("%d%d",&i,&j);
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=j;
p->nextarc=A[i-1].firstarc;
A[i-1].firstarc=p;
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=i;
p->nextarc=A[j-1].firstarc;
A[j-1].firstarc=p;
}
printf("\n");
for(k=0;k<n;k++)
{
printf("%d",A[k].data);
p=A[k].firstarc;
while(p)
{
printf("%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}///creatgraph end
void dfs(struct Vnode A[MaxSize])
{
struct ArcNode *p,*ar[MaxSize];
int x,i,y,top=-1;
int visited[MaxSize];
for(i=0;i<n;i++)
visited[i]=0;
printf("\ninput x:");
scanf("%d",&x);
printf("%d",x);
visited[x-1]=1;
p=A[x-1].firstarc;
while((p)||(top>=0))
{
if(!p)
{
p=ar[top];
top--;
}
y=p->adjvex;
if(visited[y-1]==0)
{
visited[y-1]=1;
printf("->%d",y);
p=p->nextarc;
if(p)
{
top++;
ar[top]=p;
}
p=A[y-1].firstarc;
}
else p=p->nextarc;
}
}

Ⅱ 一文帶你認識30個重要的數據結構和演算法

數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引（位置）輕松訪問元素。

它們是做什麼用的？

想像一下有一排劇院椅。每把椅子都分配了一個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配一個號碼。這是一個數組。將問題擴展到整個劇院（椅子的行和列），您將擁有一個二維數組（矩陣）。

特性

鏈表是線性數據結構，就像數組一樣。鏈表和數組的主要區別在於鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣，元素通過指針鏈接。

它們是做什麼用的？

鏈表的一個相關應用是瀏覽器的上一頁和下一頁的實現。雙鏈表是存儲用戶搜索鍵嘩顯示的頁面的完美數據結構。

特性

堆棧是一種抽象數據類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（後進先出）規則。因此，添加到堆棧中的最後一個元素是您從中刪除的第一個元素。

堆棧可以使用數組或鏈表來實現。

它們是做什麼用的？

現實生活中最常見的例子是在食堂中將盤子疊放在寬枝一起。位於頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。

堆棧最有用的一種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧，然後彈出它們。

另一個有趣的應用是有效括弧問題。給定一串括弧，您可以使用堆棧檢查它們是否匹配。

特性

隊列是受限訪問集合中的另一種數據類型，就像前面討論的堆棧一樣。主要區別在於隊列是按照FIFO（先進先出）模型組織的：隊列中第一個插入的元素是第一個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。

它們是做什麼用的？

這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如，在呼叫中心應用程序中，隊列用於保存等待從顧問那裡獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。

一種特殊且非常重要的隊列類型是優先順序隊列。元素根據與它們關聯的「優先順序」被引入隊列：具有最高優先順序的元素首先被引入隊列。這個 ADT 在許多圖演算法（Dijkstra 演算法、BFS、Prim 演算法、霍夫曼編碼 ）中是必不可少的。它是使用堆實現的。

另一種特殊類型的隊列是deque 隊列（雙關語它的發音是「deck」）。可以從隊列的兩端插入/刪除元素。

特性

Maps （dictionaries）是包含鍵集合和值集合的抽象數據類型。每個鍵都有一個與之關聯的值。

哈希表是一種特殊類型的映射。它使用散列函數生成一個散列碼，放入一個桶或槽數組：鍵被散列，結果散列指示值的存儲位置。

最常見的散列函數（在眾多散列函數中）是模常數函數。例如，如果常量是 6，則鍵 x 的值是x%6。

理想情況下，散列函數會將每個鍵分配給一個唯一的桶，但他們的大多數設計都採用了不完善的函數，這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。

它們是做什麼用的？

Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的（其鍵按字母順序排列）。

通訊錄也是一張Map。每個名字都有一個分配給它的電話號碼。

另一個有用的應用是值的標准化。假設我們要為一天中的每一分鍾（24 小時 = 1440 分鍾）分配一個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鍾。

特性

術語：

因為maps 是使用自平衡紅黑樹實現的（文章後面會解釋），所以所有操作都在 O(log n) 內完成；所有哈希表操作都是常量。

圖是表示一對兩個集合的非線性數據結構：G={V, E}，其中 V 是頂點（節點）的集合，而 E 是邊（箭頭）的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系（有時與成本/距離相關聯）的線。

圖有兩種主要類型：有稿巧行向圖和無向圖。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同。

它們是做什麼用的？

特性

圖論是一個廣闊的領域，但我們將重點介紹一些最知名的概念：

一棵樹是一個無向圖，在連通性方面最小（如果我們消除一條邊，圖將不再連接）和在無環方面最大（如果我們添加一條邊，圖將不再是無環的）。所以任何無環連通無向圖都是一棵樹，但為了簡單起見，我們將有根樹稱為樹。

根是一個固定節點，它確定樹中邊的方向，所以這就是一切「開始」的地方。葉子是樹的終端節點——這就是一切「結束」的地方。

一個頂點的孩子是它下面的事件頂點。一個頂點可以有多個子節點。一個頂點的父節點是它上面的事件頂點——它是唯一的。

它們是做什麼用的？

我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根。最年輕的一代代表葉子的集合。

樹也可以代表你工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。

特性

二叉樹是一種特殊類型的樹：每個頂點最多可以有兩個子節點。在嚴格二叉樹中，除了葉子之外，每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2ⁿ-1 個可能的節點。

二叉搜索樹是一棵二叉樹，其中節點的值屬於一個完全有序的集合——任何任意選擇的節點的值都大於左子樹中的所有值，而小於右子樹中的所有值。

它們是做什麼用的？

BT 的一項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變數/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣，它們就可以形成一個二叉樹，其中內部節點是運算符，葉子是變數/常量——它被稱為抽象語法樹（AST）。

BST 經常使用，因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。

特性

BST 有三種類型的 DFS 遍歷：

所有這些類型的樹都是自平衡二叉搜索樹。不同之處在於它們以對數時間平衡高度的方式。

AVL 樹在每次插入/刪除後都是自平衡的，因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名：Adelson-Velsky 和 Landis。

在紅黑樹中，每個節點存儲一個額外的代表顏色的位，用於確保每次插入/刪除操作後的平衡。

在 Splay 樹中，最近訪問的節點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。

它們是做什麼用的？

AVL 似乎是資料庫理論中最好的數據結構。

RBT（紅黑樹） 用於組織可比較的數據片段，例如文本片段或數字。在 Java 8 版本中，HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。

在 Windows NT 中（在虛擬內存、網路和文件系統代碼中），Splay 樹用於緩存、內存分配器、垃圾收集器、數據壓縮、繩索（替換用於長文本字元串的字元串）。

特性

最小堆是一棵二叉樹，其中每個節點的值都大於或等於其父節點的值：val[par[x]]

Ⅲ 面試准備之【數據結構】1——圖

共有：鄰接表，鄰接矩陣

有向圖獨有：十字鏈表，邊集數組  

無向圖獨有：鄰接多重表  

一個一維數組存儲圖中頂點信息，一個二維數組（稱為鄰接矩陣）存儲圖中的邊或弧的信息。

設圖G有n個頂點，則鄰接矩陣是一個nxn的方陣，定義為：Arc[i][j]=1,若<vi,vj>∈E或<vi,vj>∈E,反之等於0。

可以看出，無向圖的鄰接矩陣是對稱矩陣，要想知道某個頂點的度，其實就是這個頂點vi在鄰接矩陣中第i行（或第i列）的元素之和。

在有向圖的鄰接矩陣中，某個頂點的出（入）度是這個頂點vi在鄰接矩陣中第i 行（列）的元素之和；

        我們發現，當圖中的邊數相對於頂點較少時，鄰接矩陣是對存儲空間的極大浪費。我們可以考慮對邊或弧使用鏈式存儲的方式來避免空間浪費的問題。回憶樹結構的孩子表示法，將結點存入數組，並對結點的孩子進行鏈式存儲，不管有多少孩子，也不會存在空間浪費問題。

鄰接表的創建過程如下：

1）  圖中頂點用一個一維數組存儲，當然也可以用單鏈表來存儲，不過用數組可以較容易的讀取頂點信息，更加方便。另外，對於頂點數組中，每個數據元素還需要存儲指向第一個鄰接點的指針，以便於查找該頂點的邊信息。

2）  圖中每個頂點vi的所有鄰接點構成一個線性表，由於鄰接點的個數不定，所以用單鏈表存儲，無向圖稱為頂點vi的邊表，有向圖則稱為以vi為弧尾的出邊表。

從圖中我們知道，頂點表的各個結點由data和firstedge兩個域表示，data是數據域，存儲頂點的信息。

firstedge是指針域，指向邊表的第一個結點，即此頂點的第一個鄰接點。

邊表結點由adjvex和next兩個域組成。adjvex是鄰接點域，存儲某頂點的鄰接點在頂點表中的下標，next則存儲指

向邊表中下一個結點的指針，比如v1頂點與v0、v2互為鄰接點，則在v1的邊表中，adjvex分別為v0的0和v2的2.

如果想知道某個頂點的度，就去查找這個頂點的邊表中結點的各數。

若要判斷頂點vi和vj是否存在邊，只需要測試頂點vi的邊表adjvex中是否存在結點vj的下標就行了。

若求頂點的所有鄰接點，其實就是對此頂點的邊表進行遍歷，得到的adjvex域對應的頂點就是鄰接點。

有向圖的鄰接表中頂點vi的邊表是指以vi 為弧尾 的弧來存儲的，這樣很容易就可以得到每個頂點的出度。

有時為了便於確定頂點的入度或以頂點為弧頭的弧，可以建立一個有向圖的逆鄰接表，即對每個頂點vi都建立

一個鏈接為vi為弧頭的表。如下圖所示：

此時我們很容易就可以算出某個頂點的入度或出度是多少，判斷兩頂點是否存在弧也很容易實現。

對於帶權值的網圖，可以在邊表結點定義中再增加一個weight的數據域，存儲權值信息即可

對於有向圖來說，鄰接表是有缺陷的。關心了出度問題，想了解入度就必須要遍歷整個圖才能知道。反之，逆鄰接表解決了入度

卻不了解出度的情況。有沒有可能把鄰接表和逆鄰接表結合起來呢？

答案是肯定的，就是把它們整合在一起。這種存儲有向圖的方法是：十字鏈表（Orthogonal List）.

我們重新定義頂點表結點結構為：   

|    data    |     firstin   |    firstout    |

其中firstin表示入邊表頭指針，指向該頂點的入邊表中第一個結點，firstout表示出邊表頭指針，指向該頂點的出邊表中的第一個結點。

重新定義的 邊表 結點結構如下表：

|    tailvex    |    headvex    |    headlink    |    taillink    |

其中tailvex是指弧起點在頂點表的下標，headvex是指弧終點在頂點表中的下標，headlink是指入邊表指針域，指向終點（弧頭）相同的

下一條邊，taillink是指出邊表指針域，指向起點（弧尾）相同的下一條邊。如果是帶權值的網，還可以再增加一個weight域來存儲權值。

如下圖表示的十字鏈表：

頂點表依然是存入一個一維數組{v0,v1,v2,v3},以頂點v0來說，firstout指向的是出邊表中的第一個結點v3。所以v0邊表結點的headvex=3,

而tailvex其實就是當前頂點v0的下標0，由於v0隻有一個出邊頂點，所以headlink和taillink都是空。

這里虛線箭頭的含義，其實就是逆鄰接表的表示。對於v0來說，它有兩條入邊，分別來自頂點v1和v2。因此v0的firstin指向頂點v1的邊表

結點中headvex為0的結點，虛線（1），接著由入邊結點的headlink指向下一個入邊頂點v2，虛線（2）。

對於頂點v1,它有一個入邊頂點v2，2個出邊頂點v0和v2，所以它的firstin指向頂點v2的邊表結點中headvex為1的結點，虛線（3）.

十字鏈表的好處就是因為把鄰接表和逆鄰接表整合在了一起，這樣既容易找到以vi為尾的弧，也容易找到以vi為頭的弧，因而容易求得

頂點的出度和入度。除了結構復雜一點外，其實創建圖演算法的時間復雜度和鄰接表是相同的，因此很好的應用在有向圖中。

十字鏈表主要是針對有向圖的存儲結構進行了優化，那麼對於無向圖的鄰接表，有沒有問題呢？如果我們在無向圖的應用中，關注的重點是頂點，那麼鄰接表是不錯的選擇，但如果我們更關注邊的操作，比如對已訪問過的邊做標記，刪除某一條邊等操作，那就意味著需要找到這條邊的兩個邊表結點進行操作。如下圖，若要刪除(v0,v2)這條邊，需要對鄰接表結構中右邊表的兩個結點進行刪除，顯然這是比較繁瑣的。

因此，我們也仿照十字鏈表的方式，對邊表結點的結構進行一些改造，重新定義的邊表結點結構如下表：

|    ivex    |     ilink    |     jvex    |     jlink    |

其中ivex和jvex是指某條邊依附的兩個頂點在頂點表中的下標。ilink指向依附頂點ivex的下一條邊，jlink指向依附頂點jvex的下一條邊。

這就是鄰接多重表結構。如上圖有4個頂點和5條邊，先將邊表結點畫出來。由於是無向圖，所以ivex，jvex正反過來都可以，為了繪圖

方便，都將ivex值設置的與一旁的頂點下標相同。

下面開始連線，首先連線的（1）（2）（3）（4）是將頂點的firstedge指向一條邊，頂點下標要與ivex的值相同。接著，由於頂點v0的(v0,v1)邊的

鄰邊有(v0,v3)和(v0,v2)。因此（5）（6）的連線就是滿足指向下一條依附於頂點v0的邊的目標，注意ilink指向的結點的jvex（ivex）一定要與它本身

的jvex（ivex）的值相同。同理，連線（7）就是指（v1,v0）這條邊，它是相當於頂點v1指向（v1,v2）邊後的下一條。v2有三條邊依附，所以（3）之後就有

了（8）（9）。連線（10）就是頂點v3在連線（4）之後的下一條邊。左圖一共有5條邊，所以右圖有10條連線，完全符合預期。

鄰接多重表與鄰接表的差別， 僅僅是在於同一條邊在鄰接表中用兩個邊表結點表示，而在鄰接多重表中只有一個結點 。這樣對邊的操作就方便

多了，若要刪除左圖的(v0,v2)這條邊，只需要將右圖的（6）（9）的鏈接指向改為^即可。

---- 邊集數組是由兩個一維數組構成。一個是存儲頂點的信息；另一個是存儲邊的信息，這個邊數組每個數據元素由一條邊的起點下標（begin）、終點下標（end）和權（weight）組成。

如上圖所示，邊集數組關注的是邊的集合，在邊集數組中要查找一個頂點的度需要掃描整個邊數組，效率並不高。因此它更適合對邊依次

進行處理的操作，而不適合對頂點相關的操作

路徑長度：路徑上各活動持續時間的總和（即路徑上所有權之和）。

完成工程的最短時間：從工程開始點（源點）到完成點（匯點）的最長路徑稱為完成工程的最短時間。

關鍵路徑：路徑長度最長的路徑稱為關鍵路徑。

二分圖是一類特殊的圖，又稱為雙分圖、二部圖、偶圖。二分圖的頂點可以分成兩個互斥的獨立集 U 和 V 的圖，使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的，二分圖可以被定義成圖中所有的環都有偶數個頂點。可以將 U 和 V 當做一個著色：U 中所有頂點為藍色，V 中所有頂點著綠色，每條邊的兩個端點的顏色不同，符合圖著色問題的要求。相反的，非二分圖無法被二著色

完全二分圖 是一種特殊的二分圖，可以把圖中的頂點分成兩個集合，使得第一個集合中的所有頂點都與第二個集合中的所有頂點相連。

歐拉圖是指通過圖（無向圖或有向圖）中所有邊且每邊僅通過一次通路，相應的迴路稱為歐拉迴路。具有歐拉迴路的圖稱為歐拉圖（Euler Graph），具有歐拉通路而無歐拉迴路的圖稱為半歐拉圖。歐拉證明了如下定理： 一個非空連通圖是歐拉圖當且僅當它的每個頂點的度數都是偶數。 由此可得如下結論：一個連通圖有歐拉跡當它至多有兩個度數是奇數的頂點。

AOE網Activity On Edge Network：在現代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在帶權有向圖中若以頂點表示事件，有向邊表示活動，邊上的權值表示該活動持續的時間，這樣的圖簡稱為AOE網。

圖的存儲結構-鄰接助陣和鄰接表  https://blog.csdn.net/dongyanxia1000/article/details/53582186

圖的存儲結構-十字鏈表和鄰接多重表 https://blog.csdn.net/dongyanxia1000/article/details/53584496

Ⅳ 數據結構與演算法-隊列

隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

隊列這個概念非常好理解。你可以把它想像成排隊買票，先來的先買，後來的人只能站末尾，不允許插隊。先進者先出，這就是典型的「隊列」。

我們知道，CPU 資源是有限的，任務的處理速度與線程個數並不是線性正相關。相反，過多的線程反而會導致 CPU 頻繁切換，處理性能下降。所以，線程池的大小一般都是綜合考慮要處理任務的特點和硬體環境，來事先設置的。當我們向固定大小的線程池中請求一個線程時，如果線程池中沒有空閑資源了，這個時候線程池如何處理這個請求？是拒絕請求還是排隊請求？各種處理策略又是怎麼實現的呢？

看完下面隊列C語言實現，相信你會多少有些了解

隊列只支持兩個基本操作：入隊 enqueue()，放一個數據到隊列尾部；出隊 dequeue()，從隊列頭部取一個元素。
隊列跟棧一樣，也是一種操作受限的線性表數據結構。

隊列跟棧一樣，也是一種抽象的數據結構。它具有先進先出的特性，支持在隊尾插入元素，在隊頭刪除元素。
跟棧一樣，隊列可以用數組來實現，也可以用鏈表來實現。用數組實現的棧叫作順序棧，用鏈表實現的棧叫作鏈式棧。同樣，用數組實現的隊列叫作順序隊列，用鏈表實現的隊列叫作鏈式隊列。

隨著不停地進行入隊、出隊操作， front 和 rear 都會持續往後移動。當 rear 移動到最右邊，即使數組中還有空閑空間，也無法繼續往隊列中添加數據了。同時也不好判斷隊滿條件，可以使用循環隊列來實現

循環隊列，顧名思義，它長得像一個環。原本數組是有頭有尾的，是一條直線。現在我們把首尾相連，扳成了一個環。

經過推算，可以發現:
隊空 Q.rear==Q.front。
隊滿 (Q.rear+1)%MAXSIZE==Q.front。

注意，當隊列滿時，圖中的 Q.rear 指向的位置實際上是沒有存儲數據的。所以，循環隊列會浪費一個數組的存儲空間。

1.初始化空隊列

2.清空隊列

4.判斷隊滿

5.入隊

6.出隊

7.獲取隊列當前元素個數

8.若隊列不空,則用e返回Q的隊頭元素,並返回OK,否則返回ERROR

9.從隊頭到隊尾依次對隊列的每個元素數組

10.主函數中驗證

輸出結果

1.初始化

2.銷毀

3.置空

4.判斷隊列是否為空

5.獲取元素個數

6.入隊

7.出隊

8.獲取隊頭元素

9.遍歷隊列

驗證

輸出

Ⅳ 數據結構與演算法-二叉樹(Binary Tree)

    名詞解釋

        節點: 每個元素

        父子關系: 用來連線相鄰節點之間的關系

        父節點: A節點就是B節點的父節點

        子節點:  B節點就是A節點的子節點

        兄弟節點: B、C、D這三個節點的父節點是同一個節點

        根結點: 沒有父節點的節點

        葉子結點: 沒有子節點的節點

        節點的高度: 節點到葉子結點到最長路徑(邊數)  (計數起點為0, 從下往上)

        節點的深度: 根節點到這個節點經歷過的邊個數  (計數起點為0, 從上往下)

        節點的層數:     節點到深度 + 1  (計數起點為1)

        樹的高度: 根節點的高度

    特點

        最常用的樹數據結構

        每個節點最多有兩個子節點(左子節點、右子節點)

         滿二叉樹: 葉子節點全都在最底層，除了葉子節點之外，每個節點都有左右兩個子節點

         完全二叉樹:  葉子節點都在最底下兩層，最後一層的葉子節點都 靠左排列 ，並且除了最後一層，其他層的節點個數都要達到最大

        二叉樹存儲方式

            數組順序存儲法

                通過數組下標來順序存儲數據 (i表示當前節點深度,從0開始)

                根節點: i = 1，左節點:2 * i，右節點: 2 * i + 1，父節點: i / 2

                完全二叉樹採用此方式節省內存空間

            鏈式存儲法

                每個節點需要存儲三分數據:當前節點數據、左節點指針、右節點指針,比較佔用空間                

            遍歷

                常用方式

                前序遍歷: 樹任意節點，先列印當前節點，再列印它的左子樹，最後列印它的右子樹

                中序遍歷: 樹任意節點，先列印它的左子樹，再列印當前節點，最後列印它的右子樹

                後序遍歷: 樹任意節點，先列印它的左子樹，再列印它的右子樹，最後列印當前節點

                二叉樹的前、中、後序遍歷就是一個遞歸的過程

                時間復雜度是O(n)

                    每個節點最多被訪問兩次，遍歷操作的時間復雜度跟節點的個數n成正比

特點

    二叉查找樹為實現快速查找而生，支持快速查找一個數據、快速插入、快速刪除一個數據

    特殊結構: 其左子樹每個節點的值 < 樹的任意一個節點的值 < 其右子樹每個節點的值

            先取根節點，如果它等於要查找的數據，那就返回。

            如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；

            如果要查找的數據比根節點的值大，那就在右子樹中遞歸查找

            一般插入的數據在葉子節點上，從根節點開始依次比較要插入的數據和節點的大小關系

            如果插入數據比節點的數值大，並且節點的右子樹為空，將新數據插到右子節點位置；

            如果不為空，就再遞歸遍歷右子樹，查找插入位置。

            如果插入數據比節點的數值小，並且節點的左子樹為空，將新數據插到左子節點位置；

            如果不為空，就再遞歸遍歷左子樹，查找插入位置。

        針對要刪除節點的子節點個數的不同，需分三種情況來處理

        1.如果要刪除的節點沒有子節點，步驟如下: (如圖中的刪除節點55)

            只需將父節點中指向要刪除節點的指針置為null

        2.如果要刪除的節點只有一個子節點，步驟如下: (如圖中刪除節點13)

            只需將父節點中指向要刪除節點的指針，讓它指向要刪除節點的子節點即可

        3.如果要刪除的節點有兩個子節點，步驟如下: (如圖中的刪除節點18)

            首先，需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上；

            然後，再刪除掉這個最小節點，因為最小節點肯定沒有左子節點        

            刪除操作，有個優化方案: 就是單純將要刪除的節點標記為「已刪除」，

            這種方案刪除操作就變簡單很多，但是比較浪費內存空間

        支持快速地查找最大節點和最小節點、前驅節點和後繼節點

        另外一種重要特性: 

            中序遍歷二叉查找樹，可以輸出有序的數據序列，時間復雜度為O(n)

            因此，二叉查找樹也叫作二叉排序樹

        以上幾種操作都默認樹中節點存儲的都是數字，而且都是不存在鍵值相同的情況

        實際應用場景中採用對象的某個欄位作為鍵值來構建二叉查找樹，其他欄位稱為衛星數據

        如果存儲的兩個對象鍵值相同，兩種解決方案

        1.把值相同的數據都存儲在同一個節點(採用鏈表或支持動態擴容的數組等數據結構)   

        2.每個節點只存儲一個數據，把這個新插入的數據當作大於這個節點的值來處理，如下圖:

        查找操作

            當查找數據時遇到值相同的節點，繼續在右子樹中查找，直到遇到葉子節點才停止。

            這樣就把鍵值等於要查找值的所有節點都查找出來        

            刪除操作

                先查找到每個要刪除的節點，然後再按前面講的刪除操作的方法，依次刪除

        對於同一組數據可構造不同二叉查找樹。查找、插入、刪除操作的執行效率都不一樣

        圖最左邊樹，根節點的左右子樹極度不平衡，退化成鏈表，查找時間復雜度為O(n)

        最理想的情況，二叉查找樹是一棵完全二叉樹（或滿二叉樹）

        時間復雜度都跟樹的高度成正比，也就是O(height)

        樹的高度就等於最大層數減一，為了方便計算，我們轉換成層來表示

        滿二叉樹: 下一層節點個數是上一層的2倍，第K層包含節點個數就是2^(K-1)

        完全二叉樹: 假設最大層數是L，總的節點個數n，它包含的節點個數在1個到2^(L-1)個之間

            L的范圍是[ , +1]，完全二叉樹的高度小於等於

            極度不平衡的二叉查找樹，它的查找性能肯定不能滿足我們的需求

        平衡二叉查找樹: 樹的高度接近logn，時間復雜度較穩定為O(logn)

    1.排序對比

        散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序

        二叉查找樹只需要中序遍歷，就可以在O(n)的時間復雜度內，輸出有序的數據序列

    2.性能穩定性對比

        散列表擴容耗時很多，而且當遇到散列沖突時，性能不穩定

        最常用的平衡二叉查找樹的性能非常穩定，時間復雜度穩定在O(logn)

    3.時間復雜度對比

        散列表查找等操作時間復雜度是常量級，因存在哈希沖突，這個常量不一定比logn小

        另外加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高

    4.結構設計對比

        散列表構造比較復雜，需要考慮:散列函數設計、沖突解決辦法、擴容、縮容等

        平衡二叉查找樹只需要考慮平衡性，而且目前這個的解決方案較成熟、固定

    5.空間復雜度

        散列表: 避免過多散列沖突，裝載因子不能太大，特別基於開放定址法，否則浪費太多空間

            

        

Ⅵ 圖解：數據結構與演算法之字典樹

字典樹（Trie樹）這一數據結構是不太常見但是十分好用<typo id="typo-32" data-origin="而" ignoretag="true">而</typo>一種數據結構，博主也就是最近一段時間做了幾道位元組的題目才了解到字典樹這一數據結構。並將自己的學習內容跟大家分享。

首先，何為字典樹（Trie樹）？顧名思義，就是在查詢目標時，像字典一樣按照一定排列順序標准和步驟訪問樹的節點，舉一個簡單例子，英文字典查單詞"He"，那麼第一步你肯定要按照a-z的順序先找到h這個首字母，然後再按照相同順序找到e。博主所要介紹的字典樹就是類似字典這樣的結構。

上述查找單詞的過程就是不斷查找與所查單詞相同前綴的字元串，直至查找到所查單詞的最後一個字母。因此，字典樹又稱為前綴樹(prefix Tree)。

以hell、hi、new、nop為例建立一個字典樹，構造如下

根據上文所述可以得到字典樹的結構性質

根據以上三點來構造字典樹。

字典樹的構造其實較為簡單，和一般樹的構造沒有太大區別。接下來將對字典樹的插入、刪除、查詢操作進行分析與講解。

在沒有字典樹的時候，我們需要先構建出字典樹。

以插入hell為例：

再插入單詞hit，過程如下，檢查＝>存在則訪問/不存在則建立新節點再訪問＝>直到要插入的單詞到達最後一個字元。

字典樹的插入操作比較簡單，不需要考慮太多排序問題。

正如上文所說，按照一定的標准進行查詢目標字元串，每個節點都儲存一個字元，根節點到達子節點路徑組成的字元串即為該節點所對應的字元串，那麼查詢目標字元串時按照從根節點一步一步訪問相應字元所在的節點，其實也就是匹配字元串前綴的過程。

如下圖，在字典樹中，查詢"hell"，

[圖片上傳失敗...(image-f028c4-1611057619223)]

如果在該字典中查詢no

刪除操作相對於插入與查詢復雜一點，但是也很簡單，刪除的前提是單詞已經存在於字典樹。

刪除字典樹節點的操作需要考慮目標字元串最後一個字元是否是樹中的葉子節點。

因為一個單詞可能是另一個單詞的前綴部分，如果不是葉子節點，我們只需要把該單詞的單詞標志位清空即可，無需刪除整個「樹枝」。

比如，想要刪除"no"這個單詞

比如，想要刪除"hell"這個單詞，與第一種刪除相同，只不過是從最後一個節點，'l'節點是葉子節點，開始往上進行節點刪除操作。

比如，想要刪除"hi",那麼與前兩種其實一致，訪問到葉子節點'i',刪除葉子節點，並向上訪問，訪問到'h'，由於刪除'i'以後，'h'依然不是葉子節點，因此不再繼續刪除節點。

比如，想要刪除"nop",與前幾種類似，先訪問到葉子節點'p'刪除，然後上移發現'o'是葉子節點，然而'o'有單詞標記位，所以，這里不再繼續刪除。

有上面幾種刪除操作，我們得到了刪除的標准：

了解了這么多字典樹的各種操作，相信你對字典樹的用途有個大概了解了，字典樹最大作用是用於==字元串的各種匹配==，前綴匹配（模糊搜索），字元串查找（字典）等等。

博主只打出了「涓涓清泉」四個關鍵字，其搜索列表返回了諸多以涓涓清泉為首的選項

顧名思義，就是一個單純的字典而已，不多舉例。

字典樹的構建，通過利用空間換時間的思想以及字元串的公共前綴減少無效的字元串比較操作從而使得插入和查找字元串變得高效．其插入或者查找的時間復雜度為O(n)，n為字元串長度。

當然，字典樹有著它的弊端，當所插入的單詞沒有很多公共前綴時，字典樹的構建變得十分復雜和低效。

字典樹的難度不是很大，但卻是一種十分有用的數據結構，掌握之後，對於解決一些有關字元串匹配、公共前綴的問題十分有幫助。

當然我們也說了，字典樹有著自己的弊端，由於用空間換時間，如果遇到了一堆公共前綴很少的單詞進行字典樹構造時，空間需求就顯得十分大了。

Ⅶ 數據結構與演算法-隊列

同樣是線性表，隊列也有類似線性表的各種操作，不同的就是插入數據只能在隊尾進行，刪除數據只能在隊頭進行。

線性表有順序存儲和鏈式存儲，棧是線性表，所以有這兩種存儲方式。同樣，隊列作為一種特殊的線性表，也同樣存在這兩種存儲方式。

我們假設一個隊列有n個元素，則順序存儲的隊列需建立一個大於n的數組，並把隊列的所有元素存儲在數組的前n個單元，數組下標為0的一端即是隊頭。所謂的入隊列操作，其實就是在隊尾追加一個元素，不需要移動任何元素，因此時間復雜度為 。

與棧不同的是，隊列元素的出列是在隊頭，即下標為0的位置，那也就意味著，隊列中的所有元素都得向前移動，以保證隊列的隊頭，也就是下標為0的位置不為空，此時時間復雜度為 。

可有時想想，為什麼出隊列時一定要全部移動呢，如果不去限制隊列的元素必須存儲在數組的前n個單元這一條件，出隊的性能就會大大增加。也就是說，隊頭不需要一定在下標為0的位置，

為了避免當只有一個元素時，隊頭和隊尾重合使處理變得麻煩，所以引入兩個指針，front指針指向隊頭元素，rear指針指向隊尾元素的下一個位置，這樣當front等於rear時，此隊列不是還剩一個元素，而是空隊列。

假設是長度為5的數組，初始狀態，空隊列列如圖所示，front與rear指針均指向下標為0的位置。然後入隊a1、a2、a3、a4，front指針依然指向下標為0位置，而rear指針指向下標為4的位置。

出隊a1、a2，則front指針指向下標為2的位置，rear不變，如圖4-12-5的左圖所示，再入隊a5，此時front指針不變，rear指針移動到數組之外。嗯？數組之外，那將是哪裡？如下圖的右圖所示。

假設這個隊列的總個數不超過5個，但目前如果接著入隊的話，因數組末尾元素已經佔用，再向後加，就會產生數組越界的錯誤，可實際上，我們的隊列在下標為0和1的地方還是空閑的。我們把這種現象叫做「假溢出」。

所以解決假溢出的辦法就是後面滿了，就再從頭開始，也就是頭尾相接的循環。我們把隊列的這種頭尾相接的順序存儲結構稱為循環隊列。

如果將rear的指針指向下標為0的位置，那麼就不會出現指針指向不明的問題了，如下圖所示。

接著入隊a6，將它放置於下標為0處，rear指針指向下標為1處，如下圖的左圖所示。若再入隊a7，則rear指針就與front指針重合，同時指向下標為2的位置，如下圖的右圖所示。

由於rear可能比front大，也可能比front小，所以盡管它們只相差一個位置時就是滿的情況，但也可能是相差整整一圈。

所以若隊列的最大尺寸為QueueSize，那麼隊列滿的條件是(rear+1)%QueueSize==front（取模「%」的目的就是為了整合rear與front大小為一圈問題）。比如上面這個例子，QueueSize=5，上圖的左圖中front=0，而rear=4，(4+1)%5=0，所以此時隊列滿。

再比如圖下圖中的，front=2而rear=1。(1+1)%5=2，所以此時隊列也是滿的。

而對於下圖，front=2而rear=0，(0+1)%5=1，1≠2，所以此時隊列並沒有滿。

另外，當rear>front時，此時隊列的長度為rear-front。

但當rear<front時，，隊列長度分為兩段，一段是QueueSize-front，另一段是0+rear，加在一起，隊列長度為rear-front+QueueSize。因此通用的計算隊列滿隊公式為：

單是順序存儲，若不是循環隊列，演算法的時間性能是不高的，但循環隊列又面臨著數組可能會溢出的問題，所以我們還需要研究一下不需要擔心隊列長度的鏈式存儲結構。

隊列的鏈式存儲結構，其實就是線性表的單鏈表，只不過它只能尾進頭出而已，我們把它簡稱為鏈隊列。為了操作上的方便，我們將隊頭指針指向鏈隊列的頭結點，而隊尾指針指向終端結點。

空隊列時，front和rear都指向頭結點。

鏈隊列的結構為：

初始化一個空隊列

入隊操作時，其實就是在鏈表尾部插入結點，如圖所示。

出隊操作時，就是頭結點的後繼結點出隊，將頭結點的後繼改為它後面的結點，若鏈表除頭結點外只剩一個元素時，則需將rear指向頭結點，如圖所示。

對於循環隊列與鏈隊列的比較，可以從兩方面來考慮，從時間上，其實它們的基本操作都是常數時間，即都為O(1)的，不過循環隊列是事先申請好空間，使用期間不釋放，而對於鏈隊列，每次申請和釋放結點也會存在一些時間開銷，如果入隊出隊頻繁，則兩者還是有細微差異。對於空間上來說，循環隊列必須有一個固定的長度，所以就有了存儲元素個數和空間浪費的問題。而鏈隊列不存在這個問題，盡管它需要一個指針域，會產生一些空間上的開銷，但也可以接受。所以在空間上，鏈隊列更加靈活。

總的來說，在可以確定隊列長度最大值的情況下，建議用循環隊列，如果你無法預估隊列的長度時，則用鏈隊列。

棧和隊列也都可以通過鏈式存儲結構來實現，實現原則上與線性表基本相同如圖所示。

Ⅷ 數據結構——圖graph（基礎概念）

【各種東拼西湊來的】

圖(Graph)是由頂點和連接頂點的邊構成的離散結構。在計算機科學中，圖是最靈活的數據結構之一，很多問題都可以使用圖模型進行建模求解。例如：生態環境中不同物種的相互競爭、人與人之間的社交與關系網路、化學上用圖區分結構不同但分子式相同的同分異構體、分析計算機網路的拓撲結構確定兩台計算機是否可以通信、找到兩個城市之間的最短路徑等等。

圖的結構很簡單，就是由頂點$V$集和邊$E$集構成，因此圖可以表示成$G=(V, E)$。

注意： 頂點有時也稱為節點或者交點，邊有時也稱為鏈接。

無向圖

我們可以說這張圖中，有點集$V=\{1, 2, 3, 4, 5, 6\}$，邊集$E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\}$。在無向圖中，邊$(u, v)$和邊$(v, u)$是一樣的，因此只要記錄一個就行了。簡而言之，對稱。

有向圖

也很好理解，就是加上了方向性，頂點$(u, v)$之間的關系和頂點$(v,u)$之間的關系不同，後者或許不存在。例如，地圖應用中必須存儲單行道的信息，避免給出錯誤的方向。

加權圖 ：

權：與圖的邊或弧相關的數叫做權。

與加權圖對應的就是無權圖，或叫等權圖。如果一張圖不含權重信息，我們就認為邊與邊之間沒有差別。不過，具體建模的時候，很多時候都需要有權重，比如對中國重要城市間道路聯吵隱笑系的建模，總不能認為從北京去上海和從北京去廣州一樣遠(等權)。

還有很多細化的概念，比如：無向圖中，任意兩個頂點間都有邊，稱為 無向完全圖 ；加權圖起一個新名字，叫 網(network) ……然而，如無必要，毋增實體。

鄰接(adjacency) ：鄰接是 兩個頂點之間 的一種關系。如果圖包含$(u,v)$，則稱頂點$v$與頂點$u$鄰接。當然，在無向圖中，這也意味著頂點$u$與頂點$v$鄰接。

關聯(incidence) ：關聯是 邊和頂點之間 的關系。在有向圖中，邊$(u,v)$從頂點$u$開始關聯到$v$，或者相反，從$v$關聯到$u$。注意，有向圖中，邊不一定是對稱的，有去無回是完全有可能的。細化這個概念，就有了頂點的 入度(in-degree) 和 出度(out-degree) 。無向圖中，頂點的度就是與頂點相關聯的邊的數目，沒有入度和出度。在有向圖中，我們以圖1-2為例，頂點10有2個入度，$3\rightarrow10$，$11\rightarrow10$，但是升含沒有從10指向其它頂點的邊，因此頂點10的出度為0。

路徑(path) ：依次遍歷頂點序列之間的邊所形成的軌跡。注意，依次就意味著有序，先1後2和先2後1不一樣。

簡單路徑 : 沒有重復頂點的路徑稱為簡單路徑。說白了，這一趟路里沒有出現繞了一圈回到同一點的情況，也就是沒有 環 。

環/迴路 ：包含相同的頂點兩次或者兩次以上。圖1-3中的頂點序列$<1,2,4,3,1>$，1出現了兩次，當然還有其它的環，比如$<1,4,3,1>$。

簡單迴路/簡單環： 除了第一個頂點和最後一個頂點之外，其餘頂點不重復出現的迴路

無環圖 ：沒有環的圖，攜畢其中， 有向無環圖 有特殊的名稱，叫做 DAG(Directed Acyline Graph) （最好記住，DAG具有一些很好性質，比如很多動態規劃的問題都可以轉化成DAG中的最長路徑、最短路徑或者路徑計數的問題）。

兩個連通分支：

連通的 ：無向圖中每一對不同的頂點之間都有路徑。如果這個條件在有向圖里也成立，那麼就是 強連通 的。

連通分量 ：無向圖中的極大連通子圖。

兩點強連通：在有向圖G中，如果兩點互相可達

強連通圖： 如果有向圖G的每兩個頂點都強連通（任意兩點互相可達），稱G是一個 強連通圖 。

強連通分量： 非強連通有向圖的極大強連通子圖，稱為強連通 分量 (strongly connected components)。

關節點(割點) ：某些特定的頂點對於保持圖或連通分支的連通性有特殊的重要意義。如果 移除某個頂點 將使圖或者分支 失去連通性 ，則稱該頂點為 關節點 。（在某圖中，若刪除頂點V以及V相關的邊後，圖的一個連通分量分割為兩個或兩個以上的連通分量，則稱頂點V為該圖的一個關節點）。

橋(割邊) ：和關節點類似，刪除一條邊，就產生比原圖更多的連通分支的子圖，這條邊就稱為 割邊 或者 橋 。

雙連通圖 ：在無向連通圖中，如果刪除該圖的任何一個結點都不能改變該圖的連通性，則該圖為雙連通的無向圖。個人理解就是一個雙連通圖沒有割點，沒有橋的圖。

1.2 一些有趣的圖概念

這一部分屬於圖論的內容，基礎圖演算法不會用到，但是我覺得挺有意思的，小記如下。【這部分我沒看，照搬過來了】

同構 4 ：圖看起來結構不一樣，但它是一樣的。假定有$G_1$和$G_2$，那麼你只要確認對於$G_1$中的所有的兩個 相鄰點 $a$和$b$，可以通過某種方式$f$映射到$G_2$，映射後的兩個點$f(a)$、$f(b)$也是相鄰的。換句話說，當兩個簡單圖同構時，兩個圖的頂點之間保持相鄰關系的一一對應。

圖1-7就展示了圖的同構，這里頂點個數很少判斷圖的同構很簡單。我們可以把v1看成u1，自然我們會把u3看出v3。用數學的語言就是$f(u_1)=v_1$，$f(u_3)=v_3$。u1的另外一個連接是到u2，v1的另外一個連接是到v4，不難從相鄰頂點的關系驗證$f(u_2)=v_4$，$f(u_4)=v_2$。

歐拉迴路(Euler Circuit) ：小學數學課本上的哥尼斯堡七橋問題，能不能從鎮里的某個位置出發 不重復的經過所有橋(邊)並且返回出發點 。這也就小學的一筆畫問題，歐拉大神解決里這個問題，開創了圖論。結論很簡單：至少2個頂點的連通多重圖存在歐拉迴路的充要條件是 每個頂點的度都是偶數 。證明也很容易，大家有興趣可以閱讀相關資料。結論也很好理解，從某個起點出發，最後要回起點，中間無論路過多少次起點，都會再次離開，進、出的數目必然相等，故一定是偶數。

哈密頓迴路(Hamilton Circuit) ：哈密頓迴路條件就比歐拉迴路嚴格一點， 不能重復經過點 。你可能會感到意外，對於歐拉迴路，我們可以輕而易舉地回答，但是 我們卻很難解決哈密頓迴路問題，實際上它是一個NP完全問題 。這個術語源自1857年愛爾蘭數學家威廉·羅萬·哈密頓爵士發明的智力題。哈密頓的智力題用到了木質十二面體（如圖1-8(a)所示，十二面體有12個正五邊形表面）、十二面體每個頂點上的釘子、以及細線。十二面體的20個頂點用世界上的不同城市標記。智力題要求從一個城市開始，沿十二面體的邊旅行，訪問其他19個城市，每個恰好一次，最終回到第一個城市。

因為作者不可能向每位讀者提供帶釘子和細線的木質十二面體，所以考慮了一個 等價的問題 ：對圖1-8(b)的圖是否具有恰好經過每個頂點一次的迴路？它就是對原題的解，因為這個平面圖 同構 於十二面體頂點和邊。

著名的 旅行商問題(TSP) 要求旅行商訪問一組城市所應當選取的最短路線。這個問題可以歸結為求完全圖的哈密頓迴路，使這個迴路的邊的權重和盡可能的小。同樣，因為這是個NP完全問題，最直截了當的方法就檢查所有可能的哈密頓迴路，然後選擇權重和最小的。當然這樣效率幾乎難以忍受，時間復雜度高達$O(n!)$。在實際應用中，我們使用的啟發式搜索等 近似演算法 ，可以完全求解城市數量上萬的實例，並且甚至能在誤差1%范圍內估計上百萬個城市的問題。

關於旅行商問題目前的研究進展，可以到 http://www.math.uwaterloo.ca/... 。

1.3 小結

以為可以一帶而過，結果寫了那麼多。也沒什麼好總結的了，當然這些也至是圖論概念的一小部分，還有一些圖可能我們以後也會見到，比如順著圖到網路流，就會涉及二分圖，不過都很好理解，畢竟有圖。

1、數組（鄰接矩陣）

2、鄰接表

3、十字鏈表

4、鄰接多種表