实验三哈夫曼树实验.docx

数据结构实验报告实验名称：实验三 树学生姓名：宗妍班级：2011211101班内序号：28学号：2011210028日期：2012年12月7号实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。打印(Print)：以直观的方式打印赫夫曼树（选作）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2、 程序分析2.1存储结构（1）二叉树template class Tclass BiTree{public: BiTree(); //构造函数，其前序序列由键盘输入 ~BiTree(void); //析构函数 BiNodeT* Getroot(); //获得指向根结点的指针protected: BiNodeT *root;//指向根结点的头指针};//声明类BiTree及定义结构BiNodeData： 二叉树是由一个根结点和两棵互不相交的左右子树构成。 二叉树中的结点具有相同数据类型及层次关系。示意图： root lchild parent rchild （2）静态三叉链表struct HNode//哈夫曼树的静态三叉链表{ unsigned int weight;//结点权值 unsigned int parent;//双亲指针 unsigned int Lchild;//左孩子指针 unsigned int Rchild;//右孩子指针};示意图：(3) 编码表的节点结构struct HCode//字符及其编码结构{ char data; char code[100];};示意图：2.2关键算法分析一：关键算法 (一)初始化函数 void Huffman::Init(int a[],int n)（1）算法自然语言创建一个长度为2*n -1的三叉链表将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空从三叉链表的第n个结点开始，i=n从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4. 根据哈夫曼树创建编码表（2）源代码void Huffman::Init(int a[],int n)//创建哈夫曼树{//二叉树只有度为和度为的结点时，总结点数为（n-1）个 HTree=new HNode[2*n-1];//根据权重数组a[1—n]初始化哈夫曼树 int i,x,y; for(i=0;in;i++)//n个叶子结点 { HTree[i].weight=a[i]; HTree[i].Lchild=-1; HTree[i].Rchild=-1; HTree[i].parent=-1; } for(int i=n;i2*n-1;i++)//开始建哈夫曼树，从底层向顶层搭建 { SelectMin(HTree,i,x,y);//从--(i-1)中选出两个权值最小的结点 HTree[x].parent=i; 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; }}(3)时间复杂度在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数的时间复杂度为O（n^2）（二）统计字符出现频度的代码（1）算法自然语言①用cin.getline（）函数获取一段字符串。同时设置一个权值数组weight，以及暂时统计和存放权值的数组s。②用 strlen（）函数获取未编码时的字符串长度。③从字符串的起始位置进行权值统计，即获得str[i