基本概念

哈夫曼編碼(Huffman Coding)：又稱霍夫曼編碼、赫夫曼編碼-，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。

源代碼?

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib>using namespace std;typedef struct {char letter, *code;int weight;int parent, lchild, rchild; } HTNode, *HuffmanTree; //char a[28]=" ABCDEFGHIJKLMNOPQRSTUVWXYZ";//存字符 char a[100]; int b[100];//存權值 int n=0;//字符個數 char code[100];//存輸入的二進制代碼。 void CreateHuffmanTree(HuffmanTree &HT, char t[], int w[]) {int m, s1, s2;m=2*n-1; //總共需要2n－1個節點HT=new HTNode[m+1];//開辟空間for(int i=0; i<n; i++)//給葉子結點賦值。{HT[i].letter=t[i];HT[i].weight=w[i];}for(int i=0; i<=m; i++)//初始化所有結點的父節點，左孩子、右孩子都為0.{HT[i].code='\0';HT[i].parent=HT[i].lchild=HT[i].rchild=-1;}for(int i=n; i<m; i++)//處理每個非葉子結點{int min1,min2;min1=min2=9999;s1=s2=-1;for(int k=0; k<=i-1; k++) //找到兩個權值最小的結點作為左右子樹的根節點構造新的二叉樹。{if(HT[k].parent==-1)//只在尚未構造成二叉樹的結點中查找。{if(HT[k].weight<min1){min2=min1;s2=s1;min1=HT[k].weight;s1=k;}else if(HT[k].weight<min2){min2=HT[k].weight;s2=k;}}}HT[s1].parent=i;HT[s2].parent=i;//將他們兩個的父節點設置為 i;HT[i].lchild=s1;HT[i].rchild=s2;//把這兩個分別當作 結點i 的左右孩子。HT[i].weight=HT[s1].weight+HT[s2].weight;//他們兩個的雙親為他們兩個的和。HT[i].letter='#';} } void CreatHuffmanCode(HuffmanTree HT)//編碼。 {FILE *fp;int start, c, f;int i;char *cd=new char [n];cd[n-1]='\0';if((fp=fopen("OutMa.txt","w"))==NULL) //輸出哈夫曼編碼到文件{printf("打開輸出文件失敗。\n");exit(0);}fprintf(fp,"每個字符對應的哈夫曼編碼:\n");cout<<endl<<"每個字符對應的哈夫曼編碼為："<<endl;for(i=0; i<n; i++){start=n-1;c=i;f=HT[i].parent;while(f!=-1){start--;if(HT[f].lchild==c){cd[start]='0';}else{cd[start]='1';}c=f;f=HT[f].parent;}HT[i].code=new char[n-start];strcpy(HT[i].code,&cd[start]);cout<<HT[i].letter<<"： "<<HT[i].code<<endl;fprintf(fp,"%c %s\n",HT[i].letter,HT[i].code);}fprintf(fp,"編碼完成！\n");fclose(fp);delete cd; }void ReadData()//從文件中讀取權值 {FILE *fp1;if(NULL== (fp1=fopen("data.txt","r"))){cout<<"error"<<endl;exit(1);}int i=0;while(fscanf(fp1,"%c%d",&a[i],&b[i])!=EOF)n++,i++;n--; // memset(b,0,sizeof(b)); // char k; // n=27; // while(fscanf(fp1,"%c",&k)!=EOF) // { // for(int i=0;i<27;i++) // { // if(k==a[i]) // b[i]++; // } // }fclose(fp1);cout<<"各個數據及其對應權值為："<<endl;for(int i=0; i<n; i++){cout<<a[i]<<":"<<b[i]<<" ";if(i&&(i+1)%3==0)cout<<endl<<endl;} }void Yima(HuffmanTree HT,char cod[],int b) //譯碼 {FILE *fp;if((fp=fopen("Translate.txt","w"))==NULL){cout<<"打開翻譯文件失敗。"<<endl;exit(0);}char sen[100];char temp[50];char blank[]=" "; //空白字符串int t=0;int s=0;int xx=0;for(int i=0; i<b; i++){temp[t++]=cod[i]; //讀取字符temp[t] = '\0';for(int j=0; j<n; j++) //依次與所有字符編碼開始匹配{if (!strcmp(HT[j].code,temp)) //匹配成功{sen[s]=HT[j].letter; //將字符保存到sen中s++;xx+=t;//用于尋找出錯的位數，如果有某一位沒有匹配則記錄下來。strcpy(temp,blank);t=0;break;}}}if(t==0) //t如果被置空了，表示都匹配出來了，打印譯碼{sen[s]='\0';cout<<"譯碼為:"<<endl<<sen<<endl;fprintf(fp,"%s",sen);fclose(fp);}else //t如果沒有被置空 ， 源碼無法被完全匹配{cout<<"二進制源碼有錯,不存在此編碼，從第"<<xx+1<<"位開始"<<endl;} } void InCode(HuffmanTree HT) {cout<<"譯碼："<<endl;int x,k,symbol;char p;while(1){cout<<"請輸入要譯碼的二進制字符串,輸入'#'結束："<<endl;x=1;//判斷是否有非法字符只能是0 1k=0;//作為循環變量來使code【k】=輸入的字符symbol=1;//判斷是否輸入結束while(symbol)//輸入二進制代碼。{cin>>p;if(p!='1'&&p!='0'&&p!='#') //若存在其它字符，x設為0，表示輸入的不是二進制數。{x=0;}code[k]=p;k++;if(p=='#')symbol=0; //#號結束標志}if(x==1)Yima(HT,code,k-1); //進行譯碼else{cout<<"有非法字符！"<<endl;}cout<<"輸入Y繼續進行編碼，其他任意鍵退出譯碼:"<<endl;cin>>p;if(p=='y'||p=='Y')continue;elsebreak;} } void PrintHF1(HuffmanTree HT,int k,string ss) {ss+=" ";if(HT[k].lchild==-1||HT[k].rchild==-1){cout<<ss;cout<<HT[k].letter<<endl;return;}PrintHF1(HT,HT[k].rchild,ss);cout<<ss;cout<<HT[k].weight<<endl;PrintHF1(HT,HT[k].lchild,ss); } void PrintHF2(HuffmanTree HT,int k) {if(HT){if(HT[k].letter=='#')cout<<HT[k].weight;elsecout<<HT[k].letter;if(HT[k].lchild!=-1||HT[k].rchild!=-1){cout<<"(";PrintHF2(HT,HT[k].lchild);cout<<",";PrintHF2(HT,HT[k].rchild);cout<<")";}} }void menu() {cout<<endl<<endl<<endl<<endl; cout<<" 哈夫曼編碼/譯碼器 "<<endl;cout<<" ************************************************************"<<endl;cout<<" * *"<<endl;cout<<" * 請輸入以下數字選擇功能 *"<<endl;cout<<" * *"<<endl;cout<<" * 1:從文件中讀取數據 *"<<endl;cout<<" * 2:建立哈夫曼樹 *"<<endl;cout<<" * 3:顯示哈夫曼樹 *"<<endl;cout<<" * 4:對哈夫曼樹進行編碼 *"<<endl;cout<<" * 5:對輸入代碼進行譯碼 *"<<endl;cout<<" * 輸入其他字符退出系統 *"<<endl;cout<<" * *"<<endl;cout<<" ************************************************************"<<endl<<" 請輸入數字："; }int main() {char m;HuffmanTree HT;int p=2*n-1;while(m!=5){menu();cin>>m;if(m=='1'){system("cls");ReadData();//從文件中讀取數據。cout<<"讀入數據成功！"<<endl<<"繼續輸入數字選擇功能："<<endl;}else if(m=='2'){system("cls");CreateHuffmanTree(HT, a, b);//建立哈夫曼樹。cout<<"建立哈夫曼樹成功！"<<endl<<"繼續輸入數字選擇功能："<<endl;}else if(m=='4'){system("cls");CreatHuffmanCode(HT);//對哈夫曼樹進行編碼。cout<<"哈夫曼編碼成功！可打開OutMa.txt查看。"<<endl<<"繼續輸入數字選擇功能："<<endl;}else if(m=='5'){system("cls");InCode(HT);//對輸入代碼進行譯碼。cout<<"譯碼結果同時存入Translate.txt文件，可打開查看"<<endl<<"輸入6退出系統。"<<endl;}else if(m=='3'){system("cls");int i=0;while(i>=0)//找到根節點{if(HT[i].parent==-1)break;else{i++;continue;}}cout<<"凹入法顯示哈夫曼樹:"<<endl;string ss="";PrintHF1(HT,i,ss);cout<<"括號法顯示哈夫曼樹："<<endl;PrintHF2(HT,i);cout<<endl<<"繼續輸入數字選擇功能："<<endl;}elsebreak;}return 0; }

測試數據

data.txt

186A64B13C22D32E103F21G15H47I57J1K5L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1

參考文章

https://blog.csdn.net/Wood_Du/article/details/80366094

總結

以上是生活随笔為你收集整理的C++——赫夫曼编码-译码器(Huffman Coding)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。