应用数据结构课程设计(哈夫曼树).docx

课程设计题目Huffman编/译码器学院管理学院专业信息管理与信息系统班级0801课程设计任务书题目:Huffman编/译码器初始条件:,降低传输成本,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个Huffman码的编/译码系统。要求完成的主要任务:(包括课程设计工作量及其技术要求、说明书撰写等具体要求)一个完整的系统应具有以下功能:(l)I:初始化。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。(2)E:编码。利用已建好的Huffman树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。(3)D:译码。利用已建好的Huffman树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。(4)P:印代码文件。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。(5)T:印哈夫曼树。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。时间安排::2010年07月02日系主任(或责任教师)签名:2010年07月02日需求分析程序的任务:,降低传输成本,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。此程序就是为这样的信息收发站写一个Huffman码的编/译码系统。程序的输入和输出:从终端读入字符集大小n,以及n个字符及各个字符的权值,建立赫夫曼树,并将它存储到文件hfmTree中;利用已建好的赫夫曼树将文件中的字符编码,如果赫夫曼树不在内存中,则从文件hfmTree中读取到内存;将译得的代码存到文件CodeFile中;利用已建好的赫夫曼树对CodeFile中的代码进行译码,将结果存入文件TextFile中;最后将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。程序要达到的功能:用户可以利用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文件的形式存到相应的文件里面。测试数据如下表:(l)利用教材中的数据调试程序。(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:"THISPROGRAMISMYFAVORITE"。字符ABCDEFGHIJKLMNOPQRSTUVWXYZ频度18664132232103211547571532205763151485180238181161选择E,输入THISPROGRAMISMYFAVORITE,屏幕上显示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同时文件codefile里面也出现相应的代码选择D,从codefile中调入代码,终端显示THISPROGRAMISMYFAVORITE,并且文件textfile中也相应的存入了这段话。选择P,文件CodeFile以紧凑格式显示在终端上。选择T,将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。选择其他的字母,将出现出错提示,并重新回到选择菜单。概要设计ADTBinaryTree{数据对象D:D是具有相同特性的数据元素集合。数据关系R:若D为空,则R为空,称Huffmantree为空霍夫曼树; 若D不为空,则R={H},H是如下的二元关系:1、H满足二叉树的所有要求;2、H中所有数乘以该数所在节点的深度值之后和最小。基本操作P:InputHuffman(HuffmanHfm) 操作结果:输入并存储字符和相应权值。 Select(HuffmanTreeHT,intend,int*s1,int*s2) 初始条件:频率数组已经建立。操作结果:选择HT[1....i-1]中无双亲且权值最小的两个节点,其序号