数据结构课程设计(赫夫曼编码)

《数据结构课程设计(赫夫曼编码)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中南民族大学数据结构课程设计报告姓名：康宇年级：2010学号：10061014专业：计算机科学与技术指导老师：宋中山2013年4月15日实习报告：赫夫曼编/译码器实习报告题目：为信息收发站写一个赫夫曼码的编/译码系统班级：计科一班姓名：康宇学号：10061014完成日期：2013.4.5一、需求分析1、问题描述：利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端讲传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。2、基本要求：（1）I:初始化（In

2、itialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的赫夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D:译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P:印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5）T:印赫夫曼树（TreePrinting）。将已在内存

3、中的赫夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint中。3、实现提示：（1）编码结果以文本方式存储在文件CodeFile中。（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。二、概要设计1.元素类型：typedefstruct{intweigt;//权值intparent,lchild,rchild;//双亲，左孩子，右孩子}HTNode,*HuffmanTree;typedefchar**HuffmanCod

4、e;//存放各个字符的前缀编码1.本程序包括六个大板块：（1）主程序：intmain(){输出菜单；选择功能选项并调用对应的函数；}（2）初始化函数：voidInitialization(HuffmanTree&ht,FILE*fp){安全打开文件；输入字符数量以及各字符及其权值；对各节点进行初始化；创建赫夫曼列表；（需要调用Select()函数选择权职最小的两个节点）}voidSelect(HuffmanTree&ht,inti,int&s_1,int&s_2){找出第一个非零结点；找出第二个非零结点；遍历比较找出权值最小的两个节点；}（3）编码函数：voidEncoding(Huffma

5、nTree&ht,HuffmanCode&hc,FILE*fp1,FILE*fp2){安全打开文件；for:1àn,双亲不为空If(为左孩子)str[--start]='0';elsestr[--start]='1';储存各字符的编码；从文件中读取正文；依次遍历正文各字符，显示其编码；}（4）译码函数：voidDecoding(HuffmanTree&ht,HuffmanCode&hc,FILE*fp1,FILE*fp2){安全打开文件；While（成功读取字符）{遍历目前的编码中是否有对应的字符；if(有)输出该字符；else跳到循环体首；（再次读入一个字符再判断）}}（5）印代码文件：v

6、oidPrint(FILE*fp1,FILE*fp2){安全打开文件；从文件中读取字符，50个一行输出；}（6）印赫夫曼树：voidTreeprinting(HuffmanTreeht){安全打开文件；调用print_tree(ht,root)函数；}voidprint_tree(HuffmanTreeht,intr){if(存在节点){深度+1；递归调用print_tree(ht,ht[r].rchild);//先输出右子树用深度控制格式；输出对应的字符；递归调用print_tree(ht,ht[r].lchild);//再输出左子树深度-1}}一、详细设计#include

7、>#include#includetypedefstruct{intweigt;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//存放各个字符的前缀编码//此全局文件指针用于输出赫夫曼树到对应文件，便于调用递归FILE*TreePrint=NULL;char*s;//存放各字符