数据结构课程设计-哈夫曼树

课程设计课程设计名称：数据结构课程设计专业班级：学生姓名：学号：指导教师：磊课程设计时间：2015.7.06—2015.7.10计算机类专业课程设计任务书学生专业班级学号题目哈夫曼树编/译码系统课题性质A课题来源D指导教师磊同组无主要容1.学习掌握并熟练运用C语言进行程序设计,2.针对具体应用问题，选择、设计和实现合适的抽象数据类型；3.进行整体设计使各个函数之间紧密联系起来；任务要求1.综合运用和融化所学理论知识，提高分析和解决实际问题的能力，达到培养良好程序设计能力和习惯的目的，为开发满足问题要求的小型应用软件奠定基础，达到软件工程的综合性基础训练的目的。,2.完成需求分析报告，报告中对关键部分给出图表说明。要求格式规，工作量饱满。参考文献《C语言程序设计》（第三版）谭浩强清华大学《CPrimerPlus》(第5版)Stephenprata人民邮电审查意见指导教师签字：教研室主任签字：年月日目录目录......................................................................................................................................................11需求分析...........................................................................................................................................21.1系统介绍...............................................................................................................................21.2程序的输入和输出................................................................................................................21.3程序要达到的功能................................................................................................................21.4调试过程介绍........................................................................................................................22概要设计...........................................................................................................................................32.1数据结构设计........................................................................................................................32.2系统模块设计........................................................................................................................33详细设计...........................................................................................................................................44系统演示.........................................................................................................................................124.1主界面.................................................................................................................................124.2数据录入.............................................................................................................................134.3翻译短文.............................................................................................................................134.4反译编码.............................................................................................................................144.5打印文件编码......................................................................................................................144.6打印哈夫曼树......................................................................................................................145运行环境.........................................................................................................................................156课程心得总结.................................................................................................................................16参考文献；........................................................................................................................................161需求分析1.1系统介绍利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。此程序就是为这样的信息收发站写一个Huffman码的编／译码系统。1.2程序的输入和输出从终端读入字符集大小n，以及n个字符及各个字符的权值，建立赫夫曼树，并将它存储到文件hfmTree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫夫曼树不在存中，则从文件hfmTree中读取到存；将译得的代码存到文件CodeFile中；利用已建好的赫夫曼树对CodeFile中的代码进行译码，将结果存入文件TextFile中；最后将已在存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。1.3程序要达到的功能用户可以利用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文件的形式存到相应的文件里面。1.4调试过程介绍（l）利用教材中的数据调试程序。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：THISPROGRAMISMYFAVORITE。字符ABCDEFGHIJKLMNOPQRSTUVWXYZ频度18664132232103211547571532205763151485180238181161选择2，输入THISPROGRAMISMYFAVORITE，屏幕上显示01010同时文件codefile里面也出现相应的代码选择3，从codefile中调入代码，终端显示THISPROGRAMISMYFAVORITE，并且文件textfile中也相应的存入了这段话。选择4，文件CodeFile以紧凑格式显示在终端上。选择5，将已在存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。选择其他的数字，将出现出错提示，并重新回到选择菜单。2概要设计2.1数据结构设计InitHuffman(HuffmanHfm)；//初始化哈夫曼树Encoding(HuffmanHfm)；//翻译短文Decoding(HuffmanHfm)；//反译编码Print1(HuffmanHfm)；//打印文件编码Print2(HuffmanHfm)；//打印哈夫曼树typedefchar**HuffmanCode;//动态分配数组存储霍夫曼表码表typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储霍夫曼树typedefstruct{HuffmanTreeHT;char*c;intlength;HuffmanCodeHC;}Huffman;//分配数组存储字符串及其对应的霍夫曼树HuffmanHfm;2.2系统模块设计哈夫曼树编/译码系统录入数据翻译短文反译编码打印文件编码打印哈夫曼树退出系统3详细设计#includestdio.h#includestring.h#includemalloc.h#includestdlib.h#defineNULL0#defineOK1#defineERROR0#defineOVERFLOW-2#defineMAX_NUM32767#defineMAX60typedefchar**HuffmanCode;//动态分配数组存储哈夫曼表码表typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefstruct{HuffmanTreeHT;char*c;intlength;HuffmanCodeHC;}Huffman;//全局结构体变量，来存储字符与代码/*------------------------------------------寻找权值最小的两个节点-------------------------------------*/voidSelect(HuffmanTreeHT,intend,int*s1,int*s2){inti;in