哈夫曼编码实验报告 1

哈夫曼编码

班级：2012计算机科学与技术 姓名： 学号： 日期：2013/12/18

一、 需求分析

1 、输入：输入字符串。

2、输出：哈夫曼编码。

3、功能：初始化，读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存入哈夫曼中。编码，利用已经建立好的哈夫曼树将文件进行编码。

3、测试数据：

5

1 2 3 4 5

q w e r t

5

q w e r t

二、 概要设计

（1）类定义以及主要操作。

typedef struct{

int weight;

int parent,lchild,rchild;

char data;

}HTNode,*HuffmanTree;

typedef char**HuffmanCode;

void select(HuffmanTree &HT,int n,int &s1,int &s2); //找权值最小的下标 void CreatHuffman(HuffmanTree &HT,int *w,char *d,int n);

void HuffmanCodes(HuffmanTree &HT,HuffmanCode &HC,int n);

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int m); //将要编码的字符串存入空树中

（2）主函数测试。

int main()

{

HuffmanTree h;

HuffmanCode c;

int w[100];

char d[100];

cout

cin>>n;

cout

for(i=1;i

}

{ cin>>w[i]; } cout>d[i]; } CreatHuffman(h,w,d,n); HuffmanCodes(h,c,n); cout>m; HuffmanCoding(h,c,m); cout

三、 详细设计

见附录。

四、 调试分析

1、

五、用户使用说明

1、注意按提示输入数据。

六、测试结果

1、输入与输出：

七、附录（完整代码）

//==================================================================== // 哈夫曼编码

//--------------------------------------------------------------------

// 使用方法：略

//--------------------------------------------------------------------

// 姓名： 学号： QQ：1794559417 2013/12/18

//==================================================================== #include

#include

using namespace std;

//-----类、函数声明--------------------

typedef struct{

int weight;

int parent,lchild,rchild;

char data;

}HTNode,*HuffmanTree;

//-------------

typedef char**HuffmanCode;

//-------------

void select(HuffmanTree &HT,int n,int &s1,int &s2); //找权值最小的下标

void CreatHuffman(HuffmanTree &HT,int *w,char *d,int n);

void HuffmanCodes(HuffmanTree &HT,HuffmanCode &HC,int n);

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int m); //将要编码的字符串存入空树中

//-----全局数据定义--------------------

int i,j,n,m;

//-----主函数----------------------------------------------

int main()

{

HuffmanTree h;

HuffmanCode c;

int w[100];

char d[100];

cout>n; cout>w[i]; } cout

} { cin>>d[i]; } CreatHuffman(h,w,d,n); HuffmanCodes(h,c,n); cout>m; HuffmanCoding(h,c,m); cout

//=====函数实现======================================================= void select(HuffmanTree &HT,int n,int &s1,int &s2)

{

s1=0;s2=0;

int n1=30000,n2=30000;

for(int i=1;i

{

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

{

if(HT[i].weight

{

n2=n1;

n1=HT[i].weight;

s2=s1;

s1=i;

}

else

if(HT[i].weight

{

n2=HT[i].weight;

s2=i;

}

}

}

}

//---------------

void CreatHuffman(HuffmanTree &HT,int *w,char *d,int n)

{

int m,i,s1,s2;

m=n*2-1;

HT=new HTNode[m+1];

for(i=1;i

{

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

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].data=d[i];

}

for(i=n+1;i

{

HT[i].weight=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].data=' ';

}

for(i=n+1;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;

}

}

//---------------

void HuffmanCodes(HuffmanTree &HT,HuffmanCode &HC,int n) {

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd;

cd=new char[n+1];

int i,start,c,f;

cd[n-1]='\0';

for(i=1;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]=new char[n-start];

strcpy(HC[i],&cd[start]);

}

cout

cout

}

delete (cd);

}

//----------------

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int m) {

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd;

cd=new char[n+1];

char *zifu;

zifu= new char[m+1];

int i,start,c,f;

cd[n-1]='\0';

for(i=1;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]=new char[n-start];

strcpy(HC[i],&cd[start]);

}

cout>zifu[i]; } cout

} } }

delete (cd); }

//=====结束===========================================================

哈夫曼编码

班级：2012计算机科学与技术 姓名： 学号： 日期：2013/12/18

一、 需求分析

1 、输入：输入字符串。

2、输出：哈夫曼编码。

3、功能：初始化，读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存入哈夫曼中。编码，利用已经建立好的哈夫曼树将文件进行编码。

3、测试数据：

5

1 2 3 4 5

q w e r t

5

q w e r t

二、 概要设计

（1）类定义以及主要操作。

typedef struct{

int weight;

int parent,lchild,rchild;

char data;

}HTNode,*HuffmanTree;

typedef char**HuffmanCode;

void select(HuffmanTree &HT,int n,int &s1,int &s2); //找权值最小的下标 void CreatHuffman(HuffmanTree &HT,int *w,char *d,int n);

void HuffmanCodes(HuffmanTree &HT,HuffmanCode &HC,int n);

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int m); //将要编码的字符串存入空树中

（2）主函数测试。

int main()

{

HuffmanTree h;

HuffmanCode c;

int w[100];

char d[100];

cout

cin>>n;

cout

for(i=1;i

}

{ cin>>w[i]; } cout>d[i]; } CreatHuffman(h,w,d,n); HuffmanCodes(h,c,n); cout>m; HuffmanCoding(h,c,m); cout

三、 详细设计

见附录。

四、 调试分析

1、

五、用户使用说明

1、注意按提示输入数据。

六、测试结果

1、输入与输出：

七、附录（完整代码）

//==================================================================== // 哈夫曼编码

//--------------------------------------------------------------------

// 使用方法：略

//--------------------------------------------------------------------

// 姓名： 学号： QQ：1794559417 2013/12/18

//==================================================================== #include

#include

using namespace std;

//-----类、函数声明--------------------

typedef struct{

int weight;

int parent,lchild,rchild;

char data;

}HTNode,*HuffmanTree;

//-------------

typedef char**HuffmanCode;

//-------------

void select(HuffmanTree &HT,int n,int &s1,int &s2); //找权值最小的下标

void CreatHuffman(HuffmanTree &HT,int *w,char *d,int n);

void HuffmanCodes(HuffmanTree &HT,HuffmanCode &HC,int n);

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int m); //将要编码的字符串存入空树中

//-----全局数据定义--------------------

int i,j,n,m;

//-----主函数----------------------------------------------

int main()

{

HuffmanTree h;

HuffmanCode c;

int w[100];

char d[100];

cout>n; cout>w[i]; } cout

} { cin>>d[i]; } CreatHuffman(h,w,d,n); HuffmanCodes(h,c,n); cout>m; HuffmanCoding(h,c,m); cout

//=====函数实现======================================================= void select(HuffmanTree &HT,int n,int &s1,int &s2)

{

s1=0;s2=0;

int n1=30000,n2=30000;

for(int i=1;i

{

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

{

if(HT[i].weight

{

n2=n1;

n1=HT[i].weight;

s2=s1;

s1=i;

}

else

if(HT[i].weight

{

n2=HT[i].weight;

s2=i;

}

}

}

}

//---------------

void CreatHuffman(HuffmanTree &HT,int *w,char *d,int n)

{

int m,i,s1,s2;

m=n*2-1;

HT=new HTNode[m+1];

for(i=1;i

{

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

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].data=d[i];

}

for(i=n+1;i

{

HT[i].weight=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].data=' ';

}

for(i=n+1;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;

}

}

//---------------

void HuffmanCodes(HuffmanTree &HT,HuffmanCode &HC,int n) {

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd;

cd=new char[n+1];

int i,start,c,f;

cd[n-1]='\0';

for(i=1;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]=new char[n-start];

strcpy(HC[i],&cd[start]);

}

cout

cout

}

delete (cd);

}

//----------------

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int m) {

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd;

cd=new char[n+1];

char *zifu;

zifu= new char[m+1];

int i,start,c,f;

cd[n-1]='\0';

for(i=1;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]=new char[n-start];

strcpy(HC[i],&cd[start]);

}

cout>zifu[i]; } cout

} } }

delete (cd); }

//=====结束===========================================================


相关文章

  • 哈夫曼编码实验报告

    • 赫夫曼编码实验报告 一.实验内容 实现赫夫曼编码的算法 二.哈夫曼编码的实验步骤 1．输入n个信源符号及其对应的权值 2．利用select()函数找出权值最小的两个信源,并各自分配一个码元" 0"" 1&quo ...查看


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

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


  • 多媒体技术实验报告

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


  • 实验报告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年 ...查看


热门内容