资源介绍
#include
#include
#include
#include
using namespace std;
# define MaxN 100//初始设定的最大结点数
# define MaxC 1000//最大编码长度
# define ImpossibleWeight 10000//结点不可能达到的权值
# define n 26//字符集的个数
//-----------哈夫曼树的结点结构类型定义-----------
typedef struct //定义哈夫曼树各结点
{
int weight;//权值
int parent;//双亲结点下标
int lchild;//左孩子结点下标
int rchild;//右孩子结点下标
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef char**HuffmanCode;//动态分配数组存储哈夫曼编码表
//-------全局变量--------
HuffmanTree HT;
HuffmanCode HC;
int *w;//权值数组
//const int n=26;//字符集的个数
char *info;//字符值数组
int flag=0;//初始化标记
//**********************************************************************
//初始化函数
//函数功能： 从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中
//函数参数：
//向量HT的前n个分量表示叶子结点，最后一个分量表示根结点，各字符的编码长度不等，所以按实际长度动态分配空间
void Select(HuffmanTree t,int i,int &s1,int &s2)
{ //s1为最小的两个值中序号最小的那个
int j;
int k=ImpossibleWeight;//k的初值为不可能达到的最大权值
for(j=1;j<=i;j++)
{
if(t[j].weight0），构造哈夫曼树HT，并求出n个字符的哈弗曼编码HC
{
int i,m,c,s1,s2,start,f;
HuffmanTree p;
char* cd;
if(num<=1) return;
m=2*num-1;//m为结点数，一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
//--------初始化哈弗曼树-------
for(p=HT+1,i=1;i<=num;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=num+1;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
//--------建哈夫曼树-------------
for(i=num+1;i<=m;i++)
{
Select(HT,i-1,s1,s2);//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;//左孩子权值小，右孩子权值大
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//-------从叶子到根逆向求每个字符的哈弗曼编码--------
HC=(HuffmanCode)malloc((num+1)*sizeof(char *));//指针数组:分配n个字符编码的头指针向量
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';//判断是左孩子还是右孩子(左为0右为1)
else cd[--start]='1';
HC[i]=(char*)malloc((num-start)*sizeof(char*));//按所需长度分配空间
int j,h;
strcpy(HC[i],&cd[start]);
}
free(cd);
}
//****************初始化函数******************
void Initialization()
{
flag=1;//标记为已初始化
int i;
w=(int*)malloc(n*sizeof(int));//为26个字符权值分配空间
info=(char*)malloc(n*sizeof(char));//为26个字符分配空间
ifstream infile("ABC.txt",ios::in);
if(!infile)
{
cerr<<"打开失败"<>info[i];
infile>>w[i];
}
infile.close();
cout<<"读入字符成功！"<>string;
for(int i=0;string[i]!='\0';i++)
{
if(string[i]=='\0') break;
outfile<>string[i];
}
for(i=0;i<100;i++)
if(string[i]!='#')
cout<>code[i];
if(code[i]!='#')
{
cout<>code[i];
if(code[i]!='#')
cout<rchild,HT); //递归先序遍历
cout<weight<rchild==0) cout<weight;
coprint(HT+start->lchild,HT);
numb--;
outfile.close();
}
}
void Tree_printing(HuffmanTree HT,int num)
{
HuffmanTree p;
p=HT+2*num-1; //p=HT+26
cout<<"下面打印赫夫曼树"<:初始化哈弗曼树"<:输入待编码字符串"<:利用已建好的哈夫曼树进行编码"<:利用已建好的哈夫曼树进行译码"<:打印代码文件"<:打印哈夫曼树"<:退出"<"<>choice;
switch(choice)
{
case 'I':Initialization();break;
case 'W':Input();break;
case 'E':Encoding();break;
case 'D':Decoding();break;
case 'P':Code_printing();break;
case 'T':Tree_printing(HT,n);break;
case 'Q':;break;
default:cout<<"输入的命令出错，请重新输入！"<
- 上一篇: C语言数据结构--哈夫曼编/译码器
- 下一篇: GDB调试手册(中文版)