哈夫曼树实验报告

1、数据结构实验报告实验名称：实验三哈夫曼树学生姓名：班 级：班内序号：学 号：日 期：程序分析：2.1存储结构：二叉树2.2程序流程：template class BiTreepublic:BiTree();/构造函数，其前序序列由键盘输入BiTree(void);/ 析构函数BiNode* Getroot();/获得指向根结点的指针protected:BiNode *root;/指向根结点的头指针；/声明类BiTree及定义结构BiNodeData :二叉树是由一个根结点和两棵互不相交的左右子树构成二叉树中的结点具有相同数据类型及层次关系示意图： root哈夫曼树类的数据域，继承节点类型为in

2、t的二叉树 class Huffma nTree:public BiTreedata:HCode* HCodeTable;/编码表int tSize;/编码表中的总字符数二叉树的节点结构template struct BiNode/二叉树的结点结构T data;/记录数据T lchild;/左孩子T rchild;/右孩子T pare nt;/双亲；示意图:T dataT lchildT rchildT pare nt编码表的节点结构struct HCode/编码表中的字符char data;char code100;/该字符对应的编码;示意图:char datachar code100待编码

3、字符串由键盘输入，输入时用链表存储，链表节点为struct Node；示意图:char characterun sig ned int countbool usedNode* nextchar character;/输入的字符un sig ned int coun t;该字符的权值bool used;/建立树的时候该字符是否使用过Node* next;/保存下一个节点的地址2.3关键算法分析:1. 初始化函数(void Huffma nTree:l ni t(stri ng In put)算法伪代码：1. 初始化链表的头结点2. 获得输入字符串的第一个字符，并将其插入到链表尾部,n=1（n记录

4、的是链表中字符的个数）3. 从字符串第2个字符开始，逐个取出字符串中的字符3.1将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。3.2如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到链表尾部，同时n+4. tSize=n（tSize记录链表中字符总数，即哈夫曼树中叶子节点总数）5. 创建哈夫曼树6. 销毁链表源代码：void Huffma nTree:l nit（stri ng In put）Node *front=new Node;/初始化链表的头结点if（!fro nt）throw exception

5、（”堆空间用尽”）；fron t- next=NULL;fron t-character=NULL;fron t-co un t=0;Node *pfront=front;char ch=Input0;/ 获得第一个字符Node* New1= new Node;if(!New1)throw exception(” 堆空间用尽);New1-character=ch;/将第一个字符插入链表New1-co un t=1;New1- n ext=pfr ont-n ext;pfront-n ext=New1;字符bool replace=0; /判断在已经写入链表的字符中是否有与当前读出的字符相同的i

6、nt n=1;/统计链表中字符个数for(i nt i=1;in ext;if(int)pfront-character = (int)ch)/如果在链表中有与当前字符相同的字符，该字符权值加1pfron t-co un t+;replace=1;break;while(pfro nt- next);if(!replace) /如果在链表中没找到与当前字符相同的字符，则将该字符作为新成员插入链表Node* New=n ew Node;if(!New)throw exception(” 堆空间用尽);New-character=ch;New-co un t=1;New- next=pfr on

7、t- next; pfront-n ext=New;n+;/重置pfront和replace变量为默认值/tSize记录的是编码表中字符个数II创建哈夫曼树II销毁整个链表pfront=front;replace=0;tSize=n;CreateHTree(fr on t, n);pfront=front;while(pfr on t)fron t=pfr ont;pfron t=pfro nt-n ext;delete front;时间复杂度：若输入的字符串长度为n,则时间复杂度为0( n)2. 创建哈夫曼树(void HuffmanTree:CreateCodeTable(Node *p)

8、算法伪代码：1. 创建一个长度为 2*tSize-1的三叉链表2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前的data域，并将对应结点的孩子域和双亲域赋为空3. 从三叉链表的第tSize个结点开始，i=tSize3.1从存储字符及其权值的链表中取出两个权值最小的结点 下标x,y。3.2将下标为x和y的哈夫曼树的结点的双亲设置为第3.3将下标为x的结点设置为i结点的左孩子，将下标为i结点的右孩子，i结点的权值为x结点的权值加上 结点的双亲设置为空4根据哈夫曼树创建编码表源代码：tSize个结点x,y，记录其i个结点y的结点设置为y结点的权值，ivoid Huffma nTree:Cr

9、eateHTree(Node *p,i nt n)root= new BiNode2*n-1;/ 初始化哈夫曼树Node *fron t=p-n ext;if(n=0)throw exception(”没有输入字符”)；for(int i=0;ico unt;rooti.lchild=-1;rooti.rchild=-1;rooti.pare nt=-1;front=front-n ext;fron t=p;int New1,New2;for(i=n; in ext;for(i nt i=O;in ext;cout编码表为：e ndl;for(i=0;itSize;i+)coutHCodeT

10、ablei.data HCodeTablei.codee ndl;时间复杂度：需要遍历哈夫曼树获取编码，时间复杂度为0 (nA2 )4 .选择两个最小权值的函数算法伪代码：1. 从下标为begin的结点开始，寻找第一个没用过的结点2. 遍历哈夫曼树中从下标为begin到下标为end的结点序列，寻找没用过的同时权值又是最小的结点。3. 暂时改变找到的权值最小结点的双亲域，防止第 2次找到相同的结点。4. 将权值最小结点的下标记录下来。5. 重复步骤14，找到第2个权值最小的结点源代码：void Huffma nTree:SelectMi n(int & Newl, int & New2,i nt

11、 begi n,int en d)int min;for(int j=0;j2;j+)/要选择两个权值最小的结点int sig n=begi n;for(i nt i=begi n;ie nd;i+)/从下标为begin的结点开始，寻找第1个没用过的结点if(rooti.parent=-1)/没用过的结点其双亲应为空min=rooti.data;sig n=i;break;for(i=begi n;i rooti.data)min=rooti.data; sig n=i;结点rootsign.parent=O;暂时改变所找最小结点的双亲域，防止第 2次找到的是同一个if(!j)New仁sig

12、n;elseNew2=sig n;时间复杂度：两次遍历链表，时间复杂度为0 (n )5.将字符串倒序的函数(void HuffmanTree:Reverse(char *pch)算法伪代码：1 .得到字符串的长度2 .初始化两个记录下标的变量，一个为字符串开头字符所在的下标i，另个为字符串结尾字符所在的下标j3 .将下标为i和j的字符交换4 . i+,j -时间复杂度：时间复杂度为O (n )6. 编码函数(void HuffmanTree:Encode(string &s,string &d)算法伪代码：1. 从s开头的字符开始，逐一对 s中的字符进行编码2. 在编码表中查找与当前字符对应的

13、字符3 如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末尾。4. 重复以上步骤，直到所有待编码串中的字符都编码完毕5. 输出编码后的字符串源代码：void Huffma nTree:E ncode(stri ng &s,stri ng &d)for(int j=O;js.length();j+)/逐个对待编码字符串中的字符进行编码for(int i=O;itSize;i+)/在编码表中查找与当前字符对应的编码if(s j = HCodeTablei.data)d.appe nd(HCodeTablei.code); /编码break;coutdendl;II输出编码后的字符串

14、时间复杂度：设待编码字符串长度为n,编码表中字符个数为 m ,则复杂度为 O (n*m)7.解码函数算法伪代码：1. 得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针2. 逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为1，则指向当前结点的右孩子3. 指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点的指针的孩子结点为空4. 如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的字符5. 如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对应的字符追加到解码串中。6. 输出解码串源代码：void Huf

15、fma nTree:Decode(stri ng &s,stri ng &d)for(i nt i=0;isen gth();)int pare nt=2*tSize-1-1;/得到哈夫曼树的根结点/如果结点不为叶子结点while(rootpare nt .1 child!=-1)if(si=0)/编码为0则寻找其左孩子pare nt=rootpare nt .1 child;else/编码为1则寻找右孩子pare nt=rootpare nt.rchild;i+；if(tSize=1)/如果编码表只有一个字符，则根结点即为叶子结占八、i+;d.appe nd(1,HCodeTablepare

16、 nt.data);将叶子节点对应的字符追加到解码串中coutde ndl;时间复杂度：设待解码串长度为 n ,则复杂度为0(n)8. 计算哈夫曼编码的压缩比( void HuffmanTree:Calculate(string s1,string s2)算法伪代码：1. 获得编码前字符串的长度，即其占用的字节数2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字节数3. 压缩比将两个相除源代码：void HuffmanTree:Calculate(string s1,string s2)int cal1=s1.le ngth();int cal2=s2.le ngth();

17、cal2=ceill(float)cal2/8);/将编码串的比特数转化为字节数cout编码前的字符串长度：cal1e ndl;cout编码后的字符串长度：cal2e ndl;cout压缩比为：(double)ca l2/(double)cal1)*100%e ndl;时间复杂度:0(1)9. 打印哈夫曼树(void HuffmanTree:PrintTree(int TreeNode,int layer)算法伪代码：1. 如果待打印结点为空，则返回2. 递归调用函数打印当前结点的右子树3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打 印当前结点的权值4. 递归调用函数打

18、印当前结点的左子树源代码：void Huffma nTree:Pri ntTree(i nt TreeNode,i nt layer)/如果待打印结点为空，则返if(TreeNode=-1)回return;elsePrintTree(rootTreeNode.rchild,layer+1);/ 先打印该结点的右子树，layer记录的是该结点所在的层次for(i nt i=0;ilayer*2;i+) /根据该结点所在的层次，确定在它之前需要打印多少空格cout;coutrootTreeNode.dataendl;/ 打印该结点的权值PrintTree(rootTreeNode.lchild,l

19、ayer+1);/ 打印该结点的左子树时间复杂度：中序遍历哈夫曼树，复杂度为0(n)10. 菜单函数(void HuffmanTree:Menu()算法伪代码：1.逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的 string变量中，直到读到回车输入符为止2.删除string变量末尾的回车输入符3 .利用string变量创建哈夫曼树，初始化编码表。4. 直观打印哈夫曼树5. 对输入的字符串进行编码6. 对编码后的字符串进行解码7计算编码前后的压缩比并输出源代码：void Huffma nTree:Me nu()cout请输入你要编码的文本按回车键确定输入e ndl;stri ng

20、 In put;char letter;doletter=c in. get();In put.appe nd(1,letter);while(letter!=n);In put.erase(I nput.le ngth()-1,1);Ini t(I nput);/将字符逐个读入In put变量中/去掉In put末尾的回车符/根据输入的字符串创建哈夫曼树及其编码cout 直观打印哈夫曼树endl;Prin tTree(2*tSize-1-1,1);II打印哈夫曼树coutnn： stri ng d1,d2;cout 编码后的字符串为endl;En code(I nput,d1);/编码并打印编码串cout 解码后的字符串为endl;Decode(d1,d2);/解码并打印解码串coutASCII码编码与HUFFMAN编码的比较endl;Calculate。nput,d1);/计算编码前后的压缩比2.4其他1.由于题目要求能输入任意长的字符串，所以本程序采用了string的字符串，并采用 string类的类成员函