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ì)列簡(jiǎn)稱隊(duì)，是一種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它是一種操作受限的線性表。在表中只允許進(jìn)行插入的一端稱為隊(duì)尾，只允許進(jìn)行刪除的一端稱為隊(duì)頭。隊(duì)列的插入操作通常稱為入隊(duì)列或進(jìn)隊(duì)列，而隊(duì)列的刪除操作則稱為出隊(duì)列或退隊(duì)列。當(dāng)隊(duì)列中無(wú)數(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種：1）isfull() 隊(duì)列非空判斷：若隊(duì)列q不空，則返回true；否則，返回false。2）add(const int& x) 入隊(duì)列：在隊(duì)列q的尾部插入元素x，使元素x成為新的隊(duì)尾。3）delete(int& x)出隊(duì)列：若隊(duì)列q不空，則返回隊(duì)頭元素，并從隊(duì)頭刪除該元素；否則，拋出異常。4）first() 取隊(duì)頭元素：若隊(duì)列q不空，則返回隊(duì)頭元素；否則拋出異常。隊(duì)列是一種特殊的線性表，因此隊(duì)列可采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，也可以使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)。第2章 算法分析與數(shù)據(jù)結(jié)

3、構(gòu)2.4 線性表l 鏈隊(duì)列的表示用鏈表表示的隊(duì)列簡(jiǎn)稱為鏈隊(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 re

4、turn (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

5、;p-link = 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;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é)點(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）是n（n=0）個(gè)節(jié)點(diǎn)的有限集。在一棵非空樹中，有且僅有一個(gè)特定的稱為根的節(jié)點(diǎn)，當(dāng)n1時(shí)其余節(jié)點(diǎn)可分為m（m0）個(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)算包括：1）initiate(t) 初始化操作，置t為空樹。2）root(t)root(x) 求根函數(shù)。求樹t的根或求節(jié)點(diǎn)x所在的樹的根節(jié)點(diǎn)。若t是空樹或x不在任何一棵樹上，則函數(shù)值為“空”。3）rarent(t，x) 求雙親函數(shù)。求樹t中節(jié)點(diǎn)x的雙親節(jié)點(diǎn)。若節(jié)點(diǎn)x是樹t的根節(jié)點(diǎn)或

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

9、9）traverse(t) 遍歷操作。按某個(gè)次序依此訪問(wèn)樹中各個(gè)節(jié)點(diǎn)，并使每個(gè)節(jié)點(diǎn)只被訪問(wèn)一次。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é)點(diǎn)用圓圈表示，節(jié)點(diǎn)的名字寫在圓圈旁邊圖中的樹由節(jié)點(diǎn)的有限集t=a，b，c，d，e，f，g，h，i，j所構(gòu)成，其中a是根節(jié)點(diǎn)，t中其余節(jié)點(diǎn)可分成3個(gè)互不相交的子集：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)系來(lái)

10、描述樹結(jié)構(gòu)l 凹入表表示法每棵樹的根對(duì)應(yīng)著一個(gè)條形，子樹的根對(duì)應(yīng)著較短的條形，且樹根在上，子樹的根在下。長(zhǎ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)是子樹。（a（b（e，f（i，j），c，d（g，h） 樹形結(jié)構(gòu)的基本術(shù)語(yǔ)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ù)

11、據(jù)結(jié)構(gòu)2）孩子和雙親。樹中某個(gè)節(jié)點(diǎn)的子樹之根稱為該節(jié)點(diǎn)的孩子或兒子，相應(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）有序樹和無(wú)序樹。若將樹中

12、每個(gè)節(jié)點(diǎn)的各子樹看成是從左到右有次序的（即不能互換），則稱該樹為有序樹；否則稱為無(wú)序樹。6）森林。森林是m（m0）棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根，就得到一個(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)無(wú)前趨，它是開始節(jié)點(diǎn)；葉節(jié)點(diǎn)無(wú)后繼，它們是終端節(jié)點(diǎn)。3）祖先與子孫的關(guān)系是對(duì)父子關(guān)系的延拓，它定義了樹中節(jié)點(diǎn)之間的縱向次序。4）有序樹中，同一組兄弟節(jié)點(diǎn)從左到右有長(zhǎng)幼之分。第2章

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

14、，若終端節(jié)點(diǎn)的個(gè)數(shù)為 n0，度為2的節(jié)點(diǎn)數(shù)為n2 ，則n0 = n2+1。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(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)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。完全

15、二叉樹的特點(diǎn)：1）滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。2）在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干節(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。3）在完全二叉樹中，若某個(gè)節(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子，即該節(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)的完全

16、二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有節(jié)點(diǎn)編號(hào)，能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列。第2章 算法分析與數(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)，無(wú)雙親。2）若2in，則 ki的左孩子的編號(hào)是2i；否則， ki 無(wú)左孩子，即 ki必定是葉子。因此完全二叉樹中編號(hào)in/2的節(jié)點(diǎn)必定是葉節(jié)點(diǎn)。3）若2i+1n，則 ki的右孩子的編號(hào)是2i+1；否則 ki無(wú)右孩子。4）若i為奇數(shù)且不為1

17、，則 ki的左兄弟的編號(hào)是i-1；否則 ki無(wú)左兄弟。5）若i為偶數(shù)且小于n，則 ki的右兄弟的編號(hào)是i+1；否則ki 無(wú)右兄弟。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)l 完全二叉樹的順序存儲(chǔ)將完全二叉樹中所有節(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)向量bt0n中。其中：bt1n用來(lái)存儲(chǔ)節(jié)點(diǎn),bt0不使用或只用來(lái)存儲(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)存入向量對(duì)應(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)對(duì)完全二叉樹而言，

18、順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單又節(jié)省存儲(chǔ)空間。一般的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，雖然簡(jiǎn)單，但易造成存儲(chǔ)空間的浪費(fèi)。最壞的情況下，一個(gè)深度為k且只有k個(gè)節(jié)點(diǎn)的右單支樹需要2k-1個(gè)節(jié)點(diǎn)的存儲(chǔ)空間。在對(duì)順序存儲(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)路徑長(zhǎng)度最短的樹，有

19、著廣泛的應(yīng)用。樹中兩個(gè)節(jié)點(diǎn)之間的路徑由一個(gè)節(jié)點(diǎn)到另一節(jié)點(diǎn)的分支構(gòu)成。樹的路徑長(zhǎng)度是從根節(jié)點(diǎn)到每一個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度之和。設(shè)一棵二叉樹有 n 個(gè)葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)擁有一個(gè)權(quán)值1，2，. n，從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑長(zhǎng)度分別為 l1，l2.ln，那么樹的帶權(quán)路徑長(zhǎng)度為每個(gè)葉子的路徑長(zhǎng)度與該葉子權(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)路徑長(zhǎng)各不相同。最右邊的樹就是哈曼樹，最優(yōu)樹。第2章 算法分析與數(shù)據(jù)結(jié)構(gòu)2.5 其他常用數(shù)據(jù)結(jié)構(gòu)哈夫曼樹的構(gòu)造：對(duì)于已知的一組葉子的權(quán)值1，2. ，n 1）首先把n個(gè)葉子節(jié)點(diǎn)看作n棵樹（僅有一個(gè)