没有合适的资源?快使用搜索试试~ 我知道了~
首页Huffman与Shannon-Fano编码实验报告
Huffman与Shannon-Fano编码实验报告
5星 · 超过95%的资源 需积分: 9 57 下载量 4 浏览量
更新于2023-03-16
4
收藏 124KB DOC 举报
Huffman编码与Shannon-Fano编码简介 算法思想描述 程序源代码及部分注释 运行结果实例及实验总结
资源详情
资源推荐
一、 编码提要
Human 编码根据字符出现的概率来构造平均长度最短的编码。它是一种
变长的编码。在编码中,若各码字长度严格按照码字所对应符号出现概率的大
小的逆序排列,则编码的平均长度是最小的。(注:码字即为符号经哈夫曼编
码后得到的编码,其长度是因符号出现的概率而不同,所以说哈夫曼编码是变
长的编码。)
Shannon-Fano 算法采用从上到下的方法进行编码:首先按照符号出现的
概率排序,然后从上到下使用递归方法将符号组分成两个部分,使每一部分具
有近似相同的频率,在两边分别标记 0 和 1,最后每个符号从顶至底的 0/1 序
列就是它的二进制编码。
输入一组数,输出其所有的全排列,基本思想为:找所有排列中最小的一个排
列 P, 然后找 P 大比其它都小的排列 Q,循环执行,直到找到一个最大的排列。
二、 实验内容
1、Human 编码实现
a 、算法和思想描述
对给定的 n 个权值{W1,W2,W3,...,Wi,...,Wn}构成 n 棵二叉树的初始集合
F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树 Ti 中只有一个权值为 Wi 的根结
点,它的左右子树均为空(为方便在计算机上实现算法,一般还要求以 Ti 的权
值 Wi 的升序排列)。 在 F 中选取两棵根结点权值最小的树作为新构造的二叉
树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
从 F 中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合 F 中。
重复原步骤,直到集合 F 中只有一棵二叉树为止。
b 、程序代码及部分注释
#include <iostream>
using namespace std;
typedef struct
{
char character;
float weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef char *EachHuffcode;
void Select(HuffmanTree HT,int length,int &s1,int &s2)
{ //找出权值最小的节点或子树,分别用 s1 和 s2 返回
unsigned int min=10000; //给 min 赋初值(足够大)
HuffmanTree p=HT;
int i;
for(i=1,++p;i<=length;++i,++p)
{
if(p->weight<min&&p->parent==0)
{
min=p->weight;
s1=i;
}
}
min=10000; //恢复 min 的处置,重新开始计数找出权值第二小的节点或者子数
p=HT;
for(i=1,++p;i<=length;++i,++p)
{
if(p->weight <min&&p->parent==0)
{
if(i==s1) continue; //忽略权值最小的节点或子树
min=p->weight;
s2=i;
}
}
}//Select 函数
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, float *w,int n)
{
if(n <=1) return;
int m=2*n-1; //霍夫曼树的节点数
HT=new HTNode[m+1]; //多定义一位,保证第一位空置不用
HuffmanTree p=HT;
int i,s1,s2,c,f,start;
for(i=1,++p;i <=n;++i,++p,++w)
{
p->weight=*w;
p->parent=p->lchild=p->rchild=0;
}//for 把前 n 个节点初始化,只赋给其权值
for(;i <=m;++i,++p) p->weight=p->parent=p->lchild=p->rchild=0;
for(i=n+1;i <=m;++i)
{
Select(HT,i-1,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;
} //for 构建霍夫曼树
HC=new EachHuffcode[n+1]; //多定义一位,保证第一位空置不用
char *cd=new char[n];
cd[n-1]='\0'; //末位的标志,使传值时能到此停止
for(i=1;i <=n;++i){ //得到各节点的霍夫曼编码,并将它们记录在 HC[1]到
HC[n]中
start=n-1;
for(c=i,f=HT[i].parent; f!=0;c=f,f=HT[f].parent){
if(c==HT[f].lchild) cd[--start]='0';
else cd[--start]='1';
HC[i]=new char[n-start]; //给 HC[]分配存储空间
strcpy(HC[i],&cd[start]); //将 cd[]所存储的霍夫曼编码传给 HC[][]
}
}//for 循环赋值,得到霍夫曼树的编码
delete []cd; //释放空间
}//HumanCoding 函数
int main()
{
HuffmanTree hftree = NULL;
HuffmanCode hfcode = NULL;
int x;
cout <<"请输入信源符号的个数:" <<endl;
cin>>x;
float *weight=new float[x];
char *character=new char[x];
cout <<"分别输入各个信源符号: " <<endl;
for (int j=0; j <x; ++j) cin>> character [j];
剩余10页未读,继续阅读
zw217217
- 粉丝: 2
- 资源: 36
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的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直接复制
信息提交成功