没有合适的资源?快使用搜索试试~ 我知道了~
首页哈夫曼码的编/译码系统代码
哈夫曼码的编/译码系统代码
5星 · 超过95%的资源 需积分: 18 28 下载量 67 浏览量
更新于2023-07-15
2
收藏 96KB DOC 举报
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。这要求在发送端通过一个编码系统对待传输预先编码,在接收端将传来的数据进行译码。对于双工通道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
资源详情
资源推荐
程序代码
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
const int UINT_MAX=1000;
char str[50];
typedef struct
{
int weight,K;
int parent,lchild,rchild;
}HTNode,* HuffmanTree; //动态分配树组存储赫夫曼树
typedef char **HuffmanCode; //动态分配树组存储赫夫曼编码
//-----------全局变量-----------------------
HuffmanTree HT;
HuffmanCode HC;
int w[50],i,j,n;
char z[50];
int flag=0;
int numb=0;
// -----------------求赫夫曼编码-----------------------
struct cou
{
char data;
int count;
}cou[50];
/*函数名:min
函数功能:求两个哈夫曼树中最小权值的结点
参数:哈夫曼树头指针,结点数
实现:逐个比较哈夫曼树中无双亲结点权值,找到最小权值结点将其 parent 值
置一并返回此结点序号*/
int min(HuffmanTree t,int i) // 函数 void select()调用
{
int j,flag;
int k=UINT_MAX; // 取 k 为不小于 1000 可能的值,即 k 为最大的权
值 1000
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0) // t[j]是树的根结点
k=t[j].weight,flag=j;
t[flag].parent=1; // 给选中的根结点的双亲赋 1,避免第 2 次查找
该结点
return flag;
}
/*函数名:select
函数功能:选取哈夫曼树中权值最小的两个结点
参数:哈夫曼树头指针,结点数,两个整形指针
实现:调用两次 min 函数求得两个最小权值结点并分别以指针 s1,s2 记录,s1 为
最小的两个值中序号小的那个*/
void select(HuffmanTree t,int i,int &s1,int &s2) // s1 和 s2 为最小的两个值中序号
小的那个
{
int j;
s1=min(t,i); s2=min(t,i); //调用函数 min(),求 s1,s2 为 weight 最小的
两个节点
if(s1>s2) //交换 s1,s2,确保 s1≤s2
{
j=s1; s1=s2; s2=j;
}
}
// --------------算法 6.12--------------------------
/*函数名 HuffmanCodeing
函数功能:构造哈夫曼树并求出 N 个字符的哈夫曼编码
参数:哈夫曼树头指针,哈夫曼编码头指针,存放 N 个字符权值的数组 W,字
符数量 N
实现:检测结点数是否可以构成树,若不能,跳出函数,若能,建立哈夫曼树
并存于 HT 中,然后从叶子到根逆向求每个字符的赫夫曼编码并存于 HC 中*/
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ // w 存放 n 个字符的权值(均>0),构造赫夫曼树 HT,并求出 n 个字符的赫夫曼编
码 HC
int m,i,s1,s2,start;
HuffmanTree p;
if(n<=1) return; //检测结点数是否可以构成树
m=2*n-1; //n 为叶子节点数,m 为节点总数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0 号单元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w) //初始化赫夫曼树
{
p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0;
}
for(;i<=m;++i,++p)
/*p->weight=0;*/ p->parent=0; /* p->lchild=0; p->rchild=0;*/
for(i=n+1;i<=m;++i) // 建赫夫曼树
{ // 在 HT[1~i-1]中选择 parent 为 0 且 weight 最小的两个结点,其序号分别为
s1 和 s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
// --------从叶子到根逆向求每个字符的赫夫曼编码----------
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); // 分配 n 个字符编码的头指针向
量([0]不用)
int c,f;
char *cd;
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';
else cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char)); // 为第 i 个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从 cd 复制编码(串)到 HC
}
free(cd); // 释放工作空间
}
//---------------------获取报文并写入文件---------------------------------
/*函数名 InputCode
函数功能:获取报文并写入文件
参数:无
实现:以读的方式打开文件 tobetran.txt,若不能打开打印出错信息并跳出函数,
若能,从键盘获取字符并存入文件*/
int InputCode()
{
FILE *tobetran;
if((tobetran=fopen("tobetran.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return 0;
}
cout<<"请输入你字符串:"<<endl;
gets(str);
fputs(str,tobetran);
cout<<"获取报文成功"<<endl;
fclose(tobetran);
return strlen(str);
}
//--------------初始化赫夫曼链表---------------------------------
/*函数名:Initialization
剩余12页未读,继续阅读
twilightsunset
- 粉丝: 1
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功