今天晚上花了好几个小时写了这个程序。。。都怪我效率太低。。。
好了废话不多说,下面就给出我的代码。(这个代码参考了 严蔚敏老师 的算法)
其中具体的实现就不多讲,因为我在注释都写了。
#include<iostream>
using namespace std;
struct hTNode{
unsigned int weight;
unsigned int parent,lchild,rchild;
};
typedef hTNode* huffTree;
//定义一个双重指针来存放Huffman编码
typedef char** huffCode;
//树上所有结点的个数
int cnt,i;
/**
* 选择权值最小的两个结点
* tree: 哈弗曼树
* n: 哈弗曼树上结点的个数
* s1,s2: 选出来的结果 ,即在树上的位置
*/
void select(huffTree tree, int n, int &s1, int &s2)
{
int i;
for(i = 2; i <= n; i ++)
{
if(tree[s1].parent != 0)
{
s1 = i;
continue;
}
if(tree[i].parent == 0)
if(tree[i].weight < tree[s1].weight)
s1 = i ;
}
for(i = 1; i <= n; i ++)
{
if(i == s1) continue;
if(s2 == s1 || tree[s2].parent != 0)
{
s2 = i;
continue;
}
if(tree[i].parent == 0)
if(s1 != s2 && tree[i].weight < tree[s2].weight)
s2 = i ;
}
}
/**
* 这个函数是本程序的最主要的函数,用来建立哈弗曼树,同时生成哈弗曼编码。
* n: 输入的数据的个数
* weight: 每个节点的权值
* tree: 哈弗曼树
* code: 哈弗曼编码
*/
void HuffEncoding(int n, int* weight, huffTree &tree, huffCode &codes)
{
int s1=1, s2=2;
huffTree p;
//如果输入的数据个数小于2,那么直接返回
if(n < 2) return;
cnt = 2*n - 1;
//申请这棵哈弗曼树的内存空间
tree = (huffTree)malloc((cnt+1)*sizeof(hTNode));
//把每一个录入的数据建成结点(或者说小树)
for(p = tree+1,i = 1; i <= n; ++i, ++p, ++weight)
{
p->weight = *weight;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
//初始化哈弗曼树上的每一个结点,先都设成0
for(;i <= cnt; ++i, ++p)
{
p->weight = 0;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
//开始建立哈弗曼树
for(i = n + 1; i <= cnt; ++ i)
{
select(tree, i-1, s1, s2);
tree[s1].parent = i;
tree[s2].parent = i;
tree[i].lchild = s1;
tree[i].rchild = s2;
tree[i].weight = tree[s1].weight + tree[s2].weight;
}
//开始求各个叶子结点的Huffman编码
{
char* cd;
int start,c,f=0;
codes = (huffCode)malloc((n+1)*sizeof(char*));
cd = (char*)malloc((n+1)*sizeof(char));
cd[n-1]='\0';
for(i = 1; i <= n; ++i)
{
start = n - 1;
for(c = i,f = tree[i].parent; f != 0;
c = f, f = tree[f].parent)
if(tree[f].lchild == c) cd[--start] = '0';
else cd[--start] = '1';
codes[i] = (char*)malloc((n - start)*sizeof(char));
strcpy(codes[i],&cd[start]);
}
free(cd);
}
}//HuffEncoding
int main()
{
int nn;
int* weight;
huffTree tree;
huffCode codes;
cout<<"Please input the count of the number:";
cin>>nn;
weight = (int*)malloc(nn*sizeof(int));
cout<<"Input the data one by one:"<<endl;
for(i = 0; i < nn; i ++)
{
cin>>weight[i];
}
HuffEncoding(nn,weight,tree,codes);
for(i = 1; i <= nn; i ++)
{
printf("%d:%s\n",tree[i].weight,codes[i]);
}
return 0;
}
分享到:
相关推荐
在C语言下实现哈弗曼树的创建并进行哈弗曼编码,同时输出哈弗曼编码。
哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树哈弗曼树
哈弗曼树及哈弗曼编码的创建 void createht(htnode ht[]) //创建哈夫曼树 void createhcode(htnode ht[],hcode hcd[])/*创建哈夫曼编码*/ void encode(char ch[]) /*显示字符串s的哈夫曼编码*/
visual studio C语言实现哈弗曼树的创建,编码,解码
数据结构实验,用C++实现创建哈弗曼树,构造哈弗曼树,并根据哈弗曼树生成哈弗曼编码 构造哈弗曼树,根据哈弗曼树的构成过程,始终选择最小全职的两个节点构成一棵二叉树
NULL博文链接:https://weixiaolu.iteye.com/blog/1460430
用C++实现的数据结构的哈弗曼树的源程序,具有创建,编码,译码以及打印的功能。
vc实现的哈夫曼树及其图形化,需要安装Easyx绘图库,不同环境下可能需要略作调整,仅作参考
C++实现,完全可运行代码,注意特定磁盘需创建的文件。。
1. 将提供的字符串(自定义字符串)进行排序,获取各个字符的权重; 2. 将字符及对应的权重放入树节点(node)...6. 利用创建的哈夫曼树得到编码; 用递归得到叶子节点,由叶子节点追溯到根节点,得到编码后反转顺序;
用数据结构中的哈弗曼树的技术和思想完成密码的编译,能够实现对一段字符的编码,即实现加密,然后再对密码进行解密,可以看到原文。
根据ASCII码文件中各ASCII字符出现的频率情况创建哈夫曼树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。
蛮好的,C语言实现哈弗曼编码,创建哈弗曼二叉树
对txt文本中的数据进行提取,并创建哈夫曼树,并进行编码。 给予哈夫曼树和编码,将其翻译成字符,并存入txt文本中。
创建哈弗曼树,并进行编码译码oid main() { HuffmanTree h,h1; HuffmanCode HC; int j,m, n=0,num=0,*p1, *p,i; Linklist q; char str[30]; q=(Linklist)malloc(30*sizeof(Linklist)); Gets(str); m=...