数据结构实验三哈夫曼编码

数据结构实验报告实验名称：实验3——哈夫曼树学生姓名：XXX班级：班内序号：学号：日期：2012年12月1日1．实验要求【实验目的】通过选择下面两个题目之一进行实现，掌握如下内容：掌握二叉树基本操作的实现方法了解赫夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力【题目】利用二叉树结构实现赫夫曼编/解码器。【基本要求】初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。打印(Print)：以直观的方式打印赫夫曼树（选作）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。【测试数据】IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。【代码要求】1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2.程序分析2.1存储结构用二叉树的结构建立哈夫曼树，每个节点的结构是structHNode{intweight;intlchild; intrchild; intparent;};weightweightlchildrchildparent哈夫曼树结点结构哈夫曼树的特点：只有度为2的结点和叶子结点，所以具有n个叶子结点的哈夫曼树的结点总数为2n-1顺序存储结构：设置一个的Tree[2*n-1]数组2.2关键算法分析程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压；第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把编码后的码字存储。哈弗曼树的c++描述如下：classHuffman{public: voidselectmin(int&x,int&y,inta);voidCreateHTree(inta[],intn);voidCreateTable(charcode[],intn);voidencode(charstring[],charcode[]);voiddecoding(char*s,char*d,intn); voidprint(intlength);private: HNode*HTree; HCode*HCodeTable;};【存储算法】对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树voidHuffman::CreateHTree(inta[],intn){ HTree=newHNode[2*n-1]; for(inti=0;i<n;i++) { HTree[i].weight=a[i]; HTree[i].lchild=-1; HTree[i].rchild=-1; HTree[i].parent=-1; } intx,y; for(inti=n;i<2*n-1;i++) { selectmin(x,y,i); HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].lchild=x; HTree[i].rchild=y; HTree[i].parent=-1; }}哈夫曼树是一棵正则二叉树。根据二叉树的性质，一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，我们可以用一个静态三叉链表来存储哈夫曼树。weightLChildRChildparent02-1-1-113-1-1-126-1-1-139-1-1-14-1-1-15-1-1-1【初始化哈夫曼树】weightLChildRChildparent02-1-1413-1-1426-1-1539-1-1645015511426【创建好的哈夫曼树】【编码】voidHuffman::CreateTable(charcode[],intn){ HCodeTable=newHCode[n]; for(inti=0;i<n;i++) { HCodeTable[i].data=code[i]; intchild=i; intparent=HTree[i].parent; intk=0; while(parent!=-1) { if(child==HTree[parent].lchild) HCodeTable[i].code[k]='0'; else HCodeTable[i].code[k]='1'; k++; child=parent; parent=HTree[child].parent; } HCodeTable[i].code[k]='\0'; char*b=newchar[k]; for(intj=0;j<k;j++) { b[j]=HCodeTable[i].code[k-1-j]; } b[k]='\0'; for(intm=0;m<=k;m++) { HCodeTable[i].code[m]=b[m]; } cout<<endl; }}【解码】voidHuffman::decoding(char*s,char*d,intn){ cout<<"解a码?过y后¨®的Ì?字Á?符¤?串ä?为a：êo"<<endl; while(*s!='\0') { intparent=2*n-1-1; while(HTree[parent].lchild!=-1) { if(*s=='0') parent=HTree[parent].lchild; else parent=HTree[parent].rchild; s++; } *d=HCodeTable[parent].data; cout<<*d; d++; } cout<<endl;}2.3其他增加菜单选项，可以重新开始程序或退出程序3.程序运行结果1.程序流程图开始开始输入字符串输入字符串输入字符串输入字符串算出每个字符权值并分别存储权值和字符算出每