文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 北邮数据结构实验三题目2哈夫曼树(代码)
侵权投诉

北邮数据结构实验三题目2哈夫曼树(代码)

#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)//防止第一个就是之前找到的最小的导致下面循

第1页

你可能喜欢

  • 数据结构实验报告
  • 北邮数据结构
  • 数据结构期末试题
  • 数据结构文章编辑
  • 初中英语作文

热门文档

相关文档

  • 北邮数据结构实验三题目2哈夫曼树

    北邮数据结构实验三题目2哈夫曼树_化学_自然科学_专业资料。北京邮电大学信息与通信工程学院 数据结构实验报告实验名称:实验三题目 2 哈夫曼树 学生姓名: 班级: ...

  • 北邮数据结构实验报告三题目2-哈夫曼树

    北邮数据结构实验报告三题目2-哈夫曼树 隐藏>> 北京邮电大学信息与通信工程学院 1.实验要求利用二叉树结构实现哈夫曼编/解码器 (1).初始化:能够对输入的任意...

  • 北邮数据结构实验三-哈夫曼树

    (2).创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码... 北邮数据结构实验三题目... 13页 1下载券 北邮数据结构实验三题目... 暂无...

  • 北邮数据结构实验三题目2

    北邮数据结构实验一题目4 北邮数据结构实验二题目3...编码时借助哈夫曼树,也即带权路径长 度最小的二叉...具体 C++实现参看源代码中的 CreateTree()函数。 ...

  • 北邮数据结构实验3哈夫曼编码

    北京邮电大学信通院数据... 14页 1下载券 北邮数据结构实验三题目... 暂无...(2).创建哈夫曼树 算法伪代码: 1. 创建一个长度为 2*n-1 的三叉链表 2...

  • 北邮数据结构实验二题目3

    北邮数据结构实验二题目3_电脑基础知识_IT/计算机_专业资料。北京邮电大学电信...第8页 北京邮电大学电信工程学院 4. 总结 1、在最初尝试编写代码时,采用的是...

  • 北邮数据结构实验三题目1

    北京邮电大学信息与通信工程学院 数据结构实验报告实验名称: 实验三——题目 1 ...中序遍历,后序遍历,求二叉树的深度以及二 叉树的销毁都涉及到递归函数的巧妙...

  • 北京邮电大学信通院数据结构实验三——哈夫曼树实验报告

    2.创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码:... 北邮数据结构实验三题目... 13页 1下载券 北邮数据结构实验一_约瑟... ...

  • 北邮数据结构实验哈夫曼编码解码

    北邮数据结构实验哈夫曼编码解码_计算机软件及应用_... 创意简历模板汇集 推理型题分析与总结文档贡献者 ... 暂无评价 3页 免费 哈夫曼树的编码与解码 2页 ...

  • 北邮数据结构上机实验-哈夫曼树

    北邮数据结构上机实验-哈夫曼树_工学_高等教育_教育专区。 /*2.2题目2——...关键代码应说明其功能 3、递归程序注意调用的过程,防止栈溢? */ #include<...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email