《应用数据结构课程设计》由会员分享，可在线阅读，更多相关《应用数据结构课程设计（37页珍藏版）》请在金锄头文库上搜索。
1、学 号：0120803490117课程设计题目学院专业Huffman 编译码器管理学院信息管理与信息系统班级0801姓名王涛指导教师燕翔2010年07月09日课程设计任务书学生姓名：王涛专业班级：信管0801指导教师：燕翔工作单位：管理学院题目：Huffman 编译码器初始条件：利用 Huffman 编码进行通信可以大大提高信道利用率缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编译码系统。试为这样的信息收发站写一个 Huffman 码的编译码系统。要求完成
2、的主要任务 : （包括课程设计工作量及其技术要求、说明书撰写等具体要求）一个完整的系统应具有以下功能：（l ）I ：初始化。从终端读入字符集大小n，以及n 个字符和n 个权值，建立哈夫曼树，并将它存于文件hfmTree 中。（2）E：编码。利用已建好的 Huffman 树（如不在内存，则从文件 hfmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。（3）D：译码。利用已建好的 Huffman 树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。（4）P：印代码文件。将文件 CodeFile 以紧凑格式显示在
3、终端上， 每行 50 个代码。（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频度 1866413223210321154757153220576315148518023 8181
6、161选 择E ， 输 入THISPROGRAMISMY FAVORITE， 屏 幕 上 显 示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同时文件 codefile里面也出现相应的代码选择 D，从 codefile中调入代码，终端显示THIS PROGRAM IS MY FAVORITE，1并且文件 textfile中也相应的存入了这段话。选择 P，文件 CodeFile 以紧凑格式显示在终端上。选择
7、T，将已在内存中的哈夫曼树以直观的方式 （树或凹入表形式） 显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。选择其他的字母，将出现出错提示，并重新回到选择菜单。2. 概要设计ADT BinaryTree 数据对象 D：D 是具有相同特性的数据元素集合。数据关系 R：若 D 为空，则 R 为空，称 Huffmantree 为空霍夫曼树；若 D不为空，则 R=H，H是如下的二元关系：1、 H 满足二叉树的所有要求；2、 H 中所有数乘以该数所在节点的深度值之后和最小。基本操作 P：InputHuffman(Huffman Hfm)操作结果：输入并存储字符和相应权值。Sel
8、ect(HuffmanTree HT,int end,int *s1,int *s2)初始条件：频率数组已经建立。操作结果：选择 HT1.i-1中无双亲且权值最小的两个节点，其序号为 s1，s2。HuffmanCoding(Huffman Hfm)初始条件：频率数组已经建立。操作结果： w 存放 n 个字符的权值（均 0），构造赫夫曼树 HT ，并求出 n 个字符的构造赫夫曼编码 HC 。InitHuffman(Huffman Hfm)初始条件：频率数组已经建立。操作结果：要求用户输入字符和相应权值，初始化赫夫曼数Encoding(Huffman Hfm)初始条件：霍夫曼树HuffmanTre
9、e 已经存在。操作结果：利用已建好的Huffman 树（如不在内存，则从文件2hfmTree 中读入），对文件 ToBeTran 中的正文进行编码， 然后将结果存入文件 CodeFile 中。Decoding(Huffman Hfm)初始条件：霍夫曼树HuffmanTree 已经存在。操作结果：利用已建好的 Huffman 树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。Print(Huffman Hfm)初始条件：霍夫曼树HoffmanTree 已经存在。操作结果：将文件 CodeFile 以紧凑格式显示在终端上， 每行 50 个代码。Treeprint(Huf
10、fman Hfm)初始条件：霍夫曼树HuffmanTree 已经存在。操作结果：将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。 ADT HuffmanTree2. 2 主程序流程Void main()显示菜单；Switch(k)I ：初始化E：编码D：译码P：印代码文件T：印哈夫曼树Q：退出运行32.3程序调用模块Main 函数InitHuffmanEncodingDecodingPrintTreeprintQuit3. 详细设计3.1 数据类型：typedef char *HuffmanCode;/动态分配数组存储霍夫曼表码表t
11、ypedef structunsigned intweight;unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;/ 动态分配数组存储霍夫曼树 typedef structHuffmanTree HT;char*c;intlength;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)；4其他模块：void Select(HuffmanTree HT,int end,int *s1,int *s2)/ 选择 HT1.i-1中无双亲且权值最小的两个节点，其序号为s1，s2FOR (i=1;i*s1IF(HTi.parent是次最小的 )THEN HTi.parent *s2Huffman HuffmanCoding(Huffman Hfm) /w 存放 n 个字符的权值（均 0），构造赫夫曼树 HT，并求出 n 个字符
