#include <iostream>
#include <string>
#include<iomanip>
using namespace std;
struct HNode
{
char c;//结点代表的字符
int weight;//此字符在字符串中的权重
int parent;//双亲结点在数组中位置
int LChild;//左孩子在数组中位置
int RChild;//左孩子在数组中位置
};
struct HCode
{
char data;//存储字符
char code[100];//足够大一存储该字符的编码
};
class Huffman
{
private:
HNode* HTree;//哈夫曼树动态数组的指针
HCode* HcodeTable;//哈夫曼树的编码数组指针
int m;
public:
void Init(char *s);//初始化哈夫曼树
void Creat();//创建哈夫曼树动态数组
void SelectMin(int &x,int &y,int i);//寻找最小权重的两个数的函数
void CodeTable();//创建哈夫曼编码表
void Reverse(char c[]);//颠倒字符串的函数
void Encode(char *s,string *d);//编码函数
void Decode(char *s,char *d);//解码函数
void PrintTable();//打印哈夫曼树表
int Getm(){return m;}
~Huffman(){delete []HTree;delete []HcodeTable;}//析构函数
};
//初始化哈夫曼树
void Huffman::Init(char *s)
{
int n=0;
while (*(s+n)!='\0')
{
n++;//统计字符串字符数
}
char *temp=new char[n];//申请动态数组存储字符串以便之后对字符串排序
for (int i=0;i<n;i++)
{
temp[i]=*(s+i);
}
char ctemp;
for (int i=0;i<n-1;i++)//冒泡排序法,排序以后方便统计不同字符串出现的个数
{
for (int j=0;j<n-1-i;j++)
{
if (temp[j]>temp[j+1])
{
ctemp=temp[j];
temp[j]=temp[j+1];
temp[j+1]=ctemp;
}
}
}
int k=1;
for (int i=1;i<n;i++)//统计不同字符个数
{
if (temp[i]!=temp[i-1])
{
k++;
}
}
HTree=new HNode[2*k-1];
m=2*k-1;//存储哈夫曼数组大小
int l=0;//统计不同字符出现的频度
k=0;//控制哈夫曼数组下标
ctemp=temp[0];//做标记
for (int i=0;i<n;i++)
{
if(temp[i]==ctemp)
{
l++;//统计不同字符出现的频度
if (i==n-1)
HTree[k].weight=l;
}
else
{
HTree[k].c=ctemp;
HTree[k].weight=l;
ctemp=temp[i];
k++;
l=1;
HTree[k].c=ctemp;
HTree[k].weight=l;
}
}
delete []temp;//释放动态内存空间
Creat();//创建哈夫曼数的数组
CodeTable();//创建哈夫曼编码表
}
//创建哈夫曼树动态数组
void Huffman::Creat()
{
int n=(m+1)/2;//n表示不同字符的个数
for (int i=0;i<n;i++)
{
HTree[i].LChild=-1;
HTree[i].RChild=-1;
HTree[i].parent=-1;
}
int x,y;
for (int i=n;i<2*n-1;i++)
{
SelectMin(x,y,i);//找出最小权重的两个字符
HTree[x].parent=i;
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 i)
{
x=0;
while(HTree[x].parent!=-1)//防止第一个就是之前找到的最小的导致下面循
北邮数据结构实验三题目2哈夫曼树_化学_自然科学_专业资料。北京邮电大学信息与通信工程学院 数据结构实验报告实验名称:实验三题目 2 哈夫曼树 学生姓名: 班级: ...
北邮数据结构实验报告三题目2-哈夫曼树 隐藏>> 北京邮电大学信息与通信工程学院 1.实验要求利用二叉树结构实现哈夫曼编/解码器 (1).初始化:能够对输入的任意...
(2).创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码... 北邮数据结构实验三题目... 13页 1下载券 北邮数据结构实验三题目... 暂无...
北邮数据结构实验一题目4 北邮数据结构实验二题目3...编码时借助哈夫曼树,也即带权路径长 度最小的二叉...具体 C++实现参看源代码中的 CreateTree()函数。 ...
北京邮电大学信通院数据... 14页 1下载券 北邮数据结构实验三题目... 暂无...(2).创建哈夫曼树 算法伪代码: 1. 创建一个长度为 2*n-1 的三叉链表 2...
北邮数据结构实验二题目3_电脑基础知识_IT/计算机_专业资料。北京邮电大学电信...第8页 北京邮电大学电信工程学院 4. 总结 1、在最初尝试编写代码时,采用的是...
北京邮电大学信息与通信工程学院 数据结构实验报告实验名称: 实验三——题目 1 ...中序遍历,后序遍历,求二叉树的深度以及二 叉树的销毁都涉及到递归函数的巧妙...
2.创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码:... 北邮数据结构实验三题目... 13页 1下载券 北邮数据结构实验一_约瑟... ...
北邮数据结构实验哈夫曼编码解码_计算机软件及应用_... 创意简历模板汇集 推理型题分析与总结文档贡献者 ... 暂无评价 3页 免费 哈夫曼树的编码与解码 2页 ...
北邮数据结构上机实验-哈夫曼树_工学_高等教育_教育专区。 /*2.2题目2——...关键代码应说明其功能 3、递归程序注意调用的过程,防止栈溢? */ #include<...
热门文档