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

安徽大學數(shù)據(jù)結構課程設計報告工程名稱：哈弗曼編/譯碼系統(tǒng)的設計與實現(xiàn)姓名：鉏飛祥學號：E21414018專業(yè)：軟件工程完成日期2023/7/4計算機科學與技術學院

1.需求分析

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ù)類型的定義。主程序的流程以及各程序模塊之間的層次(調用)關系。數(shù)據(jù)結構哈夫曼樹的節(jié)點structhuff{intweight;intparent;intl;intr;};哈夫曼編碼的存儲structhuff*hufftree;程序模塊選擇1到i-1中parent為0且權值最小的兩個下標voidSelect(structhuff*HT,intn,int&s1,int&s2)構建哈夫曼樹：voidhuffmancoding(structhuff*ht,int*w,intn)對原文進行編碼：voidcode(char*c)根據(jù)報文找到原文：voiddecoding(char*zifu)3.詳細設計核心技術分析：1：構建哈夫曼樹及生成哈夫曼編碼：根據(jù)每個字符權值不同，根據(jù)最優(yōu)二叉樹的構建方法，遞歸生成哈夫曼樹，并且用數(shù)組存放哈夫曼樹。再從每一葉子節(jié)點向樹根遍歷，求得編碼例如：如下圖的四個節(jié)點v1，v2，v3，v4，他們的權值分別為7，11,4,5V2VV2V1V3V3V4第一步：選擇兩個權值最小的節(jié)點作為左右子孩子，建立一個二叉樹，雙親權值為兩個自孩子之和，如圖7119VV2VV2V1V3V3V4重復第一步：1116V2V2V1V1V3V3V427重復第一步：16V2V2V1V1V3V3V4那么此時建立的是優(yōu)有二叉樹，約定定左子樹邊編碼為1，右子樹編碼為0，那么可以對次二叉樹進行編碼，如圖：10V2V210V1V110V3V3V4那么各頂點的編碼為：V101V21V3001V40002：將原文編碼：逐個從文件讀入字符，根據(jù)已經(jīng)建立好的哈夫曼樹，找到每一字符對應的編碼3：將報文譯碼：步驟一：先讀入一個字符，存入匹配字符串步驟二：根據(jù)匹配串找所有的哈夫曼編碼，如果找到對應的編碼，那么輸入該編碼所對應的字符，如果找不到，那么讀入兩個字符存入匹配串，重復步驟二，找到為止。步驟三：把剩下的字符重復步驟一二4.測試與分析調試過程，不可能錯的分配空間的語句卻莫名的讓整個程序崩潰，關于編譯原理和內(nèi)存分配的各種問題太欠缺。學了計算機組成原理與體系結構也不知道比方在自定義函數(shù)中：Char**c;C=(char**)malloc(4*sizoef(char*));C[2]=(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無法判斷一個指針是正常指針還是“野指針〞。有個良好的編程習慣是防止“野指針〞的唯一方法。指針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)存時，應該調用free()。另外，如果在一個函數(shù)里面使用過malloc，最好要配對使用free，否那么容易造成內(nèi)存泄露〔沒有將內(nèi)存還給自由存儲區(qū)〕。但是，往往會在free的時候發(fā)生段錯誤.正確的做法是這樣：//

在分配之前加一句判斷指針是否為空，防止產(chǎn)生內(nèi)存泄露程序運行結果：完美解決所提出的問題。5.附錄#include<stdio.h>#include<stdlib.h>#include<string.h>structhuff{intweight;intparent;intl;intr;};intmm;/*記錄哈夫曼字碼的個數(shù)*/structhuff*hufftree;char**huffmancode;voidSelect(structhuff*HT,intn,int&s1,int&s2)//選擇函數(shù)，選出parent為零，且權值最小的兩個節(jié)點{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)/*對哈夫曼編碼進行譯碼*/{FILE*fp,*fp1;inti,j,p,ii;intn;charc[11];for(i=0;i<10;i++)c[i]='\0';printf("codefile.txt報文為：\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("對應原文為\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");//可以寫成red調出顏色組system("titlehuffman系統(tǒng)");//設置cmd窗口標題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讀入字符和權值分別為：\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ù)原文進行編碼*/{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("對應報文為：\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)/*構建哈夫曼樹和哈夫曼編碼*/{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