课程设计(论文)任务书软件学院软件+电气专业 1 班一、课程设计(论文)题目哈夫曼树及其编码二、课程设计(论文)工作自 2015年 1 月 5 日起至 2015年 1 月 9日止。
三、课程设计(论文) 地点: 创新大楼303,305四、课程设计(论文)内容要求：1．课程设计的目的为了配合《数据结构》课程的教学，使学生能更深刻的领会《数据结构》课程的重要性，特开设此课程设计；编写一些在特定数据结构上的算法，通过上机调试，更好的掌握各种数据结构及其特点，培养学生综合运用所学理论知识解决复杂实际问题的实践能力、研究性学习能力和团队合作能力。
2．课程设计的任务及要求1）基本要求（1）课程设计前必须选定课程设计题目，并认真进行需求分析与系统设计；（2）上机调试之前要认真准备实验程序及调试时所需的测试数据；（3）独立思考，独立完成，严禁抄袭，调试过程要规范，认真记录调试结果；（4）上机结束后认真规范撰写课设报告，对设计进行总结和讨论。
2）课程设计论文编写要求（1）要按照书稿的规格撰写打印课设论文（2）论文包括任务书、目录、绪论、正文、总结、参考文献、附录等（3）正文中要有问题描述、抽象数据类型的定义、数据的存储结构、设计的求解算法、算法的实现、调试分析与测试结果（4）课设论文装订按学校的统一要求完成3）课设考核从以下几方面来考查：（1）考勤和态度；（2）任务的难易程度及设计思路；（3）动手调试能力；（4）论文撰写的水平、格式的规范性。
4）参考文献[1] 严蔚敏, 吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社,2007年.[2] 严蔚敏, 吴伟民. 数据结构题集（C语言版）[M]. 北京：清华大学出版社, 2007年.[3] 谭浩强. C语言程序设计[M]. 北京：清华大学出版社，2006年.5）课程设计进度安排内容天数地点构思及收集资料1图书馆程序设计与调试3计算机房撰写论文1图书馆6）任务及具体要求⑴初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；⑵编码：利用建好的哈夫曼树生成哈夫曼编码；⑶输出其哈夫曼树及哈夫曼编码；⑷设字符集及频度如下表：字符空格 A B C D E F G H I J K L M频度 197 64 13 22 32 103 21 15 47 57 5 1 20 32字符 N O P Q R S T U V W X Y Z频度 57 63 1 15 48 16 80 23 8 18 1 51 1学生签名：年月日课程设计(论文)评审意见（1）考勤和态度：优（）、良（）、中（）、一般（）、差（）（2）任务难易及设计思路：优（）、良（）、中（）、一般（）、差（）（3）动手调试能力评价：优（）、良（）、中（）、一般（）、差（）（4）论文撰写水平及规范性评价：优（）、良（）、中（）、一般（）、差（）评阅人：职称：讲师年月日目录1 设计任务 (1)2 需求分析 (1)3 概要设计 (1)3.1模块设计 (1)3.2系统子程序即功能设计 (1)4 详细设计 (2)5 编码实现 (3)5.1数据类型定义 (3)5.2哈夫曼编码模块设计 (3)5.3主程序模块 (6)6 调试分析 (7)7 课设总结 (9)参考文献 (9)附录 (10)一设计任务问题描述：设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。
基本要求：⑴初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；⑵编码：利用建好的哈夫曼树生成哈夫曼编码；⑶输出其哈夫曼树及哈夫曼编码；⑷设字符集及频度如下表：字符空格 A B C D E F G H I J K L M频度 197 64 13 22 32 103 21 15 47 57 5 1 20 32字符 N O P Q R S T U V W X Y Z频度 57 63 1 15 48 16 80 23 8 18 1 51 1二需求分析（1）设计哈夫曼树。
具体构造方法如下：以字符集（空格 A B C D E F G H I J K N O P Q R S T U V W X Y Z L M）作为叶子结点。
以各字母出现的次数即频度（197 64 13 22 32 103 21 15 47 57 5 1 20 32 57 63 1 15 48 16 80 23 8 18 1 51 1）作为叶子结点的权值构造一棵哈夫曼树。
（2）设计哈哈夫曼。
按照构造出来的哈夫曼树，规定哈夫曼树的左分支为0，右分支为1，则从根结点到每个叶子结点所经过的分支对应的0和1 组成的序列便为该结点对应字符的哈夫曼编码。
三概要设计3.1模块设计本程序包含3个模块：主程序模块，哈夫曼编码模块，和选择模块。
其调用关系如下图所示。
3.2系统子程序即功能设计本程序共设置2个子程序，各子程序的函数名及各功能说明如（1）void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC（2）void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点四详细设计1问题分析哈夫曼树的定义1）哈夫曼树节点的数据类型定义为：typedef struc t //赫夫曼树的结构体{ char ch;int weight; //权值int parent,lchild,rchild;}htnode,*hfmtree;2）所实现的功能函数如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。
此函数块调用了Select（）函数。
2、void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点2、 int main()主函数：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）对文件中的正文进行编码，然后将结果存入文件codefile.txt中。
如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran.中。
读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。
3、Encoding 编码功能：对输入字符进行编码4、Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。
Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。
5.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。
使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。
系统结构图（功能模块图）五编码实现5.1数据类型定义typedef struct{ //赫夫曼树的结构体char ch;int weight; //权值int parent,lchild,rchild;}htnode,*hfmtree;typedef char **hfmcode;5.2哈夫曼编码模块设计哈夫曼编码模块设计分为两步：首先构造哈夫曼树，然后完成哈夫曼编码。
void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点{int i,j,x,y;for(j=1;j<=a;++j){if(HT[j].parent==0){x=j;break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[x].weight&&HT[i].parent==0){x=i; //选出最小的节点}}for(j=1;j<=a;++j) {if(HT[j].parent==0&&x!=j){y=j;break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i){y=i; //选出次小的节点}}if(x>y){*p1=y;*p2=x;}else{*p1=x;*p2=y;}}void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC{int i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1){return;}m=2*n-1;HT=(hfmtree)malloc((m+1)*sizeof(htnode));for(i=1;i<=n;++i) //初始化n个叶子结点{printf("请输入第%d字符信息和权值：",i);scanf("%c%d",&z,&w);while(getchar()!='\n'){continue;}HT[i].ch=z;HT[i].weight=w;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(;i<=m;++i) //初始化其余的结点{HT[i].ch='0';HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;++i) //建立赫夫曼树{Select(HT,i-1,&p1,&p2);HT[p1].parent=i;HT[p2].parent=i;HT[i].lchild=p1;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;}HC=(hfmcode)malloc((n+1)*sizeof(char *));cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;++i) //给n个字符编码{start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) {if(HT[f].lchild==c){cd[--start]='0';}else{cd[--start]='1';}}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}5.3主程序模块详见源代码六调试分析编码译码退出七课设总结通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。