实验课程名称      数据结构课程设计                           
专  业 班 级                               
学  生 姓 名                                     
学        号                                   
指  导 教 师                                       
  2012  至  2013  学年第 一 学期第 1 至 18 周
目录
一、 概  述    2
1.1课程设计的背景    2
1.2 赫夫曼树    2
1.3 课程设计目的    2
二、系统分析    3
2.1 课程设计的主要内容    3
2.2功能设计    3
三、概要设计    4
3.1 设计思想    4
3.2 函数间的关系    4
四、详细设计    5
五、运行于测试    8
六、总结与心得    11
附录：程序代码    12
试验题目：赫夫曼编码的应用
一、 概  述
1.1课程设计的背景
当下，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络传送时间已越来越引起人们的重视，赫夫曼编码正是一种运用广泛且非常有效的数据压缩技术。
1.2 赫夫曼树
    赫夫曼编码就是利用赫夫曼树求得用于通信的二进制编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示为“0码”，指向右子树的分支表示为“1”码，取每条路径上的“0”和“1”的序列作为和各个叶子对应的字符的编码，这就是所谓的赫夫曼编码。
1.3 课程设计目的
本试验就是通过先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。
二、系统分析
2.1 课程设计的主要内容
本实验要求完成发送端对等待传送数据的编码和接收端对传送来的数据的译码。要实现五个功能：接受原始数据、编码、译码、输出编码、译码存档。通过系统的提示要建立赫夫曼树并对载入的原文件进行编码，并保存到文件中，同时输出到屏幕。最后将建立的赫夫曼树用某种的存储方式存储后输出。
2.2功能设计
（1）初始化（initialization）  从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树。并将它存放于文件中。
（2）编  码（encoding）    二叉树的遍历及应用实验报告利用已经建立好的赫夫曼树（如不在内存，则从文件中读入，对文件中的正文进行编码。然后将结果存在文件中。
（3）译 码（decoding）  利用已经建立好的赫夫曼树将文件中的代码进行译码，将结果存入文件中。
（4）输出译码（print）  将文件以紧凑格式显示在终端上。同时将字符型式写入到文件中。
（5）显示赫夫曼树（treeprint）  将已经在内存中的赫夫曼树以直观的方式显示在屏幕上，同时将此字符型的赫夫曼树写入文件中。
三、概要设计
3.1 设计思想
  赫夫曼树用邻接矩阵来作为存储结构，借助静态链表来实现遍历。
3.2 函数间的关系
 
四、详细设计
1．赫夫曼树的抽象数据类型定义
ADT  HuffmanCoding{
数据对象 T：具有相同特征的数据元素的集合
数据关系 R：满足最优二叉树的关系
基本操作 P：
Init （&t）
操作结果：构造一个空赫夫曼树t。
Encode（）
操作结果：利用赫夫曼树进行编码
Decode（）
操作结果：利用赫夫曼进行译码
}
2．主函数
void mian（）
{打印表头：
while（选择选项不为0）
{输入选项：
switch(选择项)
{
case 1：初始化；break；
case 2：输入编码字符；break；
case 3：编码字符；break；
case 4：译码操作；break；
case 5：输出译码；break；
case 6：显示赫夫曼树；break；
default ：输入错误，重新选择；
}
3．求赫夫曼编码
if(t[j].weight<k&&t[j].parent==0)   
k=t[j].weight,flag=j; //flag为标志符，为不小于可能的值
t[flag].parent=1;
4．新建赫夫曼树
HT[s1].parent=HT[s2].parent=i;//将选好的两个结点设置成有同一个双亲结点                HT[i].lchild=s1;//左孩子的权值               
HT[i].rchild=s2;//右孩子的权值
HT[i].weight=HT[s1].weight+HT[s2].weight;//将两个权值相加作为新的权值        }            HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//为赫夫曼代码分配空间
5．将赫夫曼编码写入文件
用fputs(HC[i],htmTree); fputs(r,htmTree);fclose(htmTree) 这些函数来实现编码写入文件;
6．完成译码功能并将译码写入文件
因为赫夫曼树建好后是左孩子结点旁标上0，右孩子结点上标上1 所以碰到1是用左孩子结点，2是用右孩子结点，可以用条件语句来实现。         
if(i2=='0') m=HT[m].lchild;   
if(i2=='1') m=HT[m].rchild;
fputs(outext,txtfile);//将译码写入文件
五、运行于测试
1.程序运行后，出现如下主界面：
2.执行其它操作之前必须进行初始化，选择“1”执行，并输入结点数
3.依次按提示输入字符集并输入相应的权值,输入后会自动写入根目录下文件中。
4．输入要编码的字符，如下图：
6．编码，对目录下文件进行编码，编码完成后将写入目录下文件中。
7.译码，即对目录下文件中的字符进行译码，译码完成后，内容将会被写入到目录下文件中。
8．输出译码，即将中的编码字符。
9．显示赫夫曼树：
六、总结与心得
  通过两个学期对数据结构课程设计的学习，从中认识到怎样将知识迁移运用，深刻的知道了理论应用和实际相互间的密切联系，感受到了理论知识的重要，在今后的学习中一定会更加努力，认真，并且将理论与实践相结合。
在做这个课程设计论文的时候，我遇到过许多的问题，比如说，写程序以及调试程序时，有
很多地方的错误都搞不懂，不过在同学的帮助下，我成功的调试出了程序，并运行出了结果，当时我感觉非常有成就感。还有就是论文格式上，之前都没有学习过，不过通过老师讲解以及网上百度，最终我还是把它搞懂了，总之，觉得这门课程我收获了很多课堂外不能学到的东西。非常让我受益匪浅！ 通过这门课程的学习，我也确实体会到了自己的知识还有很多不足之处和个人能力的十分有限，只有通过同学、老师间的密切配合才能完成一项不错的工作。 不过从中我也体会到了在学习中也有无限的乐趣，可以将现实生活中某一问题用程序编写出来并将以调试，得出结果。 在这里也要感谢老师和同学们对我的帮助，有你们的帮助，我才会学得更好。

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