当前位置:首页 >> IT/计算机 >> 霍夫曼编码

霍夫曼编码

《 算法分析与设计》实验报告

-1-

实验 3

贪心算法

一、实验目的和要求 (1)了解前缀编码的概念,理解数据压缩的基本方法; (2)掌握最优子结构性质的证明方法; (3)掌握贪心法的设计思想并能熟练运用 (4)证明哈夫曼树满足最优子结构性质; (5)设计贪心算法求解哈夫曼编码方案; (6)设计测试数据,写出程序文档。 二、实验内容
j

设需要编码的字符集为{d1, d2, …, dn},它们出现的频率为{w1,k w2, …, wn},应用哈夫 ∑a 曼树构造最短的不等长编码方案。 三、实验环境 Turbo C 或 VC++ 四、实验学时 2 学时,必做实验 五、数据结构与算法
//霍夫曼编码 #include<iostream.h> #include<malloc.h> #include<string.h> #include <stdio.h> typedef char *HuffmanCode; //动态分配数组,存储霍夫曼编码 typedef struct { unsigned int weight; //存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 }HTNode, *HuffmanTree; void Select(HuffmanTree *ht,int n,int *s1,int *s2) {//选择两个 parent 为 0,且 weight 最小的结点 s1 和 s2 int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) {
k =i

《 算法分析与设计》实验报告

-2-

if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0 && i!=(*s1)) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0 && i!=(*s1)) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s2=min; } void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) {//构造霍夫曼树 ht。w 存放已知的 n 个权值 int m,i,s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1; i<=n; i++) //1--n 号存放叶子结点,初始化 { (*ht)[i].weight=w[i]; (*ht)[i].LChild=0; (*ht)[i].parent=0; (*ht)[i].RChild=0; } for(i=n+1; i<=m; i++) { (*ht)[i].weight=0; (*ht)[i].LChild=0; (*ht)[i].parent=0; (*ht)[i].RChild=0; } //非叶子结点初始化 cout<<endl<<"创建霍夫曼树: "<<endl; 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; cout<<(*ht)[i].weight<<"("<<(*ht)[s1].weight<<","<<(*ht)[s2].weight<<")"<<endl; }

《 算法分析与设计》实验报告

-3-

cout<<endl; } //从叶子结点到根,逆向求每个叶子结点对应的哈夫曼编码 void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) { char *cd; int i,start,p; unsigned int c; hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配 n 个编码的头指针 cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间 cd[n-1]='\0'; //从右向左逐位存放编码,首先存放编码结束符 for(i=1; i<=n; i++) //求 n 个叶子结点对应的哈夫曼编码 { start=n-1; //初始化编码起始指针 for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码 if( (*ht)[p].LChild==c) cd[--start]='0'; //左分支标 0 else cd[--start]='1'; //右分支标 1 hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第 i 个编码分配空间 strcpy(hc[i],&cd[start]); } free(cd); cout<<"各叶子结点的哈夫曼编码是:"<<endl; for(i=1; i<=n; i++) cout<<(*ht)[i].weight<<":"<<hc[i]<<endl; Cout<<endl; } void main() { HuffmanTree HT; HuffmanCode HC; int n,*w,i,wei,m; cout<<"请输入叶子结点数 n:"; cin>>n; w=(int *)malloc((n+1)*sizeof(int)); cout<<"请输入各叶子结点的权值:"<<endl; for(i=1;i<=n;i++) { cout<<"w["<<i<<"]="; fflush(stdin); cin>>wei; w[i]=wei; } CrtHuffmanTree(&HT,w,n); CrtHuffmanCode(&HT,&HC,n); }

六、核心源代码
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) {//构造霍夫曼树 ht。w 存放已知的 n 个权值 int m,i,s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

《 算法分析与设计》实验报告

-4-

for(i=1; i<=n; i++) //1--n 号存放叶子结点,初始化 { (*ht)[i].weight=w[i]; (*ht)[i].LChild=0; (*ht)[i].parent=0; (*ht)[i].RChild=0; } for(i=n+1; i<=m; i++) { (*ht)[i].weight=0; (*ht)[i].LChild=0; (*ht)[i].parent=0; (*ht)[i].RChild=0; } //非叶子结点初始化 cout<<endl<<"创建霍夫曼树: "<<endl; 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; cout<<(*ht)[i].weight<<"("<<(*ht)[s1].weight<<","<<(*ht)[s2].weight<<")"<<endl; } cout<<endl; } //从叶子结点到根,逆向求每个叶子结点对应的哈夫曼编码 void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) { char *cd; int i,start,p; unsigned int c; hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配 n 个编码的头指针 cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间 cd[n-1]='\0'; //从右向左逐位存放编码,首先存放编码结束符 for(i=1; i<=n; i++) //求 n 个叶子结点对应的哈夫曼编码 { start=n-1; //初始化编码起始指针 for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码 if( (*ht)[p].LChild==c) cd[--start]='0'; //左分支标 0 else cd[--start]='1'; //右分支标 1 hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第 i 个编码分配空间 strcpy(hc[i],&cd[start]); } free(cd); cout<<"各叶子结点的哈夫曼编码是:"<<endl; for(i=1; i<=n; i++) cout<<(*ht)[i].weight<<":"<<hc[i]<<endl; Cout<<endl;


更多相关文档:

霍夫曼编码_图文.ppt

霍夫曼编码 - 霍夫曼编码Huffman 霍夫曼编码Huffman Coding 长春理工大学 080212418 高延邦 目录 一、什么是编码 二、霍夫曼编码简介 三、霍夫曼编码的熵 ...

Huffman霍夫曼编码_图文.ppt

Huffman霍夫曼编码 - 4.2霍夫曼编码 ? 霍夫曼编码介绍 霍夫曼编码(Huffman Coding)是一种编码方法, 霍夫曼编码是可变字长编 码(VLC)的一种。 1952年, ...

哈夫曼编码_图文.ppt

? 本问题的简易系统也可以如图所示 返回开头 一个简易哈夫曼编码/译码系统图示 返回 发送端发送报文 原码报文 接收端 哈夫曼编码系统通信通道 哈夫曼译码系统 原码...

霍夫曼编码霍夫曼编码_图文.ppt

霍夫曼编码霍夫曼编码 - 多媒体技术基础(第3版) 第2章数据无损压缩 张奇 复

哈夫曼编码的方法.doc

哈夫曼编码的方法 - 1.哈夫曼编码的方法 编码过程如下 : (1) 将信源符号

霍夫曼编码.pdf

霍夫曼编码 - 实验二 Huffman 编码 一、实验目的 1.复习C++程序基

霍夫曼编码的MATLAB实现(完整版).doc

霍夫曼编码的MATLAB实现(完整版)_数学_自然科学_专业资料。霍夫曼编码的MATLAB实现完整版 %哈夫曼编码的 MATLAB 实现(基于 0、1 编码) : clc; clear; A=[0....

霍夫曼编码霍夫曼编码Huffmancoding-复旦大学_图文.ppt

霍夫曼编码霍夫曼编码Huffmancoding-复旦大学 - 多媒体技术基础(第

哈夫曼编码讲解_图文.ppt

哈夫曼编码讲解 - Huffman树及其应用 a 一、最优二叉树(霍夫曼树) b

哈夫曼编码证明.pdf

哈夫曼编码证明 - 哈夫曼编码 一、哈夫曼编码的过程 提到哈夫曼编码,我们就不得

霍夫曼编码的C语言实现.pdf

霍夫曼编码的C语言实现 - 《信息处理与编码》结课大作业 学号: 班级: 姓名: 成绩: 霍夫曼编码的C语言实现 1.编码原理 霍夫曼码由霍夫曼树构造,平均码长是...

哈夫曼编码与算术编码比较.doc

哈夫曼编码与算术编码比较 - (1)哈夫曼编码所形成的码字不是唯一的, 但编码效

三进制霍夫曼编码.doc

三进制霍夫曼编码_数学_自然科学_专业资料。精心整理 题目:将霍夫曼编码推广至三进制编码,并证明它能产生最优编码。 ※将霍夫曼编码推广至三进制编码 设一个数据...

哈夫曼编码实验报告.doc

哈夫曼编码实验报告 - 哈夫曼编码器实验报告 学院: 学院:计算机学院 班级:

哈夫曼编码算法实现完整版.doc

哈夫曼编码算法实现完整版 - 实验三 一.实验题目: 树的应用哈夫曼编码 树的应用 二.实验内容: 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息...

哈夫曼编码编译器.doc

哈夫曼编码编译器 - 一、 课题:哈夫曼编码编译器 设计一个哈夫曼编码/译码系统, 对一个文本文件中的字符进行哈夫曼编码, 生成编码文件 (压缩文件,后缀名.cod)...

哈夫曼编码译码器实验报告(免费).doc

定义结构体类型的 signode 作为哈夫曼树的节点, 定义结构体类型的 hufnode 作为 哈夫曼编码对照表的节点, 定义 HFM 类实现对哈夫曼树的创建, 利用其成员函数 ...

哈夫曼编码_贪心算法.doc

哈夫曼编码_贪心算法 - 实验目的和要求 (1)了解前缀编码的概念,理解数据压缩

霍夫曼编码.doc

霍夫曼编码_计算机软件及应用_IT/计算机_专业资料。南昌大学信息论与编码实验之霍夫曼编码 霍夫曼编码的 matlab 实现一、实验内容: 用 Matlab 语言编程实现霍夫曼(...

哈夫曼编码_图文.ppt

哈夫曼编码 - Huffman树及其应用 一、Huffman树 二、Huffma

网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com