《应用数据结构课程设计(哈夫曼树)[1].doc》由会员分享，可在线阅读，更多相关《应用数据结构课程设计(哈夫曼树)[1].doc（33页珍藏版）》请在金锄头文库上搜索。
1、 学 号： 0120803490117课 程 设 计题 目Huffman编译码器学 院管理学院专 业信息管理与信息系统班 级0801姓 名王涛指导教师燕翔2010年07月09日课程设计任务书学生姓名： 王涛 专业班级： 信管0801 指导教师： 燕翔 工作单位： 管理学院 题 目： Huffman编译码器初始条件：利用Huffman编码进行通信可以大大提高信道利用率缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编译码系统。试为这样的信息收发站写一个Huffma
2、n码的编译码系统。要求完成的主要任务: （包括课程设计工作量及其技术要求、说明书撰写等具体要求）一个完整的系统应具有以下功能：（l）I：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码。利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码。利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50
3、个代码。（5）T：印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。时间安排：序号设计内容所用时间1问题分析和任务定义0.5天2数据类型和系统设计0.5天3编码实现和静态检查3天4上机准备和上机调试2天5总结和整理设计报告1天合 计7天指导教师签名： 2010年 07月02日系主任（或责任教师）签名： 2010年 07月02日1. 需求分析1.1 程序的任务：利用Huffman编码进行通信可以大大提高信道利用率缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据
4、进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编译码系统。此程序就是为这样的信息收发站写一个Huffman码的编译码系统。1.2 程序的输入和输出：从终端读入字符集大小n，以及n个字符及各个字符的权值，建立赫夫曼树，并将它存储到文件hfmTree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫夫曼树不在内存中，则从文件hfmTree中读取到内存；将译得的代码存到文件CodeFile中；利用已建好的赫夫曼树对CodeFile中的代码进行译码，将结果存入文件TextFile中；最后将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式
5、的哈夫曼树写入文件TreePrint中。1.3 程序要达到的功能：用户可以利用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文件的形式存到相应的文件里面。1.4 测试数据如下表：（l）利用教材中的数据调试程序。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：THIS PROGRAM IS MY FAVORITE。字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ频度18664132232103211547571532205763151485180238181161 选择E，输入THIS PROGRAM IS MY FAVORI
6、TE，屏幕上显示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同时文件codefile里面也出现相应的代码选择D，从codefile中调入代码，终端显示THIS PROGRAM IS MY FAVORITE，并且文件textfile中也相应的存入了这段话。选择P，文件CodeFile以紧凑格式显示在终端上。选择T，将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写
7、入文件TreePrint中。选择其他的字母，将出现出错提示，并重新回到选择菜单。2. 概要设计ADT BinaryTree数据对象D：D是具有相同特性的数据元素集合。数据关系R：若D为空，则R为空，称Huffmantree为空霍夫曼树； 若D不为空，则R=H，H是如下的二元关系：1、 H满足二叉树的所有要求；2、 H中所有数乘以该数所在节点的深度值之后和最小。基本操作P： InputHuffman(Huffman Hfm) 操作结果：输入并存储字符和相应权值。Select(HuffmanTree HT,int end,int *s1,int *s2)初始条件：频率数组已经建立。操作结果：选择H
8、T1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2。HuffmanCoding(Huffman Hfm)初始条件：频率数组已经建立。操作结果：w存放n个字符的权值（均0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC。 InitHuffman(Huffman Hfm) 初始条件：频率数组已经建立。 操作结果：要求用户输入字符和相应权值，初始化赫夫曼数 Encoding(Huffman Hfm) 初始条件：霍夫曼树HuffmanTree已经存在。 操作结果：利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结
9、果存入文件CodeFile中。 Decoding(Huffman Hfm) 初始条件：霍夫曼树HuffmanTree已经存在。 操作结果：利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 Print(Huffman Hfm) 初始条件：霍夫曼树HoffmanTree已经存在。 操作结果：将文件CodeFile以紧凑格式显示在终端上，每行50 个代码。 Treeprint(Huffman Hfm) 初始条件：霍夫曼树HuffmanTree已经存在。 操作结果：将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件T
10、reePrint中。ADT HuffmanTree2. 2 主程序流程Void main() 显示菜单； Switch(k) I：初始化E：编码D：译码P：印代码文件T：印哈夫曼树Q：退出运行 2.3 程序调用模块 Main函数 InitHuffmanEncodingDecodingPrintTreeprintQuit3. 详细设计3.1数据类型： typedef char *HuffmanCode;/动态分配数组存储霍夫曼表码表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*Huffm
11、anTree;/动态分配数组存储霍夫曼树typedef struct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/分配数组存储字符串及其对应的霍夫曼树Huffman Hfm;char k; /*控制循环的标志*/3.2 伪码算法：主程序main()InitHuffman(Huffman Hfm)；Encoding(Huffman Hfm)；Decoding(Huffman Hfm)；Print(Huffman Hfm)；Treeprint(Huffman Hfm)；其他模块：void Select(HuffmanTr
12、ee HT,int end,int *s1,int *s2)/选择HT1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2 FOR (i=1;i*s1 IF(HTi.parent是次最小的) THEN HTi.parent*s2 Huffman HuffmanCoding(Huffman Hfm) /w存放n个字符的权值（均0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC FOR(i=n+1;i=2*n-1;+i) /选择HT1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2 Select(Hfm.HT,i-1,&s1,&s2); 修改父亲位置； 修改孩子位置； 父亲结点权值为左右孩子权值之和； /从叶子结点到根逆向求每个字符的赫夫曼编码 FOR(i=1;i=n;+i)/逐个字符求赫夫曼编码 start=n-1;/编码结束符位置for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/从叶子到根逆向求编码 IF(c=Hfm.HTf.lchild) cd-start=0; ELSE cd-start=1; 再从cd复制编码到Hfm.HC RETURN Hfm;Huffman I
