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

安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告項(xiàng)目名稱：哈弗曼編/譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)姓名：鉏飛祥學(xué)號(hào)：E21414018專業(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）初始化（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.data及其原文Textfile.txt；2.概要設(shè)計(jì)說(shuō)明本程序中用到的所有抽象數(shù)據(jù)類型的定義。主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。

數(shù)據(jù)結(jié)構(gòu)

哈夫曼樹(shù)的節(jié)點(diǎn)structhuff應(yīng)的字符，如果找不到，則讀入兩個(gè)字符存入匹配串，重復(fù)步驟二，找到為止。步驟三：把剩下的字符重復(fù)步驟一二4.測(cè)試與分析調(diào)試過(guò)程，不可能錯(cuò)的分配空間的語(yǔ)句卻莫名的讓整個(gè)程序崩潰，關(guān)于編譯原理和內(nèi)存分配的各種問(wèn)題太欠缺。學(xué)了計(jì)算機(jī)組成原理與體系結(jié)構(gòu)也不知道比如在自定義函數(shù)中：Char**c;C=(char**)malloc(4*sizoef(char*));C[2]=(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后通常要對(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)立即將指針置為NULL，防止產(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<stdio.h>#include<stdlib.h>#include<string.h>structhuff{intweight;intparent;intl;intr;};intmm;/*記錄哈夫曼字碼的個(gè)數(shù)*/structhuff*hufftree;char**huffmancode;voidSelect(structhuff*HT,intn,int&s1,int&s2)//選擇函數(shù)，選出parent為零，且權(quán)值最小的兩個(gè)節(jié)點(diǎn){ intmin1=100; intmin2=100; inti; for(i=1;i<=n;i++)if((min1>HT[i].weight)&&(HT[i].parent==0))min1=HT[i].weight;for(i=1;i<=n;i++)if((min1==HT[i].weight)&&(HT[i].parent==0)){s1=i;break;}for(i=1;i<=n;i++)if((min2>HT[i].weight)&&(HT[i].parent==0)&&(i!=s1))min2=HT[i].weight;for(i=1;i<=n;i++)if((min2==HT[i].weight)&&(HT[i].parent==0)&&(i!=s1)){s2=i;break;}}intpipei(char*c)/*在huffmancode尋找匹配的編碼*/{inti;for(i=1;i<mm;i++){if(strcmp(c,huffmancode[i])==0){returni;break;}}return0;}voiddecoding(char*zifu)/*對(duì)哈夫曼編碼進(jìn)行譯碼*/{FILE*fp,*fp1;inti,j,p,ii;intn;charc[11];for(i=0;i<10;i++)c[i]='\0';printf("codefile.txt報(bào)文為：\n");if((fp=fopen("codefile.txt","r"))==NULL){printf("error\n");}chara[100];for(i=1;;i++){fscanf(fp,"%c",&a[i]);if(a[i]=='#')break;printf("%c",a[i]);}printf("\n");fclose(fp);if((fp1=fopen("testfile.txt","w"))==NULL){printf("error\n");}i=1;j=1;intm=1;printf("對(duì)應(yīng)原文為\n");while(true){if(a[m]=='#')break;for(j=0;j<i;j++){c[j]=a[m+j];}n=pipei(c);if(n!=0){fprintf(fp1,"%c",zifu[n]);printf("%c",zifu[n]);m=m+i;i=1;}elsei++;for(ii=0;ii<10;ii++)c[ii]='\0';}printf("\n");fclose(fp1);}intmain(){system("colore0");//可以寫(xiě)成red調(diào)出顏色組system("titlehuffman系統(tǒng)");//設(shè)置cmd窗口標(biāo)題system("date/T");system("TIME/T");voidhuffmancoding(structhuff*ht,int*w,intn);voidcode(char*c);inti;FILE*fp,*fp1,*fp2;if((fp=fopen("DataFile.txt","r"))==NULL){printf("error\n");}intw[28];charc[28];printf("從文件DataFile.txt讀入字符和權(quán)值分別為：\n");for(i=1;;i++){fscanf(fp,"%c",&c[i]);if(c[i]=='#')break;fscanf(fp,"%d",&w[i]);printf("%c:",c[i]);printf("%d\n",w[i]);}fclose(fp);intm=i-1;mm=i;huffmancode=(char**)malloc(i*sizeof(char*));huffmancoding(hufftree,w,m);printf("各字符的編碼為\n");for(i=1;i<=m;i++){printf("%c:",c[i]);printf("%s\n",huffmancode[i]);}code(c);decoding(c);return0;}voidcode(char*c)/*根據(jù)原文進(jìn)行編碼*/{FILE*fp,*fp1;inti,j;chara[100];printf("tobetran.txt原文為：\n");if((fp=fopen("tobetran.txt","r"))==NULL){printf("error\n");}for(i=1;;i++){fscanf(fp,"%c",&a[i]);if(a[i]=='#'){printf("\n");break;}printf("%c",a[i]);}fclose(fp);if((fp1=fopen("code.txt","w"))==NULL){printf("error\n");}printf("對(duì)應(yīng)報(bào)文為：\n");for(i=1;;i++){if(a[i]=='#')break;for(j=1;j<=26;j++){if(a[i]==c[j]){fprintf(fp1,"%s",huffmancode[j]);printf("%s",huffmancode[j]);break;}}}printf("\n");fclose(fp1);}voidhuffmancoding(structhuff*ht,int*w,intn)/*構(gòu)建哈夫曼樹(shù)和哈夫曼編碼*/{if(n<=1)return;intm,i;m=2*n-1;ht=(structhuff*)malloc((m+1)*sizeof(structhuff));structhuff*p;for(p=ht,i=0;i<=n;i++,p++,w++){p->weight=*w;p->parent=0;p->l=0;p->r=0;}for(;i<=m;i++,p++){p->l=0;p->weight=0;p->parent=0;p->r=0;}for(i=1;i<=4;i++)for(i=n+1;i<=m;i++){ints1,s2;Select(