数据结构课程设计哈夫曼树的应用

1、武汉理工大学华夏学院课程设计报告书课程名称： 数据结构课程设计 题 目： 哈夫曼树的应用 系 名： 信息工程系 专业班级： 计算机科学与技术 姓 名： 学 号： 指导教师: 2011 年 7 月 1 日课程设计任务书学生姓名： 专业班级： 计算机 指导教师： 工作单位： 信息工程系 题 目: 哈夫曼树的应用初始条件：理论：学习了数据结构课程，掌握了基本的数据结构和常用的算法；实践：信息工程系实验室提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）输入一组数据建立哈夫曼树（2）设计哈夫曼码（3）实现译码2、数据

2、结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试等；（4）结束语；（5）参考文献。时间安排： 2011年6月27日2011年7月1日 （第19周）星期一 查阅资料星期二 系统设计，数据结构设计，算法设计星期三-星期四 编程并上机调试星期五 撰写报告星期五 验收程序，提交设计报告书。指导教师签名： 2011年6月27日 系主任（或责任教师）签名： 2011年6月27日 目 录1 引言 42 需求分析 43 数据结构与算法设计3.1数据结构设计 53.2算法设计 5

3、4 程序的实现 85 程序测试 146 结束语 6.1设计体会 16 6.2心得体会 16参考文献 161. 引言数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构及其相应的算法并初步掌握算法的时间分析和空间分析的技术。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各

4、种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。而此次课程设计通过对哈夫曼树的概念、构造算法的理解，进行编码，从而掌握赫夫曼树的编码原则。2.需求分析数据的读入存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题霍夫曼（huffman）编码原理是一种利用二叉树实现的编码原理霍夫曼（huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。 霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长

5、。这样，处理全部信息的总码长一定小于实际信息的符号长度。锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。在信息传递时，希望长度能尽可能短，即采用最短码。赫夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。3.数据结构与算法设计3.1数据结构设计,为包含的库函数#define namemax 20#define codemax 30 定义最大值typedef unsigned int uint;typedef char namenamemax;typedef char codecodemax;

6、定义各量类型void menu(); /* 定义menu菜单 */void input(); /* 输入函数 */void huffmancoding(huffmantree *ht,name *str,int *w,int n)建立哈夫曼树int huffmancoding(huffmantree *ht,name *str,int *w,int n)构建哈夫曼编码typedef struct name name; /* 字符 */ code code; /* 编码 */ uint weight; /* 权值 */ uint parent,lchild,rchild; /* */htnode

7、,*huffmantree; 3.2算法设计哈夫曼树编码算法：void huffmancoding(huffmantree *ht,name *str,int *w,int n) int i,s1,s2,start; unsigned c,f; huffmantree p; char *cd; if(ncodemax)return; *ht=(huffmantree)malloc(2*n*sizeof(htnode); for(p=*ht+1,i=1;i=n;+i,+p,+w) strcpy(*p).name,stri-1); (*p).weight=*w; (*p).parent=0; (*

8、p).lchild=0; (*p).rchild=0; for(;i=2*n-1;+i,+p)(*p).parent=0; for(i=n+1;i2*n;+i) select(*ht,i-1,&s1,&s2); (*ht)s1.parent=(*ht)s2.parent=i; (*ht)i.lchild=s1; (*ht)i.rchild=s2; (*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i1): ); scanf(%d,&n); w=(int*)

9、malloc(n*sizeof(int); str=(name*)malloc(n*sizeof(name); printf(请依次输入%d个符号(回车分隔):n,n); for(i=0;in;i+)scanf(%s,stri); printf(请依次输入%d个权值(整型):n,n); for(i=0;in;i+)scanf(%d,w+i); huffmancoding(&ht,str,w,n); for(i=1;i=n;i+)printf(%s-%sn,ht,hti.code); printf(请输入你要查的字符n); scanf(%s,temp); for(i=1;i=n;i+

10、) if(!strcmp(ht,temp)printf(%sn,hti.code); printf(请输入你要查的编码n); scanf(%s,temp); for(i=1;i=n;i+) if(!strcmp(hti.code,temp)printf(%sn,ht); printf(n按回车键返回主菜单n); getch(); menu(); 4.程序的实现#include#include#include#define namemax 20#define codemax 30typedef unsigned int uint;typedef char namename

11、max;typedef char codecodemax; typedef struct name name; code code; uint weight; uint parent,lchild,rchild;htnode,*huffmantree; void menu(); /* 定义menu菜单 */void input(); /* 输入函数 */ void menu() int select; system(cls); printf(ttt哈夫曼树的应用n); printf(*n); printf(* * n); printf(*1输入哈弗曼树的基本情况并查找 n); printf(*

12、2退出 n); printf(* * n); printf(*n); printf(请输入你的选项(1-2)：); scanf(%d,&select); switch(select) /* 判断选择 */ case 1:input();break; case 2:exit(0);break; void input() huffmantree ht; int *w,n,i; name *str; char temp50; system(cls); /* 清屏 */ printf(请输入权值的个数(1): ); scanf(%d,&n); w=(int*)malloc(n*sizeof(int);

13、 str=(name*)malloc(n*sizeof(name); printf(请依次输入%d个符号(回车分隔):n,n); for(i=0;in;i+)scanf(%s,stri); printf(请依次输入%d个权值(整型):n,n); for(i=0;in;i+)scanf(%d,w+i); huffmancoding(&ht,str,w,n); for(i=1;i=n;i+)printf(%s-%sn,ht,hti.code); printf(请输入你要查的字符n); scanf(%s,temp); for(i=1;i=n;i+) if(!strcmp(ht

14、,temp)printf(%sn,hti.code); printf(请输入你要查的编码n); scanf(%s,temp); for(i=1;i=n;i+) if(!strcmp(hti.code,temp)printf(%sn,ht); printf(n按回车键返回主菜单n); getch(); menu(); int minnode(huffmantree t,int i) int j,flag; unsigned int k=0xffffffff; for(j=1;j=i;j+) if(tj.weight*s2) j=*s1; *s1=*s2; *s2=j; int huf

15、fmancoding(huffmantree *ht,name *str,int *w,int n) int i,s1,s2,start; unsigned c,f; huffmantree p; char *cd; if(ncodemax)return; *ht=(huffmantree)malloc(2*n*sizeof(htnode); for(p=*ht+1,i=1;i=n;+i,+p,+w) strcpy(*p).name,stri-1); (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(;i=2*n-

16、1;+i,+p)(*p).parent=0; for(i=n+1;i2*n;+i) select(*ht,i-1,&s1,&s2); (*ht)s1.parent=(*ht)s2.parent=i; (*ht)i.lchild=s1; (*ht)i.rchild=s2; (*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;i+) start=n-1; for(c=i,f=(*ht)i.parent;f!=0;c=f,f=(*ht)f.parent)

17、if(*ht)f.lchild=c)cd-start=0; else cd-start=1; strcpy(*ht)i.code,&cdstart); free(cd);int main() menu();5.程序测试5-1图 menu菜单图图5-2 输入各值并生成编码图图5-3 查找字符相对应的编码以及译码图5-4图 menu退出运行图6.结束语6.1设计体会当刚拿到程序课题时，一看，感觉都挺容易的，都是我们学过的一些内容，应该很容易完成，于是就从中选了一个哈夫曼树的应用。结果一作才知道，并不如我们想的那么容易。对于建立哈夫曼树，创建哈夫曼编码等算法，总是因一点不对而编译不成功。在int h

18、uffmancoding(huffmantree *ht,name *str,int *w,int n)中，其中的那个说明总是弄不对或是落东西。而在主函数main() menu();中，其中menu的调用更是老是编译不成功，导致运行不成功或出错。6.2心得体会忙碌了一个星期，终于顺利完成了对此程序的编译及试运行。通过数据结构课程设计，我的c语言水平有了比较大的提高，其中c语言关于指针，文件的操作理解的比以前深刻不少。另外是数据结构方面的提高，对哈夫曼树的构造，及哈夫曼码方面也有不少的提高。在项目中也出现了很多的问题，最大的问题就是对程序设计框架结构的不了解，在实现代码与功能的连接时经常会出现各种不同的错误，在实现一些功能时系统常常会报错。许多错误不知从哪修改，以致托了整个设计的后腿。课程设计中，既回顾了很多以前的东西，也发现了很多的问题，以前都没遇见过的，收获很大。通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识， 此次哈夫曼树的应用系统的设计让自己对数据结构的了解更深入。参考文献1魏江江 李玮琪 编著数据结构（c语言版），清华大学出版社，2009年9月2谭浩强 著c程序设计（第三版），清华大学出版社，2005年7月3徐孝凯 数据结构实用教程m， 清华大学出版社，19