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

2、； (3) 程序所能達(dá)到的功能。1.基本要求（1）初始化（Initialzation）。從數(shù)據(jù)文件DataFile.data中讀入字符及每個字符的權(quán)值，建立哈夫曼樹HuffTree；（2）編碼（EnCoding）。用已建好的哈夫曼樹，對文件ToBeTran.data中的文本進(jìn)行編碼形成報文，將報文寫在文件Code.txt中；（3）譯碼（Decoding）。利用已建好的哈夫曼樹，對文件CodeFile.data中的代碼進(jìn)行解碼形成原文，結(jié)果存入文件Textfile.txt中；（4）輸出（Output）。輸出DataFile.data中出現(xiàn)的字符以及各字符出現(xiàn)的頻度（或概率）；輸出ToB

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

4、 &s2)構(gòu)建哈夫曼樹：void huffmancoding(struct huff *ht,int *w,int n)對原文進(jìn)行編碼：void code(char *c)根據(jù)報文找到原文：void decoding(char *zifu)3. 詳細(xì)設(shè)計 核心技術(shù)分析：1：構(gòu)建哈夫曼樹及生成哈夫曼編碼： 根據(jù)每個字符權(quán)值不同，根據(jù)最優(yōu)二叉樹的構(gòu)建方法，遞歸生成哈夫曼樹，并且用數(shù)組存放哈夫曼樹。再從每一葉子節(jié)點(diǎn)向樹根遍歷，求得編碼例如：如圖所示的四個節(jié)點(diǎn)v1，v2，v3，v4，他們的權(quán)值分別為7，11,4,5V2V1 7 11 4 5V3V4 第一步：選擇兩個權(quán)值最小的節(jié)點(diǎn)作為

5、左右子孩子，建立一個二叉樹，雙親權(quán)值為兩個自孩子之和，如圖 7 11 9VV2V1V3V4重復(fù)第一步： 11 16V2V1V3V427重復(fù)第一步： 16V2V1V3V4則此時建立的是優(yōu)有二叉樹，約定定左子樹邊編碼為1，右子樹編碼為0，則可以對次二叉樹進(jìn)行編碼，如圖： 10V210V110V3V4則各頂點(diǎn)的編碼為：V1 01V2 1V3 001V4 0002：將原文編碼：逐個從文件讀入字符，根據(jù)已經(jīng)建立好的哈夫曼樹，找到每一字符對應(yīng)的編碼3：將報文譯碼：步驟一：先讀入一個字符，存入匹配字符串步驟二：根據(jù)匹配串找所有的哈夫曼編碼，如果找到對應(yīng)的編碼，則輸入該編碼所對應(yīng)的字符，如果找不到，則讀入兩個

6、字符存入匹配串，重復(fù)步驟二，找到為止。步驟三：把剩下的字符重復(fù)步驟一二4. 測試與分析 調(diào)試過程，不可能錯的分配空間的語句卻莫名的讓整個程序崩潰，關(guān)于編譯原理和存分配的各種問題太欠缺。學(xué)了計算機(jī)組成原理與體系結(jié)構(gòu)也不知道比如在自定義函數(shù)中：Char *c;C=(char *)malloc(4*sizoef(char *);C2=(char *)malloc(4*sizeof(char);這樣竟然會讓程序這執(zhí)行到這一句時崩潰，本來不可能有錯誤的。而這句如果寫在主函數(shù)中，就不會有問題。分配的空間不大，不可能是存不夠用。解決的方法是分開，把C=(char *)malloc(4*sizoef(char

7、 *);放在主函數(shù)中，另外一句不變依然在自定義函數(shù)中。malloc和free盡量配對使用，注意：malloc后通常要對返回值進(jìn)行判斷，避免發(fā)生不必要的錯誤。注意，最好再p 被free掉后，加上p=NULL這句 “野指針”不是NULL指針，是指向“垃圾”存（不可用存）的指針。人們一般不會錯用NULL指針，因為用if語句很容易判斷。但是“野指針”是很危險的，if無法判斷一個指針是正常指針還是“野指針”。有個良好的編程習(xí)慣是避免“野指針”的唯一方法。指針p被free或者delete之后，沒有置為NULL，讓人誤以為p是個合法的指針。別看free和delete的名字（尤其是delete），它

8、們只是把指針?biāo)傅拇娼o釋放掉，但并沒有把指針本身干掉。此時指針指向的就是“垃圾”存。釋放后的指針應(yīng)立即將指針置為NULL，防止產(chǎn)生“野指針”malloc函數(shù)動態(tài)申請的存空間是在堆里(而一般局部變量存于棧里)，并且該段存不會被初始化，與全局變量不一樣，如果不采用手動free()加以釋放，則該段存一直存在，直到程序退出才被系統(tǒng)，所以為了合理使用存，在不適用該段存時，應(yīng)該調(diào)用free()。另外，如果在一個函數(shù)里面使用過malloc，最好要配對使用free，否則容易造成存泄露（沒有將存還給自由存儲區(qū)）。但是，往往會在free的時候發(fā)生段錯誤. 正確的做法是這樣：/ 在分配之前加一句

9、判斷指針是否為空，防止產(chǎn)生存泄露程序運(yùn)行結(jié)果：完美解決所提出的問題。5. 附錄 #include<stdio.h>#include<stdlib.h>#include<string.h>struct huff int weight; int parent; int l; int r;int mm;/*記錄哈夫曼字碼的個數(shù)*/struct huff *hufftree;char *huffmancode;void Select(struct huff *HT, int n, int &s1, int &s2)/選擇函數(shù)，選出parent為零，且

10、權(quán)值最小的兩個節(jié)點(diǎn)int min1=100;int min2=100;int i;for(i=1;i<=n;i+) if(min1>HTi.weight)&&(HTi.parent=0) min1=HTi.weight; for(i=1;i<=n;i+) if(min1=HTi.weight)&&(HTi.parent=0) s1=i; break; for(i=1;i<=n;i+) if(min2>HTi.weight)&&(HTi.parent=0)&&(i!=s1) min2=HTi.weigh

11、t; 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;i<mm;i+) if(strcmp(c,huffmancodei)=0) return i; break; return 0;void decoding(char *zifu)/*對哈夫曼編碼進(jìn)行譯碼*/ FILE *fp,*fp1; int i,j,p,ii; int n; cha

12、r c11; for(i=0;i<10;i+) ci='0' printf("codefile.txt報文為：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");

13、 fclose(fp); if(fp1=fopen("testfile.txt","w")=NULL) printf("errorn"); i=1; j=1; int m=1; printf("對應(yīng)原文為n"); while(true) if(am='#') break; for(j=0;j<i;j+) cj=am+j; n=pipei(c); if(n!=0) fprintf(fp1,"%c",zifun); printf("%c",zifun); m

14、=m+i; i=1; else i+; for(ii=0;ii<10;ii+) cii='0' printf("n"); fclose(fp1);int main() system("color e0"); /可以寫成 red 調(diào)出顏色組 system("title huffman系統(tǒng)"); /設(shè)置cmd窗口標(biāo)題 system("date /T"); system("TIME /T"); void huffmancoding(struct huff *ht,int *w,i

15、nt 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='#') break; fscanf(fp,"%d&

16、quot;,&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)

17、; decoding(c); return 0;void code(char *c)/*根據(jù)原文進(jìn)行編碼*/ 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"

18、;); break; printf("%c ",ai); fclose(fp); if(fp1=fopen("code.txt","w")=NULL) printf("errorn"); printf("對應(yīng)報文為：n"); for(i=1;i+) if(ai='#') break; for(j=1;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)建哈夫曼樹和哈夫曼編碼*/ 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;i<=n;i+,p+,w+) p->weight=*w; p->