哈夫曼編碼譯碼系統(tǒng)實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告項(xiàng)目名稱(chēng)：哈弗曼編/譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)姓名：鉏飛祥學(xué)號(hào)：E專(zhuān)業(yè)：軟件工程完成日期2016/7/4計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1 .需求分析1.1問(wèn)題描述 問(wèn)題描述：利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（解碼）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設(shè)計(jì)一個(gè)哈夫曼編譯碼系統(tǒng)。1.2基本要求 (1)輸入的形式和輸入值的范圍； (2)輸出的形式； (3)程序所能達(dá)到的功能。1.基本要求（1）初始化

2、（Initialzation）。從數(shù)據(jù)文件DataFile.data中讀入字符及每個(gè)字符的權(quán)值，建立哈夫曼樹(shù)HuffTree；（2）編碼（EnCoding）。用已建好的哈夫曼樹(shù)，對(duì)文件ToBeTran.data中的文本進(jìn)行編碼形成報(bào)文，將報(bào)文寫(xiě)在文件Code.txt中；（3）譯碼（Decoding）。利用已建好的哈夫曼樹(shù)，對(duì)文件CodeFile.data中的代碼進(jìn)行解碼形成原文，結(jié)果存入文件Textfile.txt中；（4）輸出（Output）。輸出DataFile.data中出現(xiàn)的字符以及各字符出現(xiàn)的頻度（或概率）；輸出ToBeTran.data及其報(bào)文Code.txt；輸出CodeFile

3、.data及其原文Textfile.txt；2. 概要設(shè)計(jì)說(shuō)明本程序中用到的所有抽象數(shù)據(jù)類(lèi)型的定義。主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。(1) 數(shù)據(jù)結(jié)構(gòu)哈夫曼樹(shù)的節(jié)點(diǎn)struct huff int weight; int parent; int l; int r;哈夫曼編碼的存儲(chǔ)struct huff *hufftree;(2) 程序模塊選擇1到i-1中parent為0且權(quán)值最小的兩個(gè)下標(biāo)void Select(struct huff *HT, int n, int &s1, int &s2)構(gòu)建哈夫曼樹(shù)：void huffmancoding(struct huff *ht,in

4、t *w,int n)對(duì)原文進(jìn)行編碼：void code(char *c)根據(jù)報(bào)文找到原文：void decoding(char *zifu)3. 詳細(xì)設(shè)計(jì) 核心技術(shù)分析：1：構(gòu)建哈夫曼樹(shù)及生成哈夫曼編碼：根據(jù)每個(gè)字符權(quán)值不同，根據(jù)最優(yōu)二叉樹(shù)的構(gòu)建方法，遞歸生成哈夫曼樹(shù)，并且用數(shù)組存放哈夫曼樹(shù)。再?gòu)拿恳蝗~子節(jié)點(diǎn)向樹(shù)根遍歷，求得編碼例如：如圖所示的四個(gè)節(jié)點(diǎn)v1，v2，v3，v4，他們的權(quán)值分別為7，11,4,5V2V1 7 11 4 5V3V4 第一步：選擇兩個(gè)權(quán)值最小的節(jié)點(diǎn)作為左右子孩子，建立一個(gè)二叉樹(shù)，雙親權(quán)值為兩個(gè)自孩子之和，如圖 7 11 9VV2V1V3V4重復(fù)第一步： 11 16V2

5、V1V3V427重復(fù)第一步： 16V2V1V3V4則此時(shí)建立的是優(yōu)有二叉樹(shù)，約定定左子樹(shù)邊編碼為1，右子樹(shù)編碼為0，則可以對(duì)次二叉樹(shù)進(jìn)行編碼，如圖： 10V210V110V3V4則各頂點(diǎn)的編碼為：V1 01V2 1V3 001V4 0002：將原文編碼：逐個(gè)從文件讀入字符，根據(jù)已經(jīng)建立好的哈夫曼樹(shù)，找到每一字符對(duì)應(yīng)的編碼3：將報(bào)文譯碼：步驟一：先讀入一個(gè)字符，存入匹配字符串步驟二：根據(jù)匹配串找所有的哈夫曼編碼，如果找到對(duì)應(yīng)的編碼，則輸入該編碼所對(duì)應(yīng)的字符，如果找不到，則讀入兩個(gè)字符存入匹配串，重復(fù)步驟二，找到為止。步驟三：把剩下的字符重復(fù)步驟一二4. 測(cè)試與分析 調(diào)試過(guò)程，不可能錯(cuò)的分配空間的

6、語(yǔ)句卻莫名的讓整個(gè)程序崩潰，關(guān)于編譯原理和內(nèi)存分配的各種問(wèn)題太欠缺。學(xué)了計(jì)算機(jī)組成原理與體系結(jié)構(gòu)也不知道比如在自定義函數(shù)中：Char *c;C=(char *)malloc(4*sizoef(char *);C2=(char *)malloc(4*sizeof(char);這樣竟然會(huì)讓程序這執(zhí)行到這一句時(shí)崩潰，本來(lái)不可能有錯(cuò)誤的。而這句如果寫(xiě)在主函數(shù)中，就不會(huì)有問(wèn)題。分配的空間不大，不可能是內(nèi)存不夠用。解決的方法是分開(kāi)，把C=(char *)malloc(4*sizoef(char *);放在主函數(shù)中，另外一句不變依然在自定義函數(shù)中。malloc和free盡量配對(duì)使用，注意：malloc后通常

7、要對(duì)返回值進(jìn)行判斷，避免發(fā)生不必要的錯(cuò)誤。注意，最好再p 被free掉后，加上p=NULL這句“野指針”不是NULL指針，是指向“垃圾”內(nèi)存（不可用內(nèi)存）的指針。人們一般不會(huì)錯(cuò)用NULL指針，因?yàn)橛胕f語(yǔ)句很容易判斷。但是“野指針”是很危險(xiǎn)的，if無(wú)法判斷一個(gè)指針是正常指針還是“野指針”。有個(gè)良好的編程習(xí)慣是避免“野指針”的唯一方法。指針p被free或者delete之后，沒(méi)有置為NULL，讓人誤以為p是個(gè)合法的指針。別看free和delete的名字（尤其是delete），它們只是把指針?biāo)傅膬?nèi)存給釋放掉，但并沒(méi)有把指針本身干掉。此時(shí)指針指向的就是“垃圾”內(nèi)存。釋放后的指針應(yīng)立即將指針置為NUL

8、L，防止產(chǎn)生“野指針”malloc函數(shù)動(dòng)態(tài)申請(qǐng)的內(nèi)存空間是在堆里(而一般局部變量存于棧里)，并且該段內(nèi)存不會(huì)被初始化，與全局變量不一樣，如果不采用手動(dòng)free()加以釋放，則該段內(nèi)存一直存在，直到程序退出才被系統(tǒng)，所以為了合理使用內(nèi)存，在不適用該段內(nèi)存時(shí)，應(yīng)該調(diào)用free()。另外，如果在一個(gè)函數(shù)里面使用過(guò)malloc，最好要配對(duì)使用free，否則容易造成內(nèi)存泄露（沒(méi)有將內(nèi)存還給自由存儲(chǔ)區(qū)）。但是，往往會(huì)在free的時(shí)候發(fā)生段錯(cuò)誤.正確的做法是這樣：/在分配之前加一句判斷指針是否為空，防止產(chǎn)生內(nèi)存泄露程序運(yùn)行結(jié)果：完美解決所提出的問(wèn)題。5. 附錄 #include#include#includ

9、estruct huff int weight; int parent; int l; int r;int mm;/*記錄哈夫曼字碼的個(gè)數(shù)*/struct huff *hufftree;char *huffmancode;void Select(struct huff *HT, int n, int &s1, int &s2)/選擇函數(shù)，選出parent為零，且權(quán)值最小的兩個(gè)節(jié)點(diǎn)int min1=100;int min2=100;int i;for(i=1;iHTi.weight)&(HTi.parent=0) min1=HTi.weight; for(i=1;i=n;i+) if(min1=

10、HTi.weight)&(HTi.parent=0) s1=i; break; for(i=1;iHTi.weight)&(HTi.parent=0)&(i!=s1) min2=HTi.weight; for(i=1;i=n;i+) if(min2=HTi.weight)&(HTi.parent=0)&(i!=s1) s2=i; break; int pipei(char *c)/*在huffmancode尋找匹配的編碼*/ int i; for(i=1;imm;i+) if(strcmp(c,huffmancodei)=0) return i; break; return 0;void de

11、coding(char *zifu)/*對(duì)哈夫曼編碼進(jìn)行譯碼*/ FILE *fp,*fp1; int i,j,p,ii; int n; char c11; for(i=0;i10;i+) ci=0; printf(codefile.txt報(bào)文為：n); if(fp=fopen(codefile.txt,r)=NULL) printf(errorn); char a100; for(i=1;i+) fscanf(fp,%c,&ai); if(ai=#) break; printf(%c,ai); printf(n); fclose(fp); if(fp1=fopen(testfile.txt,

12、w)=NULL) printf(errorn); i=1; j=1; int m=1; printf(對(duì)應(yīng)原文為n); while(true) if(am=#) break; for(j=0;ji;j+) cj=am+j; n=pipei(c); if(n!=0) fprintf(fp1,%c,zifun); printf(%c,zifun); m=m+i; i=1; else i+; for(ii=0;ii10;ii+) cii=0; printf(n); fclose(fp1);int main() system(color e0); /可以寫(xiě)成 red 調(diào)出顏色組 system(titl

13、e huffman系統(tǒng)); /設(shè)置cmd窗口標(biāo)題 system(date /T); system(TIME /T); void huffmancoding(struct huff *ht,int *w,int n); void code(char *c); int i; FILE *fp,*fp1,*fp2; if(fp=fopen(DataFile.txt,r)=NULL) printf(errorn); int w28; char c28; printf(從文件DataFile.txt讀入字符和權(quán)值分別為：n); for(i=1;i+) fscanf(fp,%c,&ci); if(ci=#

14、) break; fscanf(fp,%d,&wi); printf(%c: ,ci); printf(%dn,wi); fclose(fp); int m=i-1; mm=i; huffmancode=(char *)malloc(i*sizeof(char *); huffmancoding(hufftree,w,m); printf(各字符的編碼為n); for(i=1;i=m;i+) printf(%c: ,ci); printf(%sn,huffmancodei); code(c); decoding(c); return 0;void code(char *c)/*根據(jù)原文進(jìn)行編碼

15、*/ FILE *fp,*fp1; int i,j; char a100; printf(tobetran.txt原文為：n); if(fp=fopen(tobetran.txt,r)=NULL) printf(errorn); for(i=1;i+) fscanf(fp,%c,&ai); if(ai=#) printf(n); break; printf(%c ,ai); fclose(fp); if(fp1=fopen(code.txt,w)=NULL) printf(errorn); printf(對(duì)應(yīng)報(bào)文為：n); for(i=1;i+) if(ai=#) break; for(j=1

16、;j=26;j+) if(ai=cj) fprintf(fp1,%s,huffmancodej); printf(%s,huffmancodej); break; printf(n); fclose(fp1);void huffmancoding(struct huff *ht,int *w,int n)/*構(gòu)建哈夫曼樹(shù)和哈夫曼編碼*/ if(n=1) return; int m,i; m=2*n-1; ht=(struct huff *)malloc(m+1)*sizeof(struct huff); struct huff *p; for(p=ht,i=0;iweight=*w; p-parent=0; p-l=0; p-r=0; for(;il=0; p-weight=0; p-parent=0; p-r=0; for(i=1;i=4;i+) for(i=n+1;i=m;i+) int s1,s2; Select(ht,i-1,s1,s2); hts1.parent=i; hts2.parent=i; hti.l=s1; hti.r=s2; hti.weight=hts1.weight+hts2.weight; char *cd; cd=(char *)malloc(n*sizeof(char); cdn-1=0; int sta