1、數(shù)據(jù)結(jié)構(gòu)與算法,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,2,1.3.1 算法及其特性,算法（Algorithm）是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。 一個算法應(yīng)該具有下列特性： 有窮性。一個算法必須在有窮步之后結(jié)束，即必須在有限時間內(nèi)完成。 確定性。算法的每一步必須有確切的定義，無二義性。算法的執(zhí)行對應(yīng)著的相同的輸入僅有唯一的一條路經(jīng)。 可行性。算法中的每一步都可以通過已經(jīng)實現(xiàn)的基本運算的有限次執(zhí)行得以實現(xiàn)。 輸入。一個算法具有零個或多個輸入，這些輸入取自特定的數(shù)據(jù)對象集合。 輸出。一個算法具有一個或多個輸出，這些輸出同輸入之間存在某種特定的關(guān)系。,

2、2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,3,1.3.3 算法的性能分析,時間復雜度、空間復雜度：也成為時間性能和空間性能，是對某個算法的時間效率和空間效率的度量。 時間復雜度 將一個算法轉(zhuǎn)換成程序并在計算機上執(zhí)行時，其運行所需要的時間取決于下列因素： 空間復雜度： 一個算法的空間復雜度（Space complexity）是指算法運行從開始到結(jié)束所需的存儲量。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,4,1.2.1 有關(guān)概念和術(shù)語,1、數(shù)據(jù)項 2、數(shù)據(jù)元素 3、數(shù)據(jù)對象 4、數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)（Data Structure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不

3、會是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。 根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)： 集合結(jié)構(gòu)。線性結(jié)構(gòu)。樹結(jié)構(gòu)。圖結(jié)構(gòu)。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,5,圖1.5為表示上述四類基本結(jié)構(gòu)的示意圖。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,6,數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開發(fā)過程中的設(shè)計階段、同時涉及編碼和分析階段的若干基本問題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)的評價與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個層次的五個“要素”。,2、 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,7,2.1.1 線性表的定義

4、 線性表是線性結(jié)構(gòu)的一般形式。 線性結(jié)構(gòu)的特點是數(shù)據(jù)元素之間是一種線性關(guān)系，數(shù)據(jù)元素“一個接一個的排列”。在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)。 線性表是具有相同數(shù)據(jù)類型的n(n=0)個數(shù)據(jù)元素的有限序列，通常記為： (a1，a2， ai-1，ai，ai+1，an),2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,8,(a1，a2， ai-1，ai，ai+1，an) 其中n為表長， n0 時稱為空表。表中相鄰元素之間存在著順序關(guān)系。將 ai-1 稱為 ai 的直接前趨，ai+1 稱為 ai 的直接后繼。就是說：對于ai，當 i=2，.，n 時，有且僅有一個

5、直接前趨ai-1，當i=1，2，.，n-1 時，有且僅有一個直接后繼ai+1，而 a1是表中第一個元素，它沒有前趨，an是最后一個元素無后繼。 需要說明的是：ai為序號為i的數(shù)據(jù)元素（i=1,2,n），通常我們將它的數(shù)據(jù)類型抽象為datatype，datatype根據(jù)具體問題而定，如在學生情況信息表中，它是用戶自定義的學生類型； 在字符串中，它是字符型；等等。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,9,2.1.2 線性表的基本運算, 線性表初始化：Init_List(L) 求線性表的長度：Length_List(L) 取表元：Get_List(L,i) 按值查找：Locate_List(L,x)

6、 插入操作：Insert_List(L,i,x) 刪除操作：Delete_List(L,i) 線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間依次順序存放線性表各元素，用這種存儲形式存儲的線性表稱其為順序表。 因為內(nèi)存的地址空間是一維線性空間，因此順序表的存儲特點是：用物理上的相鄰實現(xiàn)邏輯上的相鄰。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,10,插入運算 (1) 運算說明： 線性表的插入是指在表的第i個位置上插入一個值為 x 的新元素。,插入前：(a1, a2, . , ai-1, ai , ai+1 , . , an) 插入后：(a1, a2, . , ai-1, x, ai, ai+1 ,

7、 . , an ) 其中：1in+1，n是原來的表長。 (3) 本算法中注意以下問題： 順序表中數(shù)據(jù)區(qū)域有MAXSIZE個存儲單元，所以在向順序表中做插入時先檢查表空間是否滿了，在表滿的情況下不能再做插入，否則產(chǎn)生溢出錯誤。 要檢驗插入位置的有效性，這里 i 的有效范圍是：1in+1，其中 n 為原表長。 注意數(shù)據(jù)的移動方向。 表長的修改。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,11,刪除運算 (1) 運算說明： 線性表的刪除運算是指將表中第 i 個元素從線性表中去掉。,刪除前：(a1, a2, . , ai-1, ai , ai+1 , . , an) 刪除后：(a1, a2, . , ai-

8、1, ai+1 , . , an ) 其中：1in，n是原來的表長。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,12,按值查找,(1) 運算說明： 線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,13,2.3.3 循環(huán)鏈表,對于單鏈表而言，最后一個結(jié)點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結(jié)點相連，就構(gòu)成了單循環(huán)鏈表。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,14,(2) 和單鏈表類似，雙向鏈表通常也是用頭指針標識，也可以帶頭結(jié)點和做成循環(huán)結(jié)構(gòu)。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,15,3.1.1 棧的定義及基本運算,1.棧

9、的定義 棧是限制在表的一端進行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當表中沒有元素時稱為空棧。,右圖所示棧中有三個元素，進棧的順序是a1、a2、a3，當需要出棧時其順序為a3、a2、a1，所以棧又稱為后進先出的線性表（Last In First Out），簡稱 LIFO表。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,16,2.棧的基本運算： 棧初始化：Init_Stack(s) 操作結(jié)果是構(gòu)造了一個空棧。 判棧空：Empty_Stack(s) 操作結(jié)果是若s為空棧返回為1，否則返回為0。 入棧： Push_Stack(s，x) 操作結(jié)果是在棧s的頂部插入一個新元素

10、x，x成為新的棧頂元素。 出棧：Pop_Stack(s) 在棧s存在且非空的情況下，操作結(jié)果是將棧s的頂部元素從棧中刪除。 讀棧頂元素：Top_Stack(s) 在棧s存在且非空情況下，操作結(jié)果是讀棧頂元素，棧不變化。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,17,3.3.1 隊列的定義及基本運算,在實際問題中經(jīng)常用到一種“先進先出” (FIFO-First In First Out)的數(shù)據(jù)結(jié)構(gòu)：即插入在表一端進行，刪除在表的另一端進行，這種數(shù)據(jù)結(jié)構(gòu)稱為隊或隊列，把允許插入的一端叫隊尾(rear) ，把允許刪除的一端叫隊頭(front)。 隊列也是一種運算受限制的線性表，又叫先進先出表。,如圖所示

11、是一個有5 個元素的隊列。 入隊的順序依次為a1、 a2 、a3 、a4 、 a5。 出隊時的順序?qū)⒁廊皇莂1、a2、a3、a4 、 a5 。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,18,在隊列上進行的基本操作有： 隊列初始化：Init_Queue(q) 操作結(jié)果是構(gòu)造一個空隊。 入隊操作：In_Queue(q,x) 在隊q存在情況下，操作結(jié)果是對已存在的隊列q，插入一個元素x到隊尾。 出隊操作：Out_Queue(q,x) 隊q存在且非空情況下，操作結(jié)果是刪除隊首元素，并返回其值。 讀隊頭元素：Front_Queue(q,x) 隊q存在且非空情況下，操作結(jié)果是讀出隊頭元素，并返回其值。 判隊空

12、操作：Empty_Queue(q) 隊q存在時，操作結(jié)果是若q為空隊則返回為1，否則返回為0。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,19,第5章 樹結(jié)構(gòu) 本章首先對二叉樹結(jié)構(gòu)進行較為深刻的討論，然后再介紹樹結(jié)構(gòu)中一般意義的樹和它們與二叉樹之間的關(guān)系。,1教學內(nèi)容 5.1 二叉樹 5.2 二叉樹的遍歷 5.3二叉樹遍歷的應(yīng)用 5.4 線索二叉樹 5.5 哈夫曼樹及哈夫曼編碼 5.6 樹 5.7 樹和森林與二叉樹之間的轉(zhuǎn)換 5.8 樹或森林的遍歷,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,20,1二叉樹的定義 二叉樹（Binary Tree）是個有限元素的集合，該集合或者為空、或者由一個稱為根(root

13、)的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結(jié)點。 二叉樹是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,21,2相關(guān)術(shù)語 在下列的的術(shù)語中，除特殊指明了二叉樹之外，否則也都適用于普通的樹型結(jié)構(gòu)（稱為樹）。 (1) 結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度。 (2) 葉結(jié)點：度為0的結(jié)點稱為葉結(jié)點，或者稱為終端結(jié)點。 (3) 分支結(jié)點：度不為0的結(jié)點稱為分支結(jié)點，或者稱為非終端結(jié)點。一棵樹的結(jié)點除葉結(jié)

14、點外，其余的都是分支結(jié)點。 (4) 左孩子、右孩子、雙親、兄弟：樹中一個結(jié)點的子樹的根結(jié)點稱為這個結(jié)點的孩子。在二叉樹中，左子樹的根稱為左孩子，右子樹的根稱為右孩子。反過來這個結(jié)點稱為它孩子結(jié)點的雙親。具有同一個雙親的孩子結(jié)點互稱為兄弟。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,22,(5) 路徑、路徑長度：如果一棵樹中的一串結(jié)點n1,n2,nk,有如下關(guān)系：結(jié)點ni是ni+1的父結(jié)點(1ik) ,就把n1,n2,nk稱為一條由n1至nk的路徑，這條路徑的長度是k-1。 (6) 祖先、子孫：在樹中，如果有一條路徑從結(jié)點M到結(jié)點N，那么M就稱為N的祖先，而N稱為M的子孫。 (7) 結(jié)點的層數(shù)：規(guī)定樹

15、的根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于它的雙親結(jié)點的層數(shù)加1。 (8) 樹的深度：樹中結(jié)點的最大層數(shù)稱為樹的深度。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,23,(9) 滿二叉樹。 在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。如圖所示，(a)圖就是一棵滿二叉樹，(b)圖則不是滿二叉樹，因為，雖然其所有結(jié)點要么是含有左右子樹的分支結(jié)點，要么是葉子結(jié)點，但由于其葉子未在同一層上，故不是滿二叉樹。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,24,(10) 完全二叉樹。 一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序

16、進行編號，如果編號為i（1in）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點是：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。如圖所示(a)為一棵完全二叉樹，(b)不是完全二叉樹。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,25,5.1.2 二叉樹的主要性質(zhì),性質(zhì)1 一棵非空二叉樹的第i層上最多有2i-1個結(jié)點（i1）。該性質(zhì)可由數(shù)學歸納法證明。證明略。 性質(zhì)2 一棵深度為k的二叉樹中，最多具有2k1個結(jié)點。 性質(zhì)3：對于一棵非空的二叉樹，若葉子結(jié)點數(shù)為n0

17、，度數(shù)為2的結(jié)點數(shù)為n2，則有：n0n21。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,26,5.1.3 二叉樹的存儲,1順序存儲結(jié)構(gòu) 所謂二叉樹的順序存儲，是用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點。一般是按照二叉樹結(jié)點從上至下、從左到右的順序存儲。 因此，依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標值確定結(jié)點在二叉樹中的位置，以及結(jié)點之間的關(guān)系。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,27,下面給出一棵完全二叉樹的順序存儲示意。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,28,對于一

18、般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點順序存儲在一維數(shù)組中，則數(shù)組元素下標之間的關(guān)系不能夠反映二叉樹中結(jié)點之間的邏輯關(guān)系，只有增添一些并不存在的空結(jié)點，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,29,2鏈式存儲結(jié)構(gòu) (1)二叉鏈表存儲 鏈表中每個結(jié)點由三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。結(jié)點的存儲的結(jié)構(gòu)為： 其中，data域存放某結(jié)點的數(shù)據(jù)信息；lchild 與rchild分別存放指向左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應(yīng)指針域值為空（用符號或NUL

19、L表示）。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,30,5.2.1 遞歸方法實現(xiàn)二叉樹的三種遍歷,由二叉樹的定義可知，一棵二叉樹由根結(jié)點、根結(jié)點的左子樹和根結(jié)點的右子樹三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹。 若以D、L、R分別表示訪問根結(jié)點、遍歷根結(jié)點的左子樹、遍歷根結(jié)點的右子樹，則二叉樹的遍歷方式有六種：DLR、LDR、LRD、DRL、RDL和RLD。 如果限定先左后右，則只有前三種方式，即： DLR（稱為先序遍歷) LDR（稱為中序遍歷) LRD（稱為后序遍歷) 。,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,31,1先序遍歷 先序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否

20、則， (1) 訪問根結(jié)點； (2) 先序遍歷根結(jié)點的左子樹； (3) 先序遍歷根結(jié)點的右子樹。 【算法 5-5】先序遍歷二叉樹的遞歸算法 void PreOrder(BiTree bt) if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/ Visit(bt) ; /*訪問根結(jié)點*/ PreOrder(btlchild); /*先序遞歸遍歷bt的左子樹*/ PreOrder(btrchild);/*先序遞歸遍歷bt的右子樹*/ ,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,32,對于上圖所示的二叉樹，按先序遍歷所得到的結(jié)點序列為： A B D G C E F,2020年7月27日,數(shù)據(jù)

21、結(jié)構(gòu)講義,33,2中序遍歷 中序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則， (1) 中序遍歷根結(jié)點的左子樹； (2) 訪問根結(jié)點； (3) 中序遍歷根結(jié)點的右子樹。 【算法 5-6】中序遍歷二叉樹的遞歸算法 void InOrder(BiTree bt) if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/ InOrder(btlchild); /*中序遞歸遍歷bt的左子樹*/ Visit(bt); /*訪問根結(jié)點*/ InOrder(btrchild); /*中序遞歸遍歷bt的右子樹*/ ,2020年7月27日,數(shù)據(jù)結(jié)構(gòu)講義,34,對于上圖所示的二叉樹，按中序遍歷所得到的結(jié)點序列為：