1、1,數(shù)據(jù)結構與應用,馬石安 魏文平 編著,2,內容簡介,本教材采用面向對象的觀點討論數(shù)據(jù)結構技術，并以C+類模板作為算法描述工具。 教材在簡要回顧C+程序設計概念的基礎上，全面系統(tǒng)地介紹了線性表、棧和隊列、串、數(shù)組和廣義表、樹和二叉樹及圖等數(shù)據(jù)結構，討論了常用的查找和排序技術，對每一種數(shù)據(jù)結構，除了詳細闡述其邏輯結構、存儲結構和相關算法外，還對所有算法進行了C+語言實現(xiàn)和評價，并給出了應用實例。 教材附錄給出了上機實驗內容。,3,教材目錄,第0章 C+程序設計語言預備知識 0.1 一個簡單C+語言程序 0.2 指針與引用 0.3 動態(tài)存貯分配 0.4 函數(shù) 0.5 類與對象 0.6 運算符重載

2、 0.7 模板,4,第1章 緒論 1.1 數(shù)據(jù)結構的產(chǎn)生和發(fā)展 1.2 數(shù)據(jù)結構研究的內容 1.3 基本概念和術語 1.4 算法 第2章線性表 2.1 線性表的邏輯結構 2.2 線性表的順序存儲結構 2.3 線性表的鏈式存儲結構 2.4 順序表和鏈表的比較 2.5 線性表的應用,5,第章棧和隊列 3.1 棧 3.2 隊列 3.3 棧的應用 第4章 串 4.1 串的邏輯結構 4.2 串的順序存儲結構 4.3 串的鏈式存儲結構 4.4 串的應用,6,第5章 數(shù)組和廣義表 5.1 數(shù)組 5.2 矩陣的壓縮存儲 5.3 廣義表 5.4 多維數(shù)組的應用,7,第6章 樹和二叉樹 6.1 樹的邏輯結構 6.

3、2 樹的順序存儲結構 6.3 二叉樹的邏輯結構 6.4 二叉樹的存儲結構 6.5 線索二叉樹 6.6 樹、森林與二叉樹的轉換 6.7 樹的應用,8,第7章 圖 7.1 圖的邏輯結構 7.2 圖的存儲結構 7.3 圖的遍歷 7.4 生成樹和最小生成樹 7.5 最短路徑 7.6 DAG圖及其應用,9,第8章 排序 8.1 概述 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內排序方法的比較和選擇,10,第9章 查找 9.1 概述 9.2 線性表的查找 9.3 樹表的查找 9.4 散列表的查找 附錄 實驗內容,11,第7章 圖,12,7.1 圖

4、的邏輯結構,7.2 圖的存儲結構,7.3 圖的遍歷,本章主要內容,7.4 生成樹和最小生成樹,7.5 最短路徑,7.6 DAG圖及其應用,13,7.1.1圖的定義,7.1 圖的邏輯結構,圖G由結點的有窮非空集合V和邊的有窮集合E組成，記為G=(V，E)。在圖結構中，將結點稱為頂點，以便與樹形結構加以區(qū)別，邊則是頂點的偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關系。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。E(G)可以是空集，若E(G)為空，則圖G只有頂點而沒有邊。,14,7.1.2 圖的基本術語,1. 有向圖和無向圖,如果G中的每條邊都是有方向的，則稱G為有向圖。

5、在有向圖中，一條有向邊是由兩個頂點組成的有序對，通常用尖括號表示。 例如，表示一條有向邊，vi是邊的始點，vj是邊的終點。,15,若圖G中的每條邊都是沒有方向的，則稱G為無向圖。 無向圖中的邊均是頂點的無序對，通常用圓括號表示。無序對(vi,vj)和(vj,vi)表示同一條邊。,16,無向圖G1，在該圖中： V(G1)=v1，v2，v3，v4，v5 E(G1)=(v1,v2)，(v1,v4)，(v2,v3)，(v2,v5) ，(v3,v4)，(v3,v5) ,17,有向圖G2，該圖的頂點集和邊集分別為： V(G2)=v1，v2，v3，v4，v5 E(G2)，,18,2. 稠密圖和稀疏圖 3.

6、邊和頂點的關系 若(vi,vj)是一條無向邊，則稱頂點vi和vj互為鄰接點(adjacent)，或稱vi和vj相鄰接，并稱(vi,vj)依附或關聯(lián)(incident)于頂點vi和vj或稱(vi,vj)與頂點vi和vj相關聯(lián)。 若是一條有向邊，則稱此邊是頂點vi的一條出邊，同時也是頂點vj的一條入邊；稱頂點vi鄰接到(或鄰接于)頂點vj，并稱邊關聯(lián)于vi和vj，或稱與頂點vi和vj相關聯(lián)。,19,4. 頂點的度,無向圖中頂點v的度是關聯(lián)于該頂點的邊的數(shù)目，記為D(v)。 在有向圖中，以頂點v為終點的邊的數(shù)目稱為v的入度，記為ID(v)；以頂點v為始點的邊的數(shù)目稱為v的出度，記為OD(v)。頂點v

7、的度定義為該頂點的入度和出度之和，即D(v)=ID(v)+OD(v)。,20,5. 子圖,設G=(V，E)是一個圖，若V是V的子集，E是E的子集，且E的邊所關聯(lián)的頂點均在V中，則G=(V，E)也是一個圖，并稱其為G的子圖。,21,6. 路徑,設G是圖，若存在一個頂點序列vp，v1，v2，vq-1，vq使得 (vp,v1)，(v1,v2)，(vq-1,vq)屬于E，則稱vp到vq存在一條路徑(path)，其中vp為起點，vq為終點。 路徑的長度是該路徑上邊的數(shù)目。,22,7. 有根圖和圖的根 8. 無向圖的連通圖和連通分量 9. 有向圖的強連通圖和強連通分量 10. 網(wǎng)絡,23,7.1.3 圖的

8、基本操作,圖的基本操作: 圖的初始化：Create() 銷毀圖：Destory() 刪除圖中所有元素，回收圖所占空間。 取頂點：GetVex(i) 取圖中的第i 個頂點的數(shù)據(jù)信息。,24,插入頂點：InsertVex(v) 在圖中插入頂點v。 刪除頂點：DeleteVex(v) 刪除圖中頂點v。 插入邊或?。篒nsert(v,w) 在圖中插入一條邊(v,w)或弧，如是無向圖，還應增加對稱邊(w, v)。 刪除邊或?。篋elete(v,w),25,7.2 圖的存儲結構,圖的存儲表示方法很多，鄰接矩陣表示法和鄰接表表示法是兩種最常用的方法。,7.2.1鄰接矩陣,鄰接矩陣是一種表示頂點之間相鄰關系的

9、矩陣。設G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣A是具有如下性質的n階方陣：,26,對于無向圖，若從頂點vi到vj有一條無向邊(vi,vj)，則aij=1，aji=1;否則aij=0，aji=0，故無向圖的鄰接矩陣是一個對稱矩陣。對于有向圖，若從頂點vi到vj有一條有向邊，則aij=1；否則aij=0。,27,28,29,基于鄰接矩陣存儲結構的圖的類模板定義cx7_1.h,30,鄰接矩陣的基本操作及其實現(xiàn):,1求頂點在圖中的位置 2創(chuàng)建圖 3頂點的增刪 4弧的增刪 5輸出鄰接矩陣 6銷毀有向圖,31,7.2.2 鄰接表,鄰接表表示法是圖的一種鏈接存儲結構，類似于樹的孩子鏈表表示法。 對

10、于圖G中的每個頂點vi，該方法把所有鄰接于vi的頂點鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，鄰接表中每個結點有兩個域：其一是鄰接點域(adjvex)，用以存放與vi相鄰接的頂點vj的序號j；其二是鏈域(next)，用來指示與vi相鄰接的下一頂點，從而將鄰接表的所有表結點鏈在一起。,32,為每個頂點vi的鄰接表設置一個頭結點，頭結點中包含兩個域，其中一個是頂點域vertex，用來存放頂點vi的數(shù)據(jù)信息；另一個是指針域firstedge，它指向vi的鄰接表的開始結點，相當于vi的鄰接表的頭指針。為了便于隨機訪問任一頂點的鄰接表，將所有頭結點順序存儲在一個一維數(shù)組中，稱為頂點表，將其中的頭

11、結點稱為頂點表結點。這樣就構成了圖的鄰接表表示。,33,34,35,鄰接表的基本操作及其實現(xiàn):,求頂點在圖中的位置 創(chuàng)建有向圖 頂點的增刪 弧的增刪 輸出鄰接表 銷毀有向圖,36,7.2.3 鄰接矩陣和鄰接表的比較,37,7.3 圖的遍歷,圖的遍歷是指從圖中某一頂點出發(fā)，對圖中所有頂點訪問一次且僅訪問一次的操作。,38,7.3.1 深度優(yōu)先搜索遍歷,深度優(yōu)先搜索(DFS) 遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點均未曾訪問過。則從圖中某頂點v出發(fā)進行深度優(yōu)先搜索遍歷的基本思想是： (1) 訪問頂點v； (2) 從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先搜索遍歷；

12、(3) 重復上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。,39,從圖中某頂點v出發(fā)，基于鄰接矩陣表示的深度優(yōu)先搜索的遞歸過程如程序sf7_13.cpp所示。 從圖中某頂點v出發(fā)，基于鄰接表表示的深度優(yōu)先搜索的遞歸過程如程序sf7_15.cpp所示。,40,無向圖G12和它的深度優(yōu)先搜索遍歷:,得到的頂點訪問序列為：v0 v1 v2 v5 v4 v6 v3 v7,41,7.3.2 廣度優(yōu)先搜索遍歷,廣度優(yōu)先搜索 (breadth first serch，BFS) 遍歷類似于樹的層序遍歷。 從圖中某頂點v出發(fā)進行廣度優(yōu)先遍歷的基本思想是： (1) 訪問頂點v； (2) 依次訪問v的各個未

13、被訪問的鄰接點v1，v2，vk； (3) 分別從v1，v2，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問，直至圖中所有與頂點v有路徑相通的頂點都被訪問到。,42,無向圖G12的廣度優(yōu)先搜索遍歷:,v0 v1 v3 v4 v2 v6 v5 v7,43,7.4 生成樹和最小生成樹,在圖論中，常常將一個無回路的連通圖定義為樹。沒有確定誰是根的圖稱為自由樹。,7.4.1 生成樹與生成森林,如果連通圖G的一個子圖是一棵包含G中所有頂點的樹，則該子圖稱為G的生成樹。,44,由深度優(yōu)先搜索得到的生成樹稱為深度優(yōu)先生成樹，簡稱為DFS生成樹； 由廣度優(yōu)先

14、搜索得到的生成樹稱為廣度優(yōu)先生成樹，簡稱為BFS生成樹。,45,46,圖的生成樹不唯一。從不同的頂點出發(fā)進行遍歷，可以得到不同的生成樹。,47,7.4.2 最小生成樹,帶權的連通圖也稱連通網(wǎng)，其生成樹也是帶權的，我們把生成樹各邊的權值總和稱為該生成樹的權。 圖的生成樹不唯一，從不同的頂點出發(fā)遍歷帶權的連通圖，可以得到不同的帶權生成樹，其中權值最小的生成樹稱為最小生成樹，簡稱為MST。,48,普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法是兩個利用MST性質構造最小生成樹的算法。,1普里姆算法,假設G=(V,E)是連通網(wǎng)絡，TE是G上最小生成樹中邊的集合。算法從V中任取一個頂點作為源點

15、(假定為v0)，此時U=v0(v0V)，TE開始，重復執(zhí)行下述操作：在所有uU，vV-U的邊(u，v)E中找一條代價最小的邊(u，v)并入集合TE，同時u并入U，直至UV為止。此時TE中必有n-1條邊，則T(V，TE)為G的最小生成樹。,49,50,51,52,53,采用鄰接矩陣存儲的Prim算法sf7_20.cpp,54,2克魯斯卡爾算法,假設連通網(wǎng)G(V，E)，則令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V，)，圖中每個頂點自成一個連通分量。在E中選擇權值最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條權值最小的邊。依次類推，

16、直至T中所有頂點都在同一連通分量上為止。,55,56,57,58,克魯斯卡爾算法sf7_21.cpp,59,7.5 最短路徑,7.5.1 單源最短路徑,所謂單源最短路徑：是指對已知圖G=(V，E)，給定源頂點v，找出v到其余各頂點的最短路徑。,60,1. 迪杰斯特拉(Djikstra)算法基本思想,迪杰斯特拉提出了按路徑長度遞增的次序逐一產(chǎn)生最短路徑的算法： 首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點到其它所有頂點之間的最短路徑都已求得為止。,61,設集合S存放已經(jīng)求得最短路徑的終點，則V-S為尚未求得最短路徑的終點。初始狀態(tài)時，集合S中只有一個源點，設

17、為頂點v0。迪杰斯特拉算法的具體做法是：首先產(chǎn)生從點v0到自身的路徑，其長度為0，將v0加入S；算法的每一步上，按照最短路徑值的遞增次序，產(chǎn)生下一條最短路徑，并將該路徑的終點vjV-S加入S；直到S=V，算法結束。,62,2. 算法描述,63,3. 算法實現(xiàn) 教材sf7_22.cpp,64,7.5.2所有頂點對之間的最短路徑,1. 弗洛伊德算法思想,求從頂點vi到 vj的最短路徑。設集合S的初始狀態(tài)為空集合。然后，依此向集合S中加入頂點v0，v1，v2vn-1，每次加入一個頂點。用二維數(shù)組dist保存各條最短路徑的長度，其中，distij為從i到j的當前最短路徑長度。隨著S中的頂點的不斷增加，

18、distij的值不斷修正，當S=V時，distij的值就是從i到j的最短路徑。,65,2. 算法描述,圖7.24 用弗洛伊德算法求帶權有向網(wǎng)所有頂點對的最短路徑,66,3. 算法實現(xiàn),教材sf7_23.cpp,67,7.6 DAG圖及其應用,一個無環(huán)的有向圖稱作有向無環(huán)圖，簡稱DAG圖。DAG圖是一類比有向樹更一般的特殊有向圖。,68,7.6.2 AOV網(wǎng)與拓撲排序,1AOV網(wǎng) 以有向圖中的頂點表示活動，弧表示活動之間的優(yōu)先關系，這樣的有向圖稱為頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)。,69,2拓撲排序,設G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列v0，v1，vn-1稱為一個拓撲序列，當且僅當滿足下列條件：若從vi到頂點vj有一條路徑，則在頂點序列中頂點vi必在頂點vj之前。對一個有向圖構造拓撲序列的過程稱為拓撲排序。,70,3拓撲排序的實現(xiàn),教材sf