#include "stdafx.h"
#include "hfm.h"
#include<string.h>
#include<malloc.h> //malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>
#define TRUE 1
#define FALSE 1
#define OK 1
#define ERROR 1
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean；
/************************************************************************/
/* 最优二叉树简称：哈夫曼树 */
/************************************************************************/
//哈夫曼树结构
; typedef struct{
unsigned int weight; //权重
unsigned int parent, lchild, rchild; //树的双亲节点，和左右孩子
}HTNode, *HuffmanTree;
typedef char** HuffmanCode;
//返回i个节点中权值最小的树的根节点的序号，供select()调用
int Min(HuffmanTree T, int i){
int j, flag;
unsigned int k = UINT_MAX; //%d-->UINT_MAX = -1,%u--->非常大的数
for (j = 1; j <= i; j++)
if (T[j].weight < k && T[j].parent == 0)
k = T[j].weight, flag = j; //
T[flag].parent = 1; //将parent标志为1避免二次查找
return flag; //返回
}
void Select(HuffmanTree T, int i,int& s1,int& s2){
//在i个节点中选取2个权值最小的树的根节点序号，s1为序号较小的那个
int j;
s1 = Min(T,i);
s2 = Min(T,i);
if (s1 > s2){
j = s1;
s1 = s2;
s2 = j;
}
}
//HuffmanCode代表的树解码二进制值
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n){
//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
int m, i, s1, s2, start;
unsigned c, f;
char* cd;
//分配存储空间
HuffmanTree p;
if (n <=1)
return;
//n个字符(叶子节点)有2n-1个树节点，所以树节点m
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode)); //0号元素未用
//这一步是给哈夫曼树的叶子节点初始化
for (p = HT + 1, i = 1; i <= n; ++i, ++p,++w)
{
(*p).weight = *w;
(*p).lchild = 0;
(*p).rchild = 0;
(*p).parent = 0;
}
//这一步是给哈夫曼树的非叶子节点初始化
for (; i <= m; ++i, ++p){
(*p).parent = 0;
}
/************************************************************************/
/* 做完准备工作后 ，开始建立哈夫曼树
/************************************************************************/
for (i = n + 1; i <= m; i++)
{
//在HT[1~i-1]中选择parent=0且weigh最小的节点，其序号分别为s1,s2
Select(HT, i - 1, s1, s2); //传引用
HT[s1].parent = HT[s2].parent= i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
/************************************************************************/
/* 从叶子到根逆求每个叶子节点的哈夫曼编码 */
/************************************************************************/
//分配n个字符编码的头指针向量，（[0]不用）
HC = (HuffmanCode)malloc((n + 1)*sizeof(char*));
cd = (char*)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n - 1] = '\0'; //结束符
for (i = 1; i <= n; i++) //每个节点的遍历
{
start = n - 1;
for (c = i, f = HT[i].parent; f != 0; c = f,f = HT[f].parent){ //每个节点到根节点的遍历
//从叶子节点到根节点的逆序编码
if (HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
}
HC[i] = (char*)malloc((n - start)*sizeof(char)); //生成一个块内存存储字符
//为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); //从cd赋值字符串到cd
}
free(cd); //释放资源
}
//函数声明
int Min(HuffmanTree T, int i); //求i个节点中的最小权重的序列号，并返回
void Select(HuffmanTree T, int i, int& s1, int& s2); //从两个最小权重中选取最小的(左边)给s1，右边的给s2
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n);//哈夫曼编码与解码
int main(){
HuffmanTree HT;
HuffmanCode HC;
int *w, n, i;
printf("请输入权值的个数(>1):");
scanf_s("%d",&n);
w = (int*)malloc(n*sizeof(int));
printf("请依次输入%d个权值(整形):\n",n);
for (i = 0; i <= n - 1;i++)
{
scanf_s("%d",w+i);
}
HuffmanCoding(HT, HC, w, n);
for (i = 1; i <= n;i++)
{
puts(HC[i]);
}
return 0;
}
温馨提示：答案为网友推荐，仅供参考