《北邮信通院数据结构实验报告三哈夫曼编码器》由会员分享，可在线阅读，更多相关《北邮信通院数据结构实验报告三哈夫曼编码器（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验名称： 实验三 树哈夫曼编/解码器学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年12月11日1实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印(Print)：以
2、直观的方式打印赫夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2. 程序分析2.1 存储结构Huffman树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。
3、 weight lchild rchild parent2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weight lchild rchild parent2-1-155-1-156-1-167-1-169-1-17701713238165482967-12.2 关键算法分析（1）计算出现字符的权值 利用ASCII码统计出现字符的次数，再将未出现的字符进行筛选，将出现的字符及頻数存储在数组a中。 void Huffman:Init()int nNum256= 0; /记录每一个字符出现的次数int ch = cin.get(); int i=0; while(ch!=r
4、) & (ch!=n)nNumch+; /统计字符出现的次数stri+ = ch; /记录原始字符串ch = cin.get(); /读取下一个字符stri=0; n = 0; for ( i=0;i0) /若nNumi=0，字符未出现ln = (char)i; an = nNumi; n+;时间复杂度为O（1）；（2）创建哈夫曼树：算法过程： Huffman树采用顺序存储-数组； 数组的前n个结点存储叶子结点，然后是分支结点，最后是根结点； 首先初始化叶子结点元素循环实现； 以循环结构，实现分支结点的合成，合成规则按照huffman树构成规则进行。 关键点：选择最小和次小结点合成。 void
5、 Huffman:CreateHTree()HTree = new HNode 2*n-1; /根据权重数组a0.n-1 初始化Huffman树for (int j = 0; j n; j+) HTreej.weight = aj;HTreej.LChild = HTreej.RChild = HTreej.parent = -1; int x,y; for (int i = n; i 2*n-1; i+) /开始建Huffman树 SelectMin( HTree, i, x, y); /从1i中选出两个权值最小的结点HTreex.parent = HTreey.parent = i;HTr
6、eei.weight = HTreex.weight+ HTreey.weight;HTreei.LChild = x;HTreei.RChild = y;HTreei.parent = -1;时间复杂度为O(n2)void Huffman:SelectMin( HNode *hTree,int n, int &i1, int &i2 ) int i; /找一个比较值的起始值 for(i=0; in; i+) /找i1 if(hTreei.parent=-1 ) i1=i; break; i+; for( ; ihTreei2.weight) /i1指向最小的 int j=i2; i2=i1;
7、 i1 = j; /开始找最小的两个 i+; for( ; in; i+) if(hTreei.parent=-1 & hTreei.weight hTreei1.weight ) i2=i1; i1 = i; else if( hTreei.parent=-1 & hTreei.weight hTreei2.weight) i2=i; 时间复杂度为O(n)(3)创建编码表算法过程：从叶子到根-自底向上 首先定义码表存储空间； 循环对n个叶子结点自底向上回溯到根，记下途径的左右关系，形成编码的逆序串； 将各个叶子结点对应的逆序串反序即可。 void Huffman:CreateCodeTabl
8、e() HCodeTable = new HCoden; /生成编码表for (int i=0;in;i+)HCodeTablei.data = li; int child = i;/孩子结点编号 int parent = HTreei.parent; /当前结点的父结点编号 int k=0; while(parent!=-1) if (child=HTreeparent.LChild) /左孩子标0 HCodeTablei.codek = 0; else HCodeTablei.codek = 1 ; /右孩子标1 k+; child = parent;/迭代 parent = HTreec
9、hild.parent;HCodeTablei.codek = 0;Reverse(HCodeTablei.code); /将编码字符逆置 时间复杂度为O(n)(4)生成编码串将输入的字符串的每一个字符与编码表比较void Huffman:Encode(char *d)/编码，d为编码后的字符串 char *s = str; while(*s!=0)for (int i=0;in;i+)if (*s = HCodeTablei.data )strcat(d, HCodeTablei.code); break;s+;时间复杂度为O(n)（5）解码:算法过程： 从根到叶子-自顶向下 基于huffm
10、an树存储数组，从根结点开始，依据输入待解码串s中码字0或1，分别向左或右跟踪至叶子结点，叶子结点对应的字符（见码表），即为解码得到的字符； 只要s串为结束，重复上述过程 void Huffman:Decode(char* s, char *d) /解码，s为编码串，d为解码后的字符串 while(*s!=0)int parent = 2*n-2; /根结点在HTree中的下标 while (HTreeparent.LChild!=-1) /如果不是叶子结点if (*s=0) parent = HTreeparent.LChild; else parent = HTreeparent.RChi
11、ld;s+;*d = HCodeTableparent.data;d+;时间复杂度为O（n） 2.3 其他 （1）哈夫曼树的输出是以凹入表示法来实现的，具体算法如下：void Huffman:Print(int i, int m)if (HTreei.LChild = -1)coutsetfill( )setw(m+1)lisetfill(-)setw(10-m)n;elsecoutsetfill( )setw(m+1)HTreei.weightsetfill(-)setw(10-m)n;Print(HTreei.LChild,m+1);Print(HTreei.RChild,m+1);（2）统计字符頻数时，利用字符的ASCII码进行计数统计，调用了cin.get()函数开始3. 程序运行程序框图：输入要编码的字符串统计字符頻数生成哈夫曼树
