《数据结构实验报告2.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告2.doc（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、!-数 据 结 构实验报告实验名称：_实验三 树_题目2_学生姓名：_班 级：_班内序号：_学 号：_日 期：_1实验要求实验目的： 掌握二叉树基本操作的实现方法了解哈夫曼树的思想和相关概念培养使用二叉树解决实际问题的能力实验内容：利用二叉树结构实现赫夫曼编/解码器。基本要求如下：1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、 译码(Decoding
2、)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印(Print)：以直观的方式打印赫夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2. 程序分析 2.1 存储结构二叉树： root lchild pare
3、nt rchild 静态三叉链表存储:weightLChildRChildparent0123哈夫曼编码的存储结构 0 1 0 1 0 12.2 程序流程 (或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)2.3 关键算法分析1.建立了一个类class Huffmanprivate:HNode* HTree;HCode* HCodeTable;public: void SelectMin(int &x,int &y,int a,int b); /权值最小的两个字符void CreateHTree(int realcounts,int n); /创建哈夫曼树void CreateCo
4、deTable(char counts,int n); / 创建哈夫曼编码表void Reverse(char c); /逆序void Encode(char * s,char * d); /编码void Decode(char * s, char *d,int n); /解码Huffman()delete HTree;delete HCodeTable; /析构函数;2.建立哈夫曼树void Huffman:CreateHTree(int realcounts,int n)HTree=new HNode2*n-1; /根据权重数组初始化哈夫曼树for(int i=0;i1)/因为如果只有一种
5、字符就直接它自个儿了 for( i=n;i2*n-1;i+) /建立哈夫曼树 SelectMin(x,y,0,i); /找出最小权重的两个字符 HTreex.parent=HTreey.parent=i; HTreei.weight=HTreex.weight+HTreey.weight; HTreei.LChild=x; HTreei.RChild=y; HTreei.parent=-1; 时间复杂度：n3.选取权值最小的两个值void Huffman:SelectMin(int &x,int &y,int a,int b)int j,min1,min2;min1=min2=-1;for(j
6、=a;jb;j+)if(HTreej.parent=-1)if(HTreej.weightmin1|min2=-1)if(min1!=-1)min2=min1;y=x;min1=HTreej.weight;x=j;elseif(HTreej.weightmin2|min2=-1)min2=HTreej.weight;y=j;时间复杂度：n4.哈夫曼编码表void Huffman:CreateCodeTable(char counts,int n) int i;HCodeTable = new HCoden;if(n2) HCodeTable0.data=counts0;HCodeTable0.
7、code0=0;HCodeTable0.code1=0; cout字符及其编码:counts0 0 endl;elsefor(i=0;in;i+) HCodeTablei.data=countsi; cout字符及其编码:countsi ; int child=i; int parent=HTreei.parent; int k=0; while(parent!=-1) if (child=HTreeparent.LChild) HCodeTablei.codek=0; else HCodeTablei.codek=1;k+; child=parent; parent=HTreechild.p
8、arent; HCodeTablei.codek=0; Reverse(HCodeTablei.code); k=0; while(HCodeTablei.codek!=0) coutHCodeTablei.codek; k+; coutendl;时间复杂度：n5.逆序void Huffman:Reverse(char c)int i=0,j=0;int temp;while(cj+1!=0)j+;while(ij)temp=ci;ci=cj;cj=temp;i+;j-;时间复杂度：n6。对输入的字符串进行编码void Huffman:Encode(char * s,char * d)/编码
9、cout哈夫曼编码为： ;float sum=0; /统计字节数int n=0; while(*s!=0) int i=0;while(HCodeTablei.data!=*s) i+;for (int j=0;HCodeTablei.codej!=0;j+) *d=HCodeTablei.codej; cout*d; d+; sum+=1; s+;n+;*d=0;coutendl;cout编码前字符串所占比特位为： 8*nendl;cout编码后的字符串所占比特位为sumendl;cout压缩比为：sum/(8*n)endl;coutendl; 7。对已编译好的字符串进行解码void Huf
10、fman:Decode(char * d, char *s,int n) /解码 cout解码为： ; if(n2) while(*d!=0) coutHCodeTable0.data; d+;while(*d!=0) int parent=2*n-1-1 ; / 根节点在HTree中的下标while(HTreeparent.LChild!=-1) if(*d=0) parent=HTreeparent.LChild;else parent=HTreeparent.RChild;d+;*s=HCodeTableparent.data;cout*s;s+;coutendl;8。主函数，包含了交互
11、的操作。void main() string buffer; char*d; char*s; int i,q,j=0,n=0,realcountsN; char countsN, cN; d=&c0; int count127; for(i=0;i127;i+) counti=0; cout请输入初始化的字符串(英文):nendl; getline(cin,buffer);s=&buffer0; while(bufferj!=0)count bufferj+;/不同字符的个数j+; j=0;for(i=0;i127;i+) if(counti!=0)realcountsj=counti;/提取
12、出真正存在的字符的权值countsj=i;/j+;n+;Huffman h; menu:cout1-察看编译后的文字(包含压缩比)endl;cout2-察看编译前的内容endl; docout请输入想要的操作的编号q;switch(q)case 1:h.CreateHTree(realcounts,n); h.CreateCodeTable(counts,n); h.Encode(s,d); break;case 2:d=&c0; s=&buffer0; h.Decode(d,s,n);break; ;while (q);goto menu;3.程序运行结果分析4.总结4.1实验的难点和关键点（1）获取权值最小的两个字符SelectMin的编写。（2）输入字符种类惟一时要单独讨论。（3）获取存在的字符种类。4.2心得体会通过编程深刻体会了哈夫曼的思想，感受到c+的不足，学会了运用menu 和goto menu.