嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu) (11).ppt

1、第1，6章樹和二叉樹(Tree i=10，a=110，n=111 )，為了實現(xiàn)哈夫曼編碼化，首先建構(gòu)哈夫曼樹，進行討論：明確哈夫曼樹有什么作用，權(quán)重大的節(jié)點是短路徑，權(quán)重小的節(jié)點是長路徑。對WPL最小的樹、頻度高的信息用短查詢密碼、頻度低的長查詢密碼、傳輸效率確實高的WP L2=1比特72比特53比特(24 )=35、最小冗余碼化、信息效率傳輸、5，2.huffman樹進行建構(gòu)的步驟(即Huffman算法) 以f中兩根根結(jié)點權(quán)重最小的樹作為左右的子樹來建構(gòu)新的二叉樹，以使新的二叉樹的根結(jié)點權(quán)重等于該左右的子樹的根結(jié)點權(quán)重之和。 (3)在f中刪除這些個2棵樹的同時，將新得到的二叉樹添加到f中。

2、(4)反復(fù)(2)和(3)直到f只包含一棵樹。 這棵樹是Huffman樹。 如何證明WPL是最小的最佳二叉樹？ 參照原代碼，即一次合并當(dāng)前值最小的兩個權(quán)重。 (該樹的特征：度不為1的節(jié)點)，6，step1:合并、刪除、置換權(quán)重集7，5，2，4中，始終合并當(dāng)前值最小的2個權(quán)重，具體的操作步驟：a .初始，框表示外節(jié)點.不規(guī)定則并非唯一step2:將huffman樹的所有分支編號向左“0”右“1”推一推，huffman編碼結(jié)果： d=0，i=10，a=110， n Huffman編碼也被稱為前綴代碼，其將Huffman樹與Huffman編碼相鏈接，并且8、2、Huffman編碼、哈夫曼編碼化的基本思

3、想是用于出現(xiàn)概率大的信息的短碼、用于概率小的長碼、最小冗馀、Huffman編碼、不相等長度編碼，如9、本節(jié)中的建議1:Huffman樹中的節(jié)點結(jié)構(gòu)可以修改為4或5分量形式。 將整個Huffman樹的節(jié)點保存在一個數(shù)組HT1.n.m中(Huffman樹內(nèi)外結(jié)點總數(shù)m=2n-1 )各葉子結(jié)點的查詢密碼保存在另一個“復(fù)合”組HC1.n中。 (n個權(quán)重是n個葉，對應(yīng)于n個不同的查詢密碼列)。建議2: Huffman樹的存儲結(jié)構(gòu)可以采用這樣的順序存儲結(jié)構(gòu)，其中，在建構(gòu)Huffman樹HT之后，確定n個權(quán)重/字符的Huffman查詢密碼HC 例1【嚴(yán)格問題集6.26】:假設(shè)用于通訊的電文僅由8個字符的a、

4、b、c、d、e、f、g、h構(gòu)成，它們出現(xiàn)在電文中的概率分別為0.07、0.19、0.02、6.26。 使用07的二進制編碼方式會怎么樣？ 【類同P148例2】、11、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0、0 13、12、1011、9、8、7、6、5、4、3、2、1、 小盆友lchild，rchild，12，2，7，對應(yīng)哈夫曼編碼：12，40，60，100，父代，左右的。 Huffman碼的WP L2 (0. 19.32 )3(0. 190.320.210.070.060.10.020.03 )=3、二進制等長查詢密碼的WPL用左0右1來表示、1

5、3、另一個表示：14、自動機練習(xí)說明：字符定徑套為26阿爾法、請求：建構(gòu)Huffman樹后，使用該樹對任意字符串文件進行查詢密碼和查詢密碼后，將設(shè)定Huffman編譯碼器、15、類型樹未綁定權(quán)重。 /權(quán)重成分(可擴大取得) unsigned int parent，lchild，rchild； /父母和小盆友的分量HTNode，*HuffmanTree； 胡夫曼樹類型樹* *胡夫曼代碼； /動態(tài)數(shù)組存儲Huffman查詢密碼表，Huffman樹和Huffman樹查詢密碼的存儲表示：父母，* Huffman樹或HT矢量模式：HT3.parent=9，指針類型指針，16，voidhuffmancod

6、ing (hoidhuffmancoding /n個葉的Huffman樹一共有2n-1個結(jié)點。 ht=樹形大小(m1) *大小(htnode ) )/0未使用針織面料，for(p=HT 1，i=1； i=n； I，p，w)*p=*w，0，0，0。 /初始化前n個用戶針織面料(原教材有錯誤) for (； i=m； I，p ) * p=0，0，0，0。 /葉后的存儲單元清零for(i=n 1； i=m； i)/huffman樹(從n個葉子之后存儲內(nèi)結(jié)點) Select(HT，i-1，s1，s2)； 選擇HT1i-1中父節(jié)點為0且權(quán)重最小的兩個節(jié)點，其編號分別為s1和s2 (教材中未列出該函數(shù)的原

7、代碼) HTs1.parent=i； HTS2.伙伴=I； /對父母的分量分配HTi.lchild=s1。 S2 :天空飛行器； /將小盆友值hti.weight=h ts1. weight HTS2. weight賦予合并的內(nèi)結(jié)點。 存儲*wn字符的權(quán)重int *w表示w是指向int數(shù)組的指針，*w取int，w之后*w取下一個要素w等同于數(shù)組名(即指向該int數(shù)組的指針)。 17，sizeof ()可以運算變量或變量類型。 sizeof(char* )是char型指針的空間大小，如果定義了char *p，則sizeof(p )為結(jié)果和sizeof (續(xù)) n個字符的Huffman關(guān)查詢密碼字

8、HC，HC=(Huffman代碼) malloc (n1) * sizeon /n字符查詢密碼的頭指針矢量(一維度數(shù)組)，cd=(char*) malloc(n*sizeof(char ) )； /求編碼的臨時最長空間cdn-1=“0”； /編碼終端查詢密碼(從cd0cdn-1到合法空間) for(i=1； i=n； i) /對每個字符求出Huffman查詢密碼start=n-1。 /查詢密碼終端查詢密碼位置for(c=i，f=HTi.parent； f！=0； c=f，f=HTf.parent) /從葉子到根向相反方向查詢密碼定if(HTf.lchild=c) cd-start=“0”； e

9、lse CD-開始=“1”； HCI=(char * ) malloc (n-start ) * sizeof (char ) )/為第I個字符查詢密碼分配空間，每個查詢密碼列指針strcpy(HCi， /釋放臨時空間/HuffmanCoding，p 149，18，以數(shù)組形式存儲二叉樹的若干示例性算法(練習(xí)題) 4的算法構(gòu)想：利用隊列存儲指向每個子樹節(jié)點的指針是最好的方法，因為既然要求從上到下、從左到右技巧：將根結(jié)點入隊后，將左、右小盆友節(jié)點入隊，將左小盆友入隊后，將左右小盆友節(jié)點入隊，從而按級別進行輸出。 1 .如何獲得二叉樹的深度或從一個節(jié)點開始的子樹的深度？算法構(gòu)想：僅檢查每個節(jié)點的后續(xù)

10、網(wǎng)絡(luò)鏈接表指針，如果左(右)小盆友的左(右)指針不為空，則為分層數(shù)加1，否則函數(shù)返回。 算法為附件1，算法為附件2，20，算法構(gòu)想：如果不遞歸，則在實現(xiàn)二叉樹掃描的“嵌套”規(guī)則時，必須使用棧內(nèi)存(迭代方式)。 可通過推/pop與while語句直接操作。 參見教材P130-131普通堆計程儀。 用4順序掃描的非遞歸算法是如何實現(xiàn)的？ 3、如何判斷給定二叉樹是否完全二叉樹的算法構(gòu)想：完全二叉樹的特征是，左子樹空，右子樹不可能單獨存在(前k-1層全部填滿，第k層左側(cè)也填滿)。 在技巧：分層遍歷方案中，首先對所有節(jié)點(不管當(dāng)前節(jié)點是否有左右小盆友)進行排隊。 在完全二叉樹的情況下，在分層掃描中獲得的序

11、列不總是包括連續(xù)的空指針。 如果序列中出現(xiàn)空指針，則表示不是完全二叉樹。算法為附件3，算法為附件4、21，Void ABC(Bitree p、int l、int，法1 :從根向下修正層次(比從葉向上修正簡單)，l、h分別表示二叉樹的層次數(shù)和深度。想一想。 l和h的初始值應(yīng)該是多少？ 在開始調(diào)用時，使用ABC(p，0，0 )刪除h關(guān)殘奧字計數(shù)器的“/左右兩個深度/層次計數(shù)器if (Bt=空)返回(0)”。 /如果當(dāng)前節(jié)點指針為空，則立即返回深度=樹深度(Bt-left )； /當(dāng)前節(jié)點的左側(cè)子樹right dep=樹深度(Bt-right )； /當(dāng)前節(jié)點的右側(cè)子樹if (leftdeprigh

12、tdep )返回(left dep1)； 從葉子返回(right dep1)； /BTreeDepth，法2 :遞歸地從葉子向上計數(shù)，留下深層的東西。 二十三、語音層次順序/層序掃描二叉樹入隊列(q )； /創(chuàng)建空工作團隊(初始化隊列)枚舉(q，t )。 /將一個節(jié)點插入隊列末尾的函數(shù)while (！ QueueEmpty(Q) ) DeQueue(Q，/p的右小盆友入隊/LayerOrder，附件2 :分層遍歷算法(需要使用隊列)嚴(yán)格問題集6.47，當(dāng)小盆友為空時不要將空指針入隊。 /建設(shè)隊列(初始化隊列) flag=0； /標(biāo)志初始化EnQueue(Q，t )； /節(jié)點t入隊(空指針也入隊) while (！ QueueEmpty(Q) DeQueue(Q，/執(zhí)行到目前為止在隊列空間中沒有空指針的完全二叉/IsFull_Bitree，25，statusinordertrav p=T； /初始化關(guān)棧內(nèi)存字while(p |！ 堆棧進度(s ) )/如果樹不為空或堆棧內(nèi)存不為空，則開始老虎吧定if (p )推式(s，p )。