北邮数据结构实验—Huffman编码解码器

4.2心得体会

通过哈弗曼树的程序编写，更加深入了解了树这种数据结构的特点, 据结构的应用。同时，也对哈弗曼编码的优越性能有了根本的解释。

并且熟悉了这种数

附：程序代码

#in clude #in clude using n amespace std;

#define max 1000〃哈夫曼数存储的最大叶子节点数 int judge;//初始化过程中用于判断字符是否出现过 struct HTNode {

char c; int weight;

in t lchild,rchild,pare nt; };

class CHTree {

public:

CHTree(){ht=NULL;}; void In it();

void huffma ncode(); int select(i nt i); void Display(); void can culate(); void en codi ng(); void decodi ng(); private: HTNode* ht; int m;

intn;//叶子结点数 int s1; int s2;

string a;//存储输入的字符串 stri ng code;//存储对字符串的编码

string str[max];〃存储叶子结点的哈夫曼编码 }; void CHTree::l ni t()

int i=1;〃用于记录叶子节点个数

欢迎下载 9

int j=0; int x=O,ru;

cout<<\请输入进行编码的字符串： cin> >a; int l=a .len gth();

ht=(HTNode*)malloc((max)*sizeof(HTNode));〃 分配 MAXSIZE 个叶子结点的存储空间 while(x

judge=1; for(j=0;j

if(ht[j].c==a[x]){〃 如果字符a[x]已经出现过，则记录，权值加 1 ht[j].weight++; judge=0; break;}

}

if(judge){〃若字符没有出现过，字符入列，且权值设为

n=i;〃记录叶子节点数 ht[i] .weight=1; ht[i].c=a[x]; i++; } x++;

} }

int CHTree::select(i nt i)//函数在ht[1]到ht[i]中选择pare nt为0且weight最小的结点，并将结 点序号返回 {

int j=1; int k=1; int s;

while(ht[j].pare nt!=O){

j++; s=j; } k=j+1; while(k<=i) {

while(ht[k].parent!=0) k++; if(k>i)retur n s;

if(ht[j].weight>ht[k].weight){

ht[j].parent=O;〃如果第二次和第二次以后循环中发现有比

ht[j].parent 重新设为 0

j=k;〃始终令“ ht[j] ”为二者中权值小的那一个 s=j;

ht[j]权值还小的，将 1

\

欢迎下载 10

ht[j].pare nt=-1;〃 如果 ht[j]是权值较小的，将 ht[j]的 pare nt 记为-1, } else{

s=j;

ht[j].pare nt=-1;} k++;}

return s; }

void CHTree::huffma ncode() {

int i;

if(n<=1)return; m=2* n-1;

for(i=1;i<=n;i++)〃叶子节点的初始化 { ht[i].pare nt=O; ht[i]」child=0; ht[i] .rchild=0;}

for(;i<=m;i++) //非叶子节点的初始化 {

ht[i] .weight=0; ht[i].pare nt=O; ht[i] .lchild=0; ht[i] .rchild=0;}

for(i=n+1;i<=m;++i)〃 构造哈夫曼树 {

s1= select(i-1);〃函数在ht[1]到ht[i-1]中选择pare nt为0且weight最小的结点， 并将结 点序号返s,并将ht[s1].parent设为-1

s2=select(i-1); ht[s1].pare nt=i; ht[s2].pare nt=i; ht[i] .lchild=s1; ht[i].rchild=s2;

ht[i].weight=ht[s1].weight+ht[s2].weight; }

int c,f;

for(i=1;i<=n;++i) {

for(c=i,f=ht[i].pare nt;f!=O;c=f,f=ht[f].pare nt)〃 逆向求叶子结点的哈夫曼编码

if(ht[f].lchild==c){

str[i].insert(O,\在字符串 str[i]的第 0 位置插入字符 “ 0” else{

str[i].insert(0,\在字符串 str[i]的第 0 位置插入字符“ 1 ” }

void CHTree::Display(){

cout<<\编码如下：\\n\

cout<<\字符\权值\哈夫曼编码\

for(i nt i=1;i<=n ;i++){

欢迎下载 11

cout<

}

void CHTree::ca nculate(){ int m=0;

for(i nt i=1;i<=n ;i++){

m+=(ht[i].weight)*(str[i].length());〃 该字符所占位数为频度和每个字符

huffman码长

度乘积

}

cout<<\内存分析：\\n\原始编码所占内存数为 \

cout<<\编码所占内存数为\}

void CHTree::e ncodi ng(){

for(int i=0;i

for(int j=1;j<=n;j++){〃 循环变量j用于寻找huffman编码中与该字符的相匹配的字符

编码

if(a[i]==ht[j].c)code+=str[j]; } }

cout<<\字符编码为\}

void CHTree::decodi ng(){

int i=0;

int m=code」en gth();

cout<<\对编码译码后所得字符：\while(i

int parent=2*n-1;〃根结点在 HTree中的下表

while(ht[pare nt].rchild!=O||ht[pare nt].lchild!=O)〃 自根结点向叶子节点匹配编码，叶子节点左右孩子均为 0,此时输出字符

{

if(code[i]=='0')

pare nt=ht[pare nt] .l child; else

pare nt=ht[pare nt].rchild; i++; }

cout<

void mai n() {

CHTree h;

h.lnit(); //初始化，统计输入字符的频度，赋值各叶子节点的权重 h.huffmancode();〃 建立

欢迎下载 12