数据结构实验三基于哈夫曼编码的通信系统.doc

《数据结构》课程实验 实 验 报 告 题目： 基于哈弗曼编码的通信系统的设计与实现 专业： 计算机科学与技术专业 班级： 计141班 姓名： 范浩玲 陈娟 孙妍 王文诗 吕惠擎 孙盼 完成日期： 2015年12月25日 实验三 基于哈夫曼编码的通信系统的设计与实现 试验内容 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个基于哈夫曼编码的通信系统. 一个完整的系统应具有以下功能： 1）初始化处理：建立通信系统 （1）建立有100句中文的信息集合，每个句子称为一条信息。 （2）输入编码参数： ① 从终端输入编码字符集大小n，字符编码长度m（设n为4，m为8）； ② 从终端输入编码字符（设为A，B，C，D）； （3）生成每条信息的字符编码，构造字符编码集合； （4）计算每个字符在字符编码集合中出现的概率； （5）根据字符概率构造哈夫曼树，求出每个字符的二进制编码。 2）发送端信息编码 （1）用户从信息集合中选择一条信息，找到该信息对应的字符编码； （2）根据该信息的字符编码，哈夫曼树求出的每个字符的二进制编码，构造出该信息的二进制编码，记录该二进制编码。（由于是软件模拟，没有发送设备，发送端的编码工作完成）。 3）接受端信息译码 （1）根据得到的信息的二进制编码，利用哈夫曼树求出的每个字符的二进制编码，还原出信息的字符编码； （2）根据信息的字符编码，找到对应的信息。 *实现提示 （1）本试验涉及到通讯学科的编码理论和信息学科的数据压缩技术。 （2）根据参数生成的通信系统的所有信息的有效存储问题。 （3）信息字符编码可参考随机数的方式生成，且要求保持唯一性。 试验目的 （1）掌握二叉树的存储结构及其相关操作。 （2）掌握构造哈夫曼树的基本思想，及其编码/译码过程。 三、流程图 源程序代码 #includeiostream #includecstdlib #includectime #includestring using namespace std; const int n=4;//叶子节点个数 const int MAXVALUE = 9999; int m,p; //编码参数 string l; int size; //构造哈夫曼树结点 typedef struct { int weight;//权值 int parent;//父节点 int lchild;//左子树 int rchild;//右子树 char word;//编码字符 }HNodeType; //构造哈夫曼编码数组 typedef struct { HNodeType HFMTree[2*n-1];//结点数 int bit[n]; int start; }HCodeType; HCodeType HT; HCodeType HFMCode[n]; string message[10]={ {雨纷纷},{旧故里},{草木深}, {我听闻},{你始终},{一个人},{石板上},{回荡的}, {是在等},{叶良辰} }; string psw[10];//存储编码 //对信息进行编码 void CreatCode(HCodeType HT,int n) { int i,j,k; char ch;//存储编码的字符集 //权重初始化 for(i=0;i2*n-1;i++) { HT.HFMTree[i].weight=0; } cout请输入编码字符集的大小: m= ; //字符集大小是m cinm; cout请输入编码长度大小:p = ; //编码长度大小p cinp; cout请输入编码字符:endl; for(i = 0;in;i++) { cinHT.HFMTree[i].word; } //对汉字信息进行编码 srand(time(NULL)); cout************