#include
#include
using?namespace?std;
//哈夫曼樹的存儲(chǔ)表示
typedef?char?ElemType;
typedef?struct
{
????ElemType?data;??????????????//結(jié)點(diǎn)存的數(shù)據(jù)
????int?weight;?????????????????//結(jié)點(diǎn)的權(quán)值
????int?parentlchildrchild;???//結(jié)點(diǎn)的雙親、左孩子、右孩子的下標(biāo)
}?HTNode*HuffmanTree;??????????//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹
void?Select（HuffmanTree?HTint?nint?&s1int?&s2）;
//構(gòu)造哈夫曼樹
/*算法步驟：
1.初始化：首先動(dòng)態(tài)申請(qǐng)2n個(gè)單元，然后循環(huán)2n-1次，從1號(hào)單元開始，依次將1至2n-1所有單元中的雙親、左孩子、右孩子
的下標(biāo)都初始化為0；最后再循環(huán)n次，輸入前n個(gè)單元中葉子節(jié)點(diǎn)的權(quán)值
2.創(chuàng)建樹：循環(huán)n-1次，通過n-1次的選擇、刪除與合并來創(chuàng)建哈夫曼樹。
選擇是從當(dāng)前森林中選擇雙親為0且權(quán)值最小的兩個(gè)樹根結(jié)點(diǎn)s1和s2；
刪除是指將結(jié)點(diǎn)s1和s2的雙親改為非0；合并就是將s1和s2的權(quán)值和作為一個(gè)新結(jié)點(diǎn)的權(quán)值依次存入到數(shù)組的第n+1之后的單元中，
同時(shí)記錄這個(gè)新結(jié)點(diǎn)左孩子的下標(biāo)為s1，右孩子的下標(biāo)為s2*/
void?CreateHuffmanTree（HuffmanTree?&HTint?n）
{
????//構(gòu)造哈夫曼樹HT
????if（n<=1）
????{
????????cout<<“HuffmanTree節(jié)點(diǎn)數(shù)輸入錯(cuò)誤！“<????????return;
????}
????int?m=2*n-1;
????int?s1=1s2=1;
????HT=new?HTNode[m+1];?????????//0號(hào)單元未用，所以需要?jiǎng)討B(tài)分配m+1個(gè)單元，HT[m]表示根結(jié)點(diǎn)
????for（int?i=1;?i<=m;?++i）?????//將1~m號(hào)單元中的雙親、左孩子、右孩子的下標(biāo)都初始化為0
????{
????????HT[i].parent=0;
????????HT[i].lchild=0;
????????HT[i].rchild=0;
????}
????for（int?i=1;?i<=n;?++i）?????//輸入前n個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值（包括空格）
????{

????????cout<<“請(qǐng)輸入第“<????????char?c;//用來保存之前鍵入的回車鍵
????????c=cin.get（）;
????????HT[i].data=cin.get（）;
????????cout<<“請(qǐng)輸入第“<????????cin>>HT[i].weight;
????}
????//--------------------------初始化工作結(jié)束，下面開始創(chuàng)建完整哈夫曼樹
????for（int?i=n+1;?i<=m;?++i）
????{
????????//通過n-1次的選擇、刪除、合并來創(chuàng)建哈夫曼樹
????????Select（HTi-1s1s2）;???????????????????????//在HT[k]（1<=k<=i-1）中選擇兩個(gè)其雙親域?yàn)?且權(quán)值最小的結(jié)點(diǎn)，并返回它們?cè)贖T中的序號(hào)s1和s2
????????HT[s1].parent=i;
????????HT[s2].parent=i;????????????//得到新結(jié)點(diǎn)i，從森林中刪除s1，s2，將s1和s2的雙親域由0改為i
????????HT[i].lchild=s1;
????????HT[i].rchild=s2;????????????//s1，s2分別作為i的左右孩子
????????HT[i].weight=HT[s1].weight+HT[s2].weight;???//i的權(quán)值為左右孩子權(quán)值之和
????}
}
//在HT中選擇兩個(gè)其雙親域?yàn)?且權(quán)值最小的結(jié)點(diǎn)，返回它們?cè)贖T中的序號(hào)s1和s2
void?Select（HuffmanTree?HTint?nint?&s1int?&s2）
{
????int?i=1;//開始初始化wetmin1wetmin2，使用一個(gè)i往后找，HT[i].parent==0的結(jié)點(diǎn)
????int?temp;
????int?wetmin1wetmin2;
????//開始尋找前兩個(gè)HT[i].parent==0的結(jié)點(diǎn)，給wetmin1wetmin2初始化
????while（HT[i].parent!=0）
????????i++;
????wetmin1=HT[i].weight;
????s1=i;
????i++;
????while（HT[i].parent!=0）
????????i++;
????wetmin2=HT[i].weight;
????s2=i;
????i++;//從初始值后面的結(jié)點(diǎn)開始遍歷
????//初始化wetmin1wetmin2，將小的賦值給wetmin1
????if（wetmin1>wetmin2）
????{
????????temp=wetmin2;
????????wetmin2=wetmin1;
????????wetmin1=temp;
????????temp=s2;
????????s2=s1;
????????s1=temp;
????}
????for（i;?i<=n;?i++）
????{
????????if（HT[i].parent==0&&HT[i].weight????????{
????????????wetmin2=wetmin1;
????????????wetmin1=HT[i].weight;
????????????s2=s1;
????????????s1=i;
????????}
????????else?if（HT[i].parent==0&&HT[i].weight????????{
????????????wetmin2=HT[i].weight;
????????????s2=i;
????????}
????}
}
//哈夫曼編碼表的的存儲(chǔ)表示
typedef?char?**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表
//根據(jù)哈夫曼樹求哈夫曼編碼
void?CreateHuffmanCode（HuffmanTree?HTHuffmanCode?&HCint?&n）
{
????//從葉子到根逆向求每個(gè)字符的哈夫曼編碼，存儲(chǔ)

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

????.CA....??????9940??2019-06-01?01:35??C++實(shí)現(xiàn)哈夫曼樹及哈夫曼編碼\HuffmanTree.cpp

????.CA....???1053276??2019-06-01?01:18??C++實(shí)現(xiàn)哈夫曼樹及哈夫曼編碼\HuffmanTree.exe

????.CA....??????9025??2019-06-01?01:18??C++實(shí)現(xiàn)哈夫曼樹及哈夫曼編碼\HuffmanTree.o

????.C.D...?????????0??2019-06-02?09:51??C++實(shí)現(xiàn)哈夫曼樹及哈夫曼編碼

-----------?---------??----------?-----??----

??????????????1072241????????????????????4