16793人阅读
数据结构实验（3）
一、【实验内容】【问题描述】&&&&& 利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.
【基本要求】：一个完整的系统应以下功能:(1) I. 初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中.(2) E. 编码(Encoding)。利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.(3) D. 译码(Decoding)。利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile中. (4) P. 印文件代码(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。　　　　　　测试数据：(1)&利用教科书例6-2中的数据调试程序。(2)&用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：&THIS PROGRAM IS MY FAVORITE&.。字符&&&&&& A&& B&&& C&&& D&&& E&&& F&&& G&&& H&&& I&&& J&&& K&&& L&&& M频数&186& 64&& 13&& 22&& 32&& 103& 21&& 15&& 47&& 57&& 1&&& 5&&& 32&& 20字符&N&&& O&&& P&&& Q&&& R&&& S&&& T&&& U&&& V&&& W&&& X&&& Y&&& Z频数&57&& 63&& 15&& 1&&& 48&& 51&& 80&& 23&& 8&&& 18&& 1&&& 16&& 1
二、实验目的树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.
三、实验文档：&&&&&&&&&&&&&&&&& 哈夫曼编码/译码一、&需求分析1、&利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。本实验要求：2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示&提示信息&之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。4、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。5、在本系统中，用户可以对任意长的字符串可进行编码/译码。6、程序执行的命令包括：　1) 初始化(I)　　　2) 编码(E)　　　　3) 译码(D) 4) 印代码文件(P)　5) 印哈夫曼树(T)　6) 退出(Q)７、测试数据：　　（１）利用教科书例6-2中的数据调试程序。（２）用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的　　　编码和译码：&THIS PROGRAM IS MY FAVORITE&.。字符&&&& A&& B&& C&& D&& E&& F&& G&& H&& I&& J&& K&& L&& M频数&186& 64&&& 13&&& 22&&& 32&& 103&&& 21&& 15&& 47&&& 57&&& 1&&& 5&&&& 32&&& 20字符&N& O&& P&& Q&& R&&& S&&& T&& U&&& V&& W&& X&&& Y&& Z频数&57&& 63&&& 15&&& 1&&& 48&&&& 51&&&& 80&&& 23&&&& 8&&&&& 18&&& 1&&&&& 16&&& 1
二、概要设计为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：ADT HuffmanTree{数据对象：D={ai| ai&CharSet,i=1,2,&&,n,& n&0}数据关系：R={& ai-1, ai & ai-1, ai&D, ai-1&ai ,i=2，3，&&，n}基本操作P：HuffmanTree();&&&&&& 构造函数~ HuffmanTree();&&&& 析构函数Initialization(int WeightNum);操作结果：构造哈夫曼树。Encoder()初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。操作结果：对字符串进行编码Decoder();初始条件：哈夫曼树已存在且已编码。操作结果：对二进制串进行译码Print()初始条件：编码文件已存在。操作结果：把已保存好的编码文件显示在屏幕TreePrinting()初始条件：哈夫曼树已存在。操作结果：将已在内存中的哈夫曼树以直观的方式显示在终端上2.本程序包含三个模块：1)主程序模块：void main(){&&& 初始化；do{&& 接受命令；&& 处理命令；}while(&命令&=&退出&)}2)、建树模块&&实现定义的抽象数据类型3)、编/译码模块&&实现字符串的编/译码各模块之间的调用关系如下：&&&&&&&&&&&&&&&&&&& 主程序模块&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&& 建树模块&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&& 编/译码模块三、详细设计程序代码如下//&&&&&&& 程序名：HuffmanTree.h//&&&&& 程序功能：哈夫曼树类的头文件(并用其来实现编/译码)//&&&&&&&&& 作者：刘伟高//&&&&&&&&& 日期：//&&&&&&&&& 版本：1.0
//对应类实现文件: HuffmanTree.cpp//对应主程序文件: main.cpp
#include&iostream&#include&fstream&#include&string&struct HuffmanNode&&&&&&& //定义哈夫曼树各结点{&&&&&&&& //存放结点的权值，假设只考虑处理权值为整数的情况&&&&&&&& //记录结点父亲位置，-1表示为根结点，否则表示为非根结点&int lchild,&& //分别存放该结点的左、右孩子的所在单元的编号};class HuffmanTree&&&& //建立哈夫曼树类{private:&HuffmanNode *N&&&&& //哈夫曼树中结点的存储结构&char *I&&&&&&&&&& //用来保存各字符信息&int LeafN&&&&&&&&& //树中的叶子结点总数public:&HuffmanTree();&&&& //构造函数&~HuffmanTree();&&& //析构函数&void Initialization(int WeightNum);&& //初始化函数：根据WeightNum个权值建立一棵哈夫曼树&void Encoder();&&&&&&&&&& //编码函数：利用构造好的哈夫曼树对字符进行编码&void Decoder();&&&&&&&&& //译码函数：对二进制串进行译码&void Print();&&&&&&&&&&& //印文件函数：把已保存好的编码文件显示在屏幕&void TreePrinting();&&&& //印哈夫曼树函数：将已在内存中的哈夫曼树以直观的方式显示在终端上};
//&&&&&&& 程序名：HuffmanTree.cpp//&&&&& 程序功能：实现哈夫曼树类的源文件(并用其来实现编/译码)//&&&&&&&&& 作者：刘伟高//&&&&&&&&& 日期：//&&&&&&&&& 版本：1.0
#include&HuffmanTree.h&#include&string&
////////////////////////////////////////////////////////////////////////////////& 构造函数//& 函数功能：将结点指针初始化为NULL//& 函数参数：无//& 参数返回值：无HuffmanTree::HuffmanTree(){&Node=NULL;&&&&&&&&& //将树结点初始化为空 &Info=NULL;&&&&&&&&& //将字符数组初始化为空&LeafNum=0;&&&&&&&&& //将叶子数初始化为0}//////////////////////////////////////////////////////////////////////////////// 析构函数// 函数功能：将所有结点的空间释放// 函数参数：无// 参数返回值：无HuffmanTree::~HuffmanTree(){&delete[] N&&&&&&&& //释放结点空间&delete[] I&&&&&&&& //释放字符存储空间}////////////////////////////////////////////////////////////////////////////////& 初始化函数//& 函数功能：从终端读入字符集大小n，以及n个字符和n个权值,//&&&&&&&&&&& 建立哈夫曼树,并将它存放在文件hfmTree中.//& 函数参数：int WeightNum表示代码个数//& 参数返回值：无 void HuffmanTree::Initialization(int WeightNum)&&&&&&& //初始化{&int i,j,pos1,pos2,max1,max2;&&&& //&&Node=new HuffmanNode[2*WeightNum-1];& //WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1个&Info=new char[2*WeightNum-1];&for(i=0;i&WeightNi++)&{&&cout&&&请输入第&&&i+1&&&个字符值&;&&getchar();&&&&&&&&&& //丢弃字符'/t'与'/n'&&Info[i]=getchar();&& //输入一个字符,主要是考虑输入空格而采用这种形式的&&getchar();&&cout&&&请输入该字符的权值或频度&;&&cin&&Node[i].&&&&&& //输入权值&&Node[i].parent=-1;&&&&& //为根结点&&Node[i].lchild=-1;&&&&& //无左孩子&&Node[i].rchild=-1;&&&&& //无右孩子&}&&for(i=WeightNi&2*WeightNum-1;i++) //表示需做WeightNum-1次合并&{&&pos1=-1;&&pos2=-1;&&&&&&&&& //分别用来存放当前最小值和次小值的所在单元编号 &&max1=32767;&&&&& //32767为整型数的最大值 &&max2=32767;&&&&& //分别用来存放当前找到的最小值和次小值&
&&for(j=0;j&i;j++)&&&&& //在跟节点中选出权值最小的两个&&&if(Node[j].parent==-1)&&&&&&&& //是否为根结点&&&&if(Node[j].weight&max1)&&&& //是否比最小值要小&&&&{ &&&&&max2=max1;&&&&&&&&&&& //原最小值变为次小值&&&&&max1=Node[j].&&&&& //存放最小值&&&&&pos2=pos1;&&&&&&&&&&& //修改次小值所在单元编号&&&&&pos1=j;&&&&&&&&&&&&&& //修改最小值所在单元编号&&&&}&&&&else&&&&&if(Node[j].weight&max2)&&&& //比原最小值大但比原次小值要小&&&&&{&&&&&&max2=Node[j].&&&& //存放次小值&&&&&&pos2=j;&&&&&&&&&&&&&&&&& //修改次小值所在的单元编号&&&&&}&&& //for&&Node[pos1].parent=i;&&&&&& //修改父亲位置&&Node[pos2].parent=i;&&Node[i].lchild=pos1;&&&&&& //修改儿子位置&&Node[i].rchild=pos2;&&Node[i].parent=-1;&&&&&&&&&&&& //表示新结点应该是根结点&&Node[i].weight=Node[pos1].weight+Node[pos2].&} //for&LeafNum=WeightN&&&&cout&&&是否要替换原来文件(Y/N):&;&cin&&&if(ch=='y'||ch=='Y')&{&&& //以二进制方式打开hfmTree.dat文件，并当重新运行时覆盖原文件&fop.open(&hfmTree.dat&,ios::out|ios::binary|ios::trunc);&if(fop.fail())&&&&&&&&&&&&&&&&&&&& //文件打开失败&&cout&&&文件打开失败！/n&;&fop.write((char*)&WeightNum,sizeof(WeightNum));& //写入WeightNum&for(i=0;i&WeightNi++)&&&&&&&& //把各字符信息写入文件&{&&fop.write((char*)&Info[i],sizeof(Info[i]));&&flush(cout);&}&for(i=0;i&2*WeightNum-1;i++)&&&&&&& //把个节点内容写入文件&{&&fop.write((char*)&Node[i],sizeof(Node[i]));&&flush(cout);&}&fop.close();&&&&&&&&&&& //关闭文件&}&cout&&&哈夫曼树已构造完成。/n&;}//Initialization
////////////////////////////////////////////////////////////////////////////////& 编码函数//& 函数功能：利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），//&&&&&&&&&&& 对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.//& 函数参数：无//& 参数返回值：无void HuffmanTree::Encoder(){&if(Node==NULL)&&&&&& //哈夫曼树不在内存，从文件hfmTree中读入&{&&&&&&&&& //以二进制方式打开hfmTree.dat文件&&fip.open(&hfmTree.dat&,ios::binary|ios::in);&&if(fip.fail())&&&&&& //文件打开失败&&{&&&cout&&&文件打开失败！/n&;&&&&&&&&&&&& //结束本函数&&}&&fip.read((char*)&LeafNum,sizeof(LeafNum));& //读取叶子数&&Info=new char[LeafNum]; &&Node=new HuffmanNode[2*LeafNum-1];&&for(int i=0;i&LeafNi++)&&&&&&&&&&&&& //读取字符信息&&&fip.read((char*)&Info[i],sizeof(Info[i]));&&for(i=0;i&2*LeafNum-1;i++)&&&&&&&&&&&&& //读取结点信息&&&fip.read((char*)&Node[i],sizeof(Node[i]));&}&&char *T&&&&&&&&& //用于存储需编码内容&int i=0,&char C&&&&&&&& //让用户选择读取文件或重新输入需编码内容&cout&&&你要从文件中读取内容(1)，还是重新输入(2):&;&cin&&C&if(Choose=='1')&&&&&&&&& //读取文件ToBeTran.txt&{&&ifstream fip1(&ToBeTran.txt&);&&if(fip1.fail())&&&&& //文件不存在&&{&&&cout&&&文件打开失败!/n&;&&&&&&&&&&&& //结束本函数&&}&&&&int k=0;&&while(fip1.get(ch))&&&&&&&&&&& &&{&&&k++;&&&&&&&&&&&&&&&&&&&& //计算CodeFile中代码长度&&} &&fip1.close();& &&&Tree=new char[k+1];&&ifstream fip2(&ToBeTran.txt&);
&&k=0; &&while(fip2.get(ch))&&{&&&Tree[k]=&&&&&&&&&& //读取文件内容，并存到Tree中&&&k++;&&}&&fip2.close();&&Tree[k]='/0';&&&&&&&&& //结束标志&&cout&&&需编码内容为:&;&&cout&&Tree&&&}//if(Choose=='1')
&else&&&&&&&&&& //Choose!='1',重新输入&{&&&&&&&&&& //用于输入需编码内容，由于string类对象可以输入任意长度，&&&&&&&&&&&&&&&&&&&& //所以先利用这个对象输入，再转存在Tree中& &&cin.ignore();&&cout&&&请输入需要编码的内容(可输入任意长，结束时请按2下回车):/n&;&&getline(cin,tree,'/n');&&&&&&&& //输入任意长字符串，&&&&&&&& //getline以回车('/n')作为结束符，第一次按回车表示字符串结束，第二次按回车才开始输出。&&while(tree[i]!='/0')&&&i++;&&num=i;&&&&&&&&&&&& //计算tree长度&&i=0;&&Tree=new char[num+1];&&while(tree[i]!='/0')&&&&&& //将tree中的字符转存到Tree中&&{&&&Tree[i]=tree[i];&&&i++;&&}&&&& Tree[i]='/0';&&&&&&&&& //结束标志符&}&&ofstream fop(&CodeFile.dat&,ios::trunc);&&&&& //存储编码后的代码,并覆盖原文件&i=0;&int k=0;&char *&code=new char[LeafNum];&&&&&&& //为所产生编码分配容量为LeafNum的存储空间&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& //因为不等长编码中最长的编码一定不会超过要求编码的字符个数&while(Tree[k]!='/0')&&&&&&&&&&&&& //对每一个字符编码&{&&int j,start=0;&&for(i=0;i&LeafNi++)&&&if(Info[i]==Tree[k])&&&&&&&&&&& //求出该文字所在单元的编号&&&& &&&j=i;&&while(Node[j].parent!=-1)&&&&&&& //结点j非树根&&{&&&j=Node[j].&&&&&&&&&&&& //非结点j的双亲结点&&&if(Node[j].lchild==i)&&&&&&&&&& //是左子树，则生成代码0&&&&code[start++]='0';&&&else&&&&&&&&&&&&&&&&&&&&&& //是右子树，则生成代码1&&&&code[start++]='1';/&&&i=j;&&}&&code[start]='/0';&&&&&&&&&&&& //置串结束符
& &&for(i=0;i&start/2;i++)&&&&&&&&&& //对二进制序列进行逆置&&{&&&j=code[i];&&&code[i]=code[start-i-1];&&&code[start-i-1]=j;&&}&&&&&&& i=0;&&while(code[i]!='/0')&&&&&&& //存储代码&&{&&&fop&&code[i];&&&i++;&&}&&k++;&}&fop.close();&cout&&&已编码！且存到文件CodeFile.dat中！/n/n&;}& //Encode
////////////////////////////////////////////////////////////////////////////////& 译码函数//& 函数功能：利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,//&&&&&&&&&&& 将译码结果存入文件TextFile中.//& 函数参数：无//& 参数返回值：无void HuffmanTree::Decoder(){&int i=0,k=0;&int j=LeafNum*2-1-1;&&&&& //表示从根结点开始往下搜索&char* BitS&&ifstream fip1(&CodeFile.dat&);&&&&&&&&& //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码&if(fip1.fail())&&&&&&&& //文件打开失败，还未编码&{&&cout&&&&&&&&& &请先编码！/n&;&&&}&cout&&&经译码,原内容为:&;&&while(fip1.get(ch))&&&&&&&&&&& &{&&k++;&&&&&&&&&&&&&&&&&&&& //计算CodeFile中代码长度&}&fip1.close();& &&BitStr=new char[k+1];&ifstream fip2(&CodeFile.dat&);&k=0;&while(fip2.get(ch))&{&&BitStr[k]=&&&&&&&&& //读取文件内容&&k++;&}&fip2.close();&&&&&&&&&&&&&&& &BitStr[k]='/0';&&&&&&&& //结束标志符&if(Node==NULL)&&&&&&&& //还未建哈夫曼树&{& cout&&&请先编码!/n&;&&}&ofstream fop(&TextFile.dat&);&&&&&&&& //将字符形式的编码文件写入文件CodePrin中&while(BitStr[i]!='/0')&{&&if(BitStr[i]=='0')&&&j=Node[j].&&&&&&&&& //往左走&&else&&&j=Node[j].&&&&&&&& //往右走&&if(Node[j].rchild==-1)&& //到达叶子结点&&{&&&cout&&Info[j];&&&&&&&& //输出叶子结点对应的字符&&&j=LeafNum*2-1-1;&&&&&&&&&&&& //表示重新从根结点开始往下搜索&&&fop&&Info[j];&&&&&&&&&&&&&& //存入文件&&}//if、&&i++;&}//while&fop.close();&&cout&&&/n译码成功且已存到文件TextFile.dat中！/n/n&;}//Decoder////////////////////////////////////////////////////////////////////////////////& 印文件代码函数//& 函数功能：将文件CodeFile以紧凑格式显示在终端上，//&&&&&&&&&&& 每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。//& 函数参数：无//& 参数返回值：无void HuffmanTree::Print(){&&int i=1;&ifstream fip(&CodeFile.dat&);&&&&&&&&&& //读取文件&ofstream fop(&CodePrin.dat&);&&&&&&&&&& //存储文件&if(fip.fail())&{&&cout&&&没有文件，请先编码！/n&;
&&&}&while(fip.get(ch))&{&&cout&&&&&&&&&&&&& //读取文件内容&&fop&&&&&&&&&&&&&&& //存到文件中&&if(i==50)&&&&&&& //每行输出50个字符&&{&&&cout&&&&&i=0;&&}&&i++;&}&cout&&&fip.close();&&&&&&&&& //关闭CodeFile.dat文件&fop.close();&&&&&&&&&&& //关闭CodePrin.dat文件}////////////////////////////////////////////////////////////////////////////////& 印哈夫曼树函数//& 函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，//&&&&&&&&&&& 同时将此字符形式的哈夫曼树写入文件TreePrint中。//& 函数参数：无//& 参数返回值：无void HuffmanTree::TreePrinting(){&if(Node==NULL)&&&&&&&& //未建立哈夫曼树&{&&cout&&&请先建立哈夫曼树！/n&;&&&}&ofstream fop(&TreePrint.dat&);&cout&&&结点位置(权值)& &&&&编码& &&&&左孩子& &&&&编码&&&&右孩子('^'表示叶子)/n&;&fop&&&结点位置(权值)& &&&&编码& &&&&左孩子& &&&&编码&&&&右孩子('^'表示叶子)/n&;&&for(i=(2*LeafNum-2);i&LeafNum-1;i--)&&&&&&& //输出哈夫曼树&{&&cout&&i&&&(&&&Node[i].weight&&&)&&&&--1--&&&&&Node[i].lchild&&&(&&&Node[Node[i].lchild].weight&&&)&&&&--0--&&&&&Node[i].rchild&&&(&&&Node[Node[i].rchild].weight&&&)&&&&&fop&&i&&&(&&&Node[i].weight&&&)&&&&--1--&&&&&Node[i].lchild&&&(&&&Node[Node[i].lchild].weight&&&)&&&&--0--&&&&&Node[i].rchild&&&(&&&Node[Node[i].rchild].weight&&&)&&&&}&for(;i&=0;i--)&{&&cout&&i&&&:&&&Node[i].weight&&&(&&&Info[i]&&&)---^/n&;&&fop&&i&&&:&&&Node[i].weight&&&(&&&Info[i]&&&)---^/n&;&}}
//&&&&&&& 程序名：main.cpp//&&&&& 程序功能：主函数源文件//&&&&&&&&& 作者：刘伟高//&&&&&&&&& 日期：//&&&&&&&&& 版本：1.0
#include&HuffmanTree.h&#include&string.h&#include&stdlib.h&
////////////////////////////////////////////////////////////////////////////////& 主函数//参数返回值：无
int main(){&cout&&&&&&&&&&& 欢迎使用哈夫曼码的编/译码系统!/n&;&cout&&&&&&&&&&&&&&&&&&&&&&&&&&& 刘伟高/n&;&cout&&&&&&&&&&&&&&&& 版权所有,盗版必究/n&; &cout&&&在此系统中可以进行以下操作:/n&;&cout&&&(1) 初始化(I);/n&;&cout&&&(2) 编码(E);/n&;&cout&&&(3) 译码(D);/n&;&cout&&&(4) 印代码文件(P);/n&;&cout&&&(5) 印哈夫曼树(T)/n&;&cout&&&(6) 退出(Q)/n/n&;&HuffmanT&&&&&&&& //定义哈夫曼树对象&&char C&while(1)&{&&cout&&&请从清单中选择一个操作(不区分大小写):&;&&cin&&C&&switch(Choose)&&{&&case 'I':&&case 'i':&&&cout&&&请输入编码长度：&;&&&cin&&&&&huftree.Initialization(weight);&&&&& //初始化哈夫曼树&&&&&case 'E':&&case 'e':&&&huftree.Encoder();&&&&&case 'D':&&case 'd':&&&huftree.Decoder();&&&&&case 'P':&&case 'p':&&&huftree.Print();&&&&&case 'T':&&case 't':&&&huftree.TreePrinting();&&&&&case 'Q':&&case 'q':&&&cout&&&/n&&&&&&& ***********感谢使用本系统!***********/n/n&;&&&&&&&&&& system(&pause&);&&& //暂停运行&&&return 0;&&}&&cout&&&(1) 初始化(I)&&&&& (2) 编码(E)&&&&&&&& (3) 译码(D)/n&;&&cout&&&(4) 印代码文件(P)& (5) 印哈夫曼树(T)&& (6) 退出(Q)/n&;&}}四、调试分析1、由于二维指针和string类，还有文件操作的推敲不足，使程序调试时费时不少。还有对单个空格字符的输入，也花了一些时间，不过最终能实现单个空格的输入，还是值得的。2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性，特别是文件操作方面，如果可能的话，可以把文件读入、读出分别写成一个函数（就是把文件名作为参数），然后就可以直接调用了。3、本程序模块划分比较合理，且利用指针和string类对象实现字符串的操作，操作方便。4、算法的时空分析在此程序中，存储字符串都用了指针，先动态申请空间，然后再存，这样就有效的利用了空间，不过为了实现任意长字符串的输入，引入了string类，先定义string对象，再输入。最后转存到字符指针里，这样就浪费了一些空间。而对于哈夫曼树算法本身，由于这里只是一个静态的，所以当进行网络传输时，可能会显得效率比较低。5、本实验采用数据抽象的程序设计方法，将程序分为3个模块，使得设计时思路清晰，实现时调试可以顺利完成，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。五、用户手册1、本程序的运行环境为DOS操作系统2、进入演示程序后即显示文本方式的用户界面&&&&
3、进入界面后，就会提示输入字符串的输入形式，结束符为&回车符&。六、测试结果&&& 如上图所示。七、附录源程序文件名清单：HuffmanTree.h&&&&&&&&&&&&&&&&&&& //元素结点定义单元HuffmanTree.cpp&&&&&&&&&&&&&&&&& //链表实现单元main.cpp&&&&&&&&&&&&&&&&&&&&&&&&& //主程序
四、实验总结（心得体会）１、通过实验更好的掌握了哈夫曼树，并对哈夫曼树有了深一步的了解２、掌握了用getchar可以输入单个空格４、更进一步掌握有关类的操作5、由于算法推敲不足，使程序调试时费时不少6、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性７、更熟悉了文件的操作８、更好的掌握了对程序的调试，并从中感受到调试的巨大的力量，特别是当程序不能实现预想结果时
五、参考文献：1、《数据结构与算法》&&& 黄定& 黄煜廉& 刘贤兴& 编著& 广东科技出版社& 2000年1月第1版2、《〈数据结构与算法〉学习与实验指导》& 黄煜廉 编著&& 2005. 8
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：194639次
积分：2599
积分：2599
排名：第13899名
原创：61篇
转载：14篇
评论：59条
(1)(4)(6)(1)(1)(2)(1)(1)(1)(4)(8)(4)(3)(2)(3)(1)(8)(3)(2)(1)(6)(5)(3)(4)喷泉码编译码原理研究和分析02
上亿文档资料，等你来发现
喷泉码编译码原理研究和分析02
李璐颖吴湛击王文博；（北京邮电大学北京100876）；1引言；喷泉码无码率的特性使得发送端可以无止尽的；产生编码符号信息，每一个编码符号都是根据所有信源；2002年提出了第一种高效现实可行的喷泉码―――；由于各码字的水滴；LT码；每块码字均包含信源信息,接收端并不独立随机性，；方面进一步改进，这种新的喷泉码类型被命名为；删关心接收到的是“哪滴水”；[2]；R
李璐颖吴湛击王文博
（北京邮电大学北京100876）
喷泉码无码率的特性使得发送端可以无止尽的
产生编码符号信息，每一个编码符号都是根据所有信源信息独立随机异或生成的。这个不断编码发送
2002年提出了第一种高效现实可行的喷泉码―――码字的过程可以看成一个喷泉，无穷无尽地向外喷
由于各码字的水滴。接收端则类似一个接水的水杯。[1]
LT码。其后，Shokrollahi等人在喷泉码编译码时间
每块码字均包含信源信息,接收端并不独立随机性，
方面进一步改进，这种新的喷泉码类型被命名为
删关心接收到的是“哪滴水”。所以经过删除信道时，
Raptor码。LT码和Raptor码最早都是基于LDPC除编码信息的任意部分，不会影响其他符号信息参
适合于计算机网络与译码。码的原理，为删除信道而设计的，
广播。近年来喷泉码也被不断地推广到物理层应用。2.1LT码编码原理
假设发送的信息块长度大小为k，k是正整数。因为喷泉码良好的广播特性和无需反馈信道的特
赘2…赘k，生成度多点，一种Raptor码已经被3GPP标准采用，应用于将生成矩阵上的度分布记作赘1，kt
（MBMS）在3G网络的多媒体广播多播服务中。同时，项式可以表示为赘（x）=∑t=1赘tx。赘t表示度值为t的
（IMT-Advanced研发和产业化）；国家自然科学基金；（No.109013）
*基金项目：国家重大科技专项教育部科学技术研究重点项目。
喷泉码是一类基于图的线性纠错码，其主要码
字有随机线性码、LT码和Raptor码。在删除信道条
接收端只要收到比原信息长度略件下，其性能卓越，
多的码字，就能将所有信息还原。喷泉码发送端能如同喷泉一般源源不断的产生编码信息，每个编码符号独立随机，没有固定的码率r=k/n，所以是一种无
（Rateless）也是其名称的由来。码率码字，
M.Luby于1998年提出了喷泉码的概念，并在
深空通信领域和分布式存储领域，喷泉码也在发挥越来越大的作用。
目前喷泉码的研究主要围绕其度分布的设计来进行的，其行之有效的译码算法主要有高斯消元法和迭代置信传播法两种。
2喷泉码编码原理与实现
LT码的编码方式非常的直观，对于给定的输入
，每一个输出编码符号都通过信号向量（x1，x2…xk）独立随机计算得出。
下面是计算每个编码符号的步骤：（1）根据度分布赘0，采样得到一个权值赘1…赘k，取值在1和k之间；d，
（2）根据采样得到的权值d，平均随机地生成一k；
个权值为d的v=（v1，，其中vi∈{0，1}，v2…vk）i=1…
IdealSoliton分布是最理想的译码状态，即在每
次迭代译码过程中都只有一个校验节点d=1，实现了译码运算次数的最优化。这种分布的表达式如下所示：
1/K（d）=籽
1/d（d-1）ford=2，3…K
但是在实际应用中，编码时度分布的抽样无法
从而致精确符合Ideal分布，存在一定的波动误差，
因此实际性能并使迭代中d=1断层，导致译码失败。
2.RobustSoliton分布
改进型RobustSoliton分布有效地结合了Ideal
这分布的的优点，并加入另外两个调节参数c和啄，
样的设计有利于保证在译码过程中d=1节点的期望和译值近似于S≡cln（K/啄）啄是一个概率约束，姨，
码错误概率有关；c在实际应用中可以作为一个小于1的可调整的常数，以达到优化性能的目的。
一部分是1.2.1中的Robust分布由两部分组成，
Ideal分布，另一部分子（d）如下式所示：
（K/S）ford=1，2，…-1S/Kd
ln（S/d）ford=K/S
0ford跃K/S
对两者取归一化可得Robust分布：
（d）+子（d）其中Z=∑d籽
设设设设设缮设设设设设设墒
（3）将（2）中得到的向量与输入信号向量进行异
输出编码符号可或运算，即得到一个输出编码符号。以由∑ivixi，i=1…k计算而得。
图1LT码编码示意
图1为对长度k=8的一段信息进行LT编码的
示意图，图中虚线框中表示一次度分布抽样所得向量。x0~x7表示参与编码的源信息。2.2输入信息度分布
喷泉码的度分布信息，是编码和性能的关键设计。因为喷泉码的译码开始依赖于接收信息中d=1节点的分布，而译码的顺利开展，则有赖于在迭代过程中d=1节点的可持续产生。大部分的节点的度值应该较小，以减少译码整体的冗余运算次数和保证译码过程的持续进行；少量参与编码较少的节点应
要正确译该度值较大，以防出现漏编码的信息节点。码，每个信息节点应至少有一条边和编码节点相连。
1.IdealSoliton分布
2.3Raptor码编码原理
Raptor码是将预编码和弱化的LT码相结合而改进得来的，这两部分称为外码和内码。
[5]的信息无法恢复，此时，若外码的纠删率能达到f，
达到和LT码相同则通过外码能将原信息无误译出，
这是的性能。LT码的平均译码复杂度是O（klogk），
一个k的非线性函数，Raptor码将此译码复杂度降至了O（klogk）。从而在无损误码性能的条件下，Rap-图2为Raptor编码tor的应用提高了译码器的效率。
由于平均度值使得内码译码约有d的弱化，f=e
器的结构，源信息经过预编码后得到的冗余信息和源信息一同再进行LT编码，得到Raptor编码器的编码输出信息
Raptor编码示意图
此不适合于中长码的运算。
（BP）4置信传播译码算法
（BeliefPropagation）置信传播算法也称为消息传
播（MessagePassing）算法。对于一种度分布设计得当的喷泉码，采用置信传播译码将在计算性能上获得较大的提高，但对于中长码字而言计算速度难以提高。这是一种广泛使用且有效的喷泉码译码算法。
可以用Tan-喷泉码也是一类基于图的纠错码，
假设接收端收到n个符号，每个接收符ner图表示。
号可用一个k维的列向量代表，则其校验矩阵H的
其中维度为k伊n。接收Tanner图可以用（V，表示，E）
…sk-1}表V=Vs∪Vc表示一组节点的集合，Vs={s0，s1，示一组符号节点，…ck-1}表示一组校验节Vc={c0，c1，点；当且仅当hi，≠0，∈H，E表示一组边的集合，hi，jj0≤i≤k，0≤j≤n，（si，∈E。定义E=Vs×Vc存在边cj）Vs为所有与符号节点si相邻的校验节点的集合。
3高斯消元译码算法
（GaussianElimination）高斯消元算法是一类对
在喷泉码通用的译码方式，适用于各种喷泉码码字。
删除信道的相关研究中发现，对线性码使用最大似然译码（MaximumLikelihood）算法等同于解线性方程组，即可以使用高斯消元的方法来求解。
假设接收端收到n个符号，每个接收符号代表一个由k个未知输入的线性方程，方程的右值即接收信息。则整个译码过程可以看作是一个n个方程联合求解k个未知数的一个线性方程组H?其X=N。中H是经过删除信道后的生成矩阵，大小为n×k，X为k×1的待求解输入信息向量，N为n×1的接收信息向量。
高斯消元法步骤：（1）将H矩阵扩展为含接收信息向量N的增广矩阵H'，H'=[H/N]；（2）利用矩阵初等行变换将此增广矩阵H'的H矩阵转换成单位矩阵I，此时H'=[I/N']；（3）若此单位矩阵I满秩，则译码成功，译码输出X即为N'；若此单位矩阵I不满秩，说明接译码失败，接收端收信息不足，
继续接受信息，进入下一轮译码。GE算法的缺点是译码复杂度高，其运算量O（nk）随着信息
因块长度k的增长而快速增加，
当接收端收到的符号数达到k个时，译码器被
译激活，开始进行译码。当其成功译得k个码字时，直
码结束。如果不能译码则接收端继续接收符号，
图3三种不同分布的码字性能比较图
有的符号节点被正确地译出。
如果在循环迭代起始不存在d=1的节点，则译码无法启动，在循环迭代
循环也将被终中d=1的节点消耗殆尽，
止，译码器译码失败，接收端继续接收
信息，进入下一轮译码。4.2软判决BP算法
信在AWGN和衰弱信道条件下，从号在传输过程中会受到噪声的影响，特而不能保证译码起始节点的正确性，
别是信道条件较差时，使用硬判决会引入较多的错误。所以需要引入软判决BP算法，以提高译码的可靠性。假设接收到的编码比特为Y，X是发送至信道的比特X∈{0，1}，则最大似
（LLR）然率Zc定义如下：
图4基于线性随机码的译码方式性能比较图
可以译码为止。
BP算法的计算过程是一个循环迭代的过程，又可以分为硬判决和软判决两种：4.1硬判决BP算法
硬判决算法适用于只经过删除信道，接收到的一组编码符号集合只发生丢失，而不引入误差的情况。
当其中的某个符号只存在唯一的邻居输入信息节点，则译码器认为其两者信息等同。
硬判决BP译码算法步骤如下：（1）译码器寻找校验节点中d=1的节点cp，即校验节点只和唯则将一的符号节点相连，如果存在，
和此校验节点cp相连的符号节点sq的值还原为校验节点cp的内容；
（2）寻找（1）中还原符号节点sq将sq的值相连的校验节点集合Vs，
Zc=lnXY从每个Tan-在算法运行的第l轮，
ner图中的校验节点c，传递到符号节点s的消息被；同理，从符号节点s传递到校验节点c的
异或相加，然后删除他们在Tanner图中相连的边；
直到所（3）循环迭代这个过程，
图5基于Ideal分布的译码方式性能比较图
消息被记为mc，。s
软判决BP算法译码步骤如下：
符号节点向每个相（1）初始化l=0时的消息值，
邻的校验节点传递的消息均为0；
都遵循下式的消息（2）此后l=0的每一轮更新，
更新规则：
stanhmc，（l）
本文主要介绍和分析了喷泉码的编译码方式，Raptor通过牺牲一定的编码复杂度，换取了译码复
喷泉码的核心LT码在三种不同的杂度的大幅提升。
分布下，性能有较大的差别，线性随机分布的性能最
实际应用运算复杂度过好，但由于其编码矩阵稠密，高，且不能使用快速译码算法。Ideal分布具有理论最
无法达到精优值，但实际应用中由于存在抽样误差，
准理论分布，导致译码中断严重。Robust分布性能介
且存在可调参数，有较大的实际应用价于两者之间，
可以应值。在译码算法上，高斯消元法具有普适性，但是由于其计算复杂度高，随用于各种喷泉码译码，
相比下着输入信息长度的增加，效率将大幅度下降。
BP算法需要存在一定数量度为1的点作为迭代启
对度分动，因此对随机线性码等稠密码字无法使用，
布设计合理的码字则具有卓越的性能。因此在工程应用中具有广泛的意义
Zc：=tanhc?tanhms'，仪'≠ss=移mc'，ms，cs
（3）当更新l=0轮后，每个符号节点的LLR均可以通过公式∑cmc，算出，该式表示所有和校验节点cs相邻的符号节点s的消息和。
就可以使用ML算法译（4）通过这些LLR信息，
码，或作为Raptor码外码的译码输入信息进行译码。
5数据与仿真结果
我们对三种分布的LT编码和两种译码方式进行了运算时间和性能上的比较。参与编码的信息单元长度k分别为100和300，比较参数为误块
图3是使用高斯消元译码，三种不率。
同分布编码不同性能比较，图中可以看出在不同信息单元长度时，线性随机码的均为性能最佳，Robust分布性
而Ideal分布性能最差。能居中，
图4~图6是三种分布下，不同译码算法的性能比较，选择的是高斯消元算法和硬判决置信传播算法。图4表明线性随机编码的情况下，BP由于
而缺乏度为1的起始节点，无法译码，高斯消元算法不受影响并性能良好。
图5和图6表明，无论是基于Ideal分布或Robust分布，高斯消元算法在不同信息长度下均性能优于硬判决BP算法。
基于Robust分布的译码方式性能比较图
Communication，）
[1]ByersJ，LubyM，MitzenmacherM.Adigitalfountainapproachtoasynchronousreliablemulticast.IEEEJournalonSelectedAreasin
三亿文库包含各类专业文献、文学作品欣赏、中学教育、专业论文、行业资料、各类资格考试、应用写作文书、幼儿教育、小学教育、高等教育、喷泉码编译码原理研究和分析02等内容。　
　? 时,需要接收到已经编码的数据包的数目 K ' ? KZ 。 Luby 的分析解释了 ...喷泉码编译码原理研究和... 8页 2下载券 喷泉码及其在协作通信系... 66页... 　通信原理实验五 实验报告 PCM编码、译码原理实训_信息...SP407接入可选发码时钟,有 64K、512K、2048K 三种...图 5 时分多路复用波形分析 四、 实验内容 1. ... 　摘要本次课程设计研究的是(15,7)循环码的编译码方法,在设计过程中,首先要介绍了线 性分组码的编码和译码原理,并介绍了循环码的定义及其相关内容;其次由给定的生... 　华南理工大学数字通信原理实验思考题参考答案_工学_高等...编码:用二进制码组表示有固定电平的量化值。 译码:...2014教师资格材料分析辅... 2014小学教师资格考试《... 　(编译码技术、Turbo码的 设计和分析、Turbo码在CDMA系统中的研究及应用、面向分组的Turbo码、Turbo码与其 它通信技术的结合) ,编码原理、译码原理及Turbo码的性能... 　掌握 PCM 编译码原理。 2. 掌握 PCM 基带信号的...五、实验结果记录与分析 1.用示波器观察 STA、STB ...(3) 采用PCM 基带传输,线路码为HDB3 码,设计此... 　喷泉码编码 17页 免费 2 喷泉码技术研究 4页 1财富值 喷泉码的性能分析与应用...之后,Shokrollahi 又提出了性能更 佳的 Raptor 码 2,实现了近乎理想的编译码... 　第十课:编码及译码器工作原理分析 第十课:这节课主要为下节课的存储器存储...常用译码器输入、输出端头数来称呼译 码器,如 3 线-8 线译码器,4 线-10... 　根据电路原理图,分析解释其不同的原因。 答:不同:TPJ06 有眼图信号,而 TP...P76 3. (4)具有长连 0 码格式的数据在 AMI 编译码系统中传输会带来什么...