1、哈夫曼編碼譯碼器實(shí)驗(yàn)報(bào)告（免問題解析與解題方法問題分析： 設(shè)計(jì)一個(gè)哈夫曼編碼、譯碼系統(tǒng)。對(duì)一個(gè)ASCII 編碼的文本文件中的字符進(jìn)行哈夫曼編 碼，生成編碼文件；反過來，可將編碼文件譯碼 還原為一個(gè)文本文件。（ 1） 從文件中讀入任意一篇英文短文 （文件為 ASCII 編碼，擴(kuò)展名為 txt ）；（ 2） 統(tǒng)計(jì)并輸出不同字符在文章中出現(xiàn)的頻 率（空格、換行、標(biāo)點(diǎn)等也按字符處理） ；（ 3） 根據(jù)字符頻率構(gòu)造哈夫曼樹， 并給出每個(gè) 字符的哈夫曼編碼；（ 4） 將文本文件利用哈夫曼樹進(jìn)行編碼， 存儲(chǔ) 成壓縮文件（編碼文件后綴名 .huf ）（ 5） 用哈夫曼編碼來存儲(chǔ)文件， 并和輸入文本 文件大小進(jìn)

2、行比較，計(jì)算文件壓縮率；（ 6） 進(jìn)行譯碼，將 huf 文件譯碼為 ASCII 編 碼的 txt 文件，與原 txt 文件進(jìn)行比較。 根據(jù)上述過程可以知道該編碼譯碼器的關(guān)鍵 在于字符統(tǒng)計(jì)和哈夫曼樹的創(chuàng)建以及解碼。哈夫曼樹的理論創(chuàng)建過程如下：一、構(gòu)成初始集合 對(duì)給定的 n 個(gè)權(quán)值 W1,W2,W3,.,Wi,.,Wn 構(gòu)成 n 棵二 叉樹的初始集合F=T1,T2,T3,.,Ti,.,Tn ，其中每棵二 叉樹 Ti 中只有一個(gè)權(quán)值為 Wi 的根結(jié) 點(diǎn)，它的左右子樹均為空。二、選取左右子樹在 F 中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹 作為新構(gòu)造的二叉樹的左右子樹，新 二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹 的根結(jié)

3、點(diǎn)的權(quán)值之和。三、刪除左右子樹從 F 中刪除這兩棵樹，并把這棵新的二 叉樹同樣以升序排列加入到集合 F 中。四、重復(fù)二和三兩步，重復(fù)二和三兩步，直到集合 F 中只有一 棵二叉樹為止。因此，有如下分析：1. 我們需要一個(gè)功能函數(shù)對(duì) ASCII 碼的初始 化并需要一個(gè)數(shù)組來保存它們；2. 定義代表森林的數(shù)組，在創(chuàng)建哈夫曼樹的 過程當(dāng)中保存被選中的字符，即給定報(bào)文 中出現(xiàn)的字符 ,模擬哈夫曼樹選取和刪除左 右子樹的過程；3. 自底而上地創(chuàng)建哈夫曼樹，保存根的地址 和每個(gè)葉節(jié)點(diǎn)的地址，即字符的地址，然 后自底而上檢索，首尾對(duì)換調(diào)整為哈夫曼 樹實(shí)現(xiàn)哈弗曼編碼；4. 從哈弗曼編碼文件當(dāng)中讀入字符，根據(jù)當(dāng)

4、前字符為 0 或者 1 的狀況訪問左子樹或者 右孩子，實(shí)現(xiàn)解碼；5. 使用文件讀寫操作哈夫曼編碼和解碼結(jié)果 的寫入；解題方法：結(jié)構(gòu)體、數(shù)組、類的定義：1. 定義結(jié)構(gòu)體類型的 signode 作為哈夫曼樹 的節(jié)點(diǎn)，定義結(jié)構(gòu)體類型的 hufnode 作為 哈夫曼編碼對(duì)照表的節(jié)點(diǎn)， 定義 HFM 類實(shí) 現(xiàn)對(duì)哈夫曼樹的創(chuàng)建，利用其成員函數(shù)完 成哈夫曼編碼譯碼的工作。2. 定義 signode 類型的全局?jǐn)?shù)組 SN256（為 方便調(diào)用，之后的 forest256 ，hufNode256 均為全局?jǐn)?shù)組） , 保存 ASCII 編碼的字符， 是否在文章中出現(xiàn)（ bool 類型）以及出現(xiàn) 次數(shù)（int 類型，

5、權(quán)重），左右孩子節(jié)點(diǎn)位置， 父節(jié)點(diǎn)位置信息；3. 為節(jié)省存儲(chǔ)空間， 定義 signode * 類型的全 局?jǐn)?shù)組 forest256, 模擬森林， 在創(chuàng)建哈夫 曼樹的過程中保存出現(xiàn)字符的指針，模擬 哈夫曼樹選取和刪除左右子樹的過程；4. 定 義 hufnode 類 型 的 全 局 數(shù) 組 hufNode256 ，在編碼時(shí)最為哈夫曼編碼對(duì) 照 表 的 節(jié) 點(diǎn) ， char 型 c 保 存 字 符 ,int code100保存其哈夫曼編碼；5. 定義 HFM 類，主要保存哈夫曼樹的根節(jié)點(diǎn) 指針，但其豐富的功能函數(shù)將實(shí)現(xiàn)哈夫曼 編碼譯碼的工作及其他功能；函數(shù)介紹：1. void init（signod

6、e * sig） 初始化數(shù)組 SN；2. void compress（） 輸出壓縮對(duì)比情況 的信息;3. void exchange() 用兩層 for 循環(huán)實(shí)現(xiàn) hufNodei 節(jié)點(diǎn) 的成 員哈 夫曼編 碼 數(shù)組 code 前后元素的對(duì)換， 因?yàn)樵谥暗木幋a 過程中由于是從葉節(jié)點(diǎn)追溯至根節(jié)點(diǎn)，存 入 code 數(shù)組的哈夫曼編碼與哈夫曼編碼的 概念反向，故而要調(diào)整；4. signode * getroot() 返回哈夫曼樹的 根節(jié)點(diǎn)指針；5. signode * HFM:creat() 創(chuàng)建哈夫曼 樹，首先用三個(gè) for 循環(huán)查看 forest 數(shù)組， 找到權(quán)值最小的兩個(gè)字符，以 int 型

7、的 min1,min2 記錄其下標(biāo)，定義 signode * 類 型指針 pp 指向新生成 signode 節(jié)點(diǎn)，用指 針 操 作 使 pp 指 向 的 節(jié) 點(diǎn) 的 權(quán) 值 為 min1,min2 權(quán) 值 之 和 ， pp 做 孩 子 指 向 forestmin1, 右 孩 子 指 向 forestmin2 ， min1,min2 的父指針指向 pp，然后將 pp 存 入 min1 的位置， min2 之后的每一個(gè)節(jié)點(diǎn) 依次往前移一個(gè)位置， 實(shí)現(xiàn)從 forest 數(shù)組中 清除 min1,min2 并加入 pp 的操作；6. void HFM:hufcode() 哈夫曼編碼，用 for 循環(huán)控制

8、查看 hufNode 數(shù)組，其初始化 已在 creat ()的開始完成，對(duì)每一個(gè)字符 實(shí)現(xiàn)編碼， 用 while 循環(huán)從葉節(jié)點(diǎn)開始， 如 果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子就將 codehufNodei.size+ 賦值 0，否則賦為 1， 直至當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為空， while 循環(huán)結(jié) 束；7. void HFM:savewithhufcode(FILE * inf,FILE * outf) 將讀入的文章以哈 夫曼編碼的形式存儲(chǔ)， 其中 inf 為讀入文件 的指針， outf 為寫入文件的指針 ,首先調(diào)用 rewind(inf) 函數(shù)將光標(biāo)放置在文章開頭， 防 止文件未關(guān)閉導(dǎo)致的錯(cuò)誤，每讀一個(gè)字符

9、就用 for 循環(huán)在 hufNode 數(shù)組中查找，因 為 hufNode 數(shù)組就是保存出現(xiàn)的字符的， 故一定可以找到，然后再用 fputc 函數(shù)將 code數(shù)組的內(nèi)容寫入文件， 直至讀入文件 結(jié)束；8. void HFM:inorder(signode * sig) 迭 代法遍歷樹，遍歷到葉節(jié)點(diǎn)時(shí)執(zhí)行 hufNodecount+.sig=sig 語 句 實(shí) 現(xiàn) hufNode 數(shù)組指向文章中出現(xiàn)的字符； 9.int HFM:maxc() 計(jì)數(shù)變量，記錄哈夫曼編碼最大位數(shù)；10. void HFM:hufdecode(FILE* ipf,FILE* opf) 解碼，從哈夫曼編碼到字符，輸 出到屏

10、幕和指定的文件中；11. void input(FILE * f) 初始讀入文 章，保存出現(xiàn)的字符記錄修改其權(quán)重；數(shù)據(jù)結(jié)構(gòu)選擇與算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)選擇：signode：structsignode /signode 節(jié)點(diǎn)，哈夫曼樹節(jié)點(diǎn) /charc;/字符 /intweight;/權(quán)重 /boolb;/文章中是否出現(xiàn) / signode * parent; signode * left;signode * right;signode() 化/c=NULL;b=false;weight=0; parent=left=right=NULL; ;Cweightbhufnode:struct hufnod

11、e/哈夫曼編碼對(duì)照表節(jié)點(diǎn) / signode * sig; int/保存哈夫曼編碼 /初始code100;int size;bool b;hufnode()sig=NULL;size=0;b=true;SigHFM:classHFM/哈夫曼類 /private:root;pt;signode * /哈夫曼樹根 /signode * /編碼時(shí)做哨兵指針 /int alleaf;public:HFM(int all)root=pt=NULL;alleaf=all; /all 是森林中樹的個(gè)數(shù) /HFM()signode * getroot()return root;signode/創(chuàng)建哈夫曼樹 /

12、voidcreat();hufcode();/編碼 /voidinf,FILE * outf); 件/savewithhufcode(FILE/用哈弗曼編碼存儲(chǔ)文hufdecode(FILE* ipf,FILE*/解碼 / void inorder(signode * sig); int maxc();/求取哈弗曼編碼最大長(zhǎng)度 /;opf);Rootalleafvoidpt算法設(shè)計(jì)：Doc 窗口：Minininire：TT0T0：IDT:TATATTT0;venw： DIT: KI110W： IHIHRTH：養(yǎng)丿-lm-3了訂 44r Jr 亍工4一. j Hr 42 丄I:護(hù)-亠r:ii務(wù)

13、s 4IB一4r-4l up- A o iHcrHdLlsIwdM 館.吩3;匹佚第蠱応wsM;3J3isu; .二 1 二 一 - 二二匚.二 yyy *辛4.$耳* *=*w書雯*s#s管*wN#=*lr yvg型鄒爭(zhēng)，幕型鄒歩竽驢審型$卵爭(zhēng)騎型I八yq6nq心皿q叫十冊(cè)zpxg !汕.力扎文件讀寫（部分）：總結(jié)程序分析： 本次哈夫曼編碼譯碼器的課程實(shí)驗(yàn)做得還 算成功， 不僅僅在于程序能夠正常運(yùn)行， 實(shí)現(xiàn)應(yīng) 有的功能， 關(guān)鍵在于過程， 在于小組成員的分工 合作和一起糾錯(cuò)排錯(cuò)的過程， 在完成程序的過程 中才能真正理解面向?qū)ο蠛湍K化設(shè)計(jì)的思想， 我們不僅僅是說要每人分幾個(gè)函數(shù)， 關(guān)鍵在于這

14、些函數(shù)代表的是一個(gè)個(gè)功能模塊， 任何一個(gè)模塊 出現(xiàn)問題或者模塊之間的銜接出現(xiàn)問題都將導(dǎo) 致程序運(yùn)行的失敗哈夫曼編碼譯碼器課程實(shí)驗(yàn)我主要負(fù)責(zé) 完成編碼譯碼器數(shù)據(jù)結(jié)構(gòu)和功能模塊框架的設(shè) 計(jì)，結(jié)構(gòu)體和類的定義， 以及 creat 函數(shù)，hufcode 函數(shù)， savewithhufcode 函數(shù)的實(shí)現(xiàn)。在初始設(shè) 計(jì)的時(shí)候， 我體會(huì)到書寫流程圖的重要性， 只有 又一個(gè)清晰的設(shè)計(jì)思路才能事半功倍，分工明 確，避免無效勞動(dòng)或者在錯(cuò)誤的編程方向上走彎 路，也讓大家明白自己在程序設(shè)計(jì)中的位置和職 責(zé)。初始的創(chuàng)建是哈夫曼編碼譯碼系統(tǒng)成功 的關(guān)鍵，我在創(chuàng)建的過程當(dāng)中多次使用樹的先 根，配合中根遍歷操作， 輸出接點(diǎn)

15、字符或者權(quán)重 信息，作為檢驗(yàn)， 對(duì)驗(yàn)證和糾錯(cuò)起到了非常大的 作用。在適當(dāng)?shù)牡胤秸{(diào)用它們， 運(yùn)行時(shí)可以看到 驗(yàn)證編寫程序的正確性； 通過本次實(shí)驗(yàn)，提高了自已調(diào)試程序的能 力。充分體會(huì)到了在程序執(zhí)行時(shí)的提示性輸出的 重要性。編寫大一點(diǎn)的程序，應(yīng)先寫出算法，再 寫程序， 一段一段調(diào)試； 對(duì)于沒有實(shí)現(xiàn)的操作用 空操作代替， 這樣容易找出錯(cuò)誤所在。 最忌諱將 所有代碼寫完后再調(diào)試， 這樣若程序有錯(cuò)誤， 太難找需要特別強(qiáng)調(diào)的是：1 感覺文件操作自己并不是很熟練， 盡管在 向顯示器輸出的時(shí)候并沒有什么錯(cuò)誤但是 讀寫文件的時(shí)候就沒那么順利了，比如說 當(dāng)編寫 savewithhufcode 函數(shù)時(shí)讀文件，卻 總

16、不執(zhí)行，后來通過斷點(diǎn)測(cè)試發(fā)現(xiàn)每次 fgetc() 返回值總為 -1 ，于是我考慮是否是 文件沒有打開或者文件結(jié)束的緣故，后來 想通了是之前打開的文件光標(biāo)讀操作結(jié)束 后仍在結(jié)尾故每次總返回 -1 ，故調(diào)用 rewind 函數(shù)將光標(biāo)位置移動(dòng)到文章開始。 2. 用哈夫曼編碼存儲(chǔ)文件的時(shí)候還應(yīng)注 意數(shù)字 0,1 與字符 0,1的不同，不應(yīng)直接 在fputc() 函數(shù)中直接寫入 0,1 那么將 會(huì)是寫入的文章中什么都沒有，因?yàn)?0 在ASCII碼中代表 NULL。3. 該程序函數(shù)清晰功能明確， 程序具有通 用性，對(duì)于不同的輸入文章都可進(jìn)行處 理，由于采用哈夫曼編碼對(duì)照表， 使得 查看哈夫曼編碼是效率較高

17、無需每次 遍歷哈夫曼樹。程序清單.cpp #include#include#include#include#includeHh1.husing namespace std;FILE * f1=fopen(d:pra1.txt,r);FILE * f2=fopen(d:pra2.txt,w);FILE * f3=fopen(d:pra4.huf,w);int main()init(SN); / 初始化字符數(shù)據(jù)庫 / input(f1);/ 讀入初始文件的字符 /for(int i=0;foresti!=NULL;i+)coutc:weightendl; / 輸出字符及出現(xiàn)次數(shù) / cout 出現(xiàn)

18、字符種類countendl;/輸出字符種類 / 創(chuàng) 建 哈 夫 曼 樹 實(shí) 例 / huffman.creat();/哈夫曼編碼，此時(shí)為逆向 / 調(diào) 整 首 尾 對(duì) 調(diào) 哈 夫 曼 編 碼 / 用哈夫曼編碼存儲(chǔ)原文件 /HFM huffman(count);/ 創(chuàng)建哈夫曼樹 / count=0;huffman.hufcode();exchange(); huffman.savewithhufcode(f1,f2);coutendl;cout1. 查看哈夫曼編碼 endl;cout2. 哈夫曼解碼 endl;cout3. 查看壓縮率 choice;while(choice=1&choice=3)

19、switch(choice)case 1:for(i=0;hufNodei.sig!=NULL;i+)cout 字符 c 的哈夫曼編碼 :for(int j=0;jhufNodei.size;j+)couthufNodei.codej; coutendl;cout 最大列數(shù) :huffman.maxc()endl;break;case 2:fclose(f2);f2=fopen(d:pra2.txt,r);huffman.hufdecode(f2,f3);coutendl;break;case 3:compress();coutendl;cout1. 查看哈夫曼編碼 endl;cout2. 哈

20、夫曼解碼 endl;cout3. 查看壓縮率 choice;cout* 謝謝使用 *endl;return 0;/輸出哈夫曼編碼 / 哈夫曼解碼 / 查看壓縮情況 / 退出操作 /.h#include using namespace std;struct signode/signode 節(jié)點(diǎn)，哈夫曼樹節(jié)點(diǎn)char c;/字符 /int weight;/權(quán)重 /bool b;/文章中是否出現(xiàn) /signode * parent;signode * left;signode * right;signode()/初始化 /c=NULL; b=false; weight=0;parent=left=r

21、ight=NULL; signode SN256;signode * forest256;/ 森林?jǐn)?shù)組保存出現(xiàn)的字符 /int count=0;/出現(xiàn)字符計(jì)數(shù) /float memo1=0,memo2=0;/全局變量記錄讀入字符數(shù)和編碼的0 1 數(shù)/void init(signode * sig)/SN 數(shù)組初始化，輸入常見字符 /sig0.c=a;sig1.c=b;sig2.c=c; sig3.c=d;sig4.c=e; sig5.c=f;sig6.c=g;sig7.c=h;sig8.c=i;sig9.c=j; sig10.c=k;sig11.c=l;sig12.c=m;sig13.c=n;

22、sig14.c=o; sig15.c=p;sig16.c=q;sig17.c=r;sig18.c=s;sig19.c=t; sig20.c=u;sig21.c=v;sig22.c=w;sig23.c=x;sig24.c=y; sig25.c=z;sig26.c=A;sig27.c=B;sig28.c=C;sig29.c=D;sig30.c=E; sig31.c=F;sig32.c=G;sig33.c=H;sig34.c=I;sig35.c=J; sig36.c=K;sig37.c=L;sig38.c=M;sig39.c=N;sig40.c=O; sig41.c=P;sig42.c=Q;sig4

23、3.c=R;sig44.c=S;sig45.c=T; sig46.c=U;sig47.c=V;sig48.c=W;sig49.c=X;sig50.c=Y; sig51.c=Z;sig52.c=0;sig53.c=1;sig54.c=2;sig55.c=3;sig56.c=4; sig57.c=5;sig58.c=6;sig59.c=7;sig60.c=8;sig61.c=9;sig62.c=+;sig63.c=-;sig64.c=*;sig65.c=/;sig66.c=,; sig67.c=.;sig68.c=; sig69.c=;sig70.c=:;sig71.c=;sig72.c=;sig

24、74.c=;sig75.c=?;sig76.c= ; sig77.c=(;sig78.c=);sig79.c=;sig80.c=;sig81.c=; sig82.c=;sig83.c=!;sig84.c=;sig85.c=#;sig86.c=$; sig87.c=%;sig88.c=;sig89.c=&;sig90.c=;sig91.c=10;void compress()/壓縮情況對(duì)比 /cout 壓縮前 :memo1*8bit 壓縮后 :memo2bitendl;cout 壓縮率 :memo2/(memo1*8)endl;struct hufnode/ 哈夫曼編碼對(duì)照表節(jié)點(diǎn) /signod

25、e * sig;int code100;/保存哈夫曼編碼 / int size;bool b;hufnode()sig=NULL;size=0;b=true; ;/ 調(diào)換首尾交換哈夫曼編碼 /hufnode hufNode256; void exchange()int temp;for(int i=0;hufNodei.sig!=NULL;i+)for(int s=0,b=hufNodei.size-1;s=b;s+,b-)temp=hufNodei.codes;hufNodei.codes=hufNodei.codeb;hufNodei.codeb=tempclass HFM/哈夫曼類 /p

26、rivate:signode * root;/哈夫曼樹根 /signode * pt;/編碼時(shí)做哨兵指針 /int alleaf;public:HFM(int all)root=pt=NULL;alleaf=all;/all是森林中樹的個(gè)數(shù) /HFM()signode * getroot()return root;signode * creat();void hufcode();void savewithhufcode(FILE * inf,FILE * outf);void hufdecode(FILE* ipf,FILE* opf);void inorder(signode * sig);

27、int maxc();signode * HFM:creat()signode * pp=NULL;/ 創(chuàng)建哈夫曼樹 /編碼 / 用哈弗曼編碼存儲(chǔ)文件 /解碼 /求取哈夫碼曼最大長(zhǎng)度 /for(int i=0;ib=false;/為 hufcode 函數(shù)作準(zhǔn)備，與此函數(shù)無關(guān) / while(count1)int min=10000;int min1,min2;for(int i=0;foresti!=NULL;i+)/ 以 下 三 個(gè) for 循 環(huán) 選出當(dāng)前森林中的最小兩個(gè)節(jié)點(diǎn)/if(foresti-weightweight;min1=i;/min=10000;/for(i=0;forest

28、i!=NULL&i!=min1;i+)/if(foresti-weightweight;min2=i;/for(i=min1+1;foresti!=NULL;i+) / if(foresti-weightweight;min2=i; / 至此找到 min1 min2pp=new signode();/ 新生成節(jié)點(diǎn)，權(quán)值為兩最小節(jié)點(diǎn)權(quán)值之和/pp-left=forestmin1;pp-right=forestmin2;forestmin2-b=true;/ 為 hufcode 函數(shù)作準(zhǔn)備，與此函數(shù)無關(guān) /pp-weight=forestmin1-weight+forestmin2-weight;

29、forestmin1-parent=pp;forestmin2-parent=pp;forestmin1=pp; / 新 生 成 節(jié) 點(diǎn) 加 入 森 林 for(i=min2;foresti!=NULL;i+)foresti=foresti+1; /min2 后的節(jié)點(diǎn)依次前移 /count-;root=pp;return pp;void HFM:hufcode()/哈夫曼編碼，保存在 hufNode 節(jié)點(diǎn)的數(shù)組當(dāng)中 /inorder(root);for(int i=0;hufNodei.sig!=NULL;i+)signode * gud=hufNodei.sig;while(gud-parent!=NULL) if(gud-parent-left=gud)hufNodei.codehufNodei.size+=0;else if(gud-parent-right=gud)hufNodei.codehufNodei.size+=1;gud=gud-parent;void HFM:savewithhufcode(FILE