数据结构课程设计报告题目：哈夫曼树应用
学生姓名：廖科
学号：201117010218
专业班级： 11级计科2班
指导教师：邹汉斌
设计时间： 2012年下学期第17周
目录
(一) 设计要求 (1)
(二) 设计分析 (1)
程序功能介绍 (2)
主要的函数讲解 (3)
程序总流程图 (4)
(三) 程序实现（设计流程） (5)
程序设计分析 (5)
程序主要算法分析 (5)
程序运行结果 (6)
(四) 心得小结 (11)
(五) 参考文献 (11)
(一) 设计要求
（1）从终端读入字符集大小n，以及n个字符和n个权值或者从文件中读取，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；
（2）利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
（3）利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。
(二) 设计分析
本次的HuffmanTree程序是分为两个文件来写的,程序包括ch.h头文件和Huffman.cpp主程序文件。
其中ch.h文件里面定义了二位字符数组ch[][]，它里面存储了整个程序的汉字提示字符串，Huffman.cpp文件是主程序文件，它里面定义了HuffmanTree的数据结构类型HTnode、CHnode和WEnode等结构体节点，以及创建HuffmanTree、统计字符以及权值、对文件进行编码以及存储数据等函数。
HTnode节点定义为HuffmanTree的节点，在其中定义了该节点数据权值，以及该节点的双亲和左右孩子位置；CHnode节点定义为存储每个字符的信息，包括字符、其权值以及该字符通过编码后的Ｈuffman编码字符串的指向指针；WEnode节点定义为统计字符字符权值的中间链表节点，在其定义了字符信息以及其权值统计变量。
程序功能介绍：
1.创建HuffmanTree
在此选项中，我们可以选择构建HuffmanTree的数据来源。
(1)我们可以选择读取之前保存在HfmTree.txt文件中的WElist链表数据构建WElist 链表，然后根据WElist链表中的各个字符的权值构建HuffmanTree；
(2)我们还可以选择读取需要编译的ToBeTran.txt文件中的数据文本字符，然后统计各个字符的出现次数(也就是个字符的权值)分别根据字符插入到WElist链表，然后根据WElist链表中的各个字符的权值构建HuffmanTree；
(3)我们还可以选择直接输入各个字符以及它的权值，直接构建WElist链表，然后根据WElist链表中的各个字符的权值构建HuffmanTree；
2.编码ToBeTran文件
在此选项中，我们可以编码ToBeTran.txt文件。
选择该项后，程序会对ToBeTran.txt文件中的每个字符逐一按照构建的HuffmanTree 进行编码，你可以选择是否将编码结果保存到CodeFile.txt文件中，选择保存后，你可以选择直接打开文件查看其保存情况；然后程序会按照每行50个字符显示在屏幕上，当然你也可以选择将其保存到CodePrint.txt，你还可以选择直接打开文件查看其保存情况；3.译码CodeFile文件
在此选项中，我们可以译码CodeFile.txt文件。
选择该项后，程序会对CodeFile.txt文件中的每个字符逐一按照构建的HuffmanTree 进行译码，然后程序会将译码的文档显示在屏幕上，你可以选择是否将译码结果保存到TextFile.txt文件中，选择保存后，你可以选择直接打开文件查看其保存情况；
4.输出HuffmanTree
此选项会将生成的HuffmanTree显示在屏幕上供使用者核对，主要是为了了解HuffmanTree的生成情况以及了解各字符的权值大小。
5.输出Huffman编码
此选项会将ToBeTran.txt文件中字符的编码情况显示在屏幕上供使用者核对，在此可以了解各个字符的Huffman编码，也可以检查是否有字符误编。
6.清屏
此选项会将当前屏幕中的信息清空以为了更好的进行人机对话。
7.退出
该选项直接退出程序。
主要的函数讲解
在程序中我们实现其功能定义了各类功能函数，下面就以几个主要的函数讲解其实现。1：int create_WElist_file(WElist &WE,int &n)
调用此函数，程序会将ToBeTran.txt中的字符统计其权值，并将每个字符的信息以WE链表返回；
2：int init_HTlist_CHlist(HuffmanTree &HT,CHlist &CH,WElist WE,int n) 此函数是根据字符权值链表WE初始化HuffmanTree链表HT以及Huffman编码链表CH；3：int create_HuffmanTree(HuffmanTree &HT,int n)
该函数是创建HuffmanTree的主函数，其间会调用选择最优权值函数select(HuffmanTree HT,int n,int &s1,int &s2)；
4：int create_CHlist(HuffmanTree &HT,CHlist &CH,int n)
该函数是根据HuffmanTree中的信息编码Huffman编码链表中的字符并将其保存于Huffman编码链表中相应的位置；
5：int ToBeTran_file_bianma(CHlist CH,char *Huffman_bianma_id,int n) 该函数是将ToBeTran文件中的字符根据Huffman编码链表将其编译成相应的Huffman 编码，并保存到Huffman_bianma_id数组中返回；
6：int CodeFile_file_yima(HuffmanTree HT,CHlist CH,char *Huffman_bianma_id,int n) 该函数是将CodeFile文件中的Huffman编码根据HuffmanTree将其反编成相应的字符，并保存到Huffman_bianma_id数组中返回；
其它的保存函数以及一些调用函数就不一一说明了。
程序总流程图
(三) 程序实现（设计流程）
程序设计分析
首先对整个程序的功能进行分析，对各个数据进行定义，然后确定了数据类型主要有两个，分别是HuffmanTree的节点类型，以及进行编码的字符数据和Huffman编码的保存节点类型，分析得知，为了数据保存的简便性以及各函数的数据通用性，最后引入了WElist 链表，该链表存储了编码字符和其权值，然后根据该链表可以创建HuffmanTree和Huffman 编码链表，还有一个好处是：我们可以直接保存该链表的数据以及链表的长度就可以实现HuffmanTree的保存。
然后是对整个程序的功能进行规划，对程序的的函数进行一个大致的估计，并把一些主要的函数先写好框架，然后再进行具体功能的实现。如我就是先对其上的几个重要函数打好大致框架后再具体补充的。
最后是对程序的调试和优化，程序能运行后，我就找来一些可用的数据来测试程序的正确性，如程序的编码是否正确，程序遇到特殊的数据会不会崩溃等等。对程序的优化的话，我主要是对程序的人机对话语言进行仔细推敲，并把其单独存放到一个头文件当中，这样显得程序格式标准化，更利于别人的阅读，而且好的人机对话会更显得程序的人性化。程序主要算法分析
定义了HuffmanTree的节点类型
typedef struct HTnode{
int weight;
int parent,lchild,rchild;
} HTnode,*HuffmanTree;
首先以该节点开辟HuffmanTree线性链表，且该链表的1-n位节点位叶子节点，然后在该已知节点中选择没有被访问过的节点中选择两个最小权值的节点然后合并成一个节点插到尾部，并把这两个节点标记，直到所有节点处理完，这样就创建了HuffmanTree；
然后根据字符从HuffmanTree的叶子节点开始向根节点访问，并根据访问是上一个节点的左孩子则编码加‘0’，是右孩子则编码加‘1’，这样就完成了字符的编码过程；
最后是译码过程，将Huffman编码一个一个读取出来，从根节点出发，如果编码是‘0’，则访问其左孩子，编码是‘1’，则访问其右孩子，直到到达叶子节点，然后根据其叶子节点的位置得到其对应编码的字符，这样就完成了Huffman编码的译码过程。
程序运行结果
(1)进入主程序
(2)选择2选项读入文件
(3)保存HuffmanTree
(4)编码文件
(5)格式输出编码
(6)保存格式输入编码到文件
(7)输出译码后文件
(8)保存译码到文件
(9)输出HuffmanTree
(10)输出Huffman编码
(四) 心得小结
心得:
通过这一周的数据结构课程设计使我对编程技术有了更深的认识和理解，也使我更加明白实践在程序设计中的重要性和地位。
本次课程设计虽然经过自己的努力，实现了老师的要求，但功能还过于简单，处理问题还不够全面，而且还可能存在未知bug ！虽然程序过关了，但我还是会不断去优化它，改进它。如：我们可以增加对文件的编码，以达到加密文件和压缩文件大小；程序还可以选择用二进制保存文件，保证数据的安全信；还有输入可以设置保护，以免输错信息使程序进入死循环等等。
这次课程设计是老师给的题目，经过自己的努力，实现要求。在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中对所学的C语言的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之处，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机设计程序的重要作用，特别是对软件设计模块化有了深刻的理解。通过实际操作，我学会了C语言程序编程的实战步骤、基本方法，培养了自己的逻辑、思维分析问题、解决问题的能力。
总之，通过这次课程设计，我收获颇丰，相信会为自己以后的学习和工作带来很大的好处。最重要的还是激发了我编程的兴趣和热情，让我从一个只懂理论变成了能做一些小型程序，让我对编程更加热爱了。设计增强了我们用所学知识去解决具体问题的能力，进一步培养了我们独立思考问题和解决问题的能力。
(五) 参考文献
1.数据结构(C语言版) 清华大学出版社
2.C语言程序设计(第二版) 清华大学出版社