长春大学课程设计(哈夫曼).doc

长春大学课程设计说明书题目名称哈夫曼编码/译码器院(系)计算机科学与技术专业(班级)- 9程序清单 :(1)了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计力;(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力;(4)训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所具备的科学的工作方法和作风。:设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。(1)数据结构设计对问题描述中涉及的操作对象定义相应的数据类型,并按照以数据结构为中心的原则划分模块,定义主程序模块和各抽象数据类型。本程序定义了相应的结构体变量,包括weight权值,parent双亲结点,lchild左孩子,rchild右孩子。通过结构体构建哈夫曼树,实现哈夫曼的编码和译码功能。结构体变量如下:typedefstruct//结构体{chardata; intweight;//权值 intparent;//双亲结点 intlchild;//左孩子 intrchild;右孩子}HTNode; HTNodeht[80];功能:该结构体储存相关数据包括输入的权值weight,构建哈夫曼树所需要的双亲parent,左孩子lchild,右孩子rchild。同时建立结构体数组HTNodeht[80];typedefstruct{charcd[30];//字符串 intstart;}HCode;HCodehcd[80];功能:该结构体储存输入的字符。(2)算法设计本程序在运行过程中用到的算法是哈弗曼算法,它是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树,根据给定的n个权值构成n棵二叉树的集合,其中每棵二叉树中只有一个带权weight的根结点,左右子树均空,选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和,即为哈夫曼树算法。本程序先定义结构体,通过创建哈弗曼树,对输入的字符进行编码和译码。(1)函数调用关系图及其说明如下:哈夫曼编/译码器主函数main()初始化哈弗曼树CreateHT()输入CodeInput()显示哈夫曼树Shuchu()哈夫曼编码CreateHCode()保存save()结束exit()(2)函数接口说明:函数中的参数均是使用的全局变量的传递,因而在函数间进行传递的过程中比较简单,下面就将主要函数及他们之间的参数的关系列出如下:voidCodeInput(intn,HTNodeht[])//输入字符及权值进行哈夫曼编码voidCreateHCode(HTNodeht[],HCodehcd[],intn)//进行哈夫曼编码voidCodeOutput(intn,HCodehcd[])函数输出哈夫曼编码。voidshuchu(HCodehcd[],intn)//输出哈夫曼树voidsave(intn)//,在弹出的窗口中,会提示要输入的信息:(1)界面信息:显示5个选项,分别为1:输入哈夫曼树2:哈夫曼编码3:显示哈夫曼树4:哈夫曼权值存储5:退出。(2)操作:用户输入界面的1-5选项,若输入其他选项则提示("输入有误!请输入<1--5>选项),程序分别调用相关函数。(3)用户需要输入哈夫曼树,程序会生成哈夫曼编码和哈夫曼树并显示在屏幕上,可以对哈夫曼权值保存。当退出时,选择5直接退出。:asdfgh789452程序运行结果如下:图1:菜单显示界面,选择操作类型。图2:选择1,输入哈夫曼树,先输入所有字符然后输入权值。图3:选择2,输出哈夫曼编码。图4:选择3,显示哈夫曼树。图5:选择4,保存哈夫曼权值到"d:\\"。图6:选择5,退出程序。,遇到了很多困难,之前对哈夫曼算法不是很了解,在编写源代码时有很多知识都忘了,多次翻阅课本学习,网上查找相关资料,使得编写的效率很慢。调试程序的过程中,出现了很多错误,逐个分析每一个错误,我学到了很多东西,比如一些课上没有懂的知识,我通过实践搞懂了,而且通过此次的课程设计,让我更深入的理解数据结构,并且还运用了以前所学的有关C语言的知识,并且应用到我的程序中去,