赫夫曼编译码器的实现数据结构课程设计报告.docx

赫夫曼编译码器的实现数据结构课程设计报告.docx

《赫夫曼编译码器的实现数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《赫夫曼编译码器的实现数据结构课程设计报告.docx（19页珍藏版）》请在冰点文库上搜索。

赫夫曼编译码器的实现数据结构课程设计报告

数据结构课程设计报告

题目：

赫夫曼编/译码器的实现

学生姓名：

学号：

所在学院：

班级：

指导教师：

职称：

2010年6月25日

XXX学院本科学生课程设计任务书

题　目

哈夫曼编\译码器

1、课程设计的目的

1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）

[问题描述]：

哈夫曼编\译码器

[基本要求]：

1.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。

2.编码，利用建好的huffman树生成huffman编码；

3.输出编码；

4.译码功能；

5.字符和频度如下：

字符空格ABCDEFGHIJKLMNOPQ

频度18664132232103211547571232205763151

字符RSTUVWXYZ

频度48518023818116

3、主要参考文献

［1］刘大有等，《数据结构》（C语言版），高等教育出版社

［2］严蔚敏等，《数据结构》（C语言版），清华大学出版社

［3］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社

［4］苏仕华等，数据结构课程设计，机械工业出版社

4、课程设计工作进度计划

第1天完成方案设计与程序框图

第2、3天编写程序代码

第4天程序调试分析和结果

第5天课程设计报告和总结

指导教师（签字）

日期

年月日

教研室意见：

年月日

学生（签字）：

接受任务时间：

2010年6月25日

课程设计（论文）指导教师成绩评定表

题目名称

哈夫曼编\译码器

评分项目

分值

得分

评价内涵

工作

表现

20%

01

学习态度

6

遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。

02

科学实践、调研

7

通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。

03

课题工作量

7

按期圆满完成规定的任务，工作量饱满。

能力

水平

35%

04

综合运用知识的能力

10

能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。

05

应用文献的能力

5

能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。

06

设计（实验）能力，方案的设计能力

5

能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。

07

计算及计算机应用能力

5

具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。

08

对计算或实验结果的分析能力（综合分析能力、技术经济分析能力）

10

具有较强的数据收集、分析、处理、综合的能力。

成果

质量

45%

09

插图（或图纸）质量、篇幅、设计（论文）规范化程度

5

符合本专业相关规范或规定要求；规范化符合本文件第五条要求。

10

设计说明书（论文）质量

30

综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。

11

创新

10

对前人工作有改进或突破，或有独特见解。

成绩

指导教师评语

指导教师签名：

年　月　日

摘要

利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。

关键字：

数据结构、哈夫曼编码

目录

第一章.序言1

第二章．问题分析与说明1

一．功能分析1

二．问题描述与说明1

第三章．程序总体设计2

一．设计思路及方案2

二.设计的总体框架3

第四章.详细算法与设计5

一．实现算法流程图5

二．哈夫曼编码的算法6

三．文件的编码和解码8

第五章.程序调试与运行结果8

第六章.课程设计总结9

第七章.参考文献10

第八章.附录11

第一章.序言

目的：

1、为了使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

2、为了使学生掌握软件设计的基本内容和设计方法，并培养学生进行规化

软件设计的能力。

3、为了使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

意义：

通过数据结构课程设计，我掌握了赫夫曼编/译码器的实现所需要的各种知识，了解到了哈夫曼程序设计的基本原理和知识，我相信在以后的学习当中我会更加的喜欢计算机这门高新技术学科。

第二章．问题分析与说明

一．功能分析

利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。

因此为这样的信息收发站写一个哈夫曼码的编／译码系统存在着相当大的必要。

相关知识：

数据结构、哈夫曼编码译码器、程序设计格式等。

二．问题描述与说明：

1.《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。

数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

2.哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：

指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串。

但在信息传递时，总希望总长度尽可能最短，即采用最短码。

作为信息管理专业的学生，我们应该很好的掌握这门技术。

在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！

课程设计就是为解决这个问题提供了一个平台。

3.课程设计题目：

哈夫曼编\译码器

任务和功能：

（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树的存储结构；

（2）利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对给定的n个字符正文进行编码，并输出结果。

（3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符，并输出结果。

4.问题分析

该问题要求将输入的字符以及相应的权值建立哈夫曼树，并利用建好的哈夫曼树生成哈夫曼编码。

把输入的字符按权值从小到大排序，挑出2个最小权值供哈夫曼编码调用，再将输入的字符以及他的权值，按照哈夫曼规则建立二叉树，从叶子到根逆向求编码，再使用循环,从根结点开始遍历输出。

第三章．程序总体设计

一．设计思路及方案

1.哈弗曼树的构造

根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。

这种方法的基本思想是：

（1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；

（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；

（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；

（4）重复

（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

2.哈弗曼编码

设S={d0,d1,……,d（n-1）}为待编码的字符集，W={w0,w1,……,w（n-1）}是S中各字符在电文中出现的频率。

现以W为权值，构造哈弗曼树。

哈弗曼的每个叶子结点对应一个字符。

在哈弗曼树的每个结点到其左孩子的边上标上0，到其右孩子的边上标上1。

将从根的每个叶子的路径上的数码连接起来，就是该叶子所代表的字符编码。

因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。

3.哈弗曼译码

译码过程为：

自左向右逐一扫描码文，并从哈弗曼树的根开始，将扫描得到的二进制位串中的相邻位于哈弗曼树上标的0，1相匹配，以确定一条从跟到叶子结点的路径，一但到达叶子，则译出了一个字符；再回到树根，从二进制的下一位开始继续译码

4.该系统将实现以下几大功能：

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树的存储结构；利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对给定的n个字符正文进行编码，并输出结果。

利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符，并输出结果。

二.设计的总体框架

第四章.详细算法与设计

一．实现算法流程图

1.建立HuffmanTree

voidHaffmanTree:

:

Haffman（intweight[],HaffmanTreeHT[]）

查找哈夫曼链表中两个权值最小的节点：

创建哈弗曼树

2.哈夫曼编码和译码（略）

二．哈夫曼编码的算法

　给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：

依次以叶子T[i]（0≤i≤n-1）为出发点，向上回溯至根为止。

上溯时走左分支则生成代码0，走右分支则生成代码1。

注意：

　　①由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时向量中，并设一个指针start指示编码在

该向量中的起始位置（start初始时指示向量的结束位置）。

　　②当某字符编码完成时，从临时向量的start处将编码复制到该字符相应的位串bits中即可。

　　③因为字符集大小为n，故变长编码的长度不会超过n，加上一个结束符'\0'，bits的大小应为n+1。

（2）字符集编码的存储结构及其算法描述

typedefstruct{

charch；//存储字符

charbits[n+1]；//存放编码位串

}CodeNode；

typedefCodeNodeHuffmanCode[n]；

voidCharSetHuffmanEncoding（HuffmanTreeT，HuffmanCodeH）

{//根据哈夫曼树T求哈夫曼编码表H

intc，p，i;//c和p分别指示T中孩子和双亲的位置

charcd[n+1]；//临时存放编码

intstart；//指示编码在cd中的起始位置

cd[n]='\0'；//编码结束符

for（i=0，i

H[i].ch=getchar（）；//读入叶子T[i]对应的字符

start=n；//编码起始位置的初值

c=i；//从叶子T[i]开始上溯

while（（p=T[c].parent）>=0）{//直至上溯到T[c]是树根为止

//若T[c]是T[p]的左孩子，则生成代码0；否则生成代码1

cd[--start]=（T[p）.1child==C）?

'0'：

'1'；

c=p；//继续上溯

}

strcpy（H[i].bits，&cd[start]）；//复制编码位串

}//endfor

}//CharSetHuffmanEncoding

三．文件的编码和解码（略）

第五章．程序调试与运行结果

运行结果图：

运行结果分析：

通过调试发现该程序满足哈弗曼树，哈弗曼编码的基本要求，满足课程设计任务的基本功能与要求。

但是，该程序还是有所欠缺和不足，不能通过编码译出电文。

在以后的学习中希望能将其实现，使程序变得更完善。

第六章．课程设计总结

通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。

通过对数据结构和课程设计的学习，使我们能够以问题求解方法、程序设计方法以及一些典型的数据结构算法为研究对象，分析数据对象的特征，掌握数据组织的方法和在计算机中的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，使我们初步掌握了算法的时间、空间复杂度的分析技巧，并逐步培养了良好的程序设计风格以及进行复杂程序设计的技能。

数据结构一科的重要内容和主要难点是让我们理解、习惯和熟悉算法构造性思维方法。

在课设过程中，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序运行结果的重要影响，构建最小代价生成树时，一个细微的循环控量的错误都能影响到程序的正确性，而所有的代码机制都是为一个目标的实现而运作的，所以，细致是实现算法和程序准确性必不可少的。

许多的错误让我明白了一个道理---细心是非常重要的。

同时，对于编程者而言，思路清晰是相当重要的。

在适当的时候和同学一起交流探讨是一个十分好的学习机会。

请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。

而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。

做课程设计不仅让我修补了以前学习的漏洞，也让我知道一个道理：

编程需要兴趣和实际动手。

这应该可以借鉴在老师的教学工作上。

创新思维至关重要，这不仅能让我们写出精简的代码，也有助于开发出高效的程序。

第七章.参考文献

［1］《数据结构》（C语言版），刘大有等，高等教育出版社

［2］《数据结构》（C语言版），严蔚敏等，清华大学出版社

［3］《C语言程序设计》（第二版），谭浩强、张温基等编著，高等教育出版社

［4］《数据结构课程设计》，苏仕华等，机械工业出版社

［5］《C++面向对象程序设计》，谭浩强编著，清华出版社，中国铁道出版社

［6］《C程序设计语言》，徐宝文李志等著，机械工业出版社

［7］《C和指针》，徐波译，人民邮电出版社

［8］《C陷阱与缺陷》，高巍译，人民邮电出版社

［9］《C专家编程》，徐波译，人民邮电出版社

［10］《实用C语言编程》，郭大海译，中国电力出版社

［11］《C语言核心技术》，蔡学镛译，机械工业出版社

第八章．附录

源程序：

#include

#include

#include

usingnamespacestd;

constintMaxValue=10000;

classHaffmanTree

{

public:

HaffmanTree（intn）;

HaffmanTree（）;

~HaffmanTree（）;

voidHaffman（intweight[],HaffmanTreeHT[]）;

voidHaffmanCode（HaffmanTreehaffTree[],HaffmanTreeHaffCode[],charch[],strings）;

private:

intweight;//权值

intflag;//标记

intparent;//双亲结点下标

intleftChild;//左孩子下标

intrightChild;//右孩子下标

intbit[6];//数组

intstart;//编码的起始下标

intN;

};

HaffmanTree:

:

HaffmanTree（intn）

{

N=n;

}

HaffmanTree:

:

HaffmanTree（）

{

}

HaffmanTree:

:

~HaffmanTree（）

{

}

voidHaffmanTree:

:

Haffman（intweight[],HaffmanTreeHT[]）

{

intj,m1,m2,x1,x2;

//哈夫曼树haffTree初始化。

n个叶结点的哈夫曼树共有2n-1个结点

for（inti=0;i<2*N-1;i++）

{

if（i

elseHT[i].weight=0;

HT[i].parent=0;

HT[i].flag=0;

HT[i].leftChild=-1;

HT[i].rightChild=-1;

}

//构造哈夫曼树haffTree的n-1个非叶结点

for（i=0;i

{

m1=m2=MaxValue;

x1=x2=0;

for（j=0;j

{

if（HT[j].weight

{

m2=m1;

x2=x1;

m1=HT[j].weight;

x1=j;

}

elseif（HT[j].weight

{

m2=HT[j].weight;

x2=j;

}

}

//将找出的两棵权值最小的子树合并为一棵子树

HT[x1].parent=N+i;

HT[x2].parent=N+i;

HT[x1].flag=1;

HT[x2].flag=1;

HT[N+i].weight=HT[x1].weight+HT[x2].weight;

HT[N+i].leftChild=x1;

HT[N+i].rightChild=x2;

}

}

voidHaffmanTree:

:

HaffmanCode（HaffmanTreehaffTree[],HaffmanTreeHaffCode[],charch[],strings）

{

intchild,parent;

stringcs;

for（inti=0;i

{

start=N-1;//不等长编码的最后一位为n-1

weight=haffTree[i].weight;//取得编码对应权值的字符

child=i;

parent=haffTree[child].parent;

//由叶结点向上直到根结点

while（parent!

=0）

{

if（haffTree[parent].leftChild==child）

bit[start]=0;//左孩子结点编码0

else

bit[start]=1;//右孩子结点编码1

start--;

child=parent;

parent=haffTree[child].parent;

}

//保存叶结点的编码和不等长编码的起始位

for（intj=start+1;j

HaffCode[i].bit[j]=bit[j];

HaffCode[i].start=start;

HaffCode[i].weight=weight;//记住编码对应权值的字符

}

cout<

for（i=0;i

{

cout<

for（intj=HaffCode[i].start+1;j

cout<

cout<

}

system（"pause"）;

cout<<"进行译码：

";

for（i=0;i

{

for（intj=0;j

{

if（s[i]==ch[j]）

for（intm=HaffCode[j].start+1;m

cout<

}

}

cout<

}

voidmain（void）

{

intm,q;

charp;

stringstr,ch;

cout<<"请输入权值个数：

";

cin>>m;

intweight[26];

charnode[26];

for（inti=0;i

{

cout<<"请输入第"<

";

cin>>p;

node[i]=p;

cout<<"请输入权值：

";

cin>>q;

weight[i]=q;

}system（"pause"）;

cout<<"请输入电文（注意电文必须只包含以上字符）：

";

cin>>str;

HaffmanTreeh（m）;

HaffmanTree*myHaffTree=newHaffmanTree[2*m+1];

HaffmanTree*myHaffCode=newHaffmanTree[m];

h.Haffman（weight,myHaffTree）;

h.HaffmanCode（myHaffTree,myHaffCode,node,str）;

}