《应用数据结构课程设计》由会员分享,可在线阅读,更多相关《应用数据结构课程设计(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 个字符