第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
哈夫曼树编码.docx
1． 课程设计目的
2． 课程设计内容和要求
2.1问题描述：
2.2设计内容：
2.3设计要求：
3． 课程设计总体方案及分析
3.1 问题分析：
3.2 主要设计
3.3 调试分析
3.4 测试结果
3.5 参考文献
5． 附录（源代码）
数据结构课程设计报告
课题名称：
哈夫曼树及其应用
姓 名：
学 号：
院 系： 计算机科学与技术系
专业班级：
指导教师：
完成日期：
2018 年 9 月 16 日
数据结构课程设计
目录
1． 课程设计目的............................................................................................................................................................................ 2
2． 课程设计内容和要求.............................................................................................................................................................. 2
2.1 问题描述：...............................................................................................................................................................................2
2.2 设计内容：...............................................................................................................................................................................2
2.3 设计要求： ................................................................................................................................................................2
3． 课程设计总体方案及分析..................................................................................................................................................... 2
3.1 问题分析：............................................................................................................................................................................. 2
3.2 主要设计..................................................................................................................................................................................4
3.3 调试分析..................................................................................................................................................................................6
3.4 测试结果..................................................................................................................................................................................7
3.5 参考文献..................................................................................................................................................................................8
4． 课程设计总结............................................................................................................................................................................ 8
5． 附录（源代码）........................................................................................................................................................................9
1
数据结构课程设计
1． 课程设计目的
本课程设计的目的考察学生对常见数据结构及相关算法的综合应用能力，达到理论与实际应用
相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，解决实际问题中数据的合理存
储表示，并根据相应的存储结构设计效率较高的算法实现对问题的求解；通过此次课程设计进一步
培养学生良好的程序设计技巧和分析问题解决问题的能力。
2． 课程设计内容和要求
2.1 问题描述：
1 熟悉树的各种存储结构及其特点。
2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。
2.2 设计内容：
欲发一封内容为 AABBCAB
„„(共长 100 字符,其中:A 、B 、C 、D 、E 、F 分别有 7 、
9 、12 、22 、23 、27 个)的电报报文,实现哈夫曼编码。
2.3 设计要求：
1 分析系统需求。
2 建立哈夫曼树。
3 进行哈夫曼编码,并求出平均编码长度。
4 编程实现 2、3 步骤。
3． 课程设计总体方案及分析
3.1 问题分析：
1.程序的字符以及权值：
2
字符
A
B
C
D
E
F
数据结构课程设计
权值
7
9
12
22
23
27
2.建立哈夫曼树：
i
ch
weight
lch
rch
0
A
7
-1
-1
1
B
9
-1
-1
2
C
12
-1
-1
3
D
22
-1
-1
4
E
23
-1
-1
5
F
27
-1
-1
3.哈夫曼树及哈夫曼编码：
0
22
D
A:1110
B:1111
C:110
D:00
E:01
F:10
0
100
1
45
0
55
1
1
23
E
27
F
0
28
1
12
C
0
16
1
7
A
9
B
3
数据结构课程设计
3.2 主要设计
1.哈夫曼树存储结构的描述：
const int n = 6;//叶子结点
const int m = 2 * n - 1;//结点
struct tree
{
float weight;//权值
int parent;//双亲
int lch, rch;//左右孩子
};//动态数组分配哈夫曼树
2.哈夫曼树的构造：
void creathuffmantree()
{
int i, j, p1, p2;
float s1, s2;
for (i = 1; i <= m; i++)
//初始化
{
}
hftree[i].parent = 0;
hftree[i].lch = 0;
hftree[i].rch = 0;
hftree[i].weight = 0;
for (i = 1; i <= n; i++)
cin >> hftree[i].weight;
//输入权值
for (i = n + 1; i <= m; i++)
//进行次合作
{
p1 = p2 = 0;
s1 = s2 = 32767;
//p1.p2 分别指向两个最小的值的位置
//s1.s2 代表两个最小权值
for (j = 1; j <= i - 1; j++)
//选两个最小值
if (hftree[j].parent == 0)//该权值还没有被选中
if (hftree[j].weight
数据结构课程设计
hftree[i].lch = p1;
hftree[i].rch = p2;
hftree[i].weight = hftree[p1].weight + hftree[p2].weight;
}
3.哈夫曼树编码
void huffcode()
//哈弗曼编码
{
codetype cd; //缓冲变量
int c, p, i;
for (int i = 1; i <= n; i++)
{
cd.start = n + 1;
cd.ch = 64 + i;
c = i;
p = hftree[i].parent;
while (p != 0)
//第一个树叶对应字母 A，其余依次类推
{
}
cd.start--;
if (hftree[p].lch == c) cd.bits[cd.start] = 0;//tree[i]是左子树，生成代码'0'
else cd.bits[cd.start] = 1;
//tree[i]是右子树，生成代码'1'
c = p;
p = hftree[p].parent;
code[i] = cd;
//第 i+1 个字符的编码存入 code[i]
}
4. 哈夫曼译码：
while ((b == '0') || (b == '1'))
{
if (b == '0')i = hftree[i].lch;
else i = hftree[i].rch;
if (hftree[i].lch == 0)
{
cout << code[i].ch;
i = m;
}
cin >> b;
}
5. 主函数：
void main()
{
creathuffmantree();
//建立哈夫曼树
huffcode();
trancode();
//实现哈夫曼编码
//实现哈夫曼译码
5
数据结构课程设计
}
注：具体源代码见附录
3.3 调试分析
在调试过程中，首先是使用链表进行存储，但是产生的路径是多条或不是最短路径，
所以通过算法比较，改用此算法。
3.4 测试结果
1.界面以及输入权值
2.哈夫曼树的构造
6
数据结构课程设计
3.哈夫曼编码报文
3.5 参考文献
【1】 严蔚敏 吴伟民 《数据结构(C 语言版)》 清华大学出版社， 2009 年 9 月
【2】 郑莉 董渊 何江舟 《C++语言程序设计(第四版)》 清华大学出版社 2009 年 1 月
7
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
