C++哈弗曼编码

 // haffman.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include<iostream>
using namespace std; typedef struct hfnode
{
char ch; //存储字符
int weight; //存储权值
int parent; //双亲结点位置
int lchild; //左右孩子结点位置
int rchild;
} hfnode,*hfmtree; typedef struct node
{
char code[];
} node,*hfcode; #define Nsymbols 10 hfnode *Inithfm(hfnode *tree,int n) //千万不能用关键字命名。把这些节点作为带权值的二叉树的根节点,左右子树为空
{
//tree = new hfnode[n]; //多余了,已经在main函数中声明了。
for(int i = ;i < n; i++)
{
tree[i].ch = '';
tree[i].weight = ;
tree[i].lchild = ;
tree[i].rchild = ;
tree[i].parent = ;
}
cout << "请输入想要编码的字符序列,按照先字符后次数的顺序输入" << endl;
for(int i = ;i < ; i++)
{
cin >> tree[i].ch >>tree[i].weight;
}
cout <<endl; for(int i = ;i < ;i++)
cout << tree[i].ch << " "<<tree[i].weight<<" ";
cout << endl;
return tree;
} void select(hfnode *tree,int n,int *p1,int *p2) //选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
{
//找一个作为参考,返回的是结点
int x,y;
for(int i = ;i <= n;i++)
{
if(tree[i].parent==)
{
x = i;
break;//找到一个参考点即可
}
} for(int i = ;i <= n;i++) //找出最小的结点
{
if((tree[i].parent==)&&(tree[i].weight!=))
{
if(tree[i].weight < tree[x].weight)
x = i;
}
} for(int j = ;j <= n;j++)
{
if((tree[j].parent==)&&(j!=x))
{
y = j;
break;//找到一个参考点即可
}
}
for(int j = ;j <= n;j++) //找出次小的结点
{
if((tree[j].parent==)&&(tree[j].weight!=)&&j!=x)
{
if(tree[j].weight < tree[y].weight)
y = j;
}
}
*p1 = x;
*p2 = y;
}
//对哈弗曼树进行编码。 void HfCode(hfnode *tree,int n,node *hfmcode,int m)
{
int c,f;
int start = ; for(int i=;i<;i++)
{
for(c=i,f=tree[c].parent;f!=;c=f,f=tree[c].parent) //追溯法,从叶子节点出发,一路往上追溯。
{
if(tree[f].lchild==c)
hfmcode[i].code[start++] = '';
else
hfmcode[i].code[start++] = '';
}
start = ;
}
} void Print(node *hfmcode,int m)
{
for(int i = ;i < m;i++)
{
for(int j = ;j < m;j++)
cout <<hfmcode[i].code[j];
cout << endl;
}
cout << endl;
} int main()
{
int p1=,p2=; //为了接收最小和次小的两个节点
hfnode tree[Nsymbols]; //当我们不是用指针,这种情况下,已经全部赋值了。不用再一次赋值了。
Inithfm(tree,Nsymbols); //初始化结构体数组。 //建立哈弗曼树 for(int m = ;m < *-;m++) //二叉树性质
{
select(tree,m-,&p1,&p2);
tree[p1].parent = m;
tree[p2].parent = m;
tree[m].lchild = p1;
tree[m].rchild = p2;
tree[m].weight = tree[p1].weight + tree[p2].weight;
tree[m].parent =; //其实这句也可以不用,因为初始化时已经初始化为0了。
} node hfmcode[];
// 初始化,不然打印的时候会出现未知错。
for(int i = ;i < ;i++)
{
for(int j = ;j < ;j++)
hfmcode[i].code[j]='\0';
} HfCode(tree,Nsymbols,hfmcode,); //编码函数
Print(hfmcode,); //打印函数
return ;
}

实验名称:哈弗曼编码

实验目的:了解前缀编码的概念,理解数据压缩的基本方法;

掌握Huffman编码的设计思想并能熟练应用。

实验要求:对有字符集{A,B,C,D},各字符在电文中出现的次数集为{1,3,4,7};

要求编程实现Huffman树的构造,并在此基础上编程实现Huffman编码。

实验步骤及内容

1、首先建立一个定义哈弗曼树的结构体Node,及结构体指针LinkList,该结构体包含一个存储字符的ch,存储权值的weight,存储双亲结点的parent,存储左右孩子的lchild与rchild。代码如下:

typedef struct hfnode

{

char ch;      //存储字符

int weight;   //存储权值

int parent;   //双亲结点位置

int lchild;   //左右孩子结点位置

int rchild;

} hfnode,*hfmtree;

2、定义一个存储编码的结构体,主要是为了方便打印,代码如下:

typedef struct node

{

char code[10];

} node,*hfcode;

3、初始化函数,因为默认值是一个不确定的值,必须进行初始化才行。

hfnode *Inithfm(hfnode *tree,int n)  //千万不能用关键字命名。把这些节点作为带权值的二叉树的根节点,左右子树为空

{

//tree = new hfnode[n]; //多余了,已经在main函数中声明了。

for(int i = 0;i < n; i++)

{

tree[i].ch = '0';

tree[i].weight = 0;

tree[i].lchild = 0;

tree[i].rchild = 0;

tree[i].parent = 0;

}

cout << "请输入想要编码的字符序列,按照先字符后次数的顺序输入" << endl;

for(int i = 0;i < 4; i++)

{

cin >> tree[i].ch >>tree[i].weight;

}

cout <<endl;

for(int i = 0;i < 4;i++)

cout << tree[i].ch << " "<<tree[i].weight<<" ";

cout << endl;

return tree;

}

4、选择两棵根结点权值最小的树作为左右子树。

void select(hfnode *tree,int n,int *p1,int *p2) //选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

{

//找一个作为参考,返回的是结点

int x,y;

for(int i = 0;i <= n;i++)

{

if(tree[i].parent==0)

{

x = i;

break;//找到一个参考点即可

}

}

for(int i = 0;i <= n;i++)  //找出最小的结点

{

if((tree[i].parent==0)&&(tree[i].weight!=0))

{

if(tree[i].weight < tree[x].weight)

x = i;

}

}

for(int j = 0;j <= n;j++)

{

if((tree[j].parent==0)&&(j!=x))

{

y = j;

break;//找到一个参考点即可

}

}

for(int j = 0;j <= n;j++)   //找出次小的结点

{

if((tree[j].parent==0)&&(tree[j].weight!=0)&&j!=x)

{

if(tree[j].weight < tree[y].weight)

y = j;

}

}

*p1 = x;

*p2 = y;

}

5、构造哈弗曼树

//建立哈弗曼树

for(int m = 4;m < 2*4-1;m++) //二叉树性质

{

select(tree,m-1,&p1,&p2);

tree[p1].parent = m;

tree[p2].parent = m;

tree[m].lchild = p1;

tree[m].rchild = p2;

tree[m].weight = tree[p1].weight + tree[p2].weight;

tree[m].parent =0; //其实这句也可以不用,因为初始化时已经初始化为了。

}

6、对哈弗曼树进行编码。编码函数如下:

//对哈弗曼树进行编码。

void HfCode(hfnode *tree,int n,node *hfmcode,int m)

{

int c,f;

int start = 0;

for(int i=0;i<10;i++)

{

for(c=i,f=tree[c].parent;f!=0;c=f,f=tree[c].parent) //追溯法,从叶子节点出发,一路往上追溯。

{

if(tree[f].lchild==c)

hfmcode[i].code[start++] = '0';

else

hfmcode[i].code[start++] = '1';

}

start = 0;

}

}

7、打印编码

void Print(node *hfmcode,int m)

{

for(int i = 0;i < m;i++)

{

for(int j = 0;j < m;j++)

cout <<hfmcode[i].code[j];

cout << endl;

}

cout << endl;

}

另配上一副自己用画图工具画的理论分析图:

结果与C++代码结果一致。

总结:

    此次实验,让我理解了结构体数组的使用以及初始化,内存管理等方面的熟悉,感觉收获挺大的。

上一篇:Servlet中文件上传的几种方式


下一篇:利用python+selenium在pycharm下进行页面登陆的半自动测试