课  程  设  计
（数据结构 ）
哈夫曼树和哈夫曼编码
二○○九 年 六 月 二十六 日
课程设计任务书及成绩评定
课题名称
表达式求值 哈夫曼树和哈夫曼编码
哈夫曼编码树的带权路径长度Ⅰ、题目的目的和要求：
 
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
Ⅱ、设计进度及完成情况
日  期
内              容
6.8-6.10
选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。
6.15和6.19
创建相关数据结构,录入源程序。
6.22~6.25
调试程序并记录调试中的问题，初步完成课程设计报告。
6.26
上交课程设计报告并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。
考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。
Ⅲ、主要参考文献及资料
[1] 严蔚敏 数据结构（C语言版）清华大学出版社 1999
[2] 严蔚敏 数据结构题集（C语言版）清华大学出版社 1999
[3] 谭浩强  C语言程序设计  清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料
Ⅳ、成绩评定：
设计成绩：                （教师填写）
指导老师：                （签字）
二○○ 九  年  六 月 二十六 日
第一章 概述…………………………………………………………1
第二章 系统分析……………………………………………………2
第三章 概要设计……………………………………………………3
第四章 详细设计及实现代码………………………………………8
第五章 调试过程中的问题及系统测试情况…………………… 12
第六章 结束语…………………………………………………… 13

参考文献……………………………………………………………13

第一章 概述
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学
习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。
功能：表达式求值以栈为存储结构，实现输入的表达式的求值；
        哈夫曼树和哈夫曼编码是实现最优二叉树的构造，并能通过最优二叉树进行编码，应用到电文中，并以此来译码。
利用键盘，输入相应的数值，通过程序实现表达式的求值；再利用键盘，输入各个顶点，通过程序构造最优二叉树以及为此编码。
第二章 系统分析
一、表达式求值
根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式所有指数不相同的项，则分别复抄到“和多项式”中去。
在此，安装上述抽象数据类型Polynomial中基本操作的定义，“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指着qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指针qa所指结点的指数值<指针qb所指结点的指数值，则应摘取qa指针所指结点插入到“和多项式”链表中去；②指针qa所指结点的指数值>指针qb所指结点的指数值，则应摘取指针qb所指结点插入到“和多项式”链表中去；③指针qa所指结点的指数值=指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。