L11-L14算法分析與數(shù)據(jù)結(jié)構(gòu)ppt課件

1、網(wǎng)絡(luò)游戲算法設(shè)計(jì)第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)隊(duì)列樹二叉樹哈夫曼樹掌握隊(duì)列了解樹掌握二叉樹了解哈夫曼樹第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)隊(duì)列二叉樹隊(duì)列二叉樹哈夫曼樹第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4 線性表2.4.4 隊(duì)列 隊(duì)列的定義隊(duì)列簡稱隊(duì)，是一種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它是一種操作受限的線性表。在表中只允許進(jìn)行插入的一端稱為隊(duì)尾，只允許進(jìn)行刪除的一端稱為隊(duì)頭。隊(duì)列的插入操作通常稱為入隊(duì)列或進(jìn)隊(duì)列，而隊(duì)列的刪除操作則稱為出隊(duì)列或退隊(duì)列。當(dāng)隊(duì)列中無數(shù)據(jù)元素時(shí)，稱為空隊(duì)列。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4 線性表通常用指針front指示隊(duì)頭的位置，用指針r

2、ear指向隊(duì)尾。隊(duì)列的操作第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4 線性表 隊(duì)列的基本運(yùn)算隊(duì)列的基本運(yùn)算包括以下4種：1IsFull() 隊(duì)列非空判斷：若隊(duì)列q不空，則返回TRUE；否則，返回FALSE。2Add(const int& x) 入隊(duì)列：在隊(duì)列q的尾部插入元素x，使元素x成為新的隊(duì)尾。3Delete(int& x)出隊(duì)列：若隊(duì)列q不空，則返回隊(duì)頭元素，并從隊(duì)頭刪除該元素；否則，拋出異常。4First() 取隊(duì)頭元素：若隊(duì)列q不空，則返回隊(duì)頭元素；否則拋出異常。隊(duì)列是一種特殊的線性表，因此隊(duì)列可采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，也可以使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4

3、 線性表l 鏈隊(duì)列的表示用鏈表表示的隊(duì)列簡稱為鏈隊(duì)列，在一個(gè)鏈隊(duì)列中需設(shè)定兩個(gè)指針頭指針和尾指針分別指向隊(duì)列的頭和尾。給鏈隊(duì)列添加一個(gè)頭節(jié)點(diǎn)，并設(shè)定頭指針指向頭節(jié)點(diǎn)?？贞?duì)列的判定條件是將頭指針和尾指針都指向頭節(jié)點(diǎn)。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4 線性表struct Node int data; Node *link; ;class Queue Node *front; / 指向第一個(gè)節(jié)點(diǎn)Node *rear; /指向最后一個(gè)節(jié)點(diǎn)public:Queue() front = rear = 0; / 構(gòu)造函數(shù)Queue(); / 析構(gòu)函數(shù)bool IsEmpty() const return (

4、front) ? false : true); bool IsFull() const;int First() const; / 返回第一個(gè)元素int Last() const; / 返回最后一個(gè)元素Queue& Add(const int& x);Queue& Delete(int& x); ;第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4 線性表l 鏈隊(duì)列的主要運(yùn)算算法入隊(duì)列操作：GameCollege:Queue& GameCollege:Queue:Add(const int& x)Node *p = new Node;p-data = x;p-lin

5、k = 0;if (front) rear-link = p;else front = p; / 隊(duì)列為空rear = p;return *this;第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4 線性表出隊(duì)列操作為：GameCollege:Queue& GameCollege:Queue:Delete(int& x) / 刪除第一個(gè)元素，并將其放入xif (IsEmpty() / 如果隊(duì)列為空，則引發(fā)異常Exception e(隊(duì)列為空，不能使用此操作！);throw e;x = front-data;Node *p = front;front = front-link;delete p;

6、return *this;第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)2.5.1 樹樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)是節(jié)點(diǎn)之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。 樹的定義其中“樹根是祖父，樹中出現(xiàn)“分支的節(jié)點(diǎn)是父，該家族的其余成員均是“樹葉”，而“樹枝” 則描述了家族成員之間的關(guān)系。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)樹Tree是nn=0個(gè)節(jié)點(diǎn)的有限集。在一棵非空樹中，有且僅有一個(gè)特定的稱為根的節(jié)點(diǎn)，當(dāng)n1時(shí)其余節(jié)點(diǎn)可分為mm0個(gè)互不相交的有限集T1，T2Tm，其中，每一個(gè)集合本身又是一棵樹，并且稱為根的子樹subtree）。樹的遞歸定義刻畫了樹的固有特性：一棵非空樹是

7、由若干棵子樹構(gòu)成的，而子樹又可由若干棵更小的子樹構(gòu)成。樹是一種數(shù)據(jù)結(jié)構(gòu)，可以表示為：Tree=(D，R)。其中，D是具有相同特性的數(shù)據(jù)元素的集合。若D只含一個(gè)數(shù)據(jù)元素，則R為空集；否則R是D上一個(gè)二元關(guān)系的集第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu) 樹的基本操作樹的10種基本運(yùn)算包括：1INITIATE(T) 初始化操作，置T為空樹。2ROOT(T)ROOT(x) 求根函數(shù)。求樹T的根或求節(jié)點(diǎn)x所在的樹的根節(jié)點(diǎn)。若T是空樹或x不在任何一棵樹上，則函數(shù)值為“空”。3RARENT(T，x) 求雙親函數(shù)。求樹T中節(jié)點(diǎn)x的雙親節(jié)點(diǎn)。若節(jié)點(diǎn)x是樹T的根節(jié)點(diǎn)或節(jié)點(diǎn)x不在T中，則函數(shù)值為“空”。4

8、CHILD(T，x，i) 求孩子節(jié)點(diǎn)函數(shù)。求樹T中節(jié)點(diǎn)x的第i個(gè)孩子節(jié)點(diǎn)。若節(jié)點(diǎn)x是樹T的葉子或無第i個(gè)孩子再或者節(jié)點(diǎn)x不在樹T中，則函數(shù)值為“空”。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)5RIGHT_SINLING(T，x)求右兄弟函數(shù)。求樹T中節(jié)點(diǎn)x右邊的兄弟。若節(jié)點(diǎn)x是其雙親的最右邊的孩子節(jié)點(diǎn)或節(jié)點(diǎn)x不在樹T中，則函數(shù)值為“空”。6CRT_TREE(x，F(xiàn)) 建樹操作。生成一棵以x節(jié)點(diǎn)為根，以樹F為子樹森林的樹。7INS_CHILD(y，I，x) 插入子樹操作。8DEL_CHILD(x，i) 刪除子樹操作。刪除節(jié)點(diǎn)x的第i棵子樹。9TRAVERSE(T) 遍歷操作。按某個(gè)次序

9、依此訪問樹中各個(gè)節(jié)點(diǎn)，并使每個(gè)節(jié)點(diǎn)只被訪問一次。10CLEAR(T) 清除結(jié)構(gòu)操作。將樹T置為空樹。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu) 樹的表示方法l 樹形圖表示法樹形圖表示是樹結(jié)構(gòu)的主要表示方法。樹的樹形圖表示中：節(jié)點(diǎn)用圓圈表示，節(jié)點(diǎn)的名字寫在圓圈旁邊圖中的樹由節(jié)點(diǎn)的有限集T=A，B，C，D，E，F(xiàn)，G，H，I，J所構(gòu)成，其中A是根節(jié)點(diǎn)，T中其余節(jié)點(diǎn)可分成3個(gè)互不相交的子集：T1=B，E，F(xiàn)，I，J，T2=C，T3=D，G，H第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 嵌套集合表示法嵌套集合表示法是用集合的包含關(guān)系來描述樹結(jié)構(gòu)l 凹入表表示法每棵樹的根對應(yīng)著一個(gè)條形

10、，子樹的根對應(yīng)著較短的條形，且樹根在上，子樹的根在下。長度相同的條形是兄弟節(jié)點(diǎn)。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 廣義表表示法每棵子樹構(gòu)成一個(gè)表，每棵樹的根的名字作為表的名字放在表的左邊，括號(hào)內(nèi)是子樹。（ABE，F(xiàn)I，J），C，DG，H） 樹形結(jié)構(gòu)的基本術(shù)語1節(jié)點(diǎn)的度樹中的一個(gè)節(jié)點(diǎn)擁有的子樹稱為該節(jié)點(diǎn)的度。一棵樹的度是指該樹中節(jié)點(diǎn)的最大度數(shù)，度為零的節(jié)點(diǎn)稱為葉子或終端節(jié)點(diǎn)，度不為零的節(jié)點(diǎn)稱為分支節(jié)點(diǎn)或非終端節(jié)點(diǎn)。除根節(jié)點(diǎn)之外的分支節(jié)點(diǎn)統(tǒng)稱為內(nèi)部節(jié)點(diǎn)。根節(jié)點(diǎn)又稱為開始節(jié)點(diǎn)。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)2孩子和雙親。樹中某個(gè)節(jié)點(diǎn)的子樹之根稱為該節(jié)點(diǎn)的孩子或

11、兒子，相應(yīng)地，該節(jié)點(diǎn)稱為孩子的雙親或父親。同一個(gè)雙親的孩子稱為兄弟。3祖先和子孫。若樹中存在一個(gè)節(jié)點(diǎn)序列k1，k2，ki，使得ki是ki+1的雙親(1ij)，則稱該節(jié)點(diǎn)序列是從k1到kj的一條路徑Path或道路。則稱k1是kj的祖先，kj是k1的子孫。4節(jié)點(diǎn)的層數(shù)和樹的高度。節(jié)點(diǎn)的層數(shù)從根算起：根的層數(shù)為1，也有很多書中將樹根的層數(shù)定義為0。其余節(jié)點(diǎn)的層數(shù)等于其雙親節(jié)點(diǎn)的層數(shù)加1。雙親在同一層的節(jié)點(diǎn)互為堂兄弟。樹中節(jié)點(diǎn)的最大層數(shù)稱為樹的高度或深度。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)5有序樹和無序樹。若將樹中每個(gè)節(jié)點(diǎn)的各子樹看成是從左到右有次序的即不能互換），則稱該樹為有序樹；否

12、則稱為無序樹。6森林。森林是mm0棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根，就得到一個(gè)森林；反之，加上一個(gè)節(jié)點(diǎn)作樹根，森林就變?yōu)橐豢脴?。?章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu) 樹形結(jié)構(gòu)的邏輯特征1樹中任意一節(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼即孩子節(jié)點(diǎn)，但至多只能有一個(gè)直接前趨即雙親節(jié)點(diǎn)。2樹中只有根節(jié)點(diǎn)無前趨，它是開始節(jié)點(diǎn)；葉節(jié)點(diǎn)無后繼，它們是終端節(jié)點(diǎn)。3祖先與子孫的關(guān)系是對父子關(guān)系的延拓，它定義了樹中節(jié)點(diǎn)之間的縱向次序。4有序樹中，同一組兄弟節(jié)點(diǎn)從左到右有長幼之分。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu) 二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡單，因此二叉樹

13、顯得特別重要。l二叉樹的5種基本形態(tài)第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 二叉樹與無序樹不同二叉樹中，每個(gè)節(jié)點(diǎn)最多只能有兩棵子樹，并且有左右之分。在有序樹中，雖然一個(gè)節(jié)點(diǎn)的孩子之間是有左右次序的，但是若該節(jié)點(diǎn)只有一個(gè)孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個(gè)孩子也有左右之分。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)二叉樹具有以下重要性質(zhì)：1二叉樹第i層上的節(jié)點(diǎn)數(shù)目最多為 2i-1i1）。2深度為k的二叉樹至多有 個(gè)2k-1節(jié)點(diǎn)k1）。3在任意一棵二叉樹中，若終端節(jié)點(diǎn)的個(gè)數(shù)為 n0，度為2的節(jié)點(diǎn)數(shù)為n2 ，則n0 = n2+1。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5

14、 其他常用數(shù)據(jù)結(jié)構(gòu)l 滿二叉樹和完全二叉樹滿二叉樹一棵深度為k且有 2k-1個(gè)節(jié)點(diǎn)的二叉樹稱為滿二叉樹。滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。滿二叉樹的特點(diǎn)：1每一層上的節(jié)點(diǎn)數(shù)都達(dá)到最大值。2滿二叉樹中不存在度數(shù)為1的節(jié)點(diǎn)，每個(gè)分支節(jié)點(diǎn)均有兩棵高度相同的子樹，且樹葉都在最下一層上。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)完全二叉樹：若一棵二叉樹最多只有最下面的兩層，其節(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的節(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。完全二叉樹的特點(diǎn)：1滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。2在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪

15、去若干節(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。3在完全二叉樹中，若某個(gè)節(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該節(jié)點(diǎn)必是葉節(jié)點(diǎn)。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)4具有n個(gè)節(jié)點(diǎn)的完全二叉樹的滿二叉樹深度為：1+lgn (滿二叉樹)第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 順序存儲(chǔ)結(jié)構(gòu)該方法是把二叉樹的所有節(jié)點(diǎn)按照一定的線性次序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。節(jié)點(diǎn)在這個(gè)序列中的相互位置還能反映出節(jié)點(diǎn)之間的邏輯關(guān)系。完全二叉樹節(jié)點(diǎn)編號(hào)方法：在一棵n個(gè)節(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有節(jié)點(diǎn)編號(hào)，能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列。第2章 算法分

16、析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)編號(hào)特點(diǎn)：完全二叉樹中除最下面一層外，各層都充滿了節(jié)點(diǎn)。每一層的節(jié)點(diǎn)個(gè)數(shù)恰好是上一層節(jié)點(diǎn)個(gè)數(shù)的2倍。假設(shè)編號(hào)為i的節(jié)點(diǎn)是 （1in），則有：1若i1，那么 ki的雙親編號(hào)為i/2；若i=1，那么 ki是根節(jié)點(diǎn)，無雙親。2若2in，那么 ki的左孩子的編號(hào)是2i；否則， ki 無左孩子，即 ki必定是葉子。因此完全二叉樹中編號(hào)in/2的節(jié)點(diǎn)必定是葉節(jié)點(diǎn)。3若2i+1n，那么 ki的右孩子的編號(hào)是2i+1；否則 ki無右孩子。4若i為奇數(shù)且不為1，那么 ki的左兄弟的編號(hào)是i-1；否則 ki無左兄弟。5若i為偶數(shù)且小于n，那么 ki的右兄弟的編號(hào)是i+1；否則k

17、i 無右兄弟。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 完全二叉樹的順序存儲(chǔ)將完全二叉樹中所有節(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)向量bt0n中。其中：bt1n用來存儲(chǔ)節(jié)點(diǎn),bt0不使用或只用來存儲(chǔ)節(jié)點(diǎn)數(shù)目。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)一般二叉樹的順序存儲(chǔ)1存儲(chǔ)方法將一般二叉樹添上一些 “虛節(jié)點(diǎn)”，成為“完全二叉樹”。將節(jié)點(diǎn)按編號(hào)存入向量對應(yīng)分量，其中“虛節(jié)點(diǎn)用“表示第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)2優(yōu)點(diǎn)和缺點(diǎn)對完全二叉樹而言，順序存儲(chǔ)結(jié)構(gòu)既簡單又節(jié)省存儲(chǔ)空間。一般的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，雖然簡單，但易造成存儲(chǔ)空間的浪費(fèi)。最壞的情況下，一個(gè)深度為

18、k且只有k個(gè)節(jié)點(diǎn)的右單支樹需要2k-1個(gè)節(jié)點(diǎn)的存儲(chǔ)空間。在對順序存儲(chǔ)的二叉樹做插入和刪除節(jié)點(diǎn)操作時(shí)，要大量移動(dòng)節(jié)點(diǎn)。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型定義一個(gè)樹節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和兩個(gè)指針域，指針域被稱為“左指針和“右指針”，它們分別指向節(jié)點(diǎn)的左右子樹。二叉樹結(jié)構(gòu)是由節(jié)點(diǎn)生成的。二叉樹的結(jié)構(gòu)：第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹哈夫曼樹（ Huffman ）又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。樹中兩個(gè)節(jié)點(diǎn)之間的路徑由一個(gè)節(jié)點(diǎn)到另一節(jié)點(diǎn)的分支構(gòu)成。樹的路徑長度是從根節(jié)點(diǎn)到每一個(gè)節(jié)點(diǎn)的路徑長度之和。設(shè)一棵二

19、叉樹有 n 個(gè)葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)擁有一個(gè)權(quán)值1，2，. n，從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑長度分別為 L1，L2.Ln，那么樹的帶權(quán)路徑長度為每個(gè)葉子的路徑長度與該葉子權(quán)值乘積之和。通常記作WPL k. k 。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)圖中把帶權(quán)的葉子節(jié)點(diǎn)畫成方形，其他非葉子節(jié)點(diǎn)仍為圓形。這三棵二叉樹葉子節(jié)點(diǎn)數(shù)相同，它們的權(quán)值也相同，但是它們的wpl帶權(quán)路徑長各不相同。最右邊的樹就是哈曼樹，最優(yōu)樹。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)哈夫曼樹的構(gòu)造：對于已知的一組葉子的權(quán)值1，2. ，n 1首先把n個(gè)葉子節(jié)點(diǎn)看作n棵樹僅有一個(gè)節(jié)點(diǎn)的二叉樹），把n棵樹看作一個(gè)森林2在森林中把權(quán)值最小和次小的兩棵樹合并成一棵樹