北邮数据结构实验报告

1、北邮数据结构实验报告北京邮电大学信息与通信工程学院XX级数据结构实验报告实验名称：实验三哈夫曼编/解码器的实现学生姓名：陈聪捷日期：XX年11月28日1. 实验要求一、实验目的：了解哈夫曼树的思想和相关概念;二、实验内容：利用二叉树结构实现哈夫曼编/解码器2. 初始化：能够对输入的任意长度的字符串s进行统计，统计每一个字符的频度，并成立哈夫曼树。3. 成立编码表：利用已经建好的哈夫曼树进行编码，并将每一个字符的编码输出。4. 编码：依照编码表对输入的字符串进行编码，并将编码后的字符串输出。5. 译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。6. 打印：以直观的方式打印哈

2、夫曼树。7. 计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的紧缩成效。8. 用户界面能够设计成“菜单”方式，能进行交互，依照输入的字符串中每一个字符显现的次数统计频度，对没有显现的字符一概不用编码。2. 程序分析存储结构二叉树templateclassBiTreepublic:BiTree();/构造函数，其前序序列由键盘输入BiTree(void);/析构函数BiNode*Getroot();/取得指向根结点的指针protected:BiNode*root;/指向根结点的头指针;/声明类BiTree及概念结构BiNodeData：二叉树是由一个根结点和两棵互不相交的左右子

3、树组成哈夫曼树类的数据域，继承节点类型为int的二叉树classHuffmanTree:publicBiTreedata:HCode*HCodeTable;/编码表inttSize;/编码表中的总字符数二叉树的节点结构templatestructBiNode/二叉树的结点结构Tdata;/记录数据Tlchild;/左小孩Trchild;/右小孩Tparent;/双亲;编码表的节点结构structHCodechardata;/编码表中的字符charcode;/该字符对应的编码;待编码字符串由键盘输入，输入时用链表存储，链表节点为structNodecharcharacter;/输入的字符unsi

4、gnedintcount;/该字符的权值boolused;/成立树的时候该字符是不是利用过Node*next;/保留下一个节点的地址;示用意：关键算法分析1.初始化函数(voidHuffmanTree:Init(stringInput)算法伪代码：1. 初始化链表的头结点2. 取得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)3. 从字符串第2个字符开始，逐个掏出字符串中的字符将当前掏出的字符与链表中已经存在的字符逐个比较，若是当前掏出的字符与链表中已经存在的某个字符相同，那么链表中该字符的权值加1。若是当前掏出的字符与链表中已经存在的字符都不相同，那么将其

5、加入到链表尾部，同时n+=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)5. 创建哈夫曼树6. 销毁链表源代码：voidHuffmanTree:Init(stringInput)Node*front=newNode;/初始化链表的头结点if(!front)throwexception("堆空间用尽");front->next=NULL;front->character=NULL;front->count=0;Node*pfront=front;charch=Input;/取得第一个字符Node*New1=newNode;if(!New1)th

6、rowexception("堆空间用尽");New1->character=ch;/将第一个字符插入链表New1->count=1;New1->next=pfront->next;pfront->next=New1;boolreplace=0;/判定在已经写入链表的字符中是不是有与当前读出的字符相同的字符intn=1;/统计链表中字符个数for(inti=1;ich=Input;/取得第i个字符dopfront=pfront->next;if(int)pfront->character=(int)ch)/若是在链表中有与当前字符相同

7、的字符，该字符权值加1pfront->count+;replace=1;break;while(pfront->next);if(!replace)/若是在链表中没找到与当前字符相同的字符，那么将该字符作为新成员插入链表Node*New=newNode;if(!New)throwexception("堆空间用尽");New->character=ch;New->count=1;New->next=pfront->next;pfront->next=New;n+;pfront=front;/重置pfront和replace变量为默许值

8、replace=0;tSize=n;/tSize记录的是编码表中字符个数CreateHTree(front,n);/创建哈夫曼树pfront=front;while(pfront)/销毁整个链表front=pfront;pfront=pfront->next;front;O(n)(void时刻复杂度：假设输入的字符串长度为n,那么时刻复杂度为2. 创建哈夫曼树HuffmanTree:CreateCodeTable(Node*p)算法伪代码：1. 创建一个长度为2*tSize-1的三叉链表2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点的data域，并将对应结点的

9、小孩域和双亲域赋为空3. 从三叉链表的第tSize个结点开始，i=tSize从存储字符及其权值的链表中掏出两个权值最小的结点x,y，记录其下标x,y。将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点将下标为x的结点设置为i结点的左小孩，将下标为y的结点设置为i结点的右小孩，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4. 依照哈夫曼树创建编码表源代码：voidHuffmanTree:CreateHTree(Node*p,intn)root=newBiNode;/初始化哈夫曼树Node*front=p->next;if(n=0)throwexception(&quo

10、t;没有输入字符");for(inti=0;iroot.data=front->count;root.lchild=-1;root.rchild=-1;root.parent=-1;front=front->next;front=p;intNew1,New2;for(i=n;iSelectMin(New1,New2,0,i);/从0i当选出两个权值最小的结点root.parent=root.parent=i;/用两个权值最小的结点生成新结点，新节点为其双亲root.data=root.data+root.data;/新结点的权值为其小孩的权值的和root.lchild=N

11、ew1;root.rchild=New2;root.parent=-1;CreateCodeTable(p);/创建编码表时刻复杂度：在选取两个权值最小的结点的函数中要遍历链表，时刻复杂度为O(n),故该函数的时刻复杂度为0mA2)3. 创建编码表(voidHuffmanTree:CreateCodeTable(Node*p)算法伪代码：1. 初始化编码表2. 初始化一个指针，从链表的头结点开始，遍历整个链表将链表中指针当前所指的结点包括的字符写入编码表中取得该结点对应的哈夫曼树的叶子结点及其双亲若是哈夫曼树只有一个叶子结点，将其字符对应编码设置为0若是不止一个叶子结点，从当前叶子结点开始判定

12、若是当前叶子结点是其双亲的左小孩，那么其对应的编码为0，否那么为1child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复的操作将已完成的编码倒序取得链表中的下一个字符3. 输出编码表源代码：voidHuffmanTree:CreateCodeTable(Node*p)HCodeTable=newHCode;/初始化编码表Node*front=p->next;for(inti=0;iHCodeTable.data=front->character;/将第i个字符写入编码表intchild=i;/取得第i个字符对应的叶子节点intparent=root.par

13、ent;/取得第i个字符对应的叶子节点的双亲intk=0;if(tSize=1)/若是文本中只有一种字符，它的编码为0HCodeTable.code='0'k+;while(parent!=-1)/从第i个字符对应的叶子节点开始，寻觅它到根结点的途径if(child=root.lchild)/若是当前结点为双亲的左小孩，那么编码为0，不然编码为1HCodeTable.code='0'elseHCodeTable.code='1'k+;child=parent;parent=root.parent;HCodeTable.code=''

14、;Reverse(HCodeTable.code);/将编码逆置front=front->next;/取得下一个字符coutfor(i=0;icoutparent=root.lchild;else/编码为1那么寻觅右小孩parent=root.rchild;i+;if(tSize=1)/若是编码表只有一个字符，那么根结点即为叶子结点i+;(1,HCodeTable.data);/将叶子节点对应的字符追加到解码串中cout时刻复杂度：设待解码串长度为n,那么复杂度为O(n)8. 计算哈夫曼编码的紧缩比(voidHuffmanTree:Calculate(strings1,strings2)

15、算法伪代码：1. 取得编码前字符串的长度，即其占用的字节数2. 取得编码后的字符串的长度，将其除以8然后向上取整，取得其占用的字节数3. 紧缩比将两个相除源代码：voidHuffmanTree:Calculate(strings1,strings2)intcal1=();intcal2=();cal2=ceill(float)cal2/8);/将编码串的比特数转化为字节数coutcoutcout时刻复杂度：O(1)9. 打印哈夫曼树(voidHuffmanTree:PrintTree(intTreeNode,intlayer)算法伪代码：1. 若是待打印结点为空，那么返回2. 递归挪用函数打印

16、当前结点的右子树3. 依照当前结点所在的层次确信其前面要输出多少空格，先输出空格，在打印当前结点的权值4. 递归挪用函数打印当前结点的左子树源代码：voidHuffmanTree:PrintTree(intTreeNode,intlayer)if(TreeNode=-1)/若是待打印结点为空，那么返回return;elsePrintTree(root.rchild,layer+1);/先打印该结点的右子树，layer记录的是该结点所在的层次for(inti=0;i空格coutcoutPrintTree(root.lchild,layer+1);/打印该结点的左子树时刻复杂度：中序遍历哈夫曼树，

17、复杂度为O(n)10. 菜单函数(voidHuffmanTree:Menu()算法伪代码：1. 一一读取键盘缓存区中的字符，并将它们一一追加到记录输入字符串的string变量中，直到读到回车输入符为止2. 删除string变量末尾的回车输入符3. 利用string变量创建哈夫曼树，初始化编码表。4. 直观打印哈夫曼树5. 对输入的字符串进行编码6. 对编码后的字符串进行解码7. 计算编码前后的紧缩比并输出源代码：voidHuffmanTree:Menu()coutstring Input;charletter;do/将字符逐个读入Input变量中letter=();(1,letter);while(letter!='');()-1,1);/去掉Input末尾的回车符Init(Input);/依照输入的字符串创建哈夫曼树及其编码表coutPrintTree(2*tSize-1-1,1);/打印哈夫曼树coutstringd1,d2;coutEncode(Input,d1);/编码并打印编码串coutDecode(d1,d2);/解码并打印解码串coutCa