软件技术基础论文

《软件技术基础论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》课程论文报告书题冃：哈夫曼树与哈夫曼编码系别：机电系学号：学生姓名:1、基本概念什么是哈弗曼树什么是哈夫曼编码2、基本操作构造哈弗曼树的基本步骤构造哈弗曼树的代码哈夫曼编码的基本介绍3、总结一、基本术语1.什么是哈夫曼树给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffmantree）。例如：有4个结点，权值分别为7,5,2,4,构造有4个叶子结点WPL二7*1+5*2+2*3+4*3=35带权路径WPL值最小。所以此二叉树为哈夫曼树。哈夫曼树的特点：1•权值越小的叶子节点越远离根节点，反Z,贝i

2、j越靠近根节点；2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPLo2•什么是哈夫曼编码哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的

3、每个左分支赋予0,右分支赋予1,则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。例要传输的字符集D二{A,B,C,D}字符出现频率w二{4,3,2,1}根据哈弗曼树的构造特点权值越大越靠近根节点的原则，得到下面这哈弗曼树。A(0>B(10)C(110)11X111):、基本操作1•哈弗曼树构造的基本步骤W二｛5,3,2,4｝哈弗曼树的基本构造过程第一步：初始化｛5,324｝第二步：选取与合并从当中选取两个数一个数字最小另外一个较小第三步：删除与加入｛5,4,重复二三步就构成了最优二叉树。哈夫曼树的类型定义：哈夫曼树是一种二叉树，由于哈夫曼树

4、中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2Xn—l个结点，可以用一个大小为2Xn-l的一维数组存放哈夫曼树的各个结点。由于每个结点同吋还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。静态三叉链表中:每个结点的结构为：权值双亲左孩了序号右孩子序号各结点存储在一维数组中，0号单元不使用，从1号位置开始使用。AdataparentLChildRChild1A0232B1003C1454D3005E300typedefstructHFTreeNodeintweight;/*结点的权值*/intparent;/*双亲的下标*/intlchild;/*左孩子结点的下标*

5、/intrchild;/右孩子结点的下标*/}HFTreeNode,HuffmanTree;2•构造哈弗曼树代码:#defineMaxSize100〃叶子数目#includetypedefstructHFTreeNodeintweight;/*结点的权值*/intparent;丿/*双亲的下标*/intlchild;/*左孩子结点的下标*/intrchild;!*右孩子结点的下标*/}HFTreeNode,HuffmanTree;voidSelect(HuffmanTree*HT,intg,ints[]);voidprint(HuffmanTree*HT,int

6、m);voidCreatHuffmanTree(HuffmanTreeT[MaxSize],intn){inti,p[2],lc,rc;if(n<1){printf(”结点大小不能小于ln);return;}intm=2*n;〃计算哈夫曼树的结点大小for(i=1;i

7、].weight=5;T[2].weight=7;T[3J.weight=3;T[4J.weight=2;T[5].weight=&*/print(T,m);for(i=n4-1;i