哈夫曼編碼譯碼系統(tǒng)實驗報告,數(shù)據(jù)結構課程設計

安徽大學數(shù)據(jù)結構課程設計報告項目名稱：哈弗曼編/譯碼系統(tǒng)的設計與實現(xiàn)姓名：鉏飛祥學號：E21414018專業(yè)：軟件工程完成日期2016/7/4計算機科學與技術學院11 .需求分析1.1 問題描述 問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（解碼） 。對于雙工信道（即可以雙向傳輸信息的信道） ，每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設計一個哈夫曼編譯碼系統(tǒng)。1.2 基本要求(1) 輸入的形式和輸入值的范圍；(2) 輸出的形式；(3) 程序所能達到的功能。1.基本要求（1）初始化（Initialzation） 。從數(shù)據(jù)文件 DataFile.data 中讀入字符及每個字符的權值，建立哈夫曼樹 HuffTree；（2）編碼（EnCoding） 。用已建好的哈夫曼樹，對文件 ToBeTran.data 中的文本進行編碼形成報文，將報文寫在文件 Code.txt 中；（3）譯碼（Decoding） 。利用已建好的哈夫曼樹，對文件 CodeFile.data中的代碼進行解碼形成原文，結果存入文件 Textfile.txt 中；（4）輸出（Output） 。輸出 DataFile.data 中出現(xiàn)的字符以及各字符出現(xiàn)的頻度（或概率） ；輸出 ToBeTran.data 及其報文 Code.txt；輸出CodeFile.data 及其原文 Textfile.txt；2. 概要設計說明本程序中用到的所有抽象數(shù)據(jù)類型的定義。主程序的流程以及各程序模塊之間的層次(調(diào)用)關系。 (1)數(shù)據(jù)結構 哈夫曼樹的節(jié)點struct huff2int weight;int parent;int l;int r;哈夫曼編碼的存儲struct huff *hufftree;(2)程序模塊選擇 1 到 i-1 中 parent 為 0 且權值最小的兩個下標void Select(struct huff *HT, int n, int C=(char *)malloc(4*sizoef(char *);C2=(char *)malloc(4*sizeof(char);這樣竟然會讓程序這執(zhí)行到這一句時崩潰，本來不可能有錯誤的。而這句如果寫在主函數(shù)中，就不會有問題。分配的空間不大，不可能是內(nèi)存不夠用。解決的方法是分開，把C=(char *)malloc(4*sizoef(char *);放在主函數(shù)中，另外一句不變依然在自定義函數(shù)中。malloc 和 free 盡量配對使用，注意：malloc 后通常要對返回值進行判斷，避免發(fā)生不必要的錯誤。注意，最好再 p 被 free 掉后，加上 p=NULL 這句“野指針”不是 NULL 指針，是指向“垃圾”內(nèi)存（不可用內(nèi)存）的指針。人們一般不會錯用 NULL 指針，因為用 if 語句很容易判斷。但是“野指針”是很危險的，if 無法判斷一個指針是正常指針還是“野指針”。有個良好的編程習慣是避免“野指針”的唯一方法。6指針 p 被 free 或者 delete 之后，沒有置為 NULL，讓人誤以為 p 是個合法的指針。別看 free 和 delete 的名字（尤其是 delete），它們只是把指針所指的內(nèi)存給釋放掉，但并沒有把指針本身干掉。此時指針指向的就是“垃圾”內(nèi)存。釋放后的指針應立即將指針置為 NULL，防止產(chǎn)生“野指針”malloc 函數(shù)動態(tài)申請的內(nèi)存空間是在堆里(而一般局部變量存于棧里)，并且該段內(nèi)存不會被初始化，與全局變量不一樣，如果不采用手動 free()加以釋放，則該段內(nèi)存一直存在，直到程序退出才被系統(tǒng)，所以為了合理使用內(nèi)存，在不適用該段內(nèi)存時，應該調(diào)用 free()。另外，如果在一個函數(shù)里面使用過malloc，最好要配對使用 free，否則容易造成內(nèi)存泄露（沒有將內(nèi)存還給自由存儲區(qū)）。但是，往往會在 free 的時候發(fā)生段錯誤.正確的做法是這樣：/ 在分配之前加一句判斷指針是否為空，防止產(chǎn)生內(nèi)存泄露程序運行結果：7完美解決所提出的問題。5. 附錄#include#include#includestruct huffint weight;int parent;int l;int r;int mm;/*記錄哈夫曼字碼的個數(shù)*/struct huff *hufftree;char *huffmancode;void Select(struct huff *HT, int n, int int min2=100;8int i;for(i=1;iHTi.weight)for(i=1;iHTi.weight)for(i=1;i=n;i+)if(min2=HTi.weight)break;int pipei(char *c)/*在 huffmancode 尋找匹配的編碼*/int i;for(i=1;imm;i+)if(strcmp(c,huffmancodei)=0)return i;break;9return 0;void decoding(char *zifu)/*對哈夫曼編碼進行譯碼*/FILE *fp,*fp1;int i,j,p,ii;int n;char c11;for(i=0;i10;i+)ci=0;printf(“codefile.txt 報文為：n“);if(fp=fopen(“c