哈夫曼編解碼完整c程序代碼

1、1）內(nèi)容： 利用 Huffman 編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)進(jìn)行預(yù)先編碼，在接收端進(jìn)行解碼。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/解碼系統(tǒng)。 2）要求： 一個完整的huffman編解碼系統(tǒng)應(yīng)該具有以下功能： 初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立Huffman 樹，并將它存入hfmTree 中。 編碼（Encoding）。利用已經(jīng)建好的Huffman樹（如果不在內(nèi)存，則應(yīng)從文件hfmTree中讀取），對文件ToBeTran中

2、的正文進(jìn)行編碼，然后將結(jié)果存入文件hfmTree中讀?。?，對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。 解碼（Decoding）。利用已經(jīng)建立好的Huffman樹將文件CodeFile中的代碼進(jìn)行解碼，結(jié)果存入TextFile中。 打印代碼文件（Print）。將文件CodeFile以緊湊的格式顯示在終端上，每行 50 個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。 打印Huffman樹（Tree Printing）。將已經(jīng)在內(nèi)存中的Huffman樹以直觀的形式（樹或者凹入的形式）顯示在終端上，同時將此字符形式的Huffman 樹寫入文件Tre

3、ePrint中。3) 測試數(shù)據(jù): 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立Huffman樹，并對以下報文進(jìn)行編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符 A B C D E F G H I J K L M 頻度 186 64 13 22 32 10321 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 完整代碼如下：#include<stdio.h>#include<iostream>#include<str

4、ing>#define N 100int *w;char *c,stackN,codeNN;int s1,s2;typedef struct HuffmanTreeint weight;int parent;int lchild;int rchild;HuffmanTree,*Huff;void menu(void); void Select(struct HuffmanTree HT,int i); void HuffmanTree(Huff &HT,int *w,int n);void visite(Huff HT,int i,int flag,int rear);void

5、translatef(char *scource,char *save,int n);bool uncodef(FILE *fp1,FILE *fp2,Huff HT,int n);int inputHuff();void screanio(int n);void fileio(int n);int initHuff();void Print_tree(int n,Huff HT);void Convert_tree(Huff HT,unsigned char T100100,int tt100100,int s,int *i,int j);void decoding(int n);void

6、coding(int n);void main()int n=0;menu();Huff HT;char state; dostd:cout<<"input:n"std:cin>>state;fflush(stdin); /讀取狀態(tài)switch(state) case'I':n=inputHuff();HuffmanTree(HT,w,n);std:cout<<"nHuffmanTree 初始化完畢n"break; case'C':coding(n);break; case'D&

7、#39;:decoding(n);break; case'P':Print_tree(n,HT);break; case'Q':break;while(state!='Q');void menu() /顯示菜單函數(shù)std:cout<<"=HuffmanCoding=n" std:cout<<"input tt don"std:cout<<"I ttInit_HUffTreen" /初始化huffmantreestd:cout<<"

8、C ttCodingn" /對ToBeTran.txt文件中的字符進(jìn)行編碼到CodeFile.txt中std:cout<<"D ttUnCodingn" /對CodeFile.txt中的01序列進(jìn)行解碼到TextFile.txtstd:cout<<"P ttPrintTreen" /打印哈夫曼樹std:cout<<"Q ttquitn"std:cout<<"請初始化哈夫曼樹再執(zhí)行后面的操作n"int inputHuff() /輸入各個字母及其權(quán)值int i=

9、1,n=0;int ww28;char cc28;while(1)std:cout<<"input the letter(input '#' to stop):"cci=std:cin.get();fflush(stdin);if(cci='#')break;std:cout<<"input the weight:"std:cin>>wwi;fflush(stdin);n+;i+;w=(int *)malloc(sizeof(int)*(n+1);c=(char *)malloc(siz

10、eof(char)*(n+1);for(i=0;i<n+1;i+)wi=wwi;ci=cci;return n;void HuffmanTree(Huff &HT,int *w,int n) /初始化哈夫曼樹int m,i;m=n*2-1;HT=(struct HuffmanTree *)malloc(sizeof(struct HuffmanTree)*(m+1);HT0.lchild=0;HT0.parent=0;HT0.rchild=0;HT0.weight=0;for(i=1;i<m;i+)HTi.weight=i<=n?wi:0;HTi.lchild=HTi

11、.rchild=HTi.parent=0;for(i=n+1;i<=m;i+) Select(HT,i);HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.parent=HTs2.parent=i;void Select(struct HuffmanTree HT,int i) /在HT1.i-1中選擇parent為0且weight為最小的兩個結(jié)點 int j;for(j=1;j<i;j+)if(HTj.parent =0)s1=j;s2=j;goto flag;flag: for(j=s1+1;

12、j<i;j+)if(HTj.parent=0)if(HTs1.weight >=HTj.weight)s2=s1;s1=j;if(HTs2.weight>HTj.weight&&j!=s1)s2=j;if(s1=s2)s2=j;void Print_tree(int n,Huff HT) /以凹入法的形式打印樹 unsigned char T100100; int tt100100; int i,j,m=0; FILE *fp; Convert_tree(HT,T,tt,0,&m,2*n-1); /將內(nèi)存中的赫夫曼樹轉(zhuǎn)換成凹凸表形式的樹，存于數(shù)組T中

13、if(fp=fopen("treeprint.txt","wb+")=NULL) printf("Open file treeprint.txt error!n"); printf("n以凹凸表形式打印已建好的赫夫曼樹：n"); for(i=1;i<=2*n-1;i+) for (j=0;Tij!=0;j+) if(Tij=' ') printf(" ");fputc(Tij,fp); else printf("%d",ttij);fprintf(fp,

14、"%dnnn",ttij); printf("n"); fclose(fp); printf("n此字符形式的哈夫曼樹已寫入文件treeprint.txt中.nn"); printf("n文件treeprint.txt的打開方式要為寫字板，若打開方式為記事本，則無法顯示凹凸表的形式n"); void Convert_tree(Huff HT,unsigned char T100100,int tt100100,int s,int *i,int j) /將內(nèi)存中的赫夫曼樹轉(zhuǎn)換成凹凸表形式的樹，存于數(shù)組T中 int k

15、,l; l=+(*i); for(k=0;k<s;k+) Tlk=' ' Tlk='#' ttlk=HTj.weight; if(HTj.lchild) Convert_tree(HT,T,tt,s+1,i,HTj.lchild); if(HTj.rchild) Convert_tree(HT,T,tt,s+1,i,HTj.rchild); Tl+k='0' void coding(int n) /對文件ToBeTran.txt編碼到CodeFile.txt FILE *fp1;Huff HT;HuffmanTree(HT,w,n);vis

16、ite(HT,2*n-1,2,0);fflush(stdin);translatef("ToBeTran.txt","CodeFile.txt",n);fp1=fopen("CodeFile.txt","r");printf("n編碼已寫入文件treeprint.txt中.n");fclose(fp1);void decoding(int n) /對CodeFile.txt中的01序列進(jìn)行解碼到TextFile.txtFILE *fp1,*fp2;Huff HT;HuffmanTree(HT,w

17、,n);fp1=fopen("CodeFile.txt","r");fp2=fopen("TextFile.txt","w");while(uncodef(fp1,fp2,HT,2*n-1);printf("n");printf("n解碼已寫入文件TextFile.txt中.n");fclose(fp1);fclose(fp2);void visite(Huff HT,int i,int flag,int rear)/通過遞歸調(diào)用visite()函數(shù)，得到各個字母的編碼，存儲

18、于全局變量code中int j=0,k=0;if(flag=0) stackrear='0'rear+;else if(flag=1)stackrear='1'rear+;if(HTi.lchild=0)for(j=0;j<rear;j+)codeij=stackj;codeij='#'rear-;return;visite(HT,HTi.lchild,0,rear);visite(HT,HTi.rchild,1,rear);k=rear;for(j=0;j<k;j+)codeij=stackj;codeij='#'r

19、ear-;return;void translatef(char *scource,char *save,int n)/讀取文件中的字母序列，并根據(jù)code將其轉(zhuǎn)換成01序列輸出FILE *fp1,*fp2;char p=' 'int i=0,j=0,k=0;fp1=fopen(scource,"r");fp2=fopen(save,"w");p=fgetc(fp1);printf("n得到的編碼為:n");while(p!=EOF)for(i=0;i<=n;i+)if(ci=p)for(j=0;j<N&&