1、西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告哈夫曼編/譯碼器院系名稱:計(jì)算機(jī)學(xué)院專業(yè)名稱:軟件工程班 級(jí):1103 班王夢(mèng)楠學(xué)生姓名:學(xué)號(hào)（8位）:04113078曾艷指導(dǎo)教師:設(shè)計(jì)起止時(shí)間：2012年12月3日2012年12月14日.設(shè)計(jì)目的加深對(duì)哈夫曼樹(shù)的理解與運(yùn)用，提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn) 題的能力。縮短信息傳輸時(shí)間，降低傳輸在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行二.設(shè)計(jì)內(nèi)容利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，-成本。這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼， 譯碼（復(fù)原）。為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼的編/譯碼器。1. 建立哈夫曼樹(shù)：讀入文件（*.souce），統(tǒng)

2、計(jì)文件中字符出現(xiàn)的頻度，并以這些字符的頻度作為權(quán)值，建立哈夫曼樹(shù)。2. 編碼：利用已建立好的哈夫曼樹(shù)，獲得各個(gè)字符的哈夫曼編碼，并對(duì)正文進(jìn)行編碼，然后輸出編碼結(jié)果，并存入文件（*.code）中。3. 譯碼：利用已建立好的哈夫曼樹(shù)將文件（*.code）中的代碼進(jìn)行譯碼，并輸出譯碼結(jié)果,并存入文件（*.decode）中。三.概要設(shè)計(jì)1. 功能模塊圖;2. 各個(gè)模塊詳細(xì)的功能描述。a. 獲取字符頻度模塊：通過(guò)讀入以存在文件中的字符，進(jìn)行字符頻度的統(tǒng)計(jì)，并將頻度進(jìn) 行屏幕輸出。b. 哈夫曼樹(shù)建立模塊：將已經(jīng)統(tǒng)計(jì)好的字符頻度作為權(quán)值，通過(guò)每次比較求出最小的權(quán)值, 然后進(jìn)行哈夫曼樹(shù)的建立。c. 求哈夫曼編

3、碼模塊：定義向左為0，向右為1,對(duì)每個(gè)字符的編碼進(jìn)行求解。d. 譯碼模塊：讀取保存的哈夫曼編碼文件，將編碼根據(jù)已經(jīng)建立好的哈夫曼樹(shù)進(jìn)行翻譯， 并保存。e. 屏幕輸出模塊：在屏幕上輸出字符頻度統(tǒng)計(jì)結(jié)果，哈夫曼樹(shù)，文件編碼，文件譯碼結(jié)果 等。f. 主函數(shù)模塊：調(diào)用各個(gè)功能函數(shù)。四.詳細(xì)設(shè)計(jì)1.功能函數(shù)的調(diào)用關(guān)系圖2.各功能函數(shù)的數(shù)據(jù)流程圖a. getcharsFreqO 函數(shù):chile=parentc. makeHuffma n()函數(shù)：makeHuffma n()d. dehuffma n()函數(shù)I dehuffma n()13重點(diǎn)設(shè)計(jì)及編碼a. 文件字符頻度的獲取：以字符的 ASCII 編碼

4、為數(shù)組下標(biāo)，以數(shù)組元素值為頻度，每讀入一個(gè)字符進(jìn)行元素值 的加 1，直至字符統(tǒng)計(jì)完畢，具體代碼如下：FREQ *getCharsFreq(const char *fileName, int *Count) FILE *fpin;FREQ *freq = NULL;int chars256 = 0;int count = 0;int i, j;char ch;if(fpin = fopen(fileName, r) = NULL)printf( 打開(kāi)失敗 ,文件不存在！ n); exit(-1);ch = fgetc(fpin);while(!feof(fpin)if (chars(int)ch

5、 = 0) count+;chars(int)ch+;ch = fgetc(fpin);freq = (FREQ *)malloc(sizeof(FREQ)*count);printf(” 字符 t 權(quán)值 rr);for (i = j = 0; i 256; i+)if(charsi)printf(%ct,freqj.chars =i);printf(%dn,freqj+.weight = charsi);printf( 字符種類個(gè)數(shù)： %dn, count); putchar(n);* Count = count;fclose(fpin);return freq;b. 求字符的哈夫曼編碼：定

6、義向左為 0，向右為 1，對(duì)每個(gè)字符的編碼進(jìn)行求解，具體代碼如下： void makehuffmancode(HTNode *h,int count) char * code = NULL;int i,j=0;int child, parent;code=(char *)calloc(sizeof (char),count);for(i = 0; i count; i+)parent = hi.parent;child = i;while (parent != -1)if(hparent.lchild = child) codej+ = 0;elsecodej+ = 1;child = par

7、ent;parent = hchild.parent;codej = 0;strcpy(hi.code , strrev(code,(int)strlen(code); j = 0; free(code);五測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1正常測(cè)試數(shù)據(jù)和運(yùn)行結(jié)果a. 輸入已存在文件 1.souce 運(yùn)行結(jié)果如下：下標(biāo)字符權(quán)值左孩子右孩子父節(jié)點(diǎn)編碼08-1-1490101#2-1-133001012X11-128101100331-1401110140211-128leiioi6=4-1-14200117A21-134611118021-135100009E4143011010I1

8、-1-129leiiio1131-1-12910111112M3-1141060013N2-1-1351000114021-1361601015P1-12-1-1361001117T1-12-1-13710100196-1-147111121b3-1-141600122d2-1-1371010123f11131neon2411-11-1s_1_-1QQgQ28guest-QydqlKwmnvIrtuat-machine: 字符權(quán)值#82%130221二4A2D

9、2E4I131M3N202P1R2T1V2Y1a6b3d2f1 I1k1s1z5字符種類個(gè)數(shù):27Z5-1-146iiei28ff22538(null)292101138(null)302151739(null)312192339(null)32#2242540(null)33ff326142(null.)3444743(null)354a1344(null)364141644(null)37ff4182245(null)3&4ZB2945(null)J9430JI4G(null)40#S32347(null)416122148(null)42#73364S(null)43393449(nul

10、l)440S353650(null)4S337sa50(null)46#9392751(null)47#11402051(null)4813414252(null)49ff1604352(null)5016444553(null)51#26464753(null)52ff294S4954(null)53#36so5154(null)54ff右55253-1(null)譴輸入妾保存人的文件名：2,codeb.輸入保存編碼的文件名2.code ，結(jié)果如下：hi輔入S保存A的文客：2,CMlela白日11111日11111日10日日11091111101日1094日1石111&1日611日日119&

11、11右61日111091日1右60991101日日10091日1119日日日11&日日1111c.輸入編碼文件名進(jìn)行譯碼，并將譯碼結(jié)果保存入3.decode 運(yùn)行結(jié)果如下：請(qǐng)輸入需要解碼的文怕二名：2* code請(qǐng)輸入保存解碼的文怕二名：3* decode解碼后的內(nèi)容：MAJOR=2 MINOR=eDEVNAHE=fdO DEVTY PE=dislddaaaabbbZ2ZZ22.異常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果a.輸入不存在需編碼的文件名（4.souce ）時(shí)，運(yùn)行結(jié)果如下:4.souceb.輸入不存在的編碼文件名（5.code）時(shí)，運(yùn)行結(jié)果如下:請(qǐng)輸入需要解碼的文件名: 打開(kāi)失敗，文件不存在！六.調(diào)試情況，設(shè)計(jì)技巧及體會(huì)1 .改進(jìn)方案程序只是對(duì)文件進(jìn)行了哈夫曼編/譯碼，并未實(shí)現(xiàn)將文件進(jìn)行壓縮與解壓縮