《数据结构》课程设计报告-哈夫曼树编码译码

数据结构课程设计PAGEPAGE1数据结构课程设计《数据结构》课程设计报告设计题目：__哈夫曼树编码译码

摘要哈夫曼编/译器设计：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求这发送端通过一个编码系统对待传数据预先编码，在发送端将传来的数据进行译码（复原）。对于双工信道。每端都需要一个完整的编译码系统。本程序将为这样的信息收发站写一个哈夫曼的编译码系统。哈夫曼编码/译码程序运行步骤：字查找，从英文文章中识别出字符，并把字符插入到一棵二叉排序树中。哈夫曼树中序遍历，是为了把英文文章中的不重复的字符保存起来。哈夫曼编码，在已经构造好的霍夫曼树中从每个叶子结点出发追溯到树根，逆向找出霍夫曼树中叶子结点的编码，规定：树中每个结点的左分支标上0,右分支标上1。哈夫曼译码利用霍夫曼树实现对产生的编码文件的译码，译码过程为：从根结点出发，按二进制位串的0或1进入左分支或右分支，当到达叶子结点时译出该叶子对应的单词或标点符号，若该编码文件尚未结束，则回到根结点继续进行上述过程。运行环境：windowsXP语言环境：简体中文软件大小：51KB编写工具：MicrosoftVisualstudio2008

AbstractInformation:Huffmancodingusedincommunicationcangreatlyimprovethechannelutilization,reducedtransmissiontime,andlowertransmissioncosts.However,thisrequiresthatthesenderthroughacodingsystemforpre-treatmentdata-coding,thetransmitterwillbesentfordecodingdata(recovery).Fordual-channel.Eachsideneedsacompleteencryptionsystem.ThisprocedurewillthisinformationhubsHuffmanwasoneoftheencryptionsystem.Hoffmanncodeforcodingprocedurestorunthestepsand：wordfromenglishinthewordsandpunctuationmarks；andinsertthewords,andpunctuationmarksasecondsortofatree.thetraversalorderhoffmann,toenglisharticlesdonotrepeatthewordsandpunctuationmarks.Hoffmanntreeinordertotraverse;keepthecodehasbeenconstructedinhoffmanngoodhafmantreeleavesfromthestartdatesbacktotabulatetheroots;Hoffmanndecoding;hafmantheimplementationofthecodetothecoding,codingproceduresfor：fromstarttotabulatetherootsofbinaryof0or1totheleftorright,asubdivisionofabranchistotabulatetheleavesoftheleavestranslatethewordsorpunctuationmarks,ifthecodefileisnotfinishedbutistotabulatetheprocessofcontinuing.allthecode,codingproceduresareinthefile.

目录一、问题描述……………4二、需求分析……………4三、概要设计……………5四、数据结构设计………7五、算法设计……………7六、程序测试与实现……9七、调试分析…………12八、心得体会…………12

一、问题描述1、题目内容：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试写一个哈夫曼编/译码系统。2、基本要求：一个完整的系统应具有以下功能：（1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。（2）编码。利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文件中。（3）译码。利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。（4）完成数据测试，要求编码字符不低于15个，编码文件的长度不低于50个字符。(5)计算平均编码长度。二、需求分析一个完整的系统应具有以下功能：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树。对赫夫曼树初始化。根据书本算法，对树进行从叶子到根的逆向求每个字符的赫夫曼编码。更新赫夫曼树。编码(Encoding)。利用已建好的哈夫曼树正文进行编码。将终端输入须要编码的语句逐字在已建好的赫夫曼树中查找。当在树中找到相匹配字符时，将该字符对应的赫夫曼编码同意保存。③最后将数组中的编码在终端输出。译码(Decoding)。利用已建好的哈夫曼树将文件中的代码进行译码。获取须要译码的编码组。将编码逐一读入，并在赫夫曼中根据左‘0’右‘1’去查找字符。将译好的语句在终端输出。三、概要设计操作集合：voidSelect(intcur,int&r1,int&r2);nodes[1~cur]中选择双亲为,权值最小的两个结点r1,r2voidCreatHuffmanTree(charch[],intw[],intn);public:HuffmanTree(charch[],intw[],intn);由字符,权值和字符个数构造哈夫曼树virtual~HuffmanTree();析构函数stringEncode(charch);编码LinkListDecode(stringstrCode);译码本程序主要用到了三个算法。(1)哈夫曼编码;在初始化过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。先将输入的字符和权值存放到一个结构体数组中，建立哈夫曼树，将计算所得的哈夫曼编码存储到另一个结构体数组中。(2)串的匹配;在编码过程中间，要对已经编码过的代码译码，可利用循环，将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较，如果相等就回显。(3)二叉树的遍历在印哈夫曼树(T)的中，因为哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出。四、数据结构设计structNode{chardata;//节点数据域为字符型Node*next;Node(){next=NULL;};Node(charitem,Node*link=NULL){data=item;next=link;};}structHuffmanTreeNode{intweight;unsignedintparent,leftChild,rightChild;//双亲,左右孩子域HuffmanTreeNode();HuffmanTreeNode(intw,intp=0,intlChild=0,intrChild=0);}五、算法设计1、算法分析（必须要用语言进行描述）构造树:初始化:每个字符就是一个结点，字符的频度就是结点的权:1、将结点按频度从小到大排序;2、选取频度最小的两个结点，以它们为儿子，构造出一个新的结点;新结点的权值就是它两个儿子的权值之和;构造之后，从原来的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去;3、如果结点序列里只剩下一个结点，表示构造完毕，退出。否则回到第一步。编码:编码：可以假定，对某个结点而言，其左孩子在当前阶段的编码为0，右孩子的编码为1。这样就可以通过”树的遍历“的方式来生成字长—编码对照表来到这里，基本上艰苦的已经完成了，对某个具体的字符串编码和解码就只是简单的“查表—替换”的工作了。解码:解码也是个简单的查表、替换过程。如果利用该种编码发送字符串，则它的”字宁含—编码侧应表也必须发送过去，不然对方是不知道怎么解码的。对给出的一串编码，从左向右，将编码组合起来并查表. 2、算法流程图 结束传入参数：结点个数结束传入参数：结点个数n动态分配内存，声明哈夫曼树HT，并对其值进行初始化建哈夫曼树，依次在HT[1..i-1]中Selectparent为0且weight最小的两个结点分配n个字符编码的头指针向量和求编码的工作区间从叶子到根逆向逐个字符求哈夫曼编码释放工作空间开始I<=n?六、程序测试与实现1、函数之间的调用关系2、主程序intmain(void){char*ch;int*w,n,i;cout<<"输入字符集中字符的个数："<<endl;cin>>n;ch=newchar[n];w=newint[n];cout<<"输入字符集中的字符："<<endl;for(i=0;i<n;i++)cin>>ch[i];cout<<"输入字符集中的字符的权值："<<endl;for(i=0;i<n;i++)cin>>w[i];HuffmanTreehmTree(ch,w,n);stringstrText,strCode;cout<<"请输入要编码的字符串";cin>>strText;cout<<"文本串"<<strText.c_str()<<"编码为:";for(intpos=0;pos<strText.length();pos++){stringstrTmp=hmTree.Encode(strText[pos]);cout<<strTmp.c_str();}cout<<endl;system("PAUSE");cout<<"请输入要译码的二进制串";cin>>strCode;cout<<"编码串"<<strCode.c_str()<<"译码为:";LinkListlkText=hmTree.Decode(strCode);lkText.Traverse();system("PAUSE");return0;}3、测试数据 字符集中字符个数：15 字符集中的字符：a,b,c,d,e,f,g,h,i,j,k,l,m,n,o 权值：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 要编码的字符串：abcdefghijklmno4、测试结果 0011100011110011011010110110010101010111100111011110七、调试分析1．链表中的结点变量是通过指针变量来访问的。因为在C++语言中是用P—>来表示P所指的变量，又由于结点类型是一个结构类型，因此可用P—>data和P—>next分别表示结点的数据域变量和指针域变量。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P 来访问结点，否则会引起程序错误。八、心得体会通过这次数据结构课程设计，使我对软件的界面设计有了一个比较深刻的了解，对各种内部排序方法的性能有了清晰的认识，使我感觉到到，一个优秀的软件，不仅仅是可以运行的，更应该具有人性化的界面，协调的布局，合理的结构，良好的性能和一定的容错性一个人要完成所有的工作是非常困难和耗时的.在以后的