基于C++實(shí)現(xiàn)的哈夫曼編碼解碼操作示例
本文實(shí)例講述了基于C++實(shí)現(xiàn)的哈夫曼編碼解碼操作。分享給大家供大家參考,具體如下:
哈夫曼編碼是一個(gè)通過(guò)哈夫曼樹(shù)進(jìn)行的一種編碼,一般情況下,以字符:‘0'與‘1'表示。編碼的實(shí)現(xiàn)過(guò)程很簡(jiǎn)單,只要實(shí)現(xiàn)哈夫曼樹(shù),通過(guò)遍歷哈夫曼樹(shù),這里我們從每一個(gè)葉子結(jié)點(diǎn)開(kāi)始向上遍歷,如果該結(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子,則在字符串后面追加“0”,如果為其右孩子,則在字符串后追加“1”。結(jié)束條件為沒(méi)有父節(jié)點(diǎn)。然后將字符串倒過(guò)來(lái)存入結(jié)點(diǎn)中。
C++實(shí)現(xiàn)代碼如下:
#include<iostream> #include<string> using namespace std; struct Node { double weight; string ch; string code; int lchild, rchild, parent; }; void Select(Node huffTree[], int *a, int *b, int n)//找權(quán)值最小的兩個(gè)a和b { int i; double weight = 0; //找最小的數(shù) for (i = 0; i <n; i++) { if (huffTree[i].parent != -1) //判斷節(jié)點(diǎn)是否已經(jīng)選過(guò) continue; else { if (weight == 0) { weight = huffTree[i].weight; *a = i; } else { if (huffTree[i].weight < weight) { weight = huffTree[i].weight; *a = i; } } } } weight = 0; //找第二小的數(shù) for (i = 0; i < n; i++) { if (huffTree[i].parent != -1 || (i == *a))//排除已選過(guò)的數(shù) continue; else { if (weight == 0) { weight = huffTree[i].weight; *b = i; } else { if (huffTree[i].weight < weight) { weight = huffTree[i].weight; *b = i; } } } } int temp; if (huffTree[*a].lchild < huffTree[*b].lchild) //小的數(shù)放左邊 { temp = *a; *a = *b; *b = temp; } } void Huff_Tree(Node huffTree[], int w[], string ch[], int n) { for (int i = 0; i < 2 * n - 1; i++) //初始過(guò)程 { huffTree[i].parent = -1; huffTree[i].lchild = -1; huffTree[i].rchild = -1; huffTree[i].code = ""; } for (int i = 0; i < n; i++) { huffTree[i].weight = w[i]; huffTree[i].ch = ch[i]; } for (int k = n; k < 2 * n - 1; k++) { int i1 = 0; int i2 = 0; Select(huffTree, &i1, &i2, k); //將i1,i2節(jié)點(diǎn)合成節(jié)點(diǎn)k huffTree[i1].parent = k; huffTree[i2].parent = k; huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight; huffTree[k].lchild = i1; huffTree[k].rchild = i2; } } void Huff_Code(Node huffTree[], int n) { int i, j, k; string s = ""; for (i = 0; i < n; i++) { s = ""; j = i; while (huffTree[j].parent != -1) //從葉子往上找到根節(jié)點(diǎn) { k = huffTree[j].parent; if (j == huffTree[k].lchild) //如果是根的左孩子,則記為0 { s = s + "0"; } else { s = s + "1"; } j = huffTree[j].parent; } cout << "字符 " << huffTree[i].ch << " 的編碼:"; for (int l = s.size() - 1; l >= 0; l--) { cout << s[l]; huffTree[i].code += s[l]; //保存編碼 } cout << endl; } } string Huff_Decode(Node huffTree[], int n,string s) { cout << "解碼后為:"; string temp = "",str="";//保存解碼后的字符串 for (int i = 0; i < s.size(); i++) { temp = temp + s[i]; for (int j = 0; j < n; j++) { if (temp == huffTree[j].code) { str=str+ huffTree[j].ch; temp = ""; break; } else if (i == s.size()-1&&j==n-1&&temp!="")//全部遍歷后沒(méi)有 { str= "解碼錯(cuò)誤!"; } } } return str; } int main() { //編碼過(guò)程 const int n=5; Node huffTree[2 * n]; string str[] = { "A", "B", "C", "D", "E"}; int w[] = { 30, 30, 5, 20, 15 }; Huff_Tree(huffTree, w, str, n); Huff_Code(huffTree, n); //解碼過(guò)程 string s; cout << "輸入編碼:"; cin >> s; cout << Huff_Decode(huffTree, n, s)<< endl;; system("pause"); return 0; }
運(yùn)行結(jié)果如下:
希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。
相關(guān)文章
C語(yǔ)言順序表的基本結(jié)構(gòu)與實(shí)現(xiàn)思路詳解
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性結(jié)構(gòu),一般情況下采用數(shù)組存儲(chǔ)。本文將通過(guò)示例為大家講解一下順序表的基本操作,需要的可以參考一下2023-02-02C++簡(jiǎn)單又輕松建立鏈?zhǔn)蕉鏄?shù)流程
二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指,用鏈表來(lái)表示一棵二叉樹(shù),即用鏈來(lái)指示元素的邏輯關(guān)系。通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成,數(shù)據(jù)域和左右指針域,左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址2022-06-06C語(yǔ)言鏈表實(shí)現(xiàn)簡(jiǎn)易通訊錄
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言鏈表實(shí)現(xiàn)簡(jiǎn)易通訊錄,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-05-05C語(yǔ)言實(shí)現(xiàn)abs和fabs絕對(duì)值
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)abs和fabs絕對(duì)值,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01