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

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）。從終端讀入字符集大/K，以及n個字符和n個權(quán)值，建立Huffman樹，并將它存入八手巾"66中。編碼（Encoding）。利用已經(jīng)建好的Huffman樹（如果不在內(nèi)存，則應(yīng)從文件hfmTree中讀?。?，對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件hfmTree中讀?。?，對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。解碼（Decoding）。利用已經(jīng)建立好的Huffman樹將文件CodeFile中的代碼進(jìn)行解碼，結(jié)果存入TextFile中。打印代碼文件（Print）。將文CodeFile以緊湊的格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。打印Huffman樹（TreePrinting）。將已經(jīng)在內(nèi)存中的Huffman樹以直觀的形式（樹或者凹入的形式）顯示在終端上，同時將此字符形式的Huffman樹寫入文件TreePrint中。3）測試數(shù)據(jù):用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立Huffman樹，并對以下報文進(jìn)行編碼和譯碼：“THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161完整代碼如下：#include<stdio.h>#include<iostream>#include<string>#defineN100int*w;char*c,stack[N],code[N][N];ints1,s2;typedefstructHuffmanTree{intweight;intparent;intlchild;intrchild;}HuffmanTree,*Huff;voidmenu(void);voidSelect(structHuffmanTreeHT[],inti);

voidHuffmanTree(Huff&HT,int*w,intn);voidvisite(HuffHT,inti,intflag,intrear);voidtranslatef(char*scource,char*save,intn);booluncodef(FILE*fp1,FILE*fp2,HuffHT,intn);intinputHuff();voidscreanio(intn);voidfileio(intn);intinitHuff();voidPrint_tree(intn,HuffHT);voidConvert_tree(HuffHT,unsignedcharT[100][100],int*i,intj);voiddecoding(intn);voidcoding(intn);voidmain(){intn=0;menu();HuffHT;charstate;do{std::cout<<"input:\n";std::cin>>state;fflush(stdin);switch(state){case'I':n=inputHuff();HuffmanTree(HT,w,n);std初始化完畢\n"；break;case'C':coding(n);break;case'D':decoding(n);break;case'P':Print_tree(n,HT);break;case'Q':break;}}while(state!='Q');}voidmenu(){std::cout<<"===========HuffmanCoding===========\n";std::cout<<"input\t\tdo\n";std::cout<<"I\t\tInit_HUffTree\n";huffmantreestd::cout<<"C\t\tCoding\n";ToBeTran.txt文件中的字符進(jìn)行編碼到CodeFile.txt中std::cout<<"D\t\tUnCoding\n";tt[100][100],ints,int//讀取狀態(tài):cout<<"\nHuffmanTree//顯示菜單函數(shù)//tt[100][100],ints,int//讀取狀態(tài):cout<<"\nHuffmanTree//顯示菜單函數(shù)//初始化//對//對//打印哈std::cout<<"P\t\tPrintTree\n";//打印哈夫曼樹std::cout<<"Q\t\tquit\n";std::cout4"請初始化哈夫曼樹再執(zhí)行后面的操作\n";}intinputHuff()//輸入各個字母及其權(quán)值{inti=1,n=0;intww[28];charcc[28];while(1){std::cout<<"inputtheletter(input'#'tostop):";cc[i]=std::cin.get();fflush(stdin);if(cc[i]=='#')break;std::cout<<"inputtheweight:";std::cin>>ww[i];fflush(stdin);n++;i++;}w=(int*)malloc(sizeof(int)*(n+1));c=(char*)malloc(sizeof(char)*(n+1));for(i=0;i<n+1;i++){w[i]=ww[i];c[i]=cc[i];}returnn;}voidHuffmanTree(Huff&HT,int*w,intn)//初始化哈夫曼樹{intm,i;m=n*2-1;HT=(structHuffmanTree*)malloc(sizeof(structHuffmanTree)*(m+1));HT[0].lchild=0;HT[0].parent=0;HT[0].rchild=0;HT[0].weight=0;for(i=1;i<m;i++){HT[i].weight=i<=n?w[i]:0;HT[i].lchild=HT[i].rchild=HT[i].parent=0;}for(i=n+1;i<=m;i++){Select(HT,i);HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;HT[s1].parent=HT[s2].parent=i;}}voidSelect(structHuffmanTreeHT口，inti)〃在HT[1..i-1]中選擇parent為。且weight為最小的兩個結(jié)點{intj;for(j=1;j<i;j++){if(HT[j].parent==0){s1=j;s2=j;gotoflag;}}flag:for(j=s1+1;j<i;j++){if(HT[j].parent==0){if(HT[s1].weight>=HT[j].weight){s2=s1;s1=j;}if(HT[s2].weight>HT[j].weight&&j!=s1)s2=j;if(s1==s2)s2=j;}}}voidPrint_tree(intn,HuffHT)//以凹入法的形式打印樹{unsignedcharT[100][100];inttt[100][100];inti,j,m=0;FILE*fp;Convert_tree(HT,T,tt,0,&m,2*n-1);//將內(nèi)存中的赫夫曼樹轉(zhuǎn)換成凹凸表形式的樹，存于數(shù)組T中if((fp=fopen("treeprint.txt","wb+"))==NULL)printf("Openfiletreeprint.txterror!\n");printf("\n以凹凸表形式打印已建好的赫夫曼樹：\n");for(i=1;i<=2*n-1;i++){for(j=0;T[i][j]!=0;j++){if(T[i][j]==''){printf("");fputc(T[i][j],fp);}else{printf("%d",tt[i][j]);fprintf(fp,"%d\n\n\n",tt[i][j]);}}printf("\n");}fclose(fp);printf("\n此字符形式的哈夫曼樹已寫入文件treeprint.txt中.\n\n");printf("\n文件treeprint.txt的打開方式要為寫字板，若打開方式為記事本，則無法顯示凹凸表的形式\n");}voidConvert_tree(HuffHT,unsignedcharT[100][100],inttt[100][100],ints,int*i,intj)〃將內(nèi)存中的赫夫曼樹轉(zhuǎn)換成凹凸表形式的樹，存于數(shù)組T中{intk,l;l=++(*i);for(k=0;k<s;k++)T[l][k]='';T[l][k]='#';tt[l][k]=HT[j].weight;if(HT[j].lchild)Convert_tree(HT,T,tt,s+1,i,HT[j].lchild);if(HT[j].rchild)Convert_tree(HT,T,tt,s+1,i,HT[j].rchild);T[l][++k]='\0';}voidcoding(intn)//對文件ToBeTran.txt編碼到CodeFile.txt{FILE*fp1;HuffHT;HuffmanTree(HT,w,n);visite(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);}voiddecoding(intn)〃對CodeFile.txt中的01序列進(jìn)行解碼到TextFile.txt{FILE*fp1,*fp2;HuffHT;HuffmanTree(HT,w,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);}voidvisite(HuffHT,inti,intflag,intrear)//通過遞歸調(diào)用visite()函數(shù)，得到各個字母的編碼，存儲于全局變量code□口中{intj=0,k=0;if(flag==0){stack[rear]='0';rear++;}elseif(flag==1){stack[rear]='1';rear++;}if(HT[i].lchild==0){for(j=0;j<rear;j++){code[i][j]=stack[j];}code[i][j]='#';rear--;return;visite(HT,HT[i].lchild,0,rear);visite(HT,HT[i].rchild,1,rear);k=rear;for(j=0;j<k;j++){code[i][j]=stack[j];}code[i][j]='#';rear--;return;}voidtranslatef(char*scource,char*save,intn)//讀取文件中的字母序列，并根據(jù)code口口將其轉(zhuǎn)換成01序列輸出{FILE*fp1,*fp2;charp='';inti=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(c[i]==p){for(j=0;j<N&&code[i][j]!='#';j++){fputc(code[i][j],fp2);putchar(code[i][j]);k++;if(k>=50){k=0;putchar('\n');}}}}p=fgetc(fp1);}fclose(fp1);fclose(fp2);booluncodef(FILE*fp1,FILE*fp2,HuffHT,intn)///r/