實(shí)驗(yàn)四哈夫曼樹(shù)與哈夫曼編碼報(bào)告

1、軟 件 學(xué) 院實(shí)驗(yàn)名稱(chēng)： 哈夫曼樹(shù)與哈夫曼編碼 專(zhuān) 業(yè)： 軟件工程 班 級(jí)： 卓越121班 學(xué) 號(hào)： 201207092235 學(xué)生姓名： 劉煥超 指導(dǎo)教師： 高艷霞 2014年 06 月 02 日一、實(shí)驗(yàn)?zāi)康模?、熟悉并掌握棧的創(chuàng)建、入棧和出棧等基本用法并能運(yùn)用棧完成一些特定的任務(wù)。2、將理論知識(shí)與實(shí)踐相結(jié)合，提高自己的實(shí)際動(dòng)手能力。3、通過(guò)實(shí)踐來(lái)及時(shí)發(fā)現(xiàn)自己的缺點(diǎn)與不足，以便為接下來(lái)更加有效的學(xué)習(xí)做鋪墊。4、通過(guò)對(duì)上機(jī)來(lái)檢測(cè)自己所學(xué)知識(shí)的程度，為以后更好的掌握知識(shí)改進(jìn)學(xué)習(xí)方法。二、實(shí)驗(yàn)要求1預(yù)習(xí) c 語(yǔ)言中結(jié)構(gòu)體的定義與基本操作方法。2對(duì)單鏈表的每個(gè)基本操作用單獨(dú)的函數(shù)實(shí)現(xiàn)。3編寫(xiě)完整程序

2、完成下面的實(shí)驗(yàn)內(nèi)容并上機(jī)運(yùn)行。4整理并上交實(shí)驗(yàn)報(bào)告.問(wèn)題描述已知n個(gè)字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼?；疽?. 初始化：從鍵盤(pán)讀入n個(gè)字符，以及它們的權(quán)值，建立huffman樹(shù)。（具體算法可參見(jiàn)教材p147的算法6.12）2. 編碼：根據(jù)建立的huffman樹(shù)，求每個(gè)字符的huffman編碼。對(duì)給定的待編碼字符序列進(jìn)行編碼。選作內(nèi)容. 譯碼：利用已經(jīng)建立好的huffman樹(shù)，對(duì)上面的編碼結(jié)果譯碼。譯碼的過(guò)程是分解電文中的字符串，從根結(jié)點(diǎn)出發(fā)，按字符0和1確定找左孩子或右孩子，直至葉結(jié)點(diǎn)，便求得該子串相應(yīng)的字符。4. 打印 huffman樹(shù)。測(cè)試數(shù)據(jù)利用教材p.148 例

3、62中的數(shù)據(jù)調(diào)試程序?？稍O(shè)8種符號(hào)分別為a,b,c,d,e,f,g,h。編/譯碼序列為 “cfbabbfhgh”(也可自己設(shè)定數(shù)據(jù)進(jìn)行測(cè)試)。四、算法設(shè)計(jì)思想及步驟：要是實(shí)現(xiàn)哈夫曼樹(shù)的操作，首先創(chuàng)建一個(gè)哈夫曼樹(shù)，在創(chuàng)建哈夫曼樹(shù)的時(shí)候，對(duì)哈夫曼樹(shù)的葉子和非葉子結(jié)點(diǎn)進(jìn)行初始化，而在建立哈夫曼樹(shù)時(shí)，最難的該是選擇權(quán)值最小的兩個(gè)頂點(diǎn)，然后兩個(gè)結(jié)點(diǎn)的權(quán)值和作為新的權(quán)值，再選擇兩個(gè)權(quán)值最小的為新的兩個(gè)結(jié)點(diǎn)創(chuàng)建一個(gè)的二叉樹(shù)的子樹(shù)；我并沒(méi)有像書(shū)上那種創(chuàng)建select()函數(shù)，而是我用了兩個(gè)for()循環(huán)，先找到一個(gè)最小的記錄其下標(biāo)，在進(jìn)行下一次for循環(huán)把找到的最小的除外，這樣以此循環(huán)，就可以找到最小的了。創(chuàng)

4、建哈夫曼樹(shù)后，進(jìn)行編碼，在編碼過(guò)程中，先找到根，然后遍歷，左孩子用0標(biāo)記，右孩子用1標(biāo)記，最后將編碼好的哈夫曼樹(shù)進(jìn)行輸出，就可以知道哈夫曼樹(shù)的編碼了。算法流程：請(qǐng)輸入您想輸入的字符個(gè)數(shù)請(qǐng)輸入%d個(gè)字符的權(quán)值(用空格分開(kāi))n建立哈夫曼樹(shù)huffmancoding()顯示哈夫曼樹(shù)outputhuffman();哈夫曼數(shù)的編碼chuffmancode()結(jié)束開(kāi)始首先建立一個(gè)哈夫曼樹(shù)和哈夫曼編碼的存儲(chǔ)表示：typedef struct /定義哈夫曼的結(jié)構(gòu)體 int weight; int parent,lchild,rchild;htnode,*huffmantree; huffmantree p;t

5、ypedef char * *huffmancode;crthuffmantree(huffmantree *ht , int *w, int n)：w存放n個(gè)字符的權(quán)值，構(gòu)造哈夫曼樹(shù)ht。先將葉子初始化，再將非葉子結(jié)點(diǎn)初始化，然后構(gòu)造哈夫曼樹(shù)。五、算法運(yùn)行結(jié)果六、收獲及體會(huì)及總結(jié)通過(guò)這次數(shù)據(jù)結(jié)構(gòu)試驗(yàn)，我學(xué)習(xí)了哈夫曼的建立及其一些基本的操作方法。通過(guò)這次實(shí)踐操作學(xué)會(huì)了完成一個(gè)設(shè)計(jì)的基本方法和步驟，拿到一個(gè)問(wèn)題不能急于開(kāi)始書(shū)寫(xiě)代碼要將問(wèn)題理清楚、找清思路、分好模塊再開(kāi)始敲代碼，代碼只是實(shí)現(xiàn)一個(gè)功能的工具，只有好的解決問(wèn)題的思路，才能做出好的程序。寫(xiě)完一個(gè)程序，只是完成一個(gè)設(shè)計(jì)的一小部分，后期的調(diào)試和驗(yàn)證也是重要的一部分，這次設(shè)計(jì)完成代碼后編譯都沒(méi)錯(cuò)，但運(yùn)行結(jié)果卻不正確，通過(guò)調(diào)試后才的找出錯(cuò)誤，運(yùn)行成功，但經(jīng)過(guò)一些數(shù)據(jù)的驗(yàn)證卻又發(fā)現(xiàn)問(wèn)題，再經(jīng)過(guò)改正和完善代碼才完成整個(gè)設(shè)計(jì)。所以一個(gè)設(shè)計(jì)的完成是需要不斷的改進(jìn)、調(diào)試和驗(yàn)證的，其中耐心和細(xì)心更是不可缺少的?？偨Y(jié)：1、認(rèn)真上好專(zhuān)業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫(xiě)程序的過(guò)程中要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，