算法设计哈夫曼编码
宁夏师范学院数学与计算机科学学院
《算法分析与设计》实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
实验序号: 7 实验项目名称:哈夫曼编码
学 号 姓 名 专业、班
实验地点 指导教师 时 间 一、实验目的及要求
(1) 掌握贪心算法的基本思想和组成要素;
(2) 掌握使用贪心方法解决实际问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
的基本方法和步骤; 二、实验设备(环境)及要求
1、环境要求:
硬件:PC(PII以上，128M以上内存)、因特网接入;
软件:Windows XP操作系统、VC++6.0编程环境。
2、实验要求:
(1) 独立完成实验，源代码书写
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
;
(2) 程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确;
(3) 实验完成后必须有实验结果的分析及本次实验的总结。 三、实验内容与步骤
#include
#include
#include
#define N 7 //编码字符个数
#define M (2*N-1)//哈夫曼树结点个数
typedef struct {
char c;//字符
float f;//指定字符出现的频率
int i;//序号
int parent,lchild,rchild;//分别指向父亲、左孩子、右孩子序号
char *code;//指定字符的哈夫曼前缀编码
}huffmanNode,*huffman;
typedef struct {
huffmanNode *element;//
int capacity;//优先队列最大容量
int size;//优先队列中已经具有的结点数量
}heapNode,*priorityqueue;
//判断优先队列是否为空，如果为空，则返回1，否则返回0 int isEmpty(priorityqueue h){
return h->size==0;
}
//判断优先队列是否已满，如果满，则返回1，否则0 int isFull(priorityqueue h){
return h->capacity==h->size;
}
//功能:向队列中插入指定的元素，插入后的队列具有小队性质 //先判断队列是否已满，如果已经满了，则给出提示信息，并返回 //否则采用上滤法，即先生成一个空穴，然后把比自己大的父结点向下移，直到找到插入位
置为止
//把队列中最小的元素出队列，同时队列应该保持小堆特性 //优先队列初始化
void pushPrioQueue(priorityqueue h,huffmanNode x){
int i;
if(isFull(h)){
printf("队列已满\n");
return;
}
for(i=++h->size;h->element[i/2].f>x.f;i/=2){
h->element[i]=h->element[i/2];//父结点向下移
}
h->element[i]=x;
}
//功能:将队列中出现频率最小的元素出队，并取下滤法使剩下的保持小堆性质
//首先，判断队列是否已空，如果空，提示，并返回，否则把和一个元素和队列
//中最后一个元素取回，然后按下滤法使剩下的保持小堆性质 //最后将第一个元素返回(即最小元素返回)
huffmanNode popPrioQueue(priorityqueue h){
huffmanNode minNode,lastNode;
int i,child;
if(isEmpty(h)){
printf("队列已经空");
return h->element[0];//哨兵元素
}
minNode=h->element[1];
lastNode=h->element[h->size--];
for(i=1;2*i<=h->size;i=child){
child=i*2;
if(child!=h->size&&h->element[child].f>h->element[child+1].f){
//如果右孩子结点的频率小于左孩子结点的频率则child的取值为右孩子
child++;
}
if(h->element[child].felement[i]=h->element[child];
}
else{
break;
}
}
h->element[i]=lastNode;
return minNode;
}
/*初始化优先队列，将哈夫曼树中叶子结点入队*/ priorityqueue initializePrioQueue(int n,huffman tree){
//将tree中n个元素按字符出现的频率生成堆
//tree中前n个元素是树中的叶子结点
priorityqueue h;
int i;
h=(priorityqueue)malloc(sizeof(heapNode));
if(h==NULL){
printf("out of space");
exit(-1);
}
h->capacity=n;//最大容量
h->size=0;//目前具有的元素个数
h->element=(huffman)malloc(sizeof(huffmanNode)*(n+1));
/*其中第0个元素为哨兵元素，由于元素出现的频率必须大于等于零
因此给此元素的频率设置为小于零便可,主要有入队时用到
*/
if(h->element==NULL){
printf("out of space");
exit(-1);
}
h->element[0].f=-1;
for(i=1;i<=n;i++){
pushPrioQueue(h,tree[i]);//入队列
}
return h;
}
/*功能:用于生成哈夫曼树*/
huffman ctrHuffmanTree(int n){
int m=2*n-1;//1~n存储叶子结点，n+1~m存储树的n-1个内部结点
huffman tree=(huffman)malloc(sizeof(huffmanNode)*(m+1));//用于存储哈夫曼树各结点
priorityqueue h;//用于存储优先队列首地址
int i;
if(tree==NULL){
printf("out of space");
exit(-1);
}
/*生成叶子结点*/
for(i=1;i<=n;i++){
printf("enter %d chara and weight:",i);
scanf("%c%f",&tree[i].c,&tree[i].f);
tree[i].i=i;
tree[i].parent=tree[i].lchild=tree[i].rchild=-1;
tree[i].code=NULL;
getchar();//吸收回车
}
/*初始化优先队列*/
h=initializePrioQueue(n,tree);
/*生成n-1个内部结点*/
for(i=n+1;i<=m;i++){
huffmanNode x,y,z;
x=popPrioQueue(h);
y=popPrioQueue(h);
z.f=x.f+y.f;
z.lchild=x.i;
z.rchild=y.i;
z.parent=-1;
z.i=i;
tree[x.i].parent=i;
tree[y.i].parent=i;
tree[i]=z;
pushPrioQueue(h,z);
}
/*前缀码生成*/
for(i=1;i<=n;i++){
char *c=(char *)malloc(sizeof(n));
int start=n-1;
int j=i;
if(c==NULL)
{
printf("out of space");
exit(-1);
}
c[n-1]='\0';
while(tree[j].parent!=-1){
if(tree[tree[j].parent].lchild==j)c[--start]='0';
else c[--start]='1';
j=tree[j].parent;
}
/*给编码
申请
关于撤销行政处分的申请关于工程延期监理费的申请报告关于减免管理费的申请关于减租申请书的范文关于解除警告处分的申请
空间*/
tree[i].code=(char *)malloc(sizeof(char)*(n-start));
strcpy(tree[i].code,c+start);
}
/*释放优先队列空间*/
free(h->element);
free(h);
return tree;
}
main(){
huffman tree=ctrHuffmanTree(N);
int i,j;
char s[20],ch,encoding[100];
for(i=1;i<=N;i++){
printf("character:%c,weight:%f,父结点序号:%d,前缀编
码:%s\n",tree[i].c,tree[i].f,tree[i].parent,tree[i].code);
}
printf("\n\ninput the string to encoding:");
//输入要编码的串
gets(s);
//输出编码
for(ch=s[i],i=0;ch!='\0';i++){
int j;
for(j=1;j<=N;j++){
if(tree[j].c==ch){
printf("%s",tree[j].code);
break;
}
}
ch=s[i];
}
printf("\n\n");
//输入编码，输出字符串
printf("input the binary string to deencoding:");
gets(encoding);
j=0;
//源码为:
printf("源码为");
puts(encoding);
printf("解码结果为:");
while(encoding[j]!='\0'){
i=M;//从根开始遍历，至到叶子结点
while(tree[i].lchild!=-1 ||tree[i].rchild!=-1){
if(encoding[j]=='1'){
i=tree[i].rchild;//指向右孩子
}
else
{
i=tree[i].lchild;//左孩子
}
j++;
}
printf("%c",tree[i].c);
}
//释放树空间
for(i=1;i<=N;i++)
free(tree[i].code);
free(tree);
printf("\n");
}
四、实验结果与数据处理
五、分析与讨论
哈夫曼编码是广泛的用于数据文件压缩的十分有效的编码方法，其压缩率通常在
20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1
串表示各字符的最优表示方式。
哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
称为哈夫曼编
码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T，算法以|N|个叶节点开始，执行|N|-1次的“合并”运算后产生最终所要求的树T。在crthuffmantree中，首先用字符集C中每一个字符c的频率weight初始化优先队列h，然后不断的从优先队列中取出具有最小频率的两棵树x和y，将它们合并为一棵树z。z的频率是x和y的频率之和。新树z以x为其左孩子，y为其右孩子，经过n-1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 六、教师评语 成绩
签名:
日期: 年 月 日
浙公网安备 33021202002483