哈夫曼编码实验报告

赫夫曼编码实验报告

一、实验内容

实现赫夫曼编码的算法

二、哈夫曼编码的实验步骤

1．输入n个信源符号及其对应的权值

2．利用select()函数找出权值最小的两个信源，并各自分配一个码元“ 0”“ 1”，并将这两个信源合并为一个新的信源，其权值为这两个最小信源的权值之和，得到一个包n-1个信源符号的新信源，这一过程叫做信源的第一次缩减

3. 重复步骤二，直到只剩下两个符号为止，此时从最后一级缩减信源开始，依编码路经向前返回，得到各信源符号所对应的码字

4.输出信息熵，平均码长以及编码效率

三、源代码

#include

#include

using namespace std;

#define MAX 100

typedef struct{

int weight;

int parent,Lc,Rc;

char data;

}HTNode,*HTree; //动态分配数组存储赫夫曼树

typedef char * *HCode;

void HuffmanCode(HTree &HT,HCode &HC,int *w,int n);

void Select(HTree &HT,int n,int &s1,int &s2);

void inputCode();

void outputCode(HCode HC,char *data,int *w,int n);

const int n=27;

int flag=0;

HTree Ht;

HCode Hc;

int num;

void HuffmanCode(HTree &HT,HCode &HC,int *w,int n){

//w存放n个字符权值(均>0)，构造赫夫曼树HT，并求n个字符赫夫曼编码HC。

int m,i,s1,s2;//s1,s2为在HT[1..i-1]中parent为0且weight最小的两个结点

if(n

m=2*n-1;//m为赫夫曼树的总结点数

HT=(HTree)malloc((m+1)*sizeof(HTNode));

// 对赫夫曼树进行初始化

for(i=1;i

HT[i].data=0;

HT[i].weight=w[i-1];

HT[i].parent=0;

HT[i].Lc=0;

HT[i].Rc=0;

}

for(;i

HT[i].data=0;

HT[i].weight=0;

HT[i].parent=0;

HT[i].Lc=0;

HT[i].Rc=0;

}

//***************创建HuffmanTree******************

char *cd;

int start,c,f;

for(i=n+1;i

Select(HT,i-1,s1,s2);

HT[s1].parent=HT[s2].parent=i;

HT[i].Rc=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}

//从叶子到根逆向求每个字符的赫夫曼编码

HC=(HCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针向量

cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间 cd[n-1]='\0'; // 编码结束符

for(i=1;i

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)// 从叶子到根逆向求编码

if(HT[f].Lc==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);

}//HuffmanCode

//s1为权值最小的根结点

void Select(HTree &HT,int n,int &s1,int &s2){

//在HT[1..n]选择parent为0且weight最小的两个结点，其序号分别为s1,s2。//其中s1 为weight最小值的结点，s2为weight第二小的值的结点

int flag1=1,flag2=1; //s1,s2初始化后则置0；

int i;

for(i=1;i

if(HT[i].parent==0&&(flag1||flag2))

if(flag1){

s1=i;

flag1=0;

}

else if(flag2){

s2=i;

flag2=0;

}

for(i=s1+1;i

if(HT[i].parent==0){

if(HT[i].weight

//当所比较的值比最小值小时，修改s1和s2

s1=i;

}

else if(HT[i].weight

s2=i;

}

}//Select

void inputCode(){

int n;

int w[MAX];

int i;

char data[MAX];

float Hx=0; //信源的熵

float al=0; //平均码长

int l=0; //信源符号码长

float p; //信源符号概率

cout

cin>>n;

cout

cout

for(i=0;i

cout

cin>>data[i];

cin>>w[i];

cout

}

HuffmanCode(Ht,Hc,w,n);

cout

outputCode(Hc,data,w,n);

for(i=0;i

//计算信源的熵

p=float(w[i])/100;

Hx=Hx-(p)*(log(p)/log(2));

//计算信源的平均码长

l=0;

while(Hc[i+1][l]!=0)

l++;

al=al+p*l;

}

cout}//inputCode

void outputCode(HCode HC,char *data,int *w,int n){ for(int i=1;i

cout

}//outputCode

//主函数

void main(){

inputCode();

}//main

四、运行结果

赫夫曼编码实验报告

一、实验内容

实现赫夫曼编码的算法

二、哈夫曼编码的实验步骤

1．输入n个信源符号及其对应的权值

2．利用select()函数找出权值最小的两个信源，并各自分配一个码元“ 0”“ 1”，并将这两个信源合并为一个新的信源，其权值为这两个最小信源的权值之和，得到一个包n-1个信源符号的新信源，这一过程叫做信源的第一次缩减

3. 重复步骤二，直到只剩下两个符号为止，此时从最后一级缩减信源开始，依编码路经向前返回，得到各信源符号所对应的码字

4.输出信息熵，平均码长以及编码效率

三、源代码

#include

#include

using namespace std;

#define MAX 100

typedef struct{

int weight;

int parent,Lc,Rc;

char data;

}HTNode,*HTree; //动态分配数组存储赫夫曼树

typedef char * *HCode;

void HuffmanCode(HTree &HT,HCode &HC,int *w,int n);

void Select(HTree &HT,int n,int &s1,int &s2);

void inputCode();

void outputCode(HCode HC,char *data,int *w,int n);

const int n=27;

int flag=0;

HTree Ht;

HCode Hc;

int num;

void HuffmanCode(HTree &HT,HCode &HC,int *w,int n){

//w存放n个字符权值(均>0)，构造赫夫曼树HT，并求n个字符赫夫曼编码HC。

int m,i,s1,s2;//s1,s2为在HT[1..i-1]中parent为0且weight最小的两个结点

if(n

m=2*n-1;//m为赫夫曼树的总结点数

HT=(HTree)malloc((m+1)*sizeof(HTNode));

// 对赫夫曼树进行初始化

for(i=1;i

HT[i].data=0;

HT[i].weight=w[i-1];

HT[i].parent=0;

HT[i].Lc=0;

HT[i].Rc=0;

}

for(;i

HT[i].data=0;

HT[i].weight=0;

HT[i].parent=0;

HT[i].Lc=0;

HT[i].Rc=0;

}

//***************创建HuffmanTree******************

char *cd;

int start,c,f;

for(i=n+1;i

Select(HT,i-1,s1,s2);

HT[s1].parent=HT[s2].parent=i;

HT[i].Rc=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}

//从叶子到根逆向求每个字符的赫夫曼编码

HC=(HCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针向量

cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间 cd[n-1]='\0'; // 编码结束符

for(i=1;i

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)// 从叶子到根逆向求编码

if(HT[f].Lc==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);

}//HuffmanCode

//s1为权值最小的根结点

void Select(HTree &HT,int n,int &s1,int &s2){

//在HT[1..n]选择parent为0且weight最小的两个结点，其序号分别为s1,s2。//其中s1 为weight最小值的结点，s2为weight第二小的值的结点

int flag1=1,flag2=1; //s1,s2初始化后则置0；

int i;

for(i=1;i

if(HT[i].parent==0&&(flag1||flag2))

if(flag1){

s1=i;

flag1=0;

}

else if(flag2){

s2=i;

flag2=0;

}

for(i=s1+1;i

if(HT[i].parent==0){

if(HT[i].weight

//当所比较的值比最小值小时，修改s1和s2

s1=i;

}

else if(HT[i].weight

s2=i;

}

}//Select

void inputCode(){

int n;

int w[MAX];

int i;

char data[MAX];

float Hx=0; //信源的熵

float al=0; //平均码长

int l=0; //信源符号码长

float p; //信源符号概率

cout

cin>>n;

cout

cout

for(i=0;i

cout

cin>>data[i];

cin>>w[i];

cout

}

HuffmanCode(Ht,Hc,w,n);

cout

outputCode(Hc,data,w,n);

for(i=0;i

//计算信源的熵

p=float(w[i])/100;

Hx=Hx-(p)*(log(p)/log(2));

//计算信源的平均码长

l=0;

while(Hc[i+1][l]!=0)

l++;

al=al+p*l;

}

cout}//inputCode

void outputCode(HCode HC,char *data,int *w,int n){ for(int i=1;i

cout

}//outputCode

//主函数

void main(){

inputCode();

}//main

四、运行结果


相关文章

  • 北邮期中信息论附加题实验报告

    • 信息论实验报告 3. Matlab 仿真实验:掷骰子游戏,每次同时抛掷两枚骰子,将两枚骰子点数的和作为游戏结果,重复抛掷 1000 次(视为 1000 次信源符号输出).要求: (1) 对 1000 次游戏结果进行逐符号二进制定长编码和译码 ...查看


  • 多媒体技术实验报告

    • 多媒体技术及应用实验报告 班级: 姓名:学号:电信1301秦行U201313480 实验一:Huffman编码 一．实验内容 1.了解BMP图像的格式,实现BMP图片格式的数据域及文件头的分离 2.熟悉Huffman编码原理 3.用C语言使 ...查看


  • 哈夫曼编码实验报告 1

    • 哈夫曼编码 班级:2012计算机科学与技术 姓名: 学号: 日期:2013/12/18 一. 需求分析 1 .输入:输入字符串. 2.输出:哈夫曼编码. 3.功能:初始化,读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存入哈 ...查看


  • 实验报告2_二叉树及哈夫曼编码

    • 实 验 报 告 ( 2013/ 2014 学年 第 二 学期)  课程名称 数据结构A 实验名称 实验二 二叉树的基本操作及哈夫曼编码译码系统 的实现 实验时间 2014 年 4 月 8 日 指导单位 计算机学院计算机软件教学中心 ...查看


  • 哈夫曼编码译码器实验报告

    • <数据结构>课程设计报告 QFileInfo hufFileInfo; }; HuffView负责具体画图 class HuffView : public QGraphicsView { Q_OBJECT public: exp ...查看


  • 哈夫曼编码与译码数据结构实验

    • May 21 实验报告 2015 数据结构 第四次实验 姓名:陈斌 学号:E11314079 专业:13计算机科学与技术 学号E11314079专业计算机科学与技术姓名陈斌 实验日期 2015.05.21教师签字成绩 实验报告 [实验名称] ...查看


  • 哈夫曼编码_贪心算法

    • 淮海工学院计算机工程学院 实验报告书 课程名: <算法分析与设计> 题 目: 实验3 贪心算法 班 级: 软件102班 学 号: 姓 名: 鹿 迅 实验3 贪心算法 实验目的和要求 (1)了解前缀编码的概念,理解数据压缩的基本方 ...查看


  • 5_哈夫曼树的构造

    • 实验5 赫夫曼树的构造 一.实验目的 1．理解赫夫曼树(最优树)相关基本概念及其特性: 2．掌握建立最优树的方法: 3．掌握赫夫曼编码的方法. 二.实验原理 1．基本概念 赫夫曼树(Huffman树)是指具有n个叶子结点(每个结点的权值为w ...查看


  • 哈夫曼编码译码器1

    • 滁州学院 课程设计报告 课程名称: 数据结构 设计题目: 哈夫曼编码译码器 系 别: 计算机科学与技术 专 业: 网络工程 组 别: 第十组 起止日期: 2011年4月28日 ~2011年5月23日 指导教师: 计算机科学与技术系2010年 ...查看


热门内容