第3章 線性表

3.2 線性表的定義

A B C…

B直接前驅(qū)元素: A

B直接后驅(qū)元素:C

3.6線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3.6.2線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義(P57)

• 結(jié)點(diǎn)(node)
  • 數(shù)據(jù)域:存儲(chǔ)數(shù)據(jù)元素信息的域
  • 指針域:存儲(chǔ)直接后繼位置域

• 開始結(jié)點(diǎn): 是指鏈表中的第一個(gè)結(jié)點(diǎn)，它沒(méi)有直接前驅(qū)
• 頭指針:鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針一個(gè)單鏈表可以由其頭指針唯一確定，一般用其頭指針來(lái)命名單鏈表
• 頭結(jié)點(diǎn):是在鏈表的開始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)

3.14雙向鏈表

雙向鏈表是在單鏈表的每個(gè)結(jié)點(diǎn)中,再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域

雙向鏈表的插入和刪除:

插入: s -> prior = p; s -> next = p -> next; p -> next -> prior = s; p -> next = s;刪除: p -> prior -> next = p -> next; p -> next -> prior = p ->prior; free(p);

3.15 總結(jié)回顧

線性表

• 順序存儲(chǔ)結(jié)構(gòu)
• 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
  • 單鏈表
  • 靜態(tài)鏈表
  • 循環(huán)鏈表
  • 雙向鏈表

第4章 棧和隊(duì)列

• 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表
• 隊(duì)列是只允許在一端進(jìn)行插入操作,而在另一段進(jìn)行刪除操作的線性表

4.2 棧的定義

• 棧頂(top)
• 棧底(bottom)
• 空棧
• 后進(jìn)先出(LIFO結(jié)構(gòu)),棧的兩種操作–Push和Pop

棧的插入操作稱為入棧,反之稱為出棧.

4.3 棧的抽象數(shù)據(jù)類型

棧的一些基本操作:

ADT 棧(stack) Data同線性表.元素具有相同的類型,相鄰元素具有前驅(qū)和后繼關(guān)系 OperationInitStack(*S)DestroyStack(*S)ClearStack(*S)StackEmpty(*S)判斷堆棧是否為空,返回值是ture和falseGetTop(*S)Push(*S, e)插入e值POp(*S, *e)刪除棧頂元素并用e返回其值StackLength(S)

4.4 棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)(P93)

利用下標(biāo)為0的數(shù)組一端作為棧的棧底

判斷空棧的條件是top=-1

**銷毀一個(gè)棧: **釋放內(nèi)存

**清空一個(gè)棧: **只改變地址

4.5兩棧共享空間

兩棧共享空間結(jié)構(gòu)：使用數(shù)組同時(shí)實(shí)現(xiàn)兩個(gè)棧，即棧1和棧2；棧1為空時(shí)，棧1的棧頂指針指向-1；棧2為空時(shí)，棧2 的棧頂指針指向MAXSIZE；棧1和棧2添加元素時(shí)，都會(huì)向數(shù)據(jù)中間靠攏，當(dāng)棧1的指針+1等于棧2的指針的時(shí)候，棧滿。

4.6 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

棧頂指針和單鏈表的頭指針合二為一.

4.9 棧的應(yīng)用–四則運(yùn)算表達(dá)式求值

9+(3-1)*3+10/2 這是中綴表達(dá)式

9 3 1 - 3 * + 10 2 / + 這是后綴表達(dá)式

棧的四則運(yùn)算最主要的就是讓中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式,然后再進(jìn)行一些其他的操作.

4.10 隊(duì)列的定義

隊(duì)列是只允許在一端進(jìn)行插入操作,在另一端進(jìn)行刪除操作的線性表

• 先進(jìn)先出
• 隊(duì)尾: 允許插入的一端
• 隊(duì)頭: 允許刪除的一端

4.12 循環(huán)隊(duì)列

如何判斷隊(duì)列是否已滿?利用下面共指來(lái)判斷
$$(rear?front+QueneSize)\%QueneSize==front$$

第5章 串

串是由零個(gè)或者多個(gè)字符組成的有限序列,又名叫字符串.

5.2 串的定義

串是由零個(gè)或者多個(gè)字符組成的有限序列,又名叫字符串

一般記作:
$$s="a1a2a3......an"$$
所謂序列,是指相鄰的字符串之間具有前驅(qū)和后繼的關(guān)系

5.4 串的抽象數(shù)據(jù)類型

ADT 串 (String)Data串中的元素僅由一個(gè)字符組成，相鄰元素具有前驅(qū)和后繼關(guān)系.Operation StrAssign (&T, chars)初始條件：chars是字符串常量。操作結(jié)果：生成一個(gè)其值等于chars的串T。 StrCopy (&T, S)初始條件：串S存在。操作結(jié)果：由串S復(fù)制得串T。 StrEmpty(S)初始條件：串S存在。操作結(jié)果：若S為空串，則返回TRUE，否則返回FALSE。 StrCompare(S, T)初始條件：串S和T存在。操作結(jié)果：若S>T，則返回值>0；若S=T，則返回值＝0；若S < T，則返回值 < 0。 StrLength(S)初始條件：串S存在。操作結(jié)果：返回S的元素個(gè)數(shù)，稱為串的長(zhǎng)度。 ClearString (&S)初始條件：串S存在。操作結(jié)果：將S清為空串。 Concat (&T, S1, S2)初始條件：串S1和S2存在。操作結(jié)果：用T返回由S1和S2聯(lián)接而成的新串。 SubString(&Sub, S, pos, len)初始條件：串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1操作結(jié)果：用Sub返回串S的第pos個(gè)字符長(zhǎng)度為len的子串。 Index(S, T, pos)初始條件：串S和T存在,T是非空串，1≤pos≤StrLength(S)。操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置;否則函數(shù)值為0。 Replace (&S, T, V)初始條件：串S, T和V存在，T是非空串。操作結(jié)果：用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。 StrInsert (&S, pos, T)初始條件：串S和T存在, 1≤pos≤StrLength(S)+1。操作結(jié)果：在串S的第pos個(gè)字符之前插入串T。 StrDelete (&S, pos, len)初始條件：串S存在, 1≤pos≤StrLength(S)－len+1。操作結(jié)果：從串S中刪除第pos個(gè)字符起長(zhǎng)度為len的子串。 DestroyString (&S)初始條件：串S存在。操作結(jié)果：串S被銷毀。endADT

5.6 KMP模式匹配算法

問(wèn)題描述

給定一個(gè)主串S及一個(gè)模式串P，判斷模式串是否為主串的子串；若是，返回匹配的第一個(gè)元素的位置（序號(hào)從1開始），否則返回0；如S=“abcd”，P=“bcd”，則返回2；S=“abcd”，P=“acb”，返回0。

KMP算法

https://blog.csdn.net/qq_37969433/article/details/82947411

樸素算法理解簡(jiǎn)單，但兩個(gè)串都有依次遍歷，時(shí)間復(fù)雜度為O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我們是不知道主串的內(nèi)容的，而模式串是我們自己定義的。
樸素算法中，P的第j位失配，默認(rèn)的把P串后移一位。
但在前一輪的比較中，我們已經(jīng)知道了P的前(j-1)位與S中間對(duì)應(yīng)的某(j-1)個(gè)元素已經(jīng)匹配成功了。這就意味著，在一輪的嘗試匹配中，我們get到了主串的部分內(nèi)容，我們能否利用這些內(nèi)容，讓P多移幾位(我認(rèn)為這就是KMP算法最根本的東西)，減少遍歷的趟數(shù)呢?

第6章 樹

6.2 樹的定義

樹是n個(gè)結(jié)點(diǎn)的有限集合.n=0時(shí)稱為空樹.在任意一棵非空樹中:

• 有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn);
• 當(dāng)n>1時(shí),其余結(jié)點(diǎn)可以分為m個(gè)互不相交的有限集T1,T2…Tm,其中每一個(gè)集合本身又是一課樹,并且稱為根的子樹(SubTree)

• 度: 結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)稱為結(jié)點(diǎn)的度(Degree),度為0的結(jié)點(diǎn)稱為葉節(jié)點(diǎn)或者終端結(jié)點(diǎn).度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或者分支結(jié)點(diǎn)

• 樹的度是樹的各個(gè)結(jié)點(diǎn)度的最大值
• 深度或高度: 樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度

• 有序樹和無(wú)序樹
• 森林是m棵互不相交的樹的集合

6.4 樹的存儲(chǔ)結(jié)構(gòu)(P155)

• 雙親表示法
• 孩子表示法
• 孩子兄弟表示法

http://data.biancheng.net/view/30.html

6.4.1 雙親表示法

雙親表示法

6.4.2 孩子表示法

將樹中的每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列成一個(gè)線性表，用鏈表存儲(chǔ)起來(lái)。對(duì)于含有 n 個(gè)結(jié)點(diǎn)的樹來(lái)說(shuō)，就會(huì)有 n 個(gè)單鏈表，將 n 個(gè)單鏈表的頭指針存儲(chǔ)在一個(gè)線性表中，這樣的表示方法就是孩子表示法。

孩子表示法

使用孩子表示法存儲(chǔ)的樹結(jié)構(gòu)，正好和雙親表示法相反，適用于查找某結(jié)點(diǎn)的孩子結(jié)點(diǎn)，不適用于查找其父結(jié)點(diǎn)。可以將兩種表示方法合二為一，存儲(chǔ)效果如圖 :

孩子雙親表示法 #define TElemType int #define Tree_Size 100 //孩子表示法 typedef struct CTNode{int child;//鏈表中每個(gè)結(jié)點(diǎn)存儲(chǔ)的不是數(shù)據(jù)本身，而是數(shù)據(jù)在數(shù)組中存儲(chǔ)的位置下標(biāo)struct CTNode * next; }*ChildPtr; typedef struct {TElemType data;//結(jié)點(diǎn)的數(shù)據(jù)類型ChildPtr firstchild;//孩子鏈表的頭指針 }CTBox; typedef struct{CTBox nodes[Tree_Size];//存儲(chǔ)結(jié)點(diǎn)的數(shù)組int n,r;//結(jié)點(diǎn)數(shù)量和樹根的位置 }CTree;

6.4.3 孩子兄弟表示法

任意一棵樹, 他的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的, 他的右兄弟如果存在也是唯一的.因此我們?cè)O(shè)置兩個(gè)指針,分別指向該結(jié)點(diǎn)的第一個(gè)孩子和此節(jié)點(diǎn)的右兄弟

datafirstchildrightsib

數(shù)據(jù)域	孩子域	兄弟域

上下兩個(gè)表格一個(gè)意思

這個(gè)表示方法就是把一個(gè)復(fù)雜的樹變成了二叉樹

6.5 二叉樹的定義

https://www.jianshu.com/p/bf73c8d50dc2

二叉樹(Binary Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集合,該集合或者為空集(稱為空二叉樹), 或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的,分別稱為根節(jié)點(diǎn)的左子樹和右子樹的二叉樹組成

二叉樹

二叉樹的特點(diǎn):

• 每個(gè)結(jié)點(diǎn)最多有兩顆子樹，所以二叉樹中不存在度大于2的結(jié)點(diǎn)。
• 左子樹和右子樹是有順序的，次序不能任意顛倒。
• 即使樹中某結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。

6.5.2特殊二叉樹

斜樹: 所有的結(jié)點(diǎn)都只有左子樹的二叉樹叫左斜樹。所有結(jié)點(diǎn)都是只有右子樹的二叉樹叫右斜樹。這兩者統(tǒng)稱為斜樹。

左斜樹

右斜樹

滿二叉樹: 在一棵二叉樹中。如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹

• 葉子只能出現(xiàn)在最下一層。出現(xiàn)在其它層就不可能達(dá)成平衡
• 非葉子結(jié)點(diǎn)的度一定是2
• 在同樣深度的二叉樹中，滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多，葉子數(shù)最多.并且葉子都處于同一層

滿二叉樹

完全二叉樹: 對(duì)一顆具有n個(gè)結(jié)點(diǎn)的二叉樹按層編號(hào)，如果編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹

完全二叉樹

特點(diǎn):

1）葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層。
2）最下層的葉子結(jié)點(diǎn)集中在樹的左部。
3）倒數(shù)第二層若存在葉子結(jié)點(diǎn)，一定在右部連續(xù)位置。
4）如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子，即沒(méi)有右子樹。
5）同樣結(jié)點(diǎn)數(shù)目的二叉樹，完全二叉樹深度最小。
注：滿二叉樹一定是完全二叉樹，但反過(guò)來(lái)不一定成立。

6.5.3 其他重要二叉樹

1.二叉排序樹
二叉排序樹，又叫二叉查找樹，它或者是一棵空樹；或者是具有以下性質(zhì)的二叉樹：

若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；

若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；

它的所有結(jié)點(diǎn)的左右子樹也分別為二叉排序樹。

2.平衡二叉樹

（AVL）平衡二叉樹是一種二叉排序樹，其中每個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1。它是一種高度平衡的二叉排序樹。意思是說(shuō)，要么它是一棵空樹，要么它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過(guò)1。

平衡二叉樹是一種二叉排序樹。也就是二叉排序樹包含了平衡二叉排序樹，其次它要滿足后面的約束條件，就是每個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度差不超過(guò)1

6.6 二叉樹的性質(zhì)

https://blog.csdn.net/why_still_confused/article/details/51532222

6.7 二叉樹的存儲(chǔ)結(jié)構(gòu)

6.7.2 二叉鏈表

鏈表每個(gè)結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和兩個(gè)指針域：

其中data是數(shù)據(jù)域，lchild和rchild都是指針域，分別指向左孩子和右孩子。

/*二叉樹的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義*/ typedef struct BiNode {char data; /*結(jié)點(diǎn)數(shù)據(jù)*/struct BiNode *lchild, *rchild; /*左右孩子指針*/ }BiNode,*BiTree;

6.8 遍歷二叉樹

二叉樹的遍歷是指從根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹中的所有結(jié)點(diǎn)， 使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。

https://blog.csdn.net/gatieme/article/details/51163010（二叉樹建立和遍歷的C++代碼實(shí)現(xiàn)）

1. 前序遍歷

根結(jié)點(diǎn) —> 左子樹 —> 右子樹

2. 中序遍歷

左子樹 —> 根節(jié)點(diǎn) —> 右子樹

3. 后續(xù)遍歷

左子樹 —> 右子樹—> 根節(jié)點(diǎn)

4. 層序遍歷

從根節(jié)點(diǎn)開始訪問(wèn)，從上而下逐層遍歷，在同一層中，按照從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)

6.10 線索二叉樹

為什么存在線索二叉樹：

二叉樹是一種非線性結(jié)構(gòu)，遍歷二叉樹幾乎都是通過(guò)遞歸或者用棧輔助實(shí)現(xiàn)非遞歸的遍歷。用二叉樹作為存儲(chǔ)結(jié)構(gòu)時(shí)，取到一個(gè)節(jié)點(diǎn)，只能獲取節(jié)點(diǎn)的左孩子和右孩子，不能直接得到節(jié)點(diǎn)的任一遍歷序列的前驅(qū)或者后繼。為了保存這種在遍歷中需要的信息，我們利用二叉樹中指向左右子樹的空指針來(lái)存放節(jié)點(diǎn)的前驅(qū)和后繼信息

6.10.1 線索二叉樹原理

n個(gè)節(jié)點(diǎn)的二叉樹中含有n+1個(gè)空指針域。利用二叉樹中的空指針域來(lái)存放在某種遍歷次序下的前驅(qū)和后繼，這種指針叫“線索”。這種加上了線索的二叉樹稱為線索二叉樹。

線索二叉樹節(jié)點(diǎn)

• ltag為0時(shí)指向左孩子，為1時(shí)指向該節(jié)點(diǎn)的前驅(qū)
• rtag為0時(shí)指向右孩子， 為1時(shí)指向該節(jié)點(diǎn)的后繼

6.11 樹，森林與二叉樹的轉(zhuǎn)換

https://blog.csdn.net/linraise/article/details/11745559

1. 將樹轉(zhuǎn)換成二叉樹：
（1）加線。就是在所有兄弟結(jié)點(diǎn)之間加一條連線；
（2）抹線。就是對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留他與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪除它與其它孩子結(jié)點(diǎn)之間的連線；
（3）旋轉(zhuǎn)。就是以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。

2. 森林轉(zhuǎn)換為二叉樹

森林是由若干棵樹組成，可以將森林中的每棵樹的根結(jié)點(diǎn)看作是兄弟，由于每棵樹都可以轉(zhuǎn)換為二叉樹，所以森林也可以轉(zhuǎn)換為二叉樹。

將森林轉(zhuǎn)換為二叉樹的步驟是：
（1）先把每棵樹轉(zhuǎn)換為二叉樹；
（2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，用線連接起來(lái)。當(dāng)所有的二叉樹連接起來(lái)后得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。

3. 二叉樹轉(zhuǎn)化為森林

二叉樹轉(zhuǎn)換為樹是樹轉(zhuǎn)換為二叉樹的逆過(guò)程，其步驟是：
（1）若某結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，將左孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)、右孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)……都作為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，將該結(jié)點(diǎn)與這些右孩子結(jié)點(diǎn)用線連接起來(lái)；
（2）刪除原二叉樹中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線；
（3）整理（1）和（2）兩步得到的樹，使之結(jié)構(gòu)層次分明。

4. 二叉樹轉(zhuǎn)換為森林

二叉樹轉(zhuǎn)換為森林比較簡(jiǎn)單，其步驟如下：
（1）先把每個(gè)結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線刪除，得到分離的二叉樹；
（2）把分離后的每棵二叉樹轉(zhuǎn)換為樹；
（3）整理第（2）步得到的樹，使之規(guī)范，這樣得到森林。

根據(jù)樹與二叉樹的轉(zhuǎn)換關(guān)系以及二叉樹的遍歷定義可以推知，樹的先序遍歷與其轉(zhuǎn)換的相應(yīng)的二叉樹的先序遍歷的結(jié)果序列相同；樹的后序遍歷與其轉(zhuǎn)換的二叉樹的中序遍歷的結(jié)果序列相同；樹的層序遍歷與其轉(zhuǎn)換的二叉樹的后序遍歷的結(jié)果序列相同。由森林與二叉樹的轉(zhuǎn)換關(guān)系以及森林與二叉樹的遍歷定義可知，森林的先序遍歷和中序遍歷與所轉(zhuǎn)換得到的二叉樹的先序遍歷和中序遍歷的結(jié)果序列相同。

6.12 哈夫曼樹及其應(yīng)用

6.12.2 哈夫曼樹定義與原理（P203）

構(gòu)建哈夫曼樹的步驟：

哈夫曼編碼：

第7章 圖

https://baozouai.com/2019/03/08/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E7%AC%AC%E4%B8%83%E7%AB%A0%20%20%E5%9B%BE/

圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的邊的集合組成，通常表示為：G（V，E）,其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。

7.2 圖的定義

• 無(wú)向圖：若頂點(diǎn)Vi到Vj之間的邊沒(méi)有方向，則稱這條邊為無(wú)向邊（Edge），用序偶對(duì)(Vi,Vj)表示。如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無(wú)向邊，則稱該圖是無(wú)向圖。

  上述無(wú)向圖G1來(lái)說(shuō)，G1=(V1, {E1})，其中頂點(diǎn)集合V1={A,B,C,D}；邊集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}；

• 有向圖：若從頂點(diǎn)Vi到Vj的邊是有方向的，則成這條邊為有向邊，也稱為弧（Arc）。用有序?qū)?#xff08;Vi，Vj）標(biāo)示，Vi稱為弧尾，Vj稱為弧頭。如果任意兩條邊之間都是有向的，則稱該圖為有向圖。

  [外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-aEpVicYr-1573180530985)(https://baozou.gitbooks.io/-data-structure/content/assets/152import.png)]

  有向圖G2中，G2=（V2,{E2}），頂點(diǎn)集合（A,B,C,D）,弧集合E2={<A,D>,<B,A>,<C,A>,<B,C>}.

• 無(wú)向完全圖：在一個(gè)無(wú)向圖中，任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖。含有n個(gè)頂點(diǎn)的無(wú)向完全圖有 $$n?(n+1)/2$$ 條邊

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-YzB97B8u-1573180530986)(https://baozou.gitbooks.io/-data-structure/content/assets/155import.png)]

• 有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有n個(gè)頂點(diǎn)的有向完全圖有n×(n?1)條邊

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-8L4L0N2g-1573180530986)(https://baozou.gitbooks.io/-data-structure/content/assets/157import.png)]

• 有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。稀疏和稠密是模糊的概念，是相對(duì)而言的
• 有些圖的邊或弧具有與它相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)（Weight）。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。這種帶權(quán)的圖通常稱為網(wǎng)（Network）
• 假設(shè)有兩個(gè)圖G*=(V,{E})和G*′=(V′,{E′})，如果V′?V且E′?E*，則稱G′為G的子圖（Sub-graph）

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-UOuSOE7Z-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/160import.png)]

7.2.2 圖的頂點(diǎn)和邊的關(guān)系

7.4 圖的存儲(chǔ)結(jié)構(gòu)

7.4.1 鄰接矩陣

圖的鄰接矩陣存儲(chǔ)方式是用兩個(gè)數(shù)組來(lái)表示圖。一個(gè)一維數(shù)組存儲(chǔ)圖中頂點(diǎn)信息，一個(gè)二位數(shù)組（稱為鄰接矩陣）存儲(chǔ)圖中的邊或弧的信息。

設(shè)圖G有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n*n的方陣，定義為：

• 無(wú)向圖的鄰接矩陣

• 有向圖的鄰接矩陣

• 網(wǎng)圖的鄰接表

  設(shè)圖G是網(wǎng)圖，有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n*n的方陣，定義為：

7.4.2 鄰接表

數(shù)組與鄰接表相結(jié)合的存儲(chǔ)方法稱為鄰接表

• 無(wú)相圖的鄰接表

• 有向圖的鄰接表

• 網(wǎng)圖（帶權(quán)值）的鄰接表

7.4.3 十字鏈表

十字鏈表 = 鄰接表 + 逆鄰接表

7.4.4 鄰接多重表

針對(duì)無(wú)向圖（存儲(chǔ)空間壓縮時(shí)用）

7.4.5 邊集數(shù)組

邊集數(shù)組是由兩個(gè)一維數(shù)組構(gòu)成。一個(gè)是存儲(chǔ)頂點(diǎn)的信息；另一個(gè)是存儲(chǔ)邊的信息，這個(gè)邊數(shù)組每個(gè)數(shù)據(jù)元素由一條邊的起點(diǎn)下標(biāo)(begin)、終點(diǎn)下標(biāo)(end)和權(quán)(weight)組成

begin是存儲(chǔ)起點(diǎn)下標(biāo)，end是存儲(chǔ)終點(diǎn)下標(biāo)，weight是存儲(chǔ)權(quán)值

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-zrNe533V-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/import.png23)]

邊集數(shù)組關(guān)注的是邊的集合，在邊集數(shù)組中要查找一個(gè)頂點(diǎn)的度需要掃描整個(gè)邊數(shù)組，效率并不高。因此它更適合對(duì)邊依次進(jìn)行處理的操作，而不適合對(duì)頂點(diǎn)相關(guān)的操作

7.5 圖的遍歷

定義：從圖的某一頂點(diǎn)出發(fā)訪遍圖中的其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程就叫做圖的遍歷

7.5.1 深度優(yōu)先遍歷(P239)

從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到，以上說(shuō)的只是連通圖，對(duì)于非連通圖，只需要對(duì)它的連通分量分別進(jìn)行深度優(yōu)先遍歷，即在先前一個(gè)頂點(diǎn)進(jìn)行一次深度優(yōu)先遍歷后，若圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到位置

7.5.2 廣度優(yōu)先算法(P242)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-fDuS4knY-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/import.png24)]

圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法在時(shí)間復(fù)雜度上一樣，不同之處僅在于對(duì)頂點(diǎn)的訪問(wèn)次序不同深度優(yōu)先算法更適合目標(biāo)比較明確的。以找到目標(biāo)為主要目的的情況，而廣度優(yōu)先更適合在不斷擴(kuò)大遍歷范圍時(shí)找到相對(duì)最優(yōu)解的情況

7.6 最小生成樹（B站上的王卓老師講原理講的比較好）

生成樹的特點(diǎn):

生成樹的頂點(diǎn)個(gè)數(shù)和圖的頂點(diǎn)個(gè)數(shù)相同

生成數(shù)是圖的極小聯(lián)通子圖,去掉一條邊則非聯(lián)通

一個(gè)有n個(gè)頂點(diǎn)的聯(lián)通圖的生成樹有n-1條邊

在生成樹中再加一條邊必然形成回路

生成樹中任意兩個(gè)頂點(diǎn)之間的路徑是唯一的

最小成本，就是n個(gè)頂點(diǎn)，用n-1條邊把一個(gè)連通圖連接起來(lái)，并且使得權(quán)值的和最小

最小生成樹：把構(gòu)造聯(lián)通網(wǎng)的最小代價(jià)生成樹稱為最小生成樹。最小生成樹不唯一，但是最小生成樹的權(quán)值和一定唯一。

7.6.1 普利姆(prim)算法

https://www.bilibili.com/video/av36885391/?spm_id_from=333.788.videocard.0(B站)

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-DQVfGhpK-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/import.png25)]

算法實(shí)現(xiàn)(C++) #include <iostream> #define MAXINT 6using namespace std;//聲明一個(gè)二維數(shù)組,C[i][j]存儲(chǔ)的是點(diǎn)i到點(diǎn)j的邊的權(quán)值,如果不可達(dá),則用1000表示 //借此二維數(shù)組來(lái)表示一個(gè)連通帶權(quán)圖 int c[MAXINT][MAXINT]={{1000,6,1,5,1000,1000},{6,1000,5,1000,3,1000},{1,5,1000,5,6,4},{5,1000,5,1000,1000,2},{1000,3,6,1000,1000,6},{1000,1000,4,2,6,1000}}; void Prim(int n) {int lowcost[MAXINT];//存儲(chǔ)S中到達(dá)對(duì)應(yīng)的其它各點(diǎn)的最小權(quán)值分別是多少int closest[MAXINT];//closest[]數(shù)組保存的是未在S中的點(diǎn)所到達(dá)S中包含的最近的點(diǎn)是哪一個(gè),如:closest[i]=1表示i最靠近的S中的點(diǎn)是1bool s[MAXINT];//bool型變量的S數(shù)組表示i是否已經(jīng)包括在S中int i,k;s[0]=true;//從第一個(gè)結(jié)點(diǎn)開始尋找,擴(kuò)展for(i=1;i<=n;i++)//簡(jiǎn)單初始化{lowcost[i]=c[0][i];closest[i]=0;//現(xiàn)在所有的點(diǎn)對(duì)應(yīng)的已經(jīng)在S中的最近的點(diǎn)是1s[i]=false;}cout<<"0->";for(i=0;i<n;i++){int min=1000;//最小值,設(shè)大一點(diǎn)的值,后面用來(lái)記錄lowcost數(shù)組中的最小值int j=1;for(k=1;k<=n;k++)//尋找lowcost中的最小值{if((lowcost[k]<min)&&(!s[k])){min=lowcost[k];j=k;}}cout<<j<<" "<<"->";s[j]=true;//添加點(diǎn)j到集合S中for(k=1;k<=n;k++)//因?yàn)樾录尤肓薺點(diǎn),所以要查找新加入的j點(diǎn)到未在S中的點(diǎn)K中的權(quán)值是不是可以因此更小{if((c[j][k]<lowcost[k])&&(!s[k])){lowcost[k]=c[j][k];closest[k]=j;}}}} int main() {//輸入初始化數(shù)組cout<<"請(qǐng)輸入初始權(quán)值數(shù)組:"<<endl;for(int i=0;i<MAXINT;i++){for(int j=0;j<MAXINT;j++){// cout<<"please enter c["<<i<<"]["<<j<<"]:";// cin>>c[i][j];cout<<c[i][j]<<"\t";// cout<<endl;}cout<<endl;}Prim(MAXINT-1);return 0; }

7.6.2 克魯斯卡爾(Kruskal)算法

https://www.bilibili.com/video/av36885495/?spm_id_from=333.788.videocard.0(B站)

本質(zhì)就是一種貪心算法

算法思想:

• 設(shè)聯(lián)通網(wǎng)N=(V,E)令最小生成樹初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非聯(lián)通圖T=(V,{}),每個(gè)頂點(diǎn)自成一個(gè)連通分量.
• 在E中選取代價(jià)最小的邊,若該邊依附的頂點(diǎn)落在T中的不同聯(lián)通分量上(即:不能形成環(huán)),則將此邊加入到T中,否則,舍去此邊,選取一條代價(jià)最小的邊.
• 以此類推,直到T中所有頂點(diǎn)都在同一個(gè)聯(lián)通分量上為止.

兩種算法的比較

---

算法名Prime算法Kruskal算法

算法思想	選擇點(diǎn)	選擇邊
時(shí)間復(fù)雜度	O(n^2)	O(eloge)
適應(yīng)范圍	稠密圖	稀疏圖

7.7 最短路徑

最短路徑:指兩個(gè)頂點(diǎn)之間經(jīng)過(guò)邊上的權(quán)值之和最少的路徑,并稱第一個(gè)頂點(diǎn)是源點(diǎn), 最后一個(gè)頂點(diǎn)是終點(diǎn).

要解決的兩類問(wèn)題:

• 兩點(diǎn)之間的最短路徑(單源最短路徑(Dijkstra算法))
• 某源點(diǎn)到其他各個(gè)點(diǎn)的最短路徑(所有頂點(diǎn)之間的最短路徑(Floyd算法))

7.7.1 Dijkstra算法

單源最短路徑

https://www.bilibili.com/video/av36886088/?spm_id_from=333.788.videocard.0(B站)

按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑

7.7.2 Floyd算法

https://www.bilibili.com/video/av36886554/?spm_id_from=333.788.videocard.0(B站)

所有頂點(diǎn)之間的最短路徑

算法思想:

• 逐個(gè)頂點(diǎn)試探
• 從Vi到Vj的所有可能存在的路徑中
• 選出一條長(zhǎng)度最短的路徑

7.8 拓?fù)渑判?/h2>

https://www.bilibili.com/video/av36886991/?spm_id_from=333.788.videocard.0(B站)

1.AOV網(wǎng)

用一個(gè)有向圖表示一個(gè)工程的各子工程及其相互制約的關(guān)系，其中以頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)之間的優(yōu)先制約關(guān)系，稱這種有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)，簡(jiǎn)稱AOV網(wǎng).

2.AOE網(wǎng)

用一個(gè)有向圖表示一個(gè)工程的各子工程及其相互制約的關(guān)系,以弧表示活動(dòng),以頂點(diǎn)表示活動(dòng)的開始或結(jié)束時(shí)間,稱這種有向圖為邊表示活動(dòng)的網(wǎng),簡(jiǎn)稱AOE網(wǎng).

3.AOV網(wǎng)的特點(diǎn):

• 若從i到j(luò)有一條有向路徑,則i是j的前驅(qū);j是i的后繼
• 若<i, j>是網(wǎng)中的有向邊, 則i是j的直接前驅(qū), j是i的直接后繼
• AOV網(wǎng)中不允許有回路, 因?yàn)槿绻谢芈反嬖?表明某項(xiàng)活動(dòng)是以自己為先決條件,顯然這是荒謬的.
• 如何判斷AOV網(wǎng)中是否存在回路?

4.什么是拓?fù)渑判?:

在AOV網(wǎng)沒(méi)有回路的前提下,我們將全部活動(dòng)排列成一個(gè)線性序列,使得若AOV網(wǎng)中有弧<i, j>存在, 則在這個(gè)序列中, i一定排在j的前面, 具有這種性質(zhì)的線性序列稱為拓?fù)溆行蛐蛄? 相應(yīng)的拓?fù)溆行蚺判虻乃惴ǚQ為拓?fù)渑判?

5.拓?fù)渑判虻姆椒?/p>

一個(gè)拓?fù)湫蛄胁⒉晃ㄒ?/p>

上述拓?fù)湫蛄幸部梢允荂9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8

6.拓?fù)渑判虻囊粋€(gè)重要應(yīng)用

檢測(cè)AOV網(wǎng)中是否存在環(huán)

對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?/strong>, 若網(wǎng)中所有頂點(diǎn)都在他的拓?fù)溆行蛐蛄兄?/strong>,則該AOV網(wǎng)必定不存在環(huán).

7.9 關(guān)鍵路徑

https://www.bilibili.com/video/av36907591/?spm_id_from=trigger_reload(B站)

1.AOE網(wǎng)

用一個(gè)有向圖表示一個(gè)工程的各子工程及其相互制約的關(guān)系,以弧表示活動(dòng),以頂點(diǎn)表示活動(dòng)的開始或結(jié)束時(shí)間,稱這種有向圖為邊表示活動(dòng)的網(wǎng),簡(jiǎn)稱AOE網(wǎng).

2.關(guān)鍵路徑

把工程計(jì)劃表示為邊表示的活動(dòng)的網(wǎng)絡(luò), 即AOE網(wǎng), 用頂點(diǎn)表示事件, 弧表示活動(dòng), 弧的權(quán)表示活動(dòng)持續(xù)時(shí)間

事件表示在他之前的活動(dòng)已經(jīng)完成, 在他之后的活動(dòng)可以開始

總結(jié)

以上是生活随笔為你收集整理的数据结构系列之大话数据结构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。