l11l14算法分析與數(shù)據(jù)結(jié)構(gòu)PPT課件

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

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

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

4、turn (front) ? false : true); bool isfull() const;int first() const; / 返回第一個元素int last() const; / 返回最后一個元素queue& add(const int& x);queue& delete(int& x); ;第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.4 線性表l 鏈隊列的主要運(yùn)算算法入隊列操作：gamecollege:queue& gamecollege:queue:add(const int& x)node *p = new node;p-data = x

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

6、ete p;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é)點之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。 樹的定義其中“樹根”是祖父，樹中出現(xiàn)“分支”的節(jié)點是父，該家族的其余成員均是“樹葉”，而“樹枝” 則描述了家族成員之間的關(guān)系。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)樹（tree）是n（n=0）個節(jié)點的有限集。在一棵非空樹中，有且僅有一個特定的稱為根的節(jié)點，當(dāng)n1時其余節(jié)點可分為m（m0）個互不相交的有限集t1，t2tm，其中，每一個集合本身又是一棵樹，并且稱為根的子樹（subtree）。樹的遞歸定義刻

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

8、節(jié)點x不在t中，則函數(shù)值為“空”。4）child(t，x，i) 求孩子節(jié)點函數(shù)。求樹t中節(jié)點x的第i個孩子節(jié)點。若節(jié)點x是樹t的葉子或無第i個孩子再或者節(jié)點x不在樹t中，則函數(shù)值為“空”。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)5）right_sinling(t，x)求右兄弟函數(shù)。求樹t中節(jié)點x右邊的兄弟。若節(jié)點x是其雙親的最右邊的孩子節(jié)點或節(jié)點x不在樹t中，則函數(shù)值為“空”。6）crt_tree(x，f) 建樹操作。生成一棵以x節(jié)點為根，以樹f為子樹森林的樹。7）ins_child(y，i，x) 插入子樹操作。8）del_child(x，i) 刪除子樹操作。刪除節(jié)點x的第i棵子樹。

9、9）traverse(t) 遍歷操作。按某個次序依此訪問樹中各個節(jié)點，并使每個節(jié)點只被訪問一次。10）clear(t) 清除結(jié)構(gòu)操作。將樹t置為空樹。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu) 樹的表示方法l 樹形圖表示法樹形圖表示是樹結(jié)構(gòu)的主要表示方法。樹的樹形圖表示中：節(jié)點用圓圈表示，節(jié)點的名字寫在圓圈旁邊圖中的樹由節(jié)點的有限集t=a，b，c，d，e，f，g，h，i，j所構(gòu)成，其中a是根節(jié)點，t中其余節(jié)點可分成3個互不相交的子集：t1=b，e，f，i，j，t2=c，t3=d，g，h第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 嵌套集合表示法嵌套集合表示法是用集合的包含關(guān)系來

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

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

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

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

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

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

16、二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有節(jié)點編號，能得到一個反映整個二叉樹結(jié)構(gòu)的線性序列。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)編號特點：完全二叉樹中除最下面一層外，各層都充滿了節(jié)點。每一層的節(jié)點個數(shù)恰好是上一層節(jié)點個數(shù)的2倍。假設(shè)編號為i的節(jié)點是 （1in），則有：1）若i1，則 ki的雙親編號為i/2；若i=1，則 ki是根節(jié)點，無雙親。2）若2in，則 ki的左孩子的編號是2i；否則， ki 無左孩子，即 ki必定是葉子。因此完全二叉樹中編號in/2的節(jié)點必定是葉節(jié)點。3）若2i+1n，則 ki的右孩子的編號是2i+1；否則 ki無右孩子。4）若i為奇數(shù)且不為1

17、，則 ki的左兄弟的編號是i-1；否則 ki無左兄弟。5）若i為偶數(shù)且小于n，則 ki的右兄弟的編號是i+1；否則ki 無右兄弟。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 完全二叉樹的順序存儲將完全二叉樹中所有節(jié)點按編號順序依次存儲在一個向量bt0n中。其中：bt1n用來存儲節(jié)點,bt0不使用或只用來存儲節(jié)點數(shù)目。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)一般二叉樹的順序存儲1）存儲方法將一般二叉樹添上一些 “虛節(jié)點”，成為“完全二叉樹”。將節(jié)點按編號存入向量對應(yīng)分量，其中“虛節(jié)點”用“”表示第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)2）優(yōu)點和缺點對完全二叉樹而言，

18、順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。一般的二叉樹采用順序存儲結(jié)構(gòu)時，雖然簡單，但易造成存儲空間的浪費(fèi)。最壞的情況下，一個深度為k且只有k個節(jié)點的右單支樹需要2k-1個節(jié)點的存儲空間。在對順序存儲的二叉樹做插入和刪除節(jié)點操作時，要大量移動節(jié)點。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)類型定義一個樹節(jié)點包含一個數(shù)據(jù)域和兩個指針域，指針域被稱為“左指針”和“右指針”，它們分別指向節(jié)點的左右子樹。二叉樹結(jié)構(gòu)是由節(jié)點生成的。二叉樹的結(jié)構(gòu)：第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹哈夫曼樹（ huffman ）又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹，有

19、著廣泛的應(yīng)用。樹中兩個節(jié)點之間的路徑由一個節(jié)點到另一節(jié)點的分支構(gòu)成。樹的路徑長度是從根節(jié)點到每一個節(jié)點的路徑長度之和。設(shè)一棵二叉樹有 n 個葉子節(jié)點，每個葉子節(jié)點擁有一個權(quán)值1，2，. n，從根節(jié)點到每個葉子節(jié)點的路徑長度分別為 l1，l2.ln，那么樹的帶權(quán)路徑長度為每個葉子的路徑長度與該葉子權(quán)值乘積之和。通常記作wpl k. k 。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)圖中把帶權(quán)的葉子節(jié)點畫成方形，其他非葉子節(jié)點仍為圓形。這三棵二叉樹葉子節(jié)點數(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個葉子節(jié)點看作n棵樹（僅有一個