• 大小: 5KB
    文件类型: .cpp
    金币: 1
    下载: 0 次
    发布日期: 2021-05-12
  • 语言: C/C++
  • 标签: c++  哈夫曼树  

资源简介

本程序是c++语言利用数据结构中的树来实现二院哈夫曼编译码,支持任意字符串的编译码,直接用visual studio打开运行即可。

资源截图

代码片段和文件信息

#include 
#include 
using namespace std;
struct HNode 
{
int weight;    //结点权值
    int parent;    //双亲指针
int LChild;   //左孩子指针
int RChild ;  //右孩子指针
};    
struct HCode
  {
char data;
char code[100];
  };

class Huffman
{
private:
    HNode* HTree;                    //Huffman树  
HCode* HCodeTable;               //Huffman编码表
char str[1024];                  //输入的原始字符串
char leaf[256];                  //叶子节点对应的字符
int  a[256];                     //记录每个出现的字符的个数
public:
    int  n;                          //叶子节点数
    void init();                     //初始化
    void CreateHTree();        //创建huffman树
    void CreateCodeTable();   //创建编码表
    void Encode(char *d);            //编码
void Decode(char *s char *d);   //解码
void print(int iint m);         //打印Huffman树

void SelectMin(int &x int &y int s int e );//选择两个最小的节点
void Reverse(char* s); //逆转编码
    ~ Huffman();//析构函数
};
void Huffman::init()
{
int nNum[256]= {0};                //记录每一个字符出现的次数
int ch = cin.get();  
int i=0;  
while((ch!=‘\r‘) && (ch!=‘\n‘))
{
nNum[ch]++;                   //统计字符出现的次数
str[i++] = ch;                   //记录原始字符串
ch = cin.get();                   //读取下一个字符
}
str[i]=‘\0‘;
cout<<“各个字符出现的次数:“<    n = 0;
    for ( i=0;i<256;i++)
{
if (nNum[i]>0)              //若nNum[i]==0说明该字符未出现
{
leaf[n] = (char)i;         
a[n] = nNum[i];   
n++;
cout<<(char)i<<“-“< }
}
cout<}
void Huffman::CreateHTree()
{
HTree = new HNode [2*n-1];  //根据权重数组a[0..n-1] 初始化Huffman树
for (int k = 0; k < n; k++) 
{
HTree[k].weight = a[k];
HTree[k].LChild = HTree[k].RChild = HTree[k].parent = -1;
}
    int x y;
    for (int i = n; i < 2*n-1; i++)  //开始建Huffman树
{   
SelectMin(x y 0 i);   //从1~i中选出两个权值最小的结点
HTree[x].parent = HTree[y].parent = i;
HTree[i].weight = HTree[x].weight+ HTree[y].weight;
HTree[i].LChild = x;
HTree[i].RChild = y;
HTree[i].parent = -1;
}
}

void Huffman::SelectMin(int &x int &y int s int e )
{
int i;
for ( i=s; i<=e;i++)
if (HTree[i].parent == -1)
{
x =y= i;    break;          //找出第一个有效权值x,并令y=x
}
    for ( ; i if (HTree[i].parent == -1)         //该权值未使用过
{
if ( HTree[i].weight< HTree [x].weight)
            {

评论

共有 条评论