哈夫曼树实验报告_第1页
哈夫曼树实验报告_第2页
哈夫曼树实验报告_第3页
哈夫曼树实验报告_第4页
哈夫曼树实验报告_第5页
已阅读5页,还剩9页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、d parent rchild 哈夫曼树类的数据域,继承节点类型为int的二叉树class huffmantree:public bitreedata:hcode* hcodetable;/编码表int tsize; /编码表中的总字符数二叉树的节点结构template struct binode /二叉树的结点结构t data; /记录数据t lchild; /左孩子t rchild; /右孩子t parent; /双亲;示意图:t datat lchildt rchildt parent编码表的节点结构struct hcodechar data; /编码表中的字符char code100;

3、 /该字符对应的编码;示意图:char datachar code100待编码字符串由键盘输入,输入时用链表存储,链表节点为struct nodechar character; /输入的字符unsigned int count;/该字符的权值bool used; /建立树的时候该字符是否使用过node* next; /保存下一个节点的地址 ;node* nextbool usedunsigned int countchar character示意图: 2.3 关键算法分析: 1.初始化函数(void huffmantree:init(string input))算法伪代码:1.初始化链表的头结

4、点2.获得输入字符串的第一个字符,并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)3.从字符串第2个字符开始,逐个取出字符串中的字符 3.1 将当前取出的字符与链表中已经存在的字符逐个比较,如果当前取出的字符与链表中已经存在的某个字符相同,则链表中该字符的权值加1。 3.2 如果当前取出的字符与链表中已经存在的字符都不相同,则将其加入到链表尾部,同时n+4.tsize=n(tsize记录链表中字符总数,即哈夫曼树中叶子节点总数)5.创建哈夫曼树6.销毁链表 源代码: void huffmantree:init(string input) node *front=new node; /

5、初始化链表的头结点if(!front)throw exception(堆空间用尽); front-next=null;front-character=null;front-count=0;node *pfront=front;char ch=input0; /获得第一个字符 node* new1=new node;if(!new1) throw exception(堆空间用尽);new1-character=ch; /将第一个字符插入链表new1-count=1;new1-next=pfront-next;pfront-next=new1;bool replace=0; /判断在已经写入链表的

6、字符中是否有与当前读出的字符相同的字符int n=1; /统计链表中字符个数for(int i=1;inext; if(int)pfront-character = (int)ch) /如果在链表中有与当前字符相同的字符,该字符权值加1pfront-count+;replace=1;break;while(pfront-next); if(!replace) /如果在链表中没找到与当前字符相同的字符,则将该字符作为新成 员插入链表node* new=new node;if(!new)throw exception(堆空间用尽);new-character=ch;new-count=1;new-

7、next=pfront-next;pfront-next=new;n+;pfront=front; /重置pfront和replace变量为默认值replace=0;tsize=n; /tsize记录的是编码表中字符个数createhtree(front,n); /创建哈夫曼树pfront=front;while(pfront) /销毁整个链表front=pfront;pfront=pfront-next;delete front; 时间复杂度: 若输入的字符串长度为n,则时间复杂度为o(n)2.创建哈夫曼树(void huffmantree:createcodetable(node *p))

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

9、e:createhtree(node *p,int n) root= new binode2*n-1; /初始化哈夫曼树node *front=p-next;if(n=0)throw exception(没有输入字符);for(int i=0;icount;rooti.lchild=-1;rooti.rchild=-1;rooti.parent=-1;front=front-next;front=p; int new1,new2; for(i=n;inext; for(int i=0;icharacter; /将第i个字符写入编码表 int child=i; /得到第i个字符对应的叶子节点 i

10、nt parent=rooti.parent; /得到第i个字符对应的叶子节点的双亲 int k=0; if(tsize=1) /如果文本中只有一种字符,它的编码为0 hcodetablei.codek=0; k+; while(parent!=-1) /从第i个字符对应的叶子节点开始,寻找它到根结点的路径 if(child=rootparent.lchild) /如果当前结点为双亲的左孩子,则编码为0, 否则编码为1 hcodetablei.codek=0; else hcodetablei.codek=1; k+; child=parent; parent=rootchild.parent

11、; hcodetablei.codek=0; reverse(hcodetablei.code); /将编码逆置 front=front-next; /得到下一个字符 cout编码表为:endl; for(i=0;itsize;i+) /输出编码表 couthcodetablei.data hcodetablei.codeendl; 时间复杂度: 需要遍历哈夫曼树获取编码,时间复杂度为o(n2) 4 选择两个最小权值的函数 算法伪代码:1. 从下标为begin的结点开始,寻找第一个没用过的结点2. 遍历哈夫曼树中从下标为begin到下标为end的结点序列,寻找没用过的同时权值又是最小的结点。3

12、. 暂时改变找到的权值最小结点的双亲域,防止第2次找到相同的结点。4. 将权值最小结点的下标记录下来。5. 重复步骤14,找到第2个权值最小的结点源代码:void huffmantree:selectmin(int &new1,int &new2,int begin,int end)int min;for(int j=0;j2;j+) /要选择两个权值最小的结点int sign=begin;for(int i=begin;iend;i+) /从下标为begin的结点开始,寻找第1个没用过的结点 if(rooti.parent=-1) /没用过的结点其双亲应为空 min=rooti.data;s

13、ign=i; break; for(i=begin;irooti.data)min=rooti.data;sign=i;rootsign.parent=0;/暂时改变所找最小结点的双亲域,防止第2次找到的是同一个结点if(!j)new1=sign;elsenew2=sign; 时间复杂度: 两次遍历链表,时间复杂度为o(n)5. 将字符串倒序的函数(void huffmantree:reverse(char *pch)) 算法伪代码:1 得到字符串的长度2 初始化两个记录下标的变量,一个为字符串开头字符所在的下标i,另一个为字符串结尾字符所在的下标j3 将下标为i和j的字符交换4 i+,j -

14、 - 时间复杂度: 时间复杂度为o(n)6.编码函数(void huffmantree:encode(string &s,string &d)) 算法伪代码: 1. 从s开头的字符开始,逐一对s中的字符进行编码 2. 在编码表中查找与当前字符对应的字符 3如果找到了与当前字符对应的编码表中的字符,将其编码追加到解码串的末尾。 4. 重复以上步骤,直到所有待编码串中的字符都编码完毕 5. 输出编码后的字符串源代码:void huffmantree:encode(string &s,string &d) for(int j=0;js.length();j+) /逐个对待编码字符串中的字符进行编码f

15、or(int i=0;itsize;i+) /在编码表中查找与当前字符对应的编码if(sj = hcodetablei.data)d.append(hcodetablei.code); /编码break;coutdendl; /输出编码后的字符串 时间复杂度: 设待编码字符串长度为n,编码表中字符个数为m,则复杂度为o(n*m)7.解码函数 算法伪代码:1. 得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针2. 逐个读取待解码串中的字符,若为0,则指向哈夫曼树当前结点的指针指向当前结点的左孩子,若为1,则指向当前结点的右孩子3. 指向待解码串的指针指向解码串中的下一个字符,直到

16、指向哈夫曼树结点的指针的孩子结点为空4. 如果哈夫曼树只有一个叶子结点,直接将待解码串中的编码转换为对应的字符5. 如果指向哈夫曼树结点的指针的孩子结点已经为空,则将叶子结点下标对应的字符追加到解码串中。6. 输出解码串 源代码: void huffmantree:decode(string &s,string &d) for(int i=0;is.length();) int parent=2*tsize-1-1; /得到哈夫曼树的根结点 while(rootparent.lchild!=-1) /如果结点不为叶子结点 if(si=0) /编码为0则寻找其左孩子 parent=rootpar

17、ent.lchild; else /编码为1则寻找右孩子 parent=rootparent.rchild; i+; if(tsize=1) /如果编码表只有一个字符,则根结点即为叶子结点 i+; d.append(1,hcodetableparent.data);/将叶子节点对应的字符追加到解码串中 coutdendl; 时间复杂度: 设待解码串长度为n,则复杂度为o(n)8. 计算哈夫曼编码的压缩比(void huffmantree:calculate(string s1,string s2)) 算法伪代码:1. 获得编码前字符串的长度,即其占用的字节数2. 获得编码后的字符串的长度,将其

18、除以8然后向上取整,得到其占用的字节数3. 压缩比将两个相除源代码: void huffmantree:calculate(string s1,string s2) int cal1=s1.length(); int cal2=s2.length(); cal2=ceill(float)cal2/8); /将编码串的比特数转化为字节数 cout编码前的字符串长度:cal1endl; cout编码后的字符串长度:cal2endl; cout压缩比为:(double)cal2/(double)cal1)*100%endl; 时间复杂度: o(1)9. 打印哈夫曼树(void huffmantree

19、:printtree(int treenode,int layer) ) 算法伪代码:1. 如果待打印结点为空,则返回2. 递归调用函数打印当前结点的右子树3. 根据当前结点所在的层次确定其前面要输出多少空格,先输出空格,在打印当前结点的权值4. 递归调用函数打印当前结点的左子树 源代码: void huffmantree:printtree(int treenode,int layer) if(treenode=-1) /如果待打印结点为空,则返回return;elseprinttree(roottreenode.rchild,layer+1); /先打印该结点的右子树,layer记录的是该

20、结点所在的层次for(int i=0;ilayer*2;i+) /根据该结点所在的层次,确定在它之前需要打印多少空格cout ;coutroottreenode.dataendl; /打印该结点的权值printtree(roottreenode.lchild,layer+1); /打印该结点的左子树 时间复杂度: 中序遍历哈夫曼树,复杂度为o(n)10. 菜单函数(void huffmantree:menu()) 算法伪代码: 1. 逐一读取键盘缓存区中的字符,并将它们逐一追加到记录输入字符串的string变量中,直到读到回车输入符为止 2. 删除string变量末尾的回车输入符 3利用string变量创建哈夫曼树,初始化编码表。 4. 直观打印哈夫曼树 5. 对输入的字符串进行编码 6. 对编码后的字符串进行解码 7. 计算编码前后的压缩比并输出 源代码: void huffmantree:menu() cout请输入你要编码的文本,按回车键确定输入endl; string input; char letter; do /将字符逐个读入input变量中 letter=cin.

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论