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

《数据结构》课程设计报告

题目: 哈夫曼树应用
学生姓名: 谢辉
学号: 201317010201
专业班级: 计科13102
同组姓名: 赵丽娜
指导教师: 徐晓蓉
设计时间: 2014年下学期第18周
指导老师意见:
评定成绩: 签名: 日期:
目录
一、 需求分析 2
1. 分析问题 2
2. 确定解决方案 2
3. 输入的形式和输入值的范围 3
3
3
二、概要设计 4
1. 主程序的流程图: 4
: 4
(调用)关系: 4
三、 详细设计 5
1. 哈夫曼树存储及类的定义: 5
: 6
7
四、 调试分析和测试结果. 9
1. 测试数据及其输出结果: 9
2. 调试过程中遇到的问题及解决办法: 13
五、 总结 14
六、 参考文献 14
七、 致谢 14
八、 附录 14
需求分析
分析问题
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/
译码系统。为这样的信息收发站写一个哈夫曼码的编/译码系统。
确定解决方案
设计建立带权的哈夫曼树,确定哈夫曼树的类与成员函数,以及各函数之间的调用关系,采用动态数组的存储结构存储所需要的数据,通过不同的函数来实现编码,译码以及打印二进制编码、哈夫曼树,把不同的数据存入不同的txt文件中,通过主函数调用来实现功能检测。
输入的形式和输入值的范围
手动或者从文本中读入数据的形式初始化哈夫曼树,从键盘中或者文件中读入数据,以字母A-Z代表结点,以自然数代表权值,字符串提示使用者所要执行的操作。
  
在显示器界面上或者以文本的形式来实现程序调试的输出。
 
(1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
(2)E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
(3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
(4)P:打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
测试数据:
利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符,,,,,,,,,试设计哈夫曼编码。
(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。
字符    空格    A    B    C    D    E    F    G    H    I    J    K    L    M
频度 64 13 22 32 103 21 15 47 57 1 5 32 20
字符    N    O    P    Q    R    S    T    U    V    W    X    Y    Z   
频度    57    63    15    1    48    51    80    23    8    18    1    16    1   
实现提示:
(1) 编码结果以文本方式存储在文件CodeFile中。
(2) 用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”,表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了“Q”为止。
(3) 在程序的一次执行过程中,第一次执行I,D或E命令之后,哈夫曼树已经在内存了,不必再读入。每次执行中不一定执行I命令,因为文件hfmTree可能早已建好。
二、概要设计





请重新输入选项
判断选项
是否正确
选择菜单项
主菜单
开始
1. 主程序的流程图:
是
否
图一:主程序流程图
 
:
用到三组结构体,分别是哈夫曼树的动态