哈夫曼樹課程設(shè)計 哈夫曼樹的編碼,譯碼

1、廣東技術(shù)師范學院天河學院算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 題 目： 哈夫曼編/譯碼器 設(shè) 計 者：專業(yè)班級：本網(wǎng)絡(luò)101 學 號： 02指導教師： 所屬系部： 計算機科學與技術(shù)系2012年 06月 3 日目 錄1 問題描述及要求12 需求分析13 算法思想描述14 概要設(shè)計21.創(chuàng)建哈夫曼樹及函數(shù)調(diào)用過程22.輸出哈夫曼數(shù)節(jié)點的權(quán)值的及調(diào)用過程33.進行哈夫曼編碼及調(diào)用過程34.字符串-哈夫曼碼及調(diào)用過程45 詳細設(shè)計41.創(chuàng)建哈夫曼樹42.顯示HT的終結(jié)狀態(tài)53.打印哈夫曼編碼54.打印哈夫曼樹55.字符串-哈夫曼編碼66.源程序清單76 測試數(shù)據(jù)及分析101.創(chuàng)建哈夫曼樹102.顯示HT的終結(jié)狀

2、態(tài)103.打印哈夫曼編碼104.打印哈夫曼樹115.字符串-哈夫曼編碼117課程設(shè)計總結(jié)118 參考資料12哈夫曼編/譯碼器1 問題描述及要求利用哈夫曼編碼進行通信可以大大提高信道利用率,縮短信息傳輸時間,降低傳輸成本。但是,這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼,在接收端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道(即可以雙向傳輸信息的信道),每端都需要一個完成的編譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。設(shè)計要求：1.初始化。從終端讀入字符集大小n,以及n個字符和n個權(quán)值,建立哈夫曼樹。 2.編碼。利用已建好的哈夫曼樹,對正文進行編碼。 3.譯碼。對編碼好的內(nèi)容進行譯碼。 4

3、.打印編碼。 5.打印哈夫曼樹2 需求分析（1）再通信過程中，為了提高信道利用率，縮短信息傳輸時間降，低傳輸成本 ，需要一編譯碼器。 （2）此哈夫曼編/譯碼器應(yīng)具有編和譯的雙向功能,即在發(fā)送端通過編碼系統(tǒng)對傳入的數(shù)據(jù)進行編碼, 在接受端將數(shù)據(jù)譯碼.將具有這兩項功能的編譯碼器用于雙工信道,就可滿足 雙工信道的雙向編譯功能. (3) 輸入某段報文時,系統(tǒng)將自動完成編譯輸出. 3 算法思想描述1：初始化。從中端讀入字符集大小n,以及n個字符和n各權(quán)值 ，建哈夫曼樹，并存于hfmTree中 2：編碼。利用已建好的樹，對文件 ToBeTran中的正文進行編碼， 然后將結(jié)果存入文件CodeFile . 3

4、：譯碼。利用已建好的樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。 4：印代碼文件CodeFile。將文件以緊湊格式顯示在終端上，每行50個代碼 。 同時將此字符形式的編碼文件寫入文件CodePrin中。 5：印哈夫曼樹。將已在內(nèi)存中的樹以直觀的方式（樹或凹入表形式）顯示在終端，同時將此字符形式的哈夫曼樹寫入文件TreePrin中。4 概要設(shè)計本程序主要定義了4個函數(shù): void CreateHT(HuffmanTree &HT,int n)；void preorderHT(HuffmanTree HT,int m)；void GetHhffanCode(Huffm

5、anTree HT,HuffmanCode &HC,int n)； void strHT(HuffmanTree HT,HuffmanCode HC,int n)1.創(chuàng)建哈夫曼樹及函數(shù)調(diào)用過程函數(shù)：void CreateHT(HuffmanTree &HT,int n)功能：構(gòu)造哈夫曼樹for(i=0;in;i+)printf(%c = ,chi);scanf(%d,&HTi.weight);HTi.parent=-1;HTi.lchild=-1;HTi.rchild=-1;for(i=n;i2*n-1;i+)HTi.parent=-1;HTi.lchild=-1;HTi.rchild=-1;

6、for(i=n;i2*n-1;i+)Min1=Min2=Max;Lnode=Rnode=-1;for(k=0;k=i-1;k+)if(HTk.parent=-1)if(HTk.weightMin1)Min2=Min1;Rnode=Lnode;Min1=HTk.weight;Lnode=k;Min2=HTk.weight;Rnode=k;else if(k!=Lnode&HTk.weightMin2)YN2.輸出哈夫曼數(shù)節(jié)點的權(quán)值的及調(diào)用過程函數(shù)：void preorderHT(HuffmanTree HT,int m)功能：顯示HT的終結(jié)狀態(tài)If(HTm.lchild!=-1 |HTm.rch

7、ild!=-1)Yprintf(%d ,HTm.weight);preorderHT(HT,HTm.lchildpreorderHT(HT,HTm.rchild);printf(%d ,HTm.weight);/輸出孩子節(jié)點為-1的節(jié)點的權(quán)值N3.進行哈夫曼編碼及調(diào)用過程函數(shù)：void GetHhffanCode(HuffmanTree HT,HuffmanCode &HC,int n)功能：打印哈夫曼編碼for(i=0;indelete cd4.字符串-哈夫曼碼及調(diào)用過程函數(shù)：void strHT(HuffmanTree HT,HuffmanCode HC,int n)功能：輸入一個字符串，

8、顯示該字符的哈夫曼編碼for(nt=0;strnt!=0;nt+)for(nt=0;strnt!=0;nt+)printf(%c,strnt)printf( - )strnt=0strnt!=0for(i=0;in;i+)if(strnt=chi)Yprintf(%s,HCi)5 詳細設(shè)計 1.創(chuàng)建哈夫曼樹void CreateHT(HuffmanTree &HT,int n)/創(chuàng)建哈夫曼樹int i,k,Lnode,Rnode,Min1,Min2;if(n=1)return;HT=new HNode2*n-1;strread(ch);printf(請輸入字符的權(quán)值n);for(i=0;in;

9、i+)/初始化HTprintf(%c = ,chi);scanf(%d,&HTi.weight);HTi.parent=-1;HTi.lchild=-1;HTi.rchild=-1;for(i=n;i=0)if(HTm.lchild!=-1 | HTm.rchild!=-1)/判斷孩子節(jié)點是否為-1printf(%d ,HTm.weight);preorderHT(HT,HTm.lchild);preorderHT(HT,HTm.rchild);/ifelseprintf(%d ,HTm.weight);/輸出孩子節(jié)點為-1的節(jié)點的權(quán)值/if3.打印哈夫曼編碼void GetHhffanCod

10、e(HuffmanTree HT,HuffmanCode &HC,int n)/進行哈夫曼編碼int i,c,f,start;HC=new char*n;char *cd;cd=new charn;cdn-1=0;/編碼結(jié)束符4.打印哈夫曼樹for(i=n;i2*n-1;i+)/構(gòu)造哈夫曼樹Min1=Min2=Max;Lnode=Rnode=-1;/Lnode和rnode為權(quán)值最小的兩個結(jié)點的位置for(k=0;k=i-1;k+)/在HT中找權(quán)值最小的兩個結(jié)點if(HTk.parent=-1)/只在尚未構(gòu)造二叉樹的結(jié)點中查找if(HTk.weightMin1)Min2=Min1;Rnode=L

11、node;Min1=HTk.weight;Lnode=k;else if(k!=Lnode&HTk.weight哈夫曼編碼void strHT(HuffmanTree HT,HuffmanCode HC,int n)/輸入一個字符串，顯示該字符的哈夫曼編碼char strMax;int nt,i;GetHhffanCode(HT,HC,n);printf(請輸入要轉(zhuǎn)換的字符:nn);getchar();gets(str);system(cls);printf(ntt字符串轉(zhuǎn)換為哈夫曼編碼:nntt);for(nt=0;strnt!=0;nt+)/ 原樣輸出字符串printf(%c,strnt)

12、;printf( - );for(nt=0;strnt!=0;nt+)/遍歷字符串找出對應(yīng)的哈夫曼編碼for(i=0;in;i+)if(strnt=chi)/與之前輸入的字符比較，相等就輸出對應(yīng)的哈夫曼編碼printf(%s,HCi);6.源程序清單#include#include#include# define Max 1000int n;char ch20;typedef structint weight;/結(jié)點的權(quán)值int parent,lchild,rchild;/該結(jié)點的雙親結(jié)點、左孩子結(jié)點、右孩子結(jié)點在數(shù)組中的下標HNode,*HuffmanTree;/動態(tài)分配數(shù)組存儲哈夫曼樹ty

13、pedef char *HuffmanCode;/動態(tài)分配數(shù)組存儲哈夫曼編碼表void main()/主函數(shù)int mt,i,flag=0;HuffmanTree HT;HuffmanCode HC;printf(n);printf(tt*n);printf(tt* 歡迎使用哈夫曼編/譯碼器系統(tǒng) *n);while(1)printf(nnntt1.創(chuàng)建哈夫曼樹ttt4.打印哈夫曼樹);printf(nntt2.顯示HT的終結(jié)狀態(tài)tt5.字符串-哈夫曼編碼);printf(nntt3.打印哈夫曼編碼tt0.退出n);printf(nn請輸入要進行下一步的操作是:);scanf(%d,&mt);i

14、f(mt=0)system(cls); printf(ntt退出系統(tǒng)n); exit(0);if(mt=1) flag=1;if(flag)switch(mt)case 1: system(cls);printf(請輸入要創(chuàng)建哈夫曼樹的節(jié)點個數(shù):);scanf(%d,&n);CreateHT(HT,n);system(cls);printf(tt哈夫曼樹創(chuàng)建成功!n);getchar();break;case 2: system(cls); for(i=0;i2*n-1;i+)printf(第i=%d個節(jié)點的權(quán)值為:%dt,i,HTi.weight);printf(雙親結(jié)點:%dt,HTi.p

15、arent);printf(左孩子節(jié)點:%dt,HTi.lchild);printf(右孩子節(jié)點:%dtn,HTi.rchild);break;case 3: system(cls); GetHhffanCode(HT,HC,n);printf(ntt字符對應(yīng)的哈夫曼編:n);for(i=0;i,chi);printf(%s n,HCi);break;case 4: system(cls);printf(ntt先序遍歷輸出各個節(jié)點的權(quán)值nntt);preorderHT(HT,2*n-2); break;case 5:system(cls);strHT(HT,HC,n); break;case

16、0:system(cls); printf(ntt退出系統(tǒng)ntt); exit(0);default :system(cls); printf(ntt輸入有錯,請從新輸入!n);break;/switch/ifelsesystem(cls);printf(ntt請先輸入 1 創(chuàng)建哈夫曼樹,才能進行下一個操作!nn);/while/main6 測試數(shù)據(jù)及分析1.創(chuàng)建哈夫曼樹2.顯示HT的終結(jié)狀態(tài)3.打印哈夫曼編碼4.打印哈夫曼樹 5.字符串-哈夫曼編碼7課程設(shè)計總結(jié)為期一個星期的課程設(shè)計終于圓滿落下了帷幕，回想這一個星期的前前后后，其過程有甜也有甜。苦的是：當接到通知要課程設(shè)計時，心里是那么的擔心，果然就像擔心的那樣。前兩天，做程序的代碼時一點都不會做，看課本也不懂，課程設(shè)計的進度可以說是原地踏步！這都只能怪自己吧，在上課時總是不聽課，玩手機，老師所講的內(nèi)容也是時聽時不聽，到頭來也就呈現(xiàn)了今天的局面，當時自己是那么擔心完成不了課程設(shè)計報告。說過程甜的是因為后來經(jīng)過老師和小組成員的幫忙，總算是圓滿完成了任務(wù)。通過本次實訓讓我重新學習了算法與數(shù)據(jù)結(jié)構(gòu)這門課程，我也懂得了用代碼來建立哈夫曼樹，編碼和譯碼雙向功能。通過上機實驗，將理論的