數據結構圖的構建演算法

⑴ 數據結構有哪些基本演算法

數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。

可以理解為：程序設計 = 數據結構 + 演算法

數據結構演算法具有五個基本特徵：輸入、輸出、有窮性、確定性和可行性。

1、輸入：一個演算法具有零個或者多個輸出。以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件。後面一句話翻譯過來就是，如果一個演算法本身給出了初始條件，那麼可以沒有輸出。比如，列印一句話：NSLog(@"你最牛逼！");

2、輸出：演算法至少有一個輸出。也就是說，演算法一定要有輸出。輸出的形式可以是列印，也可以使返回一個值或者多個值等。也可以是顯示某些提示。

3、有窮性：演算法的執行步驟是有限的，演算法的執行時間也是有限的。

4、確定性：演算法的每個步驟都有確定的含義，不會出現二義性。

5、可行性：演算法是可用的，也就是能夠解決當前問題。

數據結果的基本演算法有：

1、圖搜索（廣度優先、深度優先）深度優先特別重要

2、排序

3、動態規劃

4、匹配演算法和網路流演算法

5、正則表達式和字元串匹配

6、三路劃分-快速排序

7、合並排序（更具擴展性，復雜度類似快速排序）

8、DF/BF 搜索 （要知道使用場景）

9、Prim / Kruskal （最小生成樹）

10、Dijkstra （最短路徑演算法）

11、選擇演算法

⑵ 一文帶你認識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]]

⑶ 數據結構經典演算法有哪些

二叉樹遍歷：
status initqueue(Queue &Q)
{//初始化一個空隊列
Q.base=(QElemtype *)malloc(MAXSIZE*sizeof(QElemtype));
if(!Q.base)
exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}

status inqueue(Queue &Q,BiTree e)
{//將元素e入隊
if((Q.rear+1)%MAXSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}

status outqueue(Queue &Q,BiTree &e)
{//刪除隊頭元素，並用e返回其值
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}

status emptyqueue(Queue Q)
{//若隊列空，返回TRUE，否則返回FALSE
if(Q.front==Q.rear)
return TRUE;
return FALSE;
}

//以下是二叉樹的演算法
void creattree(BiTree &t)
{//先序順序建立二叉樹t
char ch;
ch=getchar();
if(ch==' ')
{
t=NULL;
return;
}
t=(BiTree)malloc(sizeof(BiNode));
if(!t) exit(OVERFLOW);
t->data=ch;
creattree(t->lchild);
creattree(t->rchild);
}
void print(TElemtype e)
{
printf("%c",e);
}
void pretraverse(BiTree t, void (*visit)(TElemtype e))
{//先序遍歷二叉樹t
if(t)
{
(*visit)(t->data);
pretraverse(t->lchild,visit);
pretraverse(t->rchild,visit);
}
}

void intraverse(BiTree t, void (*visit)(TElemtype e))
{//中序遍歷二叉樹t
if(t)
{
intraverse(t->lchild,visit);
(*visit)(t->data);
intraverse(t->rchild,visit);
}
}

void posttraverse(BiTree t, void (*visit)(TElemtype e))
{//後序遍歷二叉樹t
if(t)
{
posttraverse(t->lchild,visit);
posttraverse(t->rchild,visit);
(*visit)(t->data);
}
}

void leveltraverse(BiTree t, void (*visit)(TElemtype e))
{//層次遍歷二叉樹t
BiNode *p;
Queue Q;
//if(!t) return;
initqueue(Q);
p=t;
inqueue(Q,p);
while(!emptyqueue(Q))
{
outqueue(Q,p);
if(p)
{

(*visit)(p->data);
inqueue(Q,p->lchild);
inqueue(Q,p->rchild);
}
}

}

void destroytree(BiTree &t)
{
if(t==NULL) return;
else if(t->lchild==NULL&&t->rchild==NULL)
{
free(t);
return;
}
else{
destroytree(t->lchild);
destroytree(t->rchild);
free(t);
return;
}
}

⑷ 數據結構必須掌握的演算法有哪些

主要是樹的遍歷，查找，替換和刪除。圖的遍歷。（bfs，dfs）查找裡面的二叉樹查找
，平均數查找，harsh查找八大排序注意圖和樹的演算法因存儲結構不同而不同。其他的如表了什麼的，應該不是很難。是必須會的

⑸ 計算機考研：數據結構常用演算法解析(7)

第七章：
對於無向圖，e的范圍是：
數據結構中所討論的圖都是簡單圖，任意兩結點間不會有雙重的邊。
對於有向圖，e的范圍是：
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊，但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中採用。
鄰接表能很方便的求某頂點的鄰接點，索引對於與遍歷有關的演算法大多都採用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方，就是不方便求入度或是那些薯早握點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到一起就是十字鏈表和鄰接多重表。一個是存儲有向圖，另一個是存儲無向圖。
在十字鏈睜歷表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中，凡是能用鄰接表實現的一定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下一弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第一條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG)：是描述含有公共子式的表達式的有效工具。二叉樹也能表示表達式，但是利用有向無環圖可以實現對相同子式的共享，從而節省存儲空間。
頂點的度：
無向圖：某頂點V的度記為D(V)，代表與V相關聯的邊的條數
有向圖：頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中，若圖中任意兩頂點間都存在路徑，則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
「極大」在這里指的是：往一個連通分量中再加入頂點和邊，就構不成原圖中的一個 連通子圖，即連通分量是一個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。

考研有疑問、不知道如何總結考研考點內容、不清楚數慶考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/

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

#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;
}
}