《數據結構》60’

一、棧（stack）、隊列（Queue）、向量（Vector）

1、鏈表

• 帶哨兵節(jié)點鏈表了解清楚
• 鏈表要會寫，會分析。各種鏈表。

2、棧

LIFO（last in first out）先存進去的數據，最后被取出來，進出順序逆序。即先進后出，后進先出。

ADT Stack{

數據對象：D= {Ai |Ai屬于ElemSet,i = 1,2,3,…,n,n>0}

數據關系：R1 = {<Ai-1,Ai>,Ai>Ai-1,Ai屬于D，i = 2,…,n} An端為棧頂，A1為棧底

基本操作：

InitStack(&S) 操作結果：構造一個空棧S。

DestroyStack(&S) 初始條件：棧S已存在 操作結果：棧S被銷毀

ClearStack(&S) 初始條件：棧S已存在 操作結果：將S清為空棧

StackEmpty(S) 初始條件：棧S已存在 操作結果：若棧S為空棧，則返回TRUE,否則FALSE

StackLength(S)初始條件：棧S已經在 操作結果：返回S的元素個數，即棧的長度

GetTop(S,&e)初始條件：棧S已存在且非空 操作結果：用e返回S的棧頂元素

Push(&S,e)初始條件：棧S已存在 操作結果：插入元素e為新的 棧頂元素

Pop(&S,e)初始條件：棧S已存在且非空 操作結果：刪除S的棧頂元素，并用e返回值

StackTraverse(S,visti()) 初始條件：棧S已存在且非空 操作結果：從棧底到棧頂依次對S的每個數據元素調用函數visit(),一旦visit()失敗，則返回操作失敗。

}ADT Stack

3、隊列

隊列是一個線性集合，其元素一端加入，從另一端刪除，按照FIFO(先進先出)

處理過程：水平線 一段作為隊列的前端（front）也稱作隊首（head）,另一端作為隊列的末端（rear）也稱隊尾（tail）。元素都是從隊列末端末端進入，從隊列前端退出。

在隊列中，其處理過程可以在隊列的兩端進行，而在棧中，其處理過程只在棧的一端進行，但是兩者也有相似之處，與棧形似，隊列中也沒有操作能讓用戶“抵達”隊列中部，沒有操作允許ong戶重組或刪除多個元素。

ADT

ADT Queue{

數據對象:D={ai|ai屬于ElemSet,i = 1, 2, 3, …, n,n>0}

數據關系：R1={<ai-1,ai>|ai-1,ai屬于D，i=2,…,n}

約定a1端為隊列頭，an端為隊列尾。

基本操作：

InitQueue(&Q) 操作結果：構造一個空隊列Q。

DestoryQueue(&Q)初始條件：隊列Q已存在 操作結果：隊列Q被銷毀

ClearQueue(&Q)初始條件：隊列Q已存在 操作結果：隊列Q清為空棧

QueueEmpty(Q)初始條件：隊列Q已存在 操作結果：若隊列Q為空棧，則返回TRUE,否則FALSE

QueueLength(Q)初始條件：隊列Q已存在 操作結果：返回Q的元素個數，即隊列的長度

GetHead(Q,&e)初始條件：隊列Q非空 操作結果：用e返回Q的隊頭元素

EnQueue(&Q,&e)初始條件：隊列Q已存在 操作結果：插入元素e為Q的新隊尾元素

DeQueue(&Q,&e)初始條件：隊列Q已存在且非空 操作結果：刪除Q的隊頭元素，并用e返回其值

QueueTraverse(Q,visit())初始條件：隊列Q已存在且非空 操作結果：從隊頭到隊尾，依次對Q的每個元素調用函數visit()，一旦visit()失敗，則返回操作失敗

}ADT Queue

隊列鏈表與數組（順序）的實現(xiàn)

1.鏈表實現(xiàn)隊列：

隊列與棧的區(qū)別在于，我們必須要操作鏈表的兩端。因此，除了一個指向鏈表首元素的引用外，還需要跟蹤另一個指向鏈表末元素的引用。再增加一個整型變量count來跟蹤隊列中的元素個數。綜合考慮，我們使用末端入列，前端出列。

2.數組實現(xiàn)隊列

固定數組的實現(xiàn)在棧中很高效的，是因為所有的操作（增刪等）都是在集合的一端進行的，因而也是在數組的一端進行的，但是在隊列 的實現(xiàn)中則不是這樣，因為我們是在兩端對隊列進行操作的，因此固定數組的實現(xiàn)效率不高。

隊列的應用實例：模擬售票口

4、向量（Vector）

1.對數組結構進行抽象和擴展之后，就可以得到向量結構，因此向量也稱作數組列表（Array list）

2.向量提供一下訪問方法，使我們可以通過下標直接訪問序列中的元素，也可以將指定下標處的元素刪除，或將新元素插入指定下標。為了與通常數據結構的下標（Index）概念區(qū)分開來，我們通常將序列的下標稱為秩（Rank）

3.假定集合S由n個元素組成，他們依次按照線性次序存放，于是我們就可以直接訪問其中的第一個元素、第二個元素、。。。。即，通過[0,n-1]之間的每一個整數，都可以直接訪問到唯一的元素e，而這個整數就等于S中位于e之前的元素個數-在此，我們稱之為該元素的秩（Rank）

4.不難看出，若元素e的秩為r，則只要e的直接前驅（或直接后繼）存在，其秩就是r-1(或r+1)

5.支持通過秩直接訪問其中元素的序列，稱作向量（Vector）或數組列表（Array List）

6.ADT

操作接口（operate）功能（function）適用對象

size()	返回向量的總數	向量
get?	獲取秩為r的元素	向量
put(r, e)	用e替換秩為r元素的數值	向量
insert(r, e)	e作為秩為r元素插入，原后繼元素依次后移	向量
remove?	刪除秩為r的元素，返回該元素中原存放的對象	向量
disordered()	判斷所有元素是否已按照非降序排列	向量
sort()	調整各元素的位置，使之按照非降序排列	向量
find(e)	查找等于e且秩最大的元素	向量
search(e)	查找目標元素e，返回不大于e且秩最大的元素	有序向量
deduplicate()	剔除重復元素	向量
uniquify()	剔除重復元素	有序向量
traverse()	遍歷向量并統(tǒng)一處理所有元素，處理方法由函數對象指定	向量

二、樹

1.樹；樹的前序，中序，后序，層次序遍歷

概念：樹（Tree）是n（n>=0）個結點的有限集

術語：

節(jié)點的度：一個節(jié)點含有的子樹的個數稱為該節(jié)點的度；

葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點；

非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點；

雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；

孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；

兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；

樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；

節(jié)點的層次：從根開始定義起，根為第一層，根的子節(jié)點為第2層，以此類推；

樹的高度或深度：樹中節(jié)點的最大層次；

堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟節(jié)點；

節(jié)點的祖先：從根到該節(jié)點所經分支上的所有節(jié)點；

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫；

森林：由m(m>=0)棵互不相交的樹的集合稱為森林；

二叉樹的遍歷（traversing binary tree）：按照某種搜索路徑巡防樹中的每個結點，使每個結點均能被訪問一次且僅一次

• 先序遍歷二叉樹（根>左>右）
• 中序遍歷二叉樹（左>根>右）
• 后序遍歷二叉樹（左>右>根）
• 層次遍歷二叉樹

2.二叉樹及性質；普通樹與二叉樹的轉換；

定義：是結點的一個有限集合，該集合或者為空，或者由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。

性質：

1.二叉樹第i層上的結點數目最多為2^(i-1)(i>=1)

2.深度為k的二叉樹至多有2^(k) - 1個結點（k>=1）

3.包含n個結點的二叉樹的高度至少為log2(n+1)

4.在任意一棵二叉樹中，若終端結點的個數為n0,度為2的結點數為n2,則n0=n2+1

滿二叉樹：

1.一棵深度為k且有2^k -1個結點的二叉樹

2.可以對滿二叉樹的結點進行連續(xù)編號，約定編號從根開始，自上而下，自左而右

完全二叉樹：

深度為k的，有n個結點的二叉樹，當且僅當其每一個節(jié)點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹

特點：

1.葉子結點只可能出現(xiàn)在層次最大的兩層上

2.對任一結點，若其右分支下子孫的最大層次為I，其左下分支的子孫的最大層次必為I或者I+1

3.深度為k的完全二叉樹要第k層最少1個結點，最多2k-1個節(jié)點；整棵樹最少2k-1個結點，最多2k-2個結點

4.具有n個結點的完全二叉樹的深度為[log2 n]+1

二叉樹轉換

樹轉換為二叉樹過程：

1.樹中所有相同雙親結點的兄弟結點之間加一條線；

2.對樹中不是雙親結點的第一個孩子的結點，只保留新添加的該結點與左兄弟之間的連線，刪除該結點與雙親節(jié)點之間的連線

3.整理所有保留的連線，根據連線擺放成二叉樹的結構，轉換完成

（

個人理解版：

1.同父同母的親兄弟的結點之間連線

2.一個節(jié)點只留大兒子連線，其他兒子都刪了

3.搞定，重擺一下，轉換完成

）

二叉樹轉換為樹的過程：

1.若某結點是其雙親節(jié)點的孩子，則把該節(jié)點的右孩子，右孩子的右孩子都與該結點的雙親結點用線連起來；

2.刪除原二叉樹中所有雙親結點與右孩子結點的連線；

3.根據連線擺放成樹的結構，轉換完成。

（

個人理解版：

1.有雙親節(jié)點且為左孩子，則把他的右孩子和右右孫子與爺爺奶奶連線；

2.把所有雙親結點與右孩子的連線刪了；

3.擺放成樹，完成；

）

3、樹的存儲結構，標準形式；完全樹（complete tree）的數組形式存儲

1.雙親表示定義法：假設以一組連續(xù)空間存儲數的結點，同時在每個結點中，附設一個指示器指示其雙親結點到鏈表中的位置。

data(數據域)parent（指針域）

存儲結點的數據信息	存儲該結點的雙親所在數組中的下標

2.孩子表示法：把每個結點的孩子結點排列起來，以單鏈表作為存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結構，存放進一個一維數組中。

• 孩子鏈表的孩子結點

child(數據域)next(指針域)

存儲某個結點在表頭數組中的下標	存儲指向某結點的下一個孩子結點的指針

• 表頭數組的表頭結點

child(數據域)firstchild(頭指針域)

存儲某個結點的數據信息	存儲該結點的孩子鏈表的頭指針

孩子兄弟表示法：任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，設置兩個指針，分別指向該節(jié)點的第一個孩子和此結點的右兄弟。

data(數據域)firstchild(指針域)rightchild(指針域)

存儲結點的數據信息	存儲該結點的第一個孩子的存儲地址	存儲該結點的右兄弟結點的存儲地址

4、樹的應用，Huffman樹定義與應用；

Huffman樹：是一類帶權路徑長度最短的樹

基本概念：

1.樹的路徑長度：從根到每一個結點的路徑長度之和。

2.結點的帶權路徑長度：從該結點到樹根之間的路徑長度與結點上權的乘積。

3.樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，通常記作WPL。

Huffman算法：

1.由給定的n個權值{w0,w1,…,wn-1}，構造具有n棵二叉樹的集合F={T0，T1，…,Tn-1}，其中每一棵二叉樹Ti只有一個帶有權值wi的根結點，其左、右子樹均為空。

2.在F中選取兩棵根結點的權值最小的二叉樹，做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。

3.在F中刪去這兩棵二叉樹，加入新得的樹。

4.重復2.3，直到F只含一棵樹為止。這棵樹就是赫夫曼樹。

三、查找（search）

1、查找的概念；對線性關系結構的查找，順序查找，二分查找；

查找定義：根據給定的某個值（Key），在查找表中確定一個其關鍵字等于給定值的數據元素（或記錄）。

查找算法分類：

1.靜態(tài)查找和動態(tài)查找；

注：靜態(tài)和動態(tài)都是針對查找表而言的，動態(tài)表指查找表中有刪除和插入操作的表。

2.無序查找和有序查找

無序查找：被查找數列有序無序均可

有序查找：被查找數列必須為有序數列

平均查找長度（Average Search Length,ASL）:ASL=Pi*Ci的和。

Pi:查找表中第i個數據元素的概率；Ci：找到第i個數據元素時已經比較過的次數。

順序查找：

說明：

順序查找適合于存儲結構為順序存儲或鏈接存儲的線性表。

基本思想：

順序查找也稱為線性查找，屬于無序查找算法。從數據結構線性表的一端開始，順序掃描，一次將掃描到的結點關鍵字與給定值k想比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等于k的結點，表示查找失敗。

復雜度分析：

查找成功時平均查找長度為：（假設每個數據元素的概率相等）
$$ASL=(1/n)?(1+2+.3+...+n)=(n+1)/2;$$
當查找不成功時，需要n+1次比較，時間復雜度為O(n);所以，順序查找的時間復雜度為O(n);

二分查找：

說明：

元素必須是有序的，如果是無序的則要先進行排序操作。

基本思想：

也稱折半查找，屬于有序查找算法。用給定值k先與中間結點的關鍵字比較，中間結點把線性表分成兩個子表，若相等則查找成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束發(fā)現(xiàn)表中沒有這樣的結點。

復雜度分析：

最壞情況下，關鍵詞比較次數為log2(n+1),且期望時間復雜度為O(log2n);

注：折半查找的前提條件是需要有序表順序存儲，對于靜態(tài)查找表，一次排序后不再變化，折半查找能得到不錯的效率。但對于需要頻繁執(zhí)行插入或者刪除操作的數據集而言，維護有序的排序會帶來不小的工作量，那就不建議使用。

2、Hash查找法，常見的Hash函數（直接定址法，隨機數法），hash沖突的概念，解決沖突的方法（開散列方法/拉鏈法，閉散列方法/開址定址法），二次聚集現(xiàn)象；

Hash查找法：

通常我們查找數據是通過一個一個地比較來進行，有一種方法，要尋找的數據與其在數據集中的位置存在一種對應關系，通過這種關系就能找到數據的位置。這個對應關系稱為散列函數（哈希函數），因此建立的表為散列表（哈希表）。

散列查找是關鍵字與在數據集中的位置一一對應，通過這種對應關系能快速地找到數據，散列查找中散列函數的構造和處理沖突的方法尤為重要。

常見Hash函數

散列函數的構造：構造哈希表的前提是要有哈希函數，并且這個函數盡可能地減少沖突

（1）直接定址法（考綱點明）

可以取關鍵字的某個線性函數值為散列地址，即：
$$f(key)=a?key+b$$
這樣的哈希函數簡單均勻，不會產生沖突，但問題是這需要事先知道關鍵字的分布情況，適合查找表較小且連續(xù)的情況。

（2）數字分析法

該方法在知道關鍵字的情況下，取關鍵字的盡量不重復的幾位值組成散列地址。

（3）平方取中法

取關鍵字平方后的中間幾位為散列地址

（4）折疊法

將關鍵字分為位數相等的幾部分，最后一部分的位數可以不等，然后把這幾部分的值（舍去進位）相加作為散列地址

（5）除留余數法

該方法為最常用的構造哈希函數方法，對于散列表長為m的散列函數公式為：

f(key) = key mod p (p <=m)

使用除留余數法的一個經驗是，若散列表的表長為m，通常p為小于或等于表長的最小質數或不包含小于20質因子的合數。

實踐證明，當p取小于散列表長的最大質數時，函數較好。

（6）隨機數法（考綱點明）

選擇一個隨機函數，取關鍵字的隨機函數值作為散列地址。

Hash沖突概念：

對于不同的關鍵字可能得到同一哈希地址，即key1 != key2，而(key1)=(key2)，這種現(xiàn)象稱為沖突。

解決沖突的方法：

（1）開放定址法（考綱點明）

一旦發(fā)生沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并記錄存入，公式：

fi(key) = (f(key)+di) mod m(di = 1, 2, 3, …, m-1 )

用開放定址法解決沖突的做法是：

當沖突發(fā)生時，使用某種探測技術在散列表中形成一個探測序列，沿此序列逐個單元第查找，直到找到給定的關鍵字，或者遇到一個開放的地址（該地址單元為空）為止（若要插入，在探查到開放的地址，則可將帶插入的新節(jié)點存入改地址的單元）。查找時探測到開放地址則表明表中無待查的關鍵字，即查找失敗。

e.g.

我們的關鍵字集合為{12， 67,56,16,25,37,22,29,15,47,48,34}，表長為12.我們用散列函數f(key)=key mod 12。

當計算前S個數{12,67,56,16,25}時，都是沒有沖突的散列地址，直接存入：計算key=37時，發(fā)現(xiàn)f(37)=1，此時就與25所在的位置沖突。

于是我們應用上面的公式f(37)=(f(37)+1)mod12=2。于是將37存入下標為2的位置。這其實就是房子被人買了，于是買下一間的做法。接下來22,29,15,47都沒有沖突，正常存入。到了key=48，我們計算得到f(48)=0,與12所在的0位置沖突了，

不要緊，我們再來一次，f(48)= (f(48)+1)mod12 =1，

還是沖突，我日，再來。f(48) = (f(48)+2)mod12 =2。。。我擦還是不行。。。繼續(xù)。。。f(48) = ((f48)+3)mod12 = 3 …

f(48) = ((f48)+4)mod12 = 4 …

f(48) = ((f48)+5)mod12 = 5 …

f(48)=(f(48)+6)mod12 = 6時，才有空位，機不可失。。。立馬存入：我們把這種解決沖突的開放定址法稱為線性探測法。

demo:

TODO

二次探測法:

考慮深一步，如果發(fā)生這樣的情況，當最后一個key=34，f(key)=10，與22所在位置沖突，可能22后面沒有空位置了，反而它的前面有個空位置，盡管可以不斷地求余數后得到結果，但是效率很差。

因此我們可以改進di = 1^2,-12,2^2,-22,…,q^2,-q2(q<=m/2)，這樣就等于是可以雙向尋找到可能的空位置。

對于34來說，我們取di即可找到空位置了。另外增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區(qū)域。我稱之為二次探測法。公式如下：

fi(key) = (f(key)+di) MOD m (di = 1^2,-12,2^2,-22,…,q^2,-q2 <=m/2)

demo:

TODO

隨機探測法：

還有一種方法，實在沖突時，對于位移量di采用隨機函數計算得到，我們稱之為隨機探測法。

那么一定有朋友問，既然是隨機的，那么查找的時候不也隨機生成嘛？如何可以獲得相同的地址呢？這個問題吧，這里的隨機，其實是偽隨機數。偽隨機數是說，如果我們設置隨機種子相同，則不斷調用隨機函數可以生成不會重復的數列，我們在查找時，用同樣的隨機種子，它每次得到的數列是相同的，相同的di當然可以得到相同的散列地址。

fi(key) = (f(key)+di) MOD m(di是一個隨機數列)

總而言之，開放定址法只要在散列表未填滿時，總能找到不發(fā)生沖突的地址，是我們常用的解決沖突的方法。

[注]：

偽隨機數：

#include <iostream>using namespace std;int main() {cout << "hello world!" << endl;//偽隨機數：//偽隨機數是用確定性的算法計算出來自[0, 1]均勻分布的隨機數序列。并不真正的隨機，但具有類似于隨機數的統(tǒng)計特征，如均勻性、獨立性等。//在計算偽隨機數時，若使用的初值（種子）不變，那么偽隨機數的數序也不變。//在相同的平臺環(huán)境下，編譯生成exe后，每次運行它，顯示的隨機數都是一樣的。這是因為在相同的編譯平臺環(huán)境下，由隨機種子生成隨機數的計算方法都是一樣的，再加上隨機種子一樣，所以產生的隨機數就是一樣的。for (int i = 0; i < 6; i++){unsigned int seed = i;srand(seed);unsigned int r = rand();cout << "r = " << r << endl;}cout << "+++++++++++++++++" << endl;for (int i = 0; i < 6; i++){unsigned int seed = i;srand(seed);unsigned int r = rand();cout << "r = " << r << endl;}getchar();return 0;}

（2）再哈希法

再哈希法是當散列地址沖突時，用另外一個散列函數再計算一次，這種方法減少了沖突，但增加了計算時間。

Hi = RHi(key),i = 1,2,…,k(k<=m-1)

RHi均是不同的哈希函數，即在同義詞產生地址沖突時計算另一個哈希函數地址，直到沖突不再發(fā)生。這種方法 不容易產生“聚集”，但是增加了計算時間。

（3）鏈地址法（拉鏈法）（必考點）

鏈地址法解決沖突的做法是：將所有關鍵字散列地址相同的結點鏈接再同一個單鏈表中。若選定的散列表長度是m，則可將散列表定義為一個由m個頭指針組成的指針數組T[o…m-1]。凡是散列地址為 i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均為空指針。拉鏈法中，裝填因子α可以大于1，但一般均取α<=1。

demo:

TODO

總結：

前面我們談到了散列沖突處理的開放定址法，他的思路就是一旦發(fā)生了沖突，就去需找下一個空的散列地址。那么，有沖突就一定要換地方嗎？我們直接就在原地處理可以嗎？

答案是，可以的，于是我們就有個鏈地址法（拉鏈法）。將所有關鍵字散列地址相同的記錄存儲在一個單鏈表中，我們稱這種表為同義詞子表，在散列表只存儲所有同義詞子表的頭指針。

（4）建立公共溢出區(qū)

這種方法的基本思想：將散列表分為基本表和溢出表兩個表，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。

二次聚集現(xiàn)象：

開放定址法會造成二次聚集的現(xiàn)象，對查找不利。我們可以看到一個現(xiàn)象：

當表中i,i+1,i+2位置上已經填有記錄時，下一個哈希地址為i,i+2和i+3的記錄都將填入i+3的位置，這種在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現(xiàn)象稱為“二次聚集”，即在處理同義詞的沖突過程中又添加了非同義詞的沖突。但另一個方面，用線性探測再散列處理沖突可以保證做到：只要哈希表未填滿，總能找到一個不發(fā)生沖突的地址HK。而二次探測再散列只有在哈希表長m為形如4j+3（j為整數）的素數時才有可能。

3、BST樹定義，性質，ADT及其實現(xiàn)，BST樹查找，插入，刪除算法；

答：

BST樹定義、性質：

二叉排序樹（Binary Sort Tree），又稱為二叉查找樹（Binary Search Tree）。

定義：要么是空樹，要么具有入下性質的二叉樹：

• 二叉排序樹中，如果其根節(jié)點有左子樹，那么左子樹上所有節(jié)點都小于其根節(jié)點的值
• 二叉排序樹中，如果其根節(jié)點有右子樹，那么右子樹上所有節(jié)點都大于其根節(jié)點的值
• 二叉排序樹中的左右子樹也要求都是二叉排序樹

查找：

二叉排序樹中查找某關鍵字時，查找過程類似于次優(yōu)二叉樹，在二叉排序樹不為空樹的前提下，首先將被查找值同樹的樹結點進行比較，會有三種不同的結果：

• 如果相等，查找成功；
• 如果比較結果為根結點的關鍵字值較大，則說明該關鍵字可能存在其左子樹中；
• 如果比較結果為根結點的關鍵字值較小，則說明該關鍵字可能存在其右子樹中；

插入：

二叉排序樹本身是動態(tài)查找表的一種表現(xiàn)形式，有時會在查找過程中插入或者刪除表中元素，當因為查找失敗而需要插入數據元素時，該元素的插入位置一定位于二叉排序樹的葉子結點，并且一定是查找失敗時訪問的最后一個結點的左孩子或者右孩子。

通過使用二叉排序樹對動態(tài)查找表做查找和插入的操作，同時在中序遍歷二叉樹時，可以得到有關所有關鍵字的一個有序的序列。

一個無序序列可以通過構建一棵二叉排序樹，從而變成一個有序序列。

刪除：

在查找過程中，如果在使用二叉排序樹表示的動態(tài)查找表中刪除某個數據元素時，需要在成功刪除該結點的同時，依舊使這棵樹為二叉排序樹。

假設要刪除的結點為p,則對于二叉排序樹來說，需要根據結點p所在不同的位置作不同的操作，有一下三種可能：

• 結點p為葉子結點，此時只需要刪除該結點，并修改其雙親結點的指針即可；
• 結點p只有左子樹或者只有右子樹，此時只需要將其左子樹或者右子樹直接變?yōu)榻Y點p雙親結點的左子樹即可；
• 結點p左右子樹都有

此時有兩種處理方式：

1）令結點p的左子樹為其雙親結點的左子樹；結點p的右子樹為其自身直接前驅結點的右子樹

2）用結點p的直接前驅（或直接后繼）來替代結點p，同時再二叉排序樹中對其直接前驅（或者直接后繼）做刪除操作。為使用直接前驅代替結點p:

總結

使用二叉排序樹在查找表中做查找操作的時間復雜度同建立在二叉樹本身的結構有關。即使查找表中各種數據元素完全相同，但是不同的排列順序，構建出的二叉排序樹大不相同。

e.g.

查找表{45,24,53,12,37,93}和表{12,24,37,45,53,93}各自構建的二叉排序樹圖，下圖所示：

不同構造的二叉排序樹

使用二叉排序樹實現(xiàn)動態(tài)查找操作的過程，實際上就是從二叉排序樹的根結點到查找元素結點的過程，所以時間復雜度同被查找元素所在樹的深度（層次數）有關。

為了彌補二叉排序樹構造時產生如圖5 右側所示的影響算法效率的因素，需要對二叉排序樹做“平衡化”處理，使其成為一棵平衡二叉樹。

4、平衡樹（AVL）的定義，性質，ADT及其實現(xiàn)，平衡樹查找，插入算法，平衡因子的概念：

答：

平衡二叉樹是遵循以下兩個特點的二叉樹：

• 每棵樹中的左子樹和右子樹的深度差不能超過1
• 二叉樹中每棵子樹都要求是平衡二叉樹

其實就是二叉樹的基礎上，使樹中每棵子樹都滿足其左子樹和右子樹的深度差都不超過1.

平衡因子：每個結點都有其各自的平衡因子，表示的就是其左子樹深度同右子樹深度的差。平衡二叉樹中各平衡因子的取值只可能是：0、1、-1。

5、優(yōu)先隊列與堆，堆的定義，堆的生成，調整算法；范圍查詢；

答：

優(yōu)先隊列

是一個操作受限的線性表，數據只能在一斷進入，另一端出去，具有先進先去的性質。有時在隊列中需要處理優(yōu)先級的情況，即后面進入的數據需要提前出來，這里就需要優(yōu)先隊列。

優(yōu)先隊列是至少能夠提供插入和刪除最小值這兩種操作的數據結構。對應于隊列的操作，插入相當于入隊，刪除最小相當于出隊。

鏈表，二叉查找樹，都可以提供插入和刪除最小這兩種操作。

對于鏈表的實現(xiàn)，插入需要O(1)，刪除最小需要遍歷鏈表，故需要O（N）。

對于二叉查找樹，這兩種操作都需要O(logN)；而且隨著不停地刪除最小的操作，二叉查找樹會變得非常不平衡；同時使用二叉查找樹有些浪費，因此很多操作根本不需要。一種比較好的實現(xiàn)優(yōu)先隊列的方式是二叉堆（以下簡稱堆）。

堆

堆實質上是滿足如下性質的完全二叉樹：

樹中任一非葉結點的關鍵字均不大于（或者不小于）其左右孩子（若存在）結點的關鍵字。首先堆事完全二叉樹（只有最下面的兩層結點度能夠小于2，并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹），其次任意節(jié)點的左右孩子（若有）值都不小于其父親，這是小根堆，即最小的永遠在上面。相反是大根堆，即大的在上面。

插入：

二叉堆就是一個簡單的一維int數組，故不需要初始化，直接插入便可。每次插入都講新數據放到數組的最后的位置

刪除：

堆中每次都是只能刪除第一個數據。為了便于重建堆，實際的操作是將最后一個數據的值賦給根結點，然后再從根結點開始進行一次從上向下的調整。調整時先在左右兒子結點中找到最小的，如果父結點比這個最小的子結點還小，說明不需要調整，反之則將父結點和它交換后再考慮后面的結點。相當于從根結點將一個數據的“下沉”過程。

6、查找算法復雜度分析

四、排序(Sort)

1、排序基本概念；

重排一個記錄序列，使之成為按關鍵字有序。

常見排序可以分為以下五類：

• 插入排序（簡單插入排序、希爾排序）
• 交換排序（冒泡排序、快速排序）
• 選擇排序（簡單選擇排序、堆排序）
• 歸并排序
• 計數排序（多關鍵字排序）

算法穩(wěn)定性

• 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j],且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
• 例如，對于如下冒泡排序算法，原本是穩(wěn)定的排序算法，如果將記錄交換的條件改成r[j]>=r[j+1]，則兩個相等的記錄就會交換位置，從而變成不穩(wěn)定的算法。
• 堆排序、快速排序、希爾排序、直接選擇排序不是穩(wěn)定的排序算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩(wěn)定的排序算法。

2、插入排序、希爾排序、選擇排序、快速排序、合并排序、基數排序等排序算法基本思想，算法代碼及基本的時間復雜度分析

1.冒泡排序(Bubble-Sort)

• 交換排序的一種
• 依次比較相鄰的兩個待排序元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來，將待排序元素從左至右比較一遍稱為一趟“冒泡”
• 每趟冒泡都將待排序列中的最大關鍵字交換到最后（或者最前）位置
• 直到全部元素有序為止或者直到某次冒泡過程中沒有發(fā)生交換位置
• 把小的元素往前調（把大的元素往后調）
• 冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。

原理：

比較兩個相鄰的元素，將值大的元素交換到右邊

1.比較相鄰元素。如果第一個比第二個大，就交換他們。

2.對每一對相鄰元素做同樣的工作，從第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。

3.針對所有元素重復以上步驟，除了最后一個。

4.持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一堆數字需要比較。

思路：

依次比較相鄰的兩個數，將比較小的數放在前面，比較大的數放在后面。

(1)第一次比較：首先比較第一和第二個數，將小數放在前面，將大數放在后面。

(2)比較第2和第3個數，將小數 放在前面，大數放在后面。

…

(3)如此繼續(xù)，直到比較到最后的兩個數，將小數放在前面，大數放在后面，重復步驟，直至全部排序完成

(4)在上面一趟比較完成后，最后一個數一定是數組中最大的一個數，所以在比較第二趟的時候，最后一個數是不參加比較的。

(5)在第二趟比較完成后，倒數第二個數也一定是數組中倒數第二大數，所以在第三趟的比較中，最后兩個數是不參與比較的。

(6)依次類推，每一趟比較次數減少依次

舉例：

(1)要排序數組:[10,1,35,61,89,36,55]

(2)第一趟排序：

第一次排序：10和1比較，10大于1，交換位置 　 [1,10,35,61,89,36,55]

第二趟排序：10和35比較，10小于35，不交換位置　　[1,10,35,61,89,36,55]

第三趟排序：35和61比較，35小于61，不交換位置　　[1,10,35,61,89,36,55]

第四趟排序：61和89比較，61小于89，不交換位置　　[1,10,35,61,89,36,55]

第五趟排序：89和36比較，89大于36，交換位置　　　[1,10,35,61,36,89,55]

第六趟排序：89和55比較，89大于55，交換位置　　　[1,10,35,61,36,55,89]

第一趟總共進行了六次比較，排序結果：[1,10,35,61,36,55,89]

(3)第二趟排序：

第一次排序：1和10比較，1小于10，不交換位置　　1,10,35,61,36,55,89

第二次排序：10和35比較，10小于35，不交換位置 1,10,35,61,36,55,89

第三次排序：35和61比較，35小于61，不交換位置 1,10,35,61,36,55,89

第四次排序：61和36比較，61大于36，交換位置　　　1,10,35,36,61,55,89

第五次排序：61和55比較，61大于55，交換位置　　　1,10,35,36,55,61,89

第二趟總共進行了5次比較，排序結果：1,10,35,36,55,61,89

(4)第三趟排序：

1和10比較，1小于10，不交換位置　　1,10,35,36,55,61,89

第二次排序：10和35比較，10小于35，不交換位置 1,10,35,36,55,61,89

第三次排序：35和36比較，35小于36，不交換位置 1,10,35,36,55,61,89

第四次排序：36和61比較，36小于61，不交換位置　　　1,10,35,36,55,61,89

第三趟總共進行了4次比較，排序結果：1,10,35,36,55,61,89

到目前位置已經為有序的情形了。

算法分析：

(1)由此可見：N個數字要排序完成，總共進行N-1趟排序，每i趟的排序次數為(N-i)次，所以可以用雙重循環(huán)語句，外層控制循環(huán)多少趟，內層控制每一趟的循環(huán)次數

(2)冒泡排序的優(yōu)點：每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。如上例：第一趟比較之后，排在最后的一個數一定是最大的一個數，第二趟排序的時候，只需要比較除了最后一個數以外的其他的數，同樣也能找出一個最大的數排在參與第二趟比較的數后面，第三趟比較的時候，只需要比較除了最后兩個數以外的其他的數，以此類推……也就是說，沒進行一趟比較，每一趟少比較一次，一定程度上減少了算法的量。

(3)時間復雜度

1.如果我們的數據正序，只需要走一趟即可完成排序。所需的比較次數C和記錄移動次數M均達到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的時間復雜度為O(n)。

2.如果很不幸我們的數據是反序的，則需要進行n-1趟排序。每趟排序要進行n-i次比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：

綜上所述：冒泡排序總的平均時間復雜度為：O(n^2) ,時間復雜度和數據狀況無關。

code:Bubble Sort

#include <stdio.h>#define ARR_LEN 255 /*數組長度上限*/ #define elemType int /*元素類型*//* 冒泡排序 */ /* 1. 從當前元素起，向后依次比較每一對相鄰元素，若逆序則交換 */ /* 2. 對所有元素均重復以上步驟，直至最后一個元素 */ /* elemType arr[]: 排序目標數組; int len: 元素個數 */ void bubbleSort (elemType arr[], int len) {elemType temp;int i, j;for (i=0; i<len-1; i++) /* 外循環(huán)為排序趟數，len個數進行l(wèi)en-1趟 */for (j=0; j<len-1-i; j++) { /* 內循環(huán)為每趟比較的次數，第i趟比較len-i次 */if (arr[j] > arr[j+1]) { /* 相鄰元素比較，若逆序則交換（升序為左大于右，降序反之） */temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}} }int main (void) {elemType arr[ARR_LEN] = {3,5,1,-7,4,9,-6,8,10,4};int len = 10;int i;bubbleSort (arr, len);for (i=0; i<len; i++)printf ("%d\t", arr[i]);putchar ('\n');return 0; }

2.插入排序（Insertion-Sort）

思路1

• 創(chuàng)建一個空數組，存放排序的數據
• 從原數組中依次選擇的數據
• 在新數組中尋找插入點
• 如該點沒有數據，就將數據插入該點。否則需把該插入點后面的所有數據向后移動一位，空出位置，插入數據。

1、原理：從整個待排序列中選出一個元素插入到已經有序的子序列中去，得到一個有序的、元素加一的子序列，直到整個序列的待插入元素為0，則整個序列全部有序。

2、思路：

(1)設置監(jiān)視哨r[0]，將待插入的記錄值賦值給r[0];

(2)設置開始查找的位置j;

(3)在數組中搜索，搜索 中將第j個記錄后移，直到r[0].key>=r[j].key為止

(4)將r[0]插入r[j+1]的位置上。

3、舉例

(1)待排序數組：[5,3,4,0,6]

(2)第一趟排序：[5,3,4,0,6]

將r[0]=5設置為監(jiān)視哨，將1位置上的數3和監(jiān)視哨5進行比較，3小于5，將5和3交換。

排序結果為：[3,5,4,0,6] 此時0-1范圍上的數值大小已經排好了。

(3)第二趟比較：[3,5,4,0,6]

將4和5進行比較，4比5小，交換位置，排序結果為：[3,4,5,0,6]

將4和3進行比較，4比3大，不交換位置。

排序結果為：[3,4,5,0,6]　　此時0-2位置上的數值大小已經排列好了

(4)第三趟比較：[3,4,5,0,6]

將0和5做比較，0比5小，交換位置，排序結果為：[3,4,0,5,6]

將0和4做比較，0比4小，交換位置，排序結果為：[3,0,4,5,6]

將0和3做比較，0比3小，交換位置，排序結果為：[0,3,4,5,6]

排序結果為：[0,3,4,5,6]，此時0-3位置上的書已經排好序

(5)第四趟比較：[0,3,4,5,6]

6比5大，已經全局有序 ，不用進行任何的交換

• 實現(xiàn)思路：

1.從數組的第二個數據開始往前比較，即一開始用第二個數和他前面的一個比較，如果 符合條件（比前面的大或者小，自定義），則讓他們交換位置。

2.然后再用第三個數和第二個比較，符合則交換，但是此處還得繼續(xù)往前比較，比如有 5個數8，15，20，45, 17,17比45小，需要交換，但是17也比20小，也要交換，當不需 要和15交換以后，說明也不需要和15前面的數據比較了，肯定不需要交換，因為前 面的數據都是有序的。

3.重復步驟二，一直到數據全都排完。

• 動圖演示：

code:Insection-Sort

/* 插入排序*/int num[5] = {3, 7, 1, 8, 5};int cur;int i, j;int length = sizeof(num)/sizeof(num[0]);for (i = 1; i < length; i++){cur = num[i]; //待排序元素for (j = i - 1; j >= 0 && num[j] > cur; j--){num[j + 1] = num[j];}num[j + 1] = cur;}

3.希爾排序(Shell’s-Sort)

• 縮小增量排序
• 其實插入排序的改進版，改進點：減少插入排序(Insertion-Sort)時移動元素次數

基本思想：

先將整個待記錄序列分割為若干子序列分別進行直接插入排序，待整個序列的記錄“基本有序”時，再對全體記錄進行一次直接插入有序。

算法思想
??希爾排序是特殊的插入排序，直接插入排序每次插入前的遍歷步長為1，而希爾排序是將待排序列分為若干個子序列，對這些子序列分別進行直接插入排序，當每個子序列長度為1時，再進行一次直接插入排序時，結果一定是有序的。常見的劃分子序列的方法有：初始步長（兩個子序列相應元素相差的距離）為要排的數的一半，之后每執(zhí)行一次步長折半。

code:Shell’s-Sort

#include <stdio.h> #include <malloc.h>void shellSort(int *a, int len); // 函數聲明int main(void) {int i, len, * a;printf("請輸入要排的數的個數：");scanf("%d",&len);a = (int *)malloc(len * sizeof(int)); // 動態(tài)定義數組printf("請輸入要排的數：\n");for (i = 0; i < len; i++) { // 數組值的輸入scanf("%d",&a[i]);} shellSort(a, len); // 調用希爾排序函數printf("希爾升序排列后結果為：\n");for (i = 0; i < len; i++) { // 排序后的結果的輸出printf("%d\t",a[i]);}printf("\n");return 0; }void shellSort(int *a, int len) {int i, j, k, tmp, gap; // gap 為步長for (gap = len / 2; gap > 0; gap /= 2) { // 步長初始化為數組長度的一半，每次遍歷后步長減半,for (i = 0; i < gap; ++i) { // 變量 i 為每次分組的第一個元素下標 for (j = i + gap; j < len; j += gap) { //對步長為gap的元素進行直插排序，當gap為1時，就是直插排序tmp = a[j]; // 備份a[i]的值k = j - gap; // j初始化為i的前一個元素（與i相差gap長度）while (k >= 0 && a[k] > tmp) {a[k + gap] = a[k]; // 將在a[i]前且比tmp的值大的元素向后移動一位k -= gap;}a[k + gap] = tmp; }}} }

時間復雜度
??希爾排序的時間復雜度依賴于增量序列的函數，有人在大量的實驗后得出的結論：當n在某個特定的范圍后，在最優(yōu)的情況下，希爾排序的時間復雜度為O(n1.3)，在最差的情況下，希爾排序的時間復雜度為：O(n2).
空間復雜度
??希爾排序的空間復雜度：O(1).

4.快速排序(Quick-Sort)

基本概念

• 就平均時間而言，快速排序是目前被認為最好的一種內部排序方法，由C.A.R.Hoare發(fā)明
• 分治法(devide and conquer)思想體現(xiàn)
• Unix系統(tǒng)函數庫所提供的標準排序方法
• C標準函數庫的排序方法直接去命名為qsort()
• 軸值(pivot)：
  • 書上稱樞軸
  • 用于將記錄集“分割”為兩個部分的那個鍵值
• 分割(partition)：
  • 將記錄集分為兩個部分，前面部分記錄的鍵值都比軸值小，后面部分的鍵值都比軸值大

基本思想

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

原理

設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選

快排圖

用數組的第一個數）作為關鍵數據，然后將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時產生變動。 [1]

一趟快速排序的算法是： [1]

1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1； [1]

2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]； [1]

3）從j開始向前搜索，即由后開始向前搜索(j–)，找到第一個小于key的值A[j]，將A[j]和A[i]的值交換； [1]

4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]的值交換； [1]

5）重復第3、4步，直到ij； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，ij這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結束）。 [1]

code(Quick-Sort):

#include <iostream>using namespace std;void Qsort(int arr[], int low, int high){if (high <= low) return;int i = low;int j = high + 1;int key = arr[low];while (true){/*從左向右找比key大的值*/while (arr[++i] < key){if (i == high){break;}}/*從右向左找比key小的值*/while (arr[--j] > key){if (j == low){break;}}if (i >= j) break;/*交換i,j對應的值*/int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}/*中樞值與j對應值交換*/int temp = arr[low];arr[low] = arr[j];arr[j] = temp;Qsort(arr, low, j - 1);Qsort(arr, j + 1, high); }int main() {int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*這里原文第三個參數要減1否則內存越界*/for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++){cout << a[i] << "";}return 0; }/*參考數據結構p274(清華大學出版社，嚴蔚敏)*/

5.選擇排序(Selection-Sort)

基本思想：

• 是每一次從待排序的數據元素中選出最小（或者最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。選擇排序是不穩(wěn)定的排序方法
• 與冒泡排序不同：減少了元素交換次數

選擇排序：從小到大的方式開始排序

思路：

第一次循環(huán)找到數組中最小的一個元素，放在數組的第一個位置

第二次循環(huán)找到數組中第二小的一個元素，放在數組的第二個位置

第三次循環(huán)找到數組中第三小的一個元素，放在數組的第三個位置

以此類推，直到走完數組中的所有元素

code(Selection-Sort):

//選擇排序 void selectionSort(int arr[], int len) {int i, j, tmp = 0;for (i = 0; i < len - 1; i++){int min = i;for (j = i + 1; j < len; j++) //走訪未排序的元素{if (arr[j] < arr[min]) //找到目前最小值{min = j; //記錄最小值}}//做交換tmp = arr[min]; arr[min] = arr[i];arr[i] = tmp;} }

6.計數排序(Counter-Sort)

• 是一種基于非比較的排序算法，該算法于1954年由Harold H.Seward提出。它的優(yōu)勢在于對一定范圍內的整數排序時，它的復雜度為O(n+k)(k是整數的范圍)，快于任何比較排序算法。這是一種犧牲空間換時間的做法。
• 這適合數字類型的排序

基本思想

• 開啟額外的空間，來存儲數組中的元素
• 舊數組中元素（數字）作為新數組的下標，并記錄相同元素的個數
• 最后將新數組反向輸出，從而得到有序的數組

動圖演示

code(Counter-Sort)

//計數排序 void CountSort(int data[], int n) {int i, j, count, *data_p, temp;data_p = (int*)malloc(sizeof(int)*n);for (i = 0; i < n; i++)//初始化data_p{data_p[i] = 0;}for (i = 0; i < n; i++){count = 0;for (j = 0; j < n; j++)//掃描待排序數組{if (data[j] < data[i])//統(tǒng)計比data[i]值小的值的個數{count++;}}while (data_p[count] != 0)//對于相等非0的數據，應向后措一位。數據為0時，因數組data_p被初始化為0，故不受影響。{/* 注意此處應使用while循環(huán)進行判斷，若用if條件則超過三個重復值后有0出現(xiàn) */count++;}data_p[count] = data[i];//存放到data_p中的對應位置}//用于檢查當有多個數相同時的情況i = 0, j = n;while (i < j){if (data_p[i] == 0){temp = i - 1;data_p[i] = data_p[temp];}//of ifi++;}//of whilefor (i = 0; i < n; i++)//把排序完的數據復制到data中{data[i] = data_p[i];}free(data_p);//釋放data_p }

7.桶排序(Bucket-Sort)

基本思想

將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）

桶排序算法，從小到大的方式開始排序

實現(xiàn)思路：將一個數組盡量拆分成一個個小數組（桶），再對桶里面的元素進行排序，這個排序可以各種類型排序：插入，快排等

和計數排序不同：計數排序只能用于數字，每個元素作為新數組下標。

code(Bucket-Sort)

/** 桶排序** 參數說明：* a -- 待排序數組* n -- 數組a的長度* max -- 數組a中最大值的范圍*/ void BucketSort(int a[], int n, int max) {int i, j;int *buckets;if (a == NULL || n < 1 || max < 1)return;// 創(chuàng)建一個容量為max的數組buckets，并且將buckets中的所有數據都初始化為0。if ((buckets = (int *)malloc(max * sizeof(int))) == NULL)return;memset(buckets, 0, max * sizeof(int));// 1. 計數for (i = 0; i < n; i++)buckets[a[i]]++;// 2. 排序for (i = 0, j = 0; i < max; i++)while ((buckets[i]--) > 0)a[j++] = i;free(buckets); }

8.歸并排序(Merge-Sort)

基本思想

利用歸并思想實現(xiàn)的排序方法，該算法采用經典的分治(divide-and-conquer)策略(分治法將問題分成一些小的問題然后遞歸求解，而治的階段則將分的階段得到的各個答案“修補”在一起，即分而治之)

思路：

• 分階段
  • 類似于二分查找：將一個大數組拆半拆分成2個數組
  • 再對這2個數組進行拆半拆分為4個小數組
  • …
  • 直到小數組（長度=1）不可再拆分
  • 最后交換左右2個子數組來排序
• 治階段
  • 將2個子數組合并為一個有序數組
  • 創(chuàng)建一個臨時temp數組，長度為2個子數組長度和
  • 最終完成兩個子數組的合并

code(Merge-Sort)

// 遞歸的方式實現(xiàn)歸并排序 #define MAXSIZE 10 // 實現(xiàn)歸并，并把結果存放到list1 void merging(int *list1, int list1_size, int *list2, int list2_size) {int i, j, k, m;int temp[MAXSIZE];i = j = k = 0;while (i < list1_size && j < list2_size){if (list1[i] < list2[j]){temp[k] = list1[i];k++;i++;}else{temp[k++] = list2[j++];}}while (i < list1_size){temp[k++] = list1[i++];}while (j < list2_size){temp[k++] = list2[j++];}for (m = 0; m < (list1_size + list2_size); m++){list1[m] = temp[m];} }void MergeSort(int k[], int n) {if (n > 1){/**list1是左半部分，list2是右半部分*/int *list1 = k;int list1_size = n / 2;int *list2 = k + list1_size;int list2_size = n - list1_size;MergeSort(list1, list1_size);MergeSort(list2, list2_size);// 把兩個合在一起merging(list1, list1_size, list2, list2_size);} }

9.基數排序(Redix-Sort)

基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。

動畫：

code(Radix-Sort)

//基數排序 int maxbit(int data[], int n) //輔助函數，求數據的最大位數 {int maxData = data[0]; ///< 最大數/// 先求出最大數，再求其位數，這樣有原先依次每個數判斷其位數，稍微優(yōu)化點。for (int i = 1; i < n; ++i){if (maxData < data[i])maxData = data[i];}int d = 1;int p = 10;while (maxData >= p){//p *= 10; // Maybe overflowmaxData /= 10;++d;}return d;/* int d = 1; //保存最大的位數int p = 10;for(int i = 0; i < n; ++i){while(data[i] >= p){p *= 10;++d;}}return d;*/ } void RadixSort(int data[], int n) {int d = maxbit(data, n);int *tmp = new int[n];int *count = new int[10]; //計數器int i, j, k;int radix = 1;for (i = 1; i <= d; i++) //進行d次排序{for (j = 0; j < 10; j++)count[j] = 0; //每次分配前清空計數器for (j = 0; j < n; j++){k = (data[j] / radix) % 10; //統(tǒng)計每個桶中的記錄數count[k]++;}for (j = 1; j < 10; j++)count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶for (j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中{k = (data[j] / radix) % 10;tmp[count[k] - 1] = data[j];count[k]--;}for (j = 0; j < n; j++) //將臨時數組的內容復制到data中data[j] = tmp[j];radix = radix * 10;}delete[]tmp;delete[]count; }

10.堆排序(Heap-Sort)

堆排序是指利用堆這種數據結構所設計的一種排序算法。堆積是一種近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種：

1.大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列；

2.小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；

堆排序的平均時間復雜度為Ο(nlogn)。

算法步驟

1.創(chuàng)建一個堆H[o…n-1];

2.把堆首（最大值）和堆尾互換；

3.把堆的尺寸縮小1，并調用shift_down(0)，目的是把新的數組頂端數據調整到相應位置；

4.重復步驟2，直到堆的尺寸為1。

動圖

code(Heap-Sort)

//堆排序 void swap(int *a, int *b) {int temp = *b;*b = *a;*a = temp; }void max_heapify(int arr[], int start, int end) {// 建立父節(jié)點指標和子節(jié)點指標int dad = start;int son = dad * 2 + 1;while (son <= end) { // 若子節(jié)點指標在範圍內才做比較if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節(jié)點大小，選擇最大的son++;if (arr[dad] > arr[son]) //如果父節(jié)點大於子節(jié)點代表調整完畢，直接跳出函數return;else { // 否則交換父子內容再繼續(xù)子節(jié)點和孫節(jié)點比較swap(&arr[dad], &arr[son]);dad = son;son = dad * 2 + 1;}} }void HeapSort(int arr[], int len) {int i;// 初始化，i從最後一個父節(jié)點開始調整for (i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);// 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢for (i = len - 1; i > 0; i--) {swap(&arr[0], &arr[i]);max_heapify(arr, 0, i - 1);} }

五、圖

1、圖的基本概念

答：

**頂點：**使用圖表示的每個數據元素稱作頂點

頂點之間的關系有兩種“有向圖和無向圖”，如下圖所示：

(a)中頂點V1和V2只有單方向的關系，只能通過V1找到V2，反過來行不通，因此兩頂點之間的關系表示為：<V1,V2>；

(b)中頂點之間具有雙向的關系，之間用直線連通，對于V1和V2頂點來說，既可以通過V1找到V2，也可以通過V2找到V1，兩頂點之間的關系表示為：(V1,V2)；

“弧”和“邊”：

在有向圖中，<v,w>表示為從v到w的一條弧；在無向圖中，(v,w)表示為頂點v和頂點w之間的一條邊。

完全圖：

對于無向圖來說，如果圖中每個頂點都和除自身之外的所有頂點有關系，那么就稱這樣的無向圖為完全圖。下圖就為一個完全圖。

對于有n個頂點的完全圖，其中的邊的數目為：
$$\frac{1}{2}n(n?1)$$

2、圖的存儲結構，鄰接矩陣，鄰接表

答：

順序存儲結構+三種鏈式存儲結構（鄰接表，鄰接多重表，十字鏈表）

(1)數組表示法：（鄰接矩陣）

使用數組存儲圖時，需要使用兩個數組，一個數組存放在圖中頂點本身的數據（一維數組），另外一個數組用于存儲各頂點之間的關系（二維數組）。

不同類型的圖，存儲方式略有不同，根據圖有權無權，可以將圖分為兩個大類：圖和網。

圖：

包括無向圖和有向圖。在使用二維數組存儲圖中頂點之間的關系時，如果頂點之間存在邊或者弧，在相應位置用1表示，反之用0表示。

網：

是指帶權的圖，包括無向網和有向網。使用二維數組存儲網中頂點之間的關系，頂點之間如果有邊或者弧的存成，在數組的相應位置存儲其權值；反之用∞表示。

（2）鄰接表

鄰接表是圖的一種鏈式存儲結構。使用鄰接表存儲圖時，對于圖中的每一個頂點和它相關的鄰接點，都存儲到一個鏈表中。每個鏈表都配有頭結點，頭結點的數據域不為NULL，而是用于存儲頂點本身的數據；后續(xù)鏈表中各個結點存儲的是當前頂點的所有鄰接點。

所以，采用鄰接表存儲圖時，有多少頂點就會構建多少個鏈表，為了便于管理這些鏈表，常用的方法是將所有鏈表的鏈表頭按照一定的順序存儲在一個數組中（也可以用鏈表串起來）。

在鄰接表中，每個鏈表的頭結點和其他結點的組成成分有略微的不同。

頭結點需要存儲每個頂點的數據和指向下一個節(jié)點的指針，由兩部分構成；而在存儲鄰接接點時，由于每個頂點的數據都存儲在數組中，所以每個鄰接點只需要存儲自己在數組中的位置下標即可。另外還需要一個指向下一個節(jié)點的指針。除此之外，如果存儲的是網，還需要一個記錄權值的信息域。所以表頭結點和其他結點的構造分別為：

表結點結構

info域對于無向圖來說，本身不具備權值和其他相關信息，就可以根據需要將之刪除。

例如：

當存儲下圖a所示的有向圖時，構建的鄰接表如下圖b所示

? 有向圖和對應的鄰接表

3、圖的遍歷，廣度優(yōu)先遍歷和深度優(yōu)先遍歷

答：

深度優(yōu)先遍歷（DFS,Depth First Search）

無向圖

深度優(yōu)先搜索的過程類似于樹的先序遍歷，首先從例子中體會深度優(yōu)先搜索。例如上圖是一個無向圖，采用深度優(yōu)先算法遍歷整個圖的過程為：

1.首先任意找一個未被遍歷過的頂點，例如從V1開始，由于V1率先訪問過了，所以需要標記V1的狀態(tài)為訪問過；

2.然后遍歷V1的鄰接點，例如訪問V2，并做標記，然后訪問V2的鄰接點，例如V4（做標記），然后V8，然后V5；

3.當繼續(xù)遍歷V5的鄰接點時，，根據之前做的標記顯示，所有鄰接點都被訪問過了。此時，從V5回退到V8,看V8是否有未被訪問過的鄰接點，如果沒有，繼續(xù)回退到V4,V2,V1；

4.通過查看V1，找到一個未被訪問過的頂點V3，繼續(xù)遍歷，然后訪問V3鄰接點V6，然后V7；

5.由于V7沒有未被訪問的鄰接點，所以回退到V6，繼續(xù)回退到V3，最后達到V1，發(fā)現(xiàn)沒有未被訪問的；

6.最后一步需要判斷是否所有頂點都被訪問，如果還有未被訪問的，以未被訪問的頂點為第一個頂點，繼續(xù)依照上邊的方式進行遍歷。

所謂深度優(yōu)先搜索，是從圖中的一個頂點出發(fā)，每次遍歷當前訪問頂點的臨界點，一直到訪問的頂點沒有未被訪問過的臨界點為止。然后采用一次回退的方式，查看來的路上每一個頂點是否有其它未被訪問的臨界點。訪問完成后，判斷圖中的頂點是否已經全部遍歷完成，如果沒有，以未訪問的頂點為起始點，重復上述過程。

廣度優(yōu)先遍歷(BFS,Breadth First Search)

廣度優(yōu)先遍歷類似于樹的層次遍歷。從圖的某一個頂點出發(fā)，遍歷每一個頂點時，一次遍歷其所有的鄰接點，然后再從這些鄰接點出發(fā)，同樣依次訪問它們的鄰接點。按照此過程，直到圖中所有被訪問過的頂點鄰接點都被訪問到過。

最后還需要做的操作就是查看圖中是否已存在尚未被訪問的頂點。若有，則以該頂點為起始點，重復上述遍歷過程。

總結：

深度優(yōu)先搜索算法的實現(xiàn)運用主要是回溯法，類似于樹的先序遍歷算法；廣度優(yōu)先搜索算法借助隊列的先進先出特點，類似于樹的層次遍歷。

----------------------------------------網友版,感覺不錯---------------------------------------------------

---

深度優(yōu)先搜索（DFS）
深度優(yōu)先搜索在搜索過程中訪問某個頂點后，需要遞歸地訪問此頂點的所有未訪問過的相鄰頂點。
初始條件下所有節(jié)點為白色，選擇一個作為起始頂點，按照如下步驟遍歷：
a. 選擇起始頂點涂成灰色，表示還未訪問
b. 從該頂點的鄰接頂點中選擇一個，繼續(xù)這個過程（即再尋找鄰接結點的鄰接結點），一直深入下去，直到一個頂點沒有鄰接結點了，涂黑它，表示訪問過了
c. 回溯到這個涂黑頂點的上一層頂點，再找這個上一層頂點的其余鄰接結點，繼續(xù)如上操作，如果所有鄰接結點往下都訪問過了，就把自己涂黑，再回溯到更上一層。
d. 上一層繼續(xù)做如上操作，知道所有頂點都訪問過。
用圖可以更清楚的表達這個過程：

1.初始狀態(tài)，從頂點1開始

2.依次訪問過頂點1,2,3后，終止于頂點3

3.從頂點3回溯到頂點2，繼續(xù)訪問頂點5，并且終止于頂點5

4.從頂點5回溯到頂點2，并且終止于頂點2

5.從頂點2回溯到頂點1，并終止于頂點1

6.從頂點4開始訪問，并終止于頂點4

從頂點1開始做深度搜索：

初始狀態(tài)，從頂點1開始

依次訪問過頂點1,2,3后，終止于頂點3

從頂點3回溯到頂點2，繼續(xù)訪問頂點5，并且終止于頂點5

從頂點5回溯到頂點2，并且終止于頂點2

從頂點2回溯到頂點1，并終止于頂點1

從頂點4開始訪問，并終止于頂點4

上面的圖可以通過如下鄰接矩陣表示：

int maze[5][5] = {{ 0, 1, 1, 0, 0 },{ 0, 0, 1, 0, 1 },{ 0, 0, 1, 0, 0 },{ 1, 1, 0, 0, 1 },{ 0, 0, 1, 0, 0 } };

DFS核心代碼如下（遞歸實現(xiàn)）：

#include <iostream> #define N 5 using namespace std; int maze[N][N] = {{ 0, 1, 1, 0, 0 },{ 0, 0, 1, 0, 1 },{ 0, 0, 1, 0, 0 },{ 1, 1, 0, 0, 1 },{ 0, 0, 1, 0, 0 } }; int visited[N + 1] = { 0, }; void DFS(int start) {visited[start] = 1;for (int i = 1; i <= N; i++){if (!visited[i] && maze[start - 1][i - 1] == 1)DFS(i);}cout << start << " "; } int main() {for (int i = 1; i <= N; i++){if (visited[i] == 1)continue;DFS(i);}return 0; }

非遞歸實現(xiàn)如下，借助一個棧：

#include <iostream> #include <stack> #define N 5 using namespace std; int maze[N][N] = {{ 0, 1, 1, 0, 0 },{ 0, 0, 1, 0, 1 },{ 0, 0, 1, 0, 0 },{ 1, 1, 0, 0, 1 },{ 0, 0, 1, 0, 0 } }; int visited[N + 1] = { 0, }; void DFS(int start) {stack<int> s;s.push(start);visited[start] = 1;bool is_push = false;while (!s.empty()){is_push = false;int v = s.top();for (int i = 1; i <= N; i++){if (maze[v - 1][i - 1] == 1 && !visited[i]){visited[i] = 1;s.push(i);is_push = true;break;}}if (!is_push){cout << v << " ";s.pop();}} } int main() {for (int i = 1; i <= N; i++){if (visited[i] == 1)continue;DFS(i);}return 0; }

有的DFS是先訪問讀取到的結點，等回溯時就不再輸出該結點，也是可以的。算法和我上面的區(qū)別就是輸出點的時機不同，思想還是一樣的。DFS在環(huán)監(jiān)測和拓撲排序中都有不錯的應用。

廣度優(yōu)先搜索（BFS）
廣度優(yōu)先搜索在進一步遍歷圖中頂點之前，先訪問當前頂點的所有鄰接結點。
a .首先選擇一個頂點作為起始結點，并將其染成灰色，其余結點為白色。
b. 將起始結點放入隊列中。
c. 從隊列首部選出一個頂點，并找出所有與之鄰接的結點，將找到的鄰接結點放入隊列尾部，將已訪問過結點涂成黑色，沒訪問過的結點是白色。如果頂點的顏色是灰色，表示已經發(fā)現(xiàn)并且放入了隊列，如果頂點的顏色是白色，表示還沒有發(fā)現(xiàn)
d. 按照同樣的方法處理隊列中的下一個結點。
基本就是出隊的頂點變成黑色，在隊列里的是灰色，還沒入隊的是白色。
用一副圖來表達這個流程如下：

1.初始狀態(tài)，從頂點1開始，隊列={1}

2.訪問1的鄰接頂點，1出隊變黑，2,3入隊，隊列={2,3,}

3.訪問2的鄰接結點，2出隊，4入隊，隊列={3,4}

4.訪問3的鄰接結點，3出隊，隊列={4}

5.訪問4的鄰接結點，4出隊，隊列={ 空}

從頂點1開始進行廣度優(yōu)先搜索：

初始狀態(tài)，從頂點1開始，隊列={1}

訪問1的鄰接頂點，1出隊變黑，2,3入隊，隊列={2,3,}

訪問2的鄰接結點，2出隊，4入隊，隊列={3,4}

訪問3的鄰接結點，3出隊，隊列={4}

訪問4的鄰接結點，4出隊，隊列={ 空}
結點5對于1來說不可達。
上面的圖可以通過如下鄰接矩陣表示：

int maze[5][5] = {{ 0, 1, 1, 0, 0 },{ 0, 0, 1, 1, 0 },{ 0, 1, 1, 1, 0 },{ 1, 0, 0, 0, 0 },{ 0, 0, 1, 1, 0 } };

BFS核心代碼如下：

#include <iostream> #include <queue> #define N 5 using namespace std; int maze[N][N] = {{ 0, 1, 1, 0, 0 },{ 0, 0, 1, 1, 0 },{ 0, 1, 1, 1, 0 },{ 1, 0, 0, 0, 0 },{ 0, 0, 1, 1, 0 } }; int visited[N + 1] = { 0, }; void BFS(int start) {queue<int> Q;Q.push(start);visited[start] = 1;while (!Q.empty()){int front = Q.front();cout << front << " ";Q.pop();for (int i = 1; i <= N; i++){if (!visited[i] && maze[front - 1][i - 1] == 1){visited[i] = 1;Q.push(i);}}} } int main() {for (int i = 1; i <= N; i++){if (visited[i] == 1)continue;BFS(i);}return 0; }

4、最小生成樹基本概念，Prim算法，Kruskal算法；最短路徑問題，廣度優(yōu)先遍歷算法，Dijkstra算法,Floyd算法；拓撲排序

答：

（1）最小生成樹問題

假設通過綜合分析，城市之間的權值如圖a所示，對于b的方案中，選擇權值總和為7的兩種方案最節(jié)約經費。

簡單的理解就是給定一個帶有權值的連通圖（連通網），如何從眾多的生成樹中篩選出權值綜合最小生成樹，即為該圖的最小生成樹。

給定一個連通網，求最小生成樹的方法有：普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法。

Prim算法：

普里姆算法在找最小生成樹時，將頂點分為兩類，一類是在查找的過程中包含在樹中的（假設為A類），剩下的是另一類（假設為B類）。

對于給定的連通網，起始狀態(tài)全部頂點都歸為B類。在找最小生成樹時，選定任意一個頂點作為起始點，并將之從B類移至A類；然后找出B類中到A類中的頂點之間權值最小的頂點，將之從B類移至A類，如此重復，直到B類中沒有頂點為止。所走過的頂點和邊就是該連通圖的最小生成樹。

通過普里姆算法查找上圖中(a)的最小生成樹的步驟為：

假如從頂點A出發(fā)，頂點B、C、D到頂點A的權值分別為2、4、2，所以，對于頂點A來水，頂點B和頂點D到A的權值最小，假設先找到頂點B：

繼續(xù)分析頂點C和D，頂點C到B的權值為3，到A的權值為4；頂點D到A的權值為2，到B的權值為無窮大（如果之間沒有直接通路，設定權值為無窮大）。所以頂點D到A的權值最小:

最后，只剩下頂點C，到A的權值為4，到B的權值和到D的權值一樣大，為3.所以該連通圖有兩個最小生成樹：

例子：

此圖結果應為：A-C,C-F,F-D,C-B,B-E

普里姆算法的運行效率只與連通網中包含的頂點數有關，而和網所包含的變數無關。所以普里姆算法只適合解決邊稠密的網，該算法運行的時間復雜度為：O(n^2)

Kruskal算法：

克魯斯卡爾算法的具體思路是：

將所有邊按照權值的大小進行升序排序，然后從小到大，一一判斷，條件為：如果這個邊不會與之前選擇的所有邊組成回路，就可以作為最小生成樹的一部分；反之，舍去。直到具有n個頂點的連通網篩選出來n-1條邊為止。篩選出來的邊和所有的頂點構成此連通網的最小生成樹。

判斷是否會產生回路的方法為：

在初始狀態(tài)下給每個頂點賦予不同的標記，對于遍歷過程的每條邊，都有兩個頂點，判斷這兩個頂點的標記是否一致，如果一致，說明它們本身就處在一棵樹中，如果連續(xù)連接就會產生回路；如果不一致，說明它們之間還沒有任何關系，可以連接。

假設遍歷一條由頂點A和B構成的邊，而頂點A和頂點B標記不同，此時不僅需要將頂點A的標記更新為頂點B的標記，還需要更改所有和頂點A標記相同的頂點的標記，全部改為頂點B的標記。

連通網

例如，使用克魯斯卡爾算法找上圖的最小生成樹的過程為：

首先，在初始狀態(tài)下，對各頂點賦予不同的標記（用顏色區(qū)別），如下圖所示：

對所有邊按照權值大小進行排序，按照從小到大的順序進行判斷，首先是（1,3），由于頂點1和頂點3標記不同，所以可以構成生成樹的一部分，遍歷所有頂點，將與頂點3標記相同的全部更改為頂點1的標記，如下圖所示：

其次是（4,6）邊，兩頂點標記不同，所以可以構成生成樹的一部分，更新所有頂點的標記為：

其次是（2,5）邊，兩頂點標記不同，可以構成樹的一部分，更新所遇頂點的標記為：

然后最小的是（3,6）邊，兩者標記不同，可以連接，遍歷所有頂點，將與頂點6標記相同的所有頂點更改為頂點1的標記：

繼續(xù)選擇權值最小的邊，此時會發(fā)現(xiàn)，權值為5的邊有3個，其中（1,4）和（3,4）各自兩頂點的標記一樣，如果連接會產生回路，所以舍去，而（2,3）標記不一樣，可以選擇，將所有與頂點2標記相同的頂點的標記全部改為同頂點3相同的標記：

當選取的邊的數量相比于頂點的數量小1時，說明最小生成樹已經生成。所以最終采用克魯斯卡爾算法得到的最小生成樹如上圖所示。

總結：

Prim(普里姆)算法，該算法從頂點的角度為出發(fā)點，時間復雜度為O(n^2),更適合于解決邊的稠密度更高的連通網。

Kruskal(克魯斯卡爾)算法，從邊的角度求網的最小生成樹，時間復雜度為O(eloge)，和普里姆算法相反，適合求邊稀疏的網的最小生成樹。

（2）最短路徑問題

在一個網（有權圖）中，求一個頂點到另外一個頂點的最短路徑的計算方式有兩種：迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法。迪杰斯特拉算法計算的是：有向網中的某個頂點到其余所有頂點的最短路徑；弗洛伊德算法計算的是：任意兩個頂點之間的最短路徑。

迪杰斯特拉（Dijkstra）算法：

迪杰斯特拉算法計算的是從網中一個頂點到其它頂點之間的最短路徑問題。

帶權有向圖

如圖所示，一個有向圖，在計算V0到其它所有頂點之間的最小路徑時，迪杰斯特拉算法的計算方式為：

從V0出發(fā)，由于可以直接到達V2和V5，而其它頂點和V0之間沒有弧的存在，所以之間的距離設定為無窮大，可以得到下面這個表格：

從表格中可以看到，V0到V2的距離最近，所以迪杰斯特拉算法設定V0-V2為V0到V2之間的最短路徑，最短路徑的權值和為10.

已經判斷V0-V2為最短路徑，所以以V2為起始點，判斷V2到除了V0以外的其余各點之間的距離，如果對應的權值比前一張表格中記錄的數值小，就說明網中有一條更短的路徑，直接更新表格；反之表格中的數據不變。可以得到下面這個表格：

例如，表格中V0到V3的距離，發(fā)現(xiàn)當通過V2到達V3的距離比之前的∞要小，所以更新表格。

更新之后，發(fā)現(xiàn)V0-V4的最短路徑的值為30.之后從V4出發(fā)，判斷到未確定最短路徑的其他頂點的距離，繼續(xù)更新表格：

更新后確認從V0到V3的最短路徑為V0-V4-V3，權值為50。然后從V3出發(fā)，繼續(xù)判斷：

對于V5來說，通過V0-V4-V3-V5的路徑要比之前的權值90還要小，所以更新表格，更新后可以看到，V0-V5的距離此時最短，可以確認V0到V5的最短路徑為60.

最后確定V0-V1的最短路徑，由于從V0無法到達V1，最終設定V0到V1的最短路徑為∞（無窮大）。

在確定了V0與其他所遇頂點的最短路徑后，迪杰斯特拉算法才算結束。示例中借用了 有向圖對迪杰斯特拉算法進行講解，實際上無向圖的最短路徑問題也可以使用迪杰斯特拉算法解決，解決過程與上述過程完全一致。

總結：

迪杰斯特拉算法解決的是從網中一個頂點到所有其他頂點之間的最短路徑，算法整體的時間復雜度為O(n^2)。但是如果需要求任意兩頂點之間的最短路徑，使用迪杰斯特拉算法雖然也可以解決，但是大材小用，相比之下弗洛伊德算法更適合解決此問題。

弗洛伊德(Floyd)算法：

弗洛伊德的核心思想：對于網中的任意兩個頂點（例如頂點A到頂點B）來說，之間的最短路徑不外乎有兩種情況：

1.直接從頂點A到頂點B的弧的權值為頂點A到頂點B的最短路徑；

2.從頂點A開始，經過若干頂點，最終達到頂點B，期間經過的弧的權值和為頂點A到頂點B的最短路徑

帶權圖

例如，在使用弗洛伊德算法計算上圖中的任意兩個頂點之間的最短路徑時，具體實施步驟為：

首先，記錄頂點之間初始的權值，如下表所示：

依次遍歷所有的頂點，假設從V0開始，將V0作為中間點，看每對頂點之間的距離值是否會更小。最終V0對于每對頂點之間的距離沒有任何改善。

對于V0來說，由于該頂點只有出度，沒有入度，所以沒有作為中間點的可能。同理，V1也沒有可能。

將V2作為每對頂點的中間點，有影響的為（V0,V3）和（V1,V3）：例如，（V0,V3）權值為無窮大，而（V0,V2）+（V2+V3）=60，比之前的值小，相比而言后者的路徑更短；同理（V1,V3）也是如此。

更新表格為：

以V3為中間頂點遍歷各隊頂點，更新表格：

以V4為中間頂點遍歷各隊頂點，更新表格：

對于頂點V5而言，和頂點V0和V1相類似，所不同的是，V5只有入度，沒有出度，所以對各隊頂點的距離不會產生影響。最終采用弗洛伊德算法求得的各個頂點之間的最短路徑如上圖所示。

改算法相比于德杰斯特拉算法在解決此問題上的時間復雜度雖然相同，都是O(n^3)，但是弗洛伊德算法的實現(xiàn)形式更簡單。

（3）拓撲排序

對有向無環(huán)圖進行拓撲排序，只需要遵循兩個原則：

1.在圖中選擇一個沒有前驅的頂點V；

2.從圖中刪除頂點V和所有以該頂點為尾的弧。

例如，在對圖1中的左圖進行拓撲排序時的步驟如圖2所示：

圖2拓撲排序

有向無環(huán)圖如果頂點本身具有實際意義，例如用有向無環(huán)圖表示大學期間所學習的全部課程，每個頂點都表示一門課程，有向邊表示課程學習的先后次序，例如先學《程序設計基礎》和《離散數學》，然后才能學習《數據結構》。所以用來表示某種活動間的優(yōu)先關系的有向圖簡稱為“AOV網”。

進行拓撲排序時，首先找到沒有前驅的頂點V1,如圖2（1）所示；在刪除頂點V1以及V1作為起點的弧后，繼續(xù)查找沒有前驅的頂點，此時，V2和V3都符合條件，可以隨機選擇一個，例如圖2（2）所示，選擇V2，然后繼續(xù)重復以上的操作，直至最后找不到沒有前驅的頂點。

所以對于圖2來說，拓撲排序最后得到的序列有兩種：

• V1 ->V2 ->V3 ->V4

• V1 ->V3 ->V2 ->V4

不變?？梢缘玫较旅孢@個表格：

[外鏈圖片轉存中…(img-VO9vTdwn-1607958359982)]

例如，表格中V0到V3的距離，發(fā)現(xiàn)當通過V2到達V3的距離比之前的∞要小，所以更新表格。

更新之后，發(fā)現(xiàn)V0-V4的最短路徑的值為30.之后從V4出發(fā)，判斷到未確定最短路徑的其他頂點的距離，繼續(xù)更新表格：

[外鏈圖片轉存中…(img-HPPsCdw0-1607958359982)]

更新后確認從V0到V3的最短路徑為V0-V4-V3，權值為50。然后從V3出發(fā)，繼續(xù)判斷：

[外鏈圖片轉存中…(img-ZU1FYFKC-1607958359983)]

對于V5來說，通過V0-V4-V3-V5的路徑要比之前的權值90還要小，所以更新表格，更新后可以看到，V0-V5的距離此時最短，可以確認V0到V5的最短路徑為60.

最后確定V0-V1的最短路徑，由于從V0無法到達V1，最終設定V0到V1的最短路徑為∞（無窮大）。

在確定了V0與其他所遇頂點的最短路徑后，迪杰斯特拉算法才算結束。示例中借用了 有向圖對迪杰斯特拉算法進行講解，實際上無向圖的最短路徑問題也可以使用迪杰斯特拉算法解決，解決過程與上述過程完全一致。

總結：

迪杰斯特拉算法解決的是從網中一個頂點到所有其他頂點之間的最短路徑，算法整體的時間復雜度為O(n^2)。但是如果需要求任意兩頂點之間的最短路徑，使用迪杰斯特拉算法雖然也可以解決，但是大材小用，相比之下弗洛伊德算法更適合解決此問題。

弗洛伊德(Floyd)算法：

弗洛伊德的核心思想：對于網中的任意兩個頂點（例如頂點A到頂點B）來說，之間的最短路徑不外乎有兩種情況：

1.直接從頂點A到頂點B的弧的權值為頂點A到頂點B的最短路徑；

2.從頂點A開始，經過若干頂點，最終達到頂點B，期間經過的弧的權值和為頂點A到頂點B的最短路徑

[外鏈圖片轉存中…(img-LPnDzSfx-1607958359984)]

帶權圖

例如，在使用弗洛伊德算法計算上圖中的任意兩個頂點之間的最短路徑時，具體實施步驟為：

首先，記錄頂點之間初始的權值，如下表所示：

[外鏈圖片轉存中…(img-qSVZFNO2-1607958359984)]

依次遍歷所有的頂點，假設從V0開始，將V0作為中間點，看每對頂點之間的距離值是否會更小。最終V0對于每對頂點之間的距離沒有任何改善。

對于V0來說，由于該頂點只有出度，沒有入度，所以沒有作為中間點的可能。同理，V1也沒有可能。

將V2作為每對頂點的中間點，有影響的為（V0,V3）和（V1,V3）：例如，（V0,V3）權值為無窮大，而（V0,V2）+（V2+V3）=60，比之前的值小，相比而言后者的路徑更短；同理（V1,V3）也是如此。

更新表格為：

[外鏈圖片轉存中…(img-8ZhHaGXV-1607958359985)]

以V3為中間頂點遍歷各隊頂點，更新表格：

[外鏈圖片轉存中…(img-kSJp3Vit-1607958359985)]

以V4為中間頂點遍歷各隊頂點，更新表格：

[外鏈圖片轉存中…(img-p3mDlZhs-1607958359985)]

對于頂點V5而言，和頂點V0和V1相類似，所不同的是，V5只有入度，沒有出度，所以對各隊頂點的距離不會產生影響。最終采用弗洛伊德算法求得的各個頂點之間的最短路徑如上圖所示。

改算法相比于德杰斯特拉算法在解決此問題上的時間復雜度雖然相同，都是O(n^3)，但是弗洛伊德算法的實現(xiàn)形式更簡單。

（3）拓撲排序

對有向無環(huán)圖進行拓撲排序，只需要遵循兩個原則：

1.在圖中選擇一個沒有前驅的頂點V；

2.從圖中刪除頂點V和所有以該頂點為尾的弧。

例如，在對圖1中的左圖進行拓撲排序時的步驟如圖2所示：

[外鏈圖片轉存中…(img-rbewsxFn-1607958359986)]圖2拓撲排序

有向無環(huán)圖如果頂點本身具有實際意義，例如用有向無環(huán)圖表示大學期間所學習的全部課程，每個頂點都表示一門課程，有向邊表示課程學習的先后次序，例如先學《程序設計基礎》和《離散數學》，然后才能學習《數據結構》。所以用來表示某種活動間的優(yōu)先關系的有向圖簡稱為“AOV網”。

進行拓撲排序時，首先找到沒有前驅的頂點V1,如圖2（1）所示；在刪除頂點V1以及V1作為起點的弧后，繼續(xù)查找沒有前驅的頂點，此時，V2和V3都符合條件，可以隨機選擇一個，例如圖2（2）所示，選擇V2，然后繼續(xù)重復以上的操作，直至最后找不到沒有前驅的頂點。

所以對于圖2來說，拓撲排序最后得到的序列有兩種：

• V1 ->V2 ->V3 ->V4

• V1 ->V3 ->V2 ->V4

總結

以上是生活随笔為你收集整理的【浅谈数据结构】《数据结构》Data Structure的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。