C++实现Huffman树
#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
//存储HuffmanTree的数据结构
typedef struct tagHuffmanTree
{
unsigned int nWeight;
unsigned int nParent,nLchild,nRchild; //用于保存节点在数组中的位置
}HTNode, *HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char* HuffmanCodeLine;
typedef char** HuffmanCode; // 动态分配数组存储赫夫曼编码表。。二级指针
//从数列中找出parent为0且权值最小的两个叶节点.. nMin1和nMin2为数组中位置
void SelectMinWeight(HuffmanTree &HT, int nNodeCount, int &nMin1, int &nMin2)
{
int i = 0;
int c = 0;
int nMinWeight1 = 65535;
int nMinWeight2 = 65535;
int *pOrder = new int[nNodeCount];
for (i=1; i<=nNodeCount; ++i)
{
if (0 == HT[i].nParent) //统计parent为0的节点及下标
{
pOrder[c++] = i;
}
}
//比较parent为0的节点中权值大小,获取权值小的位置
for (i=0; i<c; ++i)
{
// 在每次循环中, 始终将较小值存入nMinWeight1, 较大值存入nMinWeight2;
// 执行完毕后, nMinWeight1中是最小值, nMinWeight2中是次小值.
int nTempWeight = HT[pOrder[i]].nWeight;
if (nTempWeight < nMinWeight1)
{
nMinWeight2 = nMinWeight1;
nMin2 = nMin1;
nMinWeight1 = nTempWeight;
nMin1 = pOrder[i];
}
else if (nTempWeight < nMinWeight2)
{
nMinWeight2 = nTempWeight;
nMin2 = pOrder[i];
}
}
if (pOrder)
{
delete [] pOrder;
pOrder = NULL;
}
return;
}
//建树及获取叶子节点编码
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *pWeight, int nLeafCount)
{
if (nLeafCount <= 1)
{
return;
}
//pWeight为存放权值的数组；nLeafCount为叶子节点数目，即待编码节点数
int nNodeCount = 2*nLeafCount - 1; //总节点数目
HT = new HTNode[nNodeCount + 1]; //多申请一个空间，为了0号单元不使用
HTNode *pTemp = NULL;
int i = 0;
//初始化前几个存储单元，存放叶子节点。
for (i=1,pTemp=HT+1; i<=nLeafCount; ++i, ++pTemp, ++pWeight) //pTemp=HT+1，第0号单元不用
{
(*pTemp).nWeight = *pWeight;
(*pTemp).nParent = 0;
(*pTemp).nLchild = 0;
(*pTemp).nRchild = 0;
}
//初始化HT后几个存储单元，均为存放后来生成的Parent节点的、
for (; i<=nNodeCount; ++i,++pTemp)
{
(*pTemp).nWeight = 0;
(*pTemp).nParent = 0;
(*pTemp).nLchild = 0;
(*pTemp).nRchild = 0;
}
//建立HuffmanTree。
int nMin1, nMin2;
for (i=nLeafCount+1; i<=nNodeCount; ++i)
{
//在HT[1...i-1]中寻找parent为0且权值最小的两个。分别为nMin1, nMin2（nMin1, nMin2是在数组中的位置）
SelectMinWeight(HT, i-1, nMin1, nMin2);
HT[nMin1].nParent = i;
HT[nMin2].nParent = i;
HT[i].nLchild = nMin1;
HT[i].nRchild = nMin2;
HT[i].nWeight = HT[nMin1].nWeight + HT[nMin2].nWeight;
}
//----------------编码部分-------------------------------
//从叶子到根逆向求编码
HC = new HuffmanCodeLine[nLeafCount + 1]; //0号单元未用
char *pCode = new char[nLeafCount]; //用于保存一个节点的编码序列
memset(pCode, 0, nLeafCount);
//pCode[nLeafCount - 1] = '\0'; //编码结束符
int nStart = 0;
for (i=1; i<=nLeafCount; ++i) //遍历叶子节点
{
nStart = nLeafCount - 1; //编码结束符的位置,pCode数组最后一个位置
int nTempPos;
unsigned int nParent;
for (nTempPos=i,nParent=HT[i].nParent; nParent!=0; nTempPos=nParent, nParent=HT[nParent].nParent)
{
if (nTempPos == HT[nParent].nLchild) //默认左子树赋值0，右子树赋值1
{
pCode[--nStart] = '0';
}
else
{
pCode[--nStart] = '1';
}
}
HC[i] = new char[ nLeafCount - nStart ];
strcpy(HC[i], &pCode[nStart]); //将一个叶子节点的编码拷贝
}
if (pCode)
{
delete [] pCode;
pCode = NULL;
}
return;
}
//主程序入口
int _tmain(int argc, _TCHAR* argv[])
{
int i = 0;
int nLeafCount = 0; //叶子数即为要编码的节点数
//int nNodeCount = 0;
cout<<"Input num of leaf:"<<endl;
cin>>nLeafCount;
while (0 == nLeafCount)
{
cout<<"Num of leaf can not be 0"<<endl;
cin>>nLeafCount;
}
//申请内存保存字符值和权值
char *pLetter = new char[nLeafCount]; //保存字符值
int *pWeight = new int[nLeafCount]; //保存权值
for (i=0; i<nLeafCount; ++i)
{
cout<<"Input letter and weight"<<endl;
cin>>pLetter[i]>>pWeight[i];
}
HuffmanTree HT = NULL;
HuffmanCode HC = NULL;
HuffmanCoding(HT, HC, pWeight, nLeafCount); //调用方法，建立Huffman树，并获取编码序列
for (int i=1
补充：软件开发 , C++ ,
