哈夫曼編碼應用
問題描述
? 給定字串，將每個不同的字符的哈夫曼編碼表示并輸出其哈夫曼編碼，并再將其哈夫曼編碼還原回字串
分析一下
構建哈夫曼樹
? 使用靜態鏈表，先將所有的結點關系全部清零，再進行結點和相應權值的賦值，遍歷后n-1個結點 (新根)，從n個結點中選兩個最小的權值了合成一棵樹，并將新根加入到比較結點中(并將這兩棵樹標記以及結合，不再進行下次的比較)，最后后合成一顆哈夫曼樹
哈夫曼編碼
? 在這里用到了一個大陣列嵌套一個小陣列，大陣列I的功能是存放每一個結點的哈夫曼編碼，小陣列中存放每一個結點的沒有個哈夫曼編碼的反碼
? 從葉子結點分別向根出發即可，若該結點時雙親結點的左孩子，則記0，反之記為1，記錄在一個記錄陣列中直到該結點沒有雙親(根結點)，每遍歷完一個結點后將記錄陣列復制到對應的小陣列中，并及時清空記錄陣列進行下次使用，
? 在輸出方面使用了多重的for回圈，依次遍字串，將字串的每一個字符與結點進行比較，若相等則輸出對應的(該結點)的哈夫曼編碼，最后再用一陣列接收，以便后續的使用
解碼
? 依次遍歷沒有過哈夫曼遍歷，從根結點出發，遇0向左，遇1則右，若到了葉子（無左孩子或無右孩子），則輸出，并將更新結點值
看看代碼吧
必沒問題！！！(有問題就用個dev吧...)
#include<iostream>
#define Max_S 1000000
#define MaxSize 100
using namespace std;
//靜態鏈表
typedef struct TreeNode{
char data;
int weight;
int parent,lchild,rchild;
}HTNode, *HuffmanTree;
//編碼陣列
typedef struct{
int HC[MaxSize];
}info,*Info;//一個大陣列套一個小陣列
//===========================================================
//一些串和二叉樹的演算法
//求串長
int Strstrlen(char a[]){
int i = 1;
for(;a[i] !='\0';){ i++; }
return i;
}
//字串賦值
void StrAssige(char(&S)[MaxSize+1],char a[]){
S[0] = Strstrlen(a);
for(int i = 1;i <= Strstrlen(a);i++){
S[i] = a[i-1];
}
}
//求深度
int qiushendu(HuffmanTree t,int root){
if(root == 0) return 0;
if(t[root].lchild == 0&&t[root].rchild == 0) return 1;
return (max(qiushendu(t,t[root].lchild),qiushendu(t,t[root].rchild)) + 1);
}
//==================================================================
//獲取兩個最小值
int *Select(HuffmanTree HT,int n){
int s1,s2;////最小值與極小值
int mmin = Max_S;//先等于無窮大
int min = Max_S;
for(int i = 1;i <= n;i++){
if(HT[i].parent != 0) continue;//雙親不為零代表已經構成新樹，應去除
else{
if(mmin >= HT[i].weight){//最小的
min = mmin ;
s2 = s1;
mmin = HT[i].weight;
s1 = i;
}else if(min >= HT[i].weight){//次小的
min = HT[i].weight;
s2 = i;
}
}
}
//若最小值相等，則淺(先遍歷的)樹的序號在前
int S1 = qiushendu(HT,s1);
int S2 = qiushendu(HT,s2);
if(S1 >= S2){
int temp;
temp = s1; s1 = s2; s2 = temp;//交換順序
}
//用陣列存放最小值和次小值
int a[3] = {0,s1,s2};
return a;
}
//===========================================================================
//構建哈夫曼樹
void CreatHuffmanTree(HuffmanTree &HT,char *huf,int *wei,int n){
int s1,s2;//最小值與極小值
if(n <= 1){
cout << "抱歉，您輸入的結點數不符合邏輯";
return;
}
int m = 2*n-1;//總結點樹
HT = new HTNode[m+1];//放棄下標為零的陣列
//先遍歷前n個數,初始化
for(int i = 1;i <= m;i++){//全部初始化為零
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
//賦結點、權值
for(int i;i <= n;i++){
HT[i].data = https://www.cnblogs.com/wht-de-bk/p/huf[i];//結點
HT[i].weight = wei[(int)huf[i]];//權值
}
//遍歷后n+1個，新根
for(int i = n+1;i <= m;i++){
//找出最小額兩個結點
int *a;//獲取s1和s2
a = Select(HT,i-1);//在n個數中找
s1 = a[1]; s2 = a[2];
//更新各個數值
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
//=================================================
//哈夫曼樹編碼化，并輸出
void HuffmanCode(HuffmanTree HT,info* I, int n){
int lchild,rchilg,parent,copyparent;//左孩子值，有孩子子，雙親值，類雙親值(永遠是雙親值值的孩子，但不知是左孩子右)
int jilv[100];//記錄陣列每個結點的編碼(0/1)，算深度即可無需大開
for(int i = 1;i <= n;i++){//依次遍歷葉子結點
int n = 0;//記錄數
//初始化各個雙親值
copyparent = i;
parent = HT[i].parent;
while(parent != 0&©parent != 0){//兩個雙親都不為零
if(HT[parent].lchild == copyparent){//結點的雙親的左孩子與他的序號相等，記為零
jilv[++n] = 0;
}else{
jilv[++n] = 1;
}
copyparent = parent;//更新類雙親
parent = HT[parent].parent;//更新雙親
}
I[i].HC[0] = jilv[0] = n;//第一個字符的總編碼數
for(int m = 1;m <= jilv[0];m++)//將第一個字符的所有編碼復制到第一個存在陣列中去
I[i].HC[m] = jilv[m];
//輸出
cout << HT[i].data <<":";
for(int m = jilv[0];m >=1;m--){//反向輸出
cout << I[i].HC[m];
jilv[m] = 0;//記錄陣列清空
}
cout << endl;
jilv[0] = 0;//記錄陣列清零
}
}
//完整輸出哈夫曼編碼
int *printHuf(char *h,char *huf,info* I){
static int hufman[MaxSize+1];
int mum = 0;
for(int i = 1;i <= h[0];i++){//遍歷原陣列
for(int j = 1;j <= huf[0];j++){//遍歷結點
if(h[i] == huf[j]){//如果相等
for(int m = I[j].HC[0];m >=1;m--){//反向輸出
cout << I[j].HC[m];
hufman[++mum] = I[j].HC[m];
}
}
}
}
hufman[0] = mum;
return hufman;
}
//==================================================================================
//哈夫曼解碼，并輸出
void HuffmanDeCode(int * HufMan,HuffmanTree HT,int n){
HuffmanTree p = HT;
int lchild,rchid,r,m = 2*n-1;
for(int i = 1;i <= HufMan[0];i++){//遍歷每一個哈夫曼編碼
//與0向左，由1向右
if(HufMan[i] == 0){
m = p[m].lchild;
}else{
m = p[m].rchild;
}
//若無孩子則直接輸出(沒有度為一的數)，并更新根結點和m的值
if(p[m].lchild == 0||p[m].rchild == 0){
cout << p[m].data;
p = HT;
m = 2*n- 1;
}
}
}
int main(){
int wei[1000] = {0};//權值陣列
char huf[MaxSize+1];//哈夫曼結點陣列
char a[MaxSize+1];//賦值串
char h[MaxSize+1];//要編譯的字串
cout << "請輸入要編碼的字符:";
gets(a);
StrAssige(h,a);
//賦結點、權值
for(int i = 1,n = 0;i <=h[0];i++){
wei[(int)h[i]]++;//權值++
if(wei[(int)h[i]] == 1){//第一次遇到的不同得字符
huf[++n] = h[i];//結點確定
}
huf[0] = n;//總結點數
}
//哈夫曼樹
HuffmanTree HT;
//創建哈夫曼樹
CreatHuffmanTree(HT,huf,wei,huf[0]);
//======================================================================================
//將字串哈夫曼編碼化,并輸出每個結點的哈夫曼編碼
info *I = new info[huf[0]];//就是一個大陣列，大陣列存放每一個字符的哈夫曼編碼，小陣列存放每一位的
HuffmanCode(HT,I,huf[0]);
//輸出完整的哈夫曼編碼 ,并捕獲
int* HufMan;
cout << "獲得的哈夫曼編碼為：";
HufMan = printHuf(h,huf,I);
cout << endl;
//==================================================================================
//解碼哈夫曼編碼
cout << "該哈夫曼編碼的解碼為：";
HuffmanDeCode(HufMan,HT,huf[0]);
cout <<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/537978.html
標籤：C++