huffman实验报告

1、一、 问题描述 1. 实验题目：huffman编解码2. 基本要求：初始化（initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立huffman 树，并将它存入hfmtree 中。 编码（encoding）。利用已经建好的huffman树（如果不在内存，则应从文件hfmtree中读取），对文件tobetran中的正文进行编码，然后将结果存入文件codefile中。 解码（decoding）。利用已经建立好的huffman树将文件codefile中的代码进行解码，结果存入textfile中。 打印代码文件（print）。将文件codefile以紧凑的格式显示在终端上

2、，每行 50 个代码。同时将此字符形式的编码文件写入文件codeprint中。 打印huffman树（tree printing）。将已经在内存中的huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的huffman 树写入文件treeprint中。 3. 测试数据：用下表给出的字符集和频度的实际统计数据建立huffman树，并对以下报文进行编码和译码：“this program is my favorite”。 字符a b c d e f g h i j k l m 频度 18664 13 22 32 10321 15 47 57 1 5 32 20 字符 n o

3、p q r s t u v w x y z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 输入输出: 字符集大小 n，n个字符和 n个权值均从终端读入，初始化后的huffman树存储在hfmtree文件中，待编码文件为tobetran,编码结果以文本的方式存储在文件codefile中，解码文件存在textfile中,打印的编码和赫夫曼树分别存储在codeprint和treeprint文件中。 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上一个退出功能“q”，表示退出（quit）。用户键入一个选择功能符，此功能执行完毕后再显示此菜单，直至某次用户选择了q为

4、止。 二、 需求分析 1. 本程序可以根据输入字符集和频度建立huffman树并且对给定文本进行编解码，还可以直接读入建立好的huffman树再对给定文本编解码，打印编码、解码结果、表格形式及树形的huffman树。2. 程序运行后显示提示信息，提示用户选择要进行的操作。i：按提示输入字符总数，然后是每个字符及其权值(输入时以逗号分隔)，字符为char型，权值为整型。e：输入字符的总数。d：无需输入。p：无需输入。t：无需输入。q：结束程序。3. 用户输入完毕后，输出结果如下： i：建立的huffman树以列表形式被存入hfmtree.txt中。每行的数据从左到右依次为节点中储存的字符，节点的

5、左孩子序号，节点的双亲序号，节点的右孩子序号，节点的权值。e：编码结果存入文件codefile.txt中。d：解码结果存入文件textfile.txt中。p：将编码结果以紧凑的格式显示在终端上，每行 50 个代码。同时此字符形式的编码文件被写入文件codeprint.txt中。t：huffman树以树形显示在终端上，同时此字符形式的huffman树被写入文件treeprint.txt中。q：程序结束。三、 概要设计 为了实现上述功能，需要链表、栈、队列、二叉树四个抽象数据类型。 1. 链表抽象数据类型定义：adt lnode 数据对象： d=ai|ailnode,i=1,2.,n,n0 数据关

6、系：r=|ai-1,aid, ai-1ai ,i=2,.,n 基本操作：/初始化链表 void initlist_l(linklist &l); /判断链表是否为空 bool listempty_l(linklist l); /求链表长度 int listlength_l(linklist l); /插入元素 bool listinsert_l(linklist &l,int i,elemtype e); /删除元素 bool listdelete_l(linklist &l,int i,elemtype &e); adt lnode2. 栈抽象数据类型定义adt sqstack数据对象：d=

7、ai|aisqstack,i=1,2.,n,n0 数据关系：r=|ai-1,aid, ai-1ai ,i=2,.,n基本操作：/初始化栈bool initstack_sq(sqstack &s,int msize);/判断栈是否空bool stackempty_sq(sqstack s);/求栈长度int stacklength_sq(sqstack s);/元素入栈bool push_sq(sqstack &s, selemtype e);/元素出栈bool pop_sq(sqstack &s,selemtype &e); adtsqstack3. 队列抽象数据类型定义adt linkque

8、ue数据对象：d=ai|ailinkqueue,i=1,2.,n,n0 数据关系：r=|ai-1,aid, ai-1ai ,i=2,.,n基本操作：/初始化队列bool initqueue_l(linkqueue &q);/判断队列是否为空bool stackfull_sq(sqstack s);bool queueempty_l(linkqueue q);/求队列长度bool gethead_l(linkqueue q,qelemtype &e);/元素入队列bool enqueue_l(linkqueue &q, qelemtype e);/元素出队列bool dequeue_l(link

9、queue &q,qelemtype &e); adt linkqueue4. 二叉树抽象数据类型定义adt htnode数据对象：d=ai|aihtnode,i=1,2.,n,n0 数据关系：r=|ai-1,aid, ai-1ai ,i=2,.,n基本操作：/求每个节点层次void level(hufftree ht,int y,int l,int lev);/中序遍历打印树形huffmantreevoid inorder(hufftree ht,file *fp,int k,int a);/选择权值最小的两个节点void select(hufftree ht,int t,int &q1,i

10、nt &q2);/初始化huffman树void huffmantree(hufftree ht,char *code,int *w,int n);/huffman编码void coding(hufftree ht,int root,char *hc,sqstack &s); adt htnode5.本程序保护模块： 主程序模块 huffman单元模块：实现二叉树的抽象数据类型 stack单元模块：实现链表、栈、队列抽象数据类型 调用关系：主程序模块-huffman单元模块-stack单元模块四、 详细设计 1.结点类型和结点指针类型： 链表：typedef struct lnodechar

11、data;struct lnode *next;lnode，*linklist;栈：typedef structselemtype * elem;int stacksize;int top;sqstack;队列：typedef linklist queueptr; typedef structqueueptr front; queueptr rear;linkqueue; 二叉树：typedef structint weight;char data;int parent,lchild,rchild;htnode;typedef htnode *hufftree;2. 链表的实现 本实验只用到链

12、表节点类型的定义，用来定义queueptr,没有用到实现链表操作的函数。3.栈的实现/元素入栈bool push_sq(sqstack &s, selemtype e)if(stackfull_sq(s)return false;s.elem+s.top=e;return true;其余略4.队列的实现bool dequeue_l(linkqueue &q,qelemtype &e)if(q.front=q.rear)return false;queueptr p=q.front-next;q.front-next=p-next;e=p-data;if(q.rear=p)q.rear=q.fr

13、ont;delete p;return true;其余略5.二叉树的实现/选择权值最小的两个节点void select(hufftree ht,int t,int &q1,int &q2) int i,j;for(i=1;i=t*2-1;i+)if(hti.parent=0)q1=i;break;for(i=1;i=t*2-1;i+)if(hti.weighthtq1.weight&hti.parent=0&hti.weight!=0)q1=i;for(i=1;i=t*2-1;i+)if(hti.parent=0&i!=q1)q2=i;break;for(j=1;j=t*2-1;j+)if(h

14、tj.weighthtq1.weight)q2=j;/初始化huffman树void huffmantree(hufftree ht,char *code,int *w,int n)int m=n*2-1,i,s1,s2;for(i=1;i=m;i+)hti.lchild=hti.rchild=hti.parent=0;hti.weight=i=n?wi:0;hti.data=i=n?codei:#;for(i=n+1;i=m;i+)select(ht,n,s1,s2);hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight

15、;hts1.parent=hts2.parent=i;/huffman编码void coding(hufftree ht,int root,char *hc,sqstack &s)char ch,e;if(root!=0)if(htroot.lchild=0)push_sq(s,0);hcroot=new charstacklength_sq(s);strcpy(hcroot,s.elem);pop_sq(s,ch);push_sq(s,0);coding(ht,htroot.lchild,hc,s);pop_sq(s,e);push_sq(s,1);coding(ht,htroot.rchi

16、ld,hc,s);pop_sq(s,e);/求节点深度void level(hufftree ht,int y,int l,int lev)if(y!=0)lev+;ly=lev;level(ht,hty.lchild,l,lev);level(ht,hty.rchild,l,lev);/中序遍历打印树形huffmantreevoid inorder(hufftree ht,file *fp,int k,int a)int le=0,i;if(k=0) return; elseinorder(ht,fp,htk.rchild,a);le=ak; for(i=0;ilchild, htht-rc

17、hild, htht-parent。原先编写是inorder每次执行时，同时调用level算出节点层次，但是结果一直不对（现在还没发现错误在哪(*_*) ），后来在同学的建议下先用一个数组存储所有节点的level，然后在inorder中使用，得到了正确的结果。5.复杂度分析函数 时间复杂度 空间复杂度select o(n) o(1)huffmantree o(n) o(n)coding o(n) o(n)level o(n) o(n)inorder o(n) o(n)六、 使用说明 程序运行后根据提示输入所要进行的操作，字符集大小 n，n个字符和 n个权值。程序将初始化后的huffman树存储

18、在hfmtree文件中，编码结果以文本的方式存储在文件codefile中，解码文件存在textfile中,打印的编码和哈弗曼树分别存储在codeprint和treeprint文件中。七、 调试结果 用下表给出的字符集和频度的实际统计数据建立huffman树，并对以下报文进行编码和译码：“this program is my favorite”。 字符a b c d e f g h i j k l m 频度 18664 13 22 32 10321 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 频度 57 63 15 1 48 51 80 23

19、8 18 1 16 1 结果：hfmntree:,0,50,0,186a,0,45,0,64b,0,33,0,13c,0,37,0,22d,0,39,0,32e,0,48,0,103f,0,36,0,21g,0,33,0,15h,0,41,0,47i,0,43,0,57j,0,28,0,1k,0,28,0,5l,0,40,0,32m,0,36,0,20n,0,44,0,57o,0,44,0,63p,0,34,0,15q,0,29,0,1r,0,42,0,48s,0,42,0,51t,0,46,0,80u,0,37,0,23v,0,31,0,8w,0,35,0,18x,0,30,0,1y,0,3

20、4,0,16z,0,31,0,1#,11,29,12,6#,18,30,28,7#,25,32,29,8#,27,32,23,9#,30,35,31,17#,3,38,8,28#,17,38,26,31#,32,39,24,35#,14,40,7,41#,4,41,22,45#,33,43,34,59#,5,45,35,67#,13,46,36,73#,37,47,9,92#,19,47,20,99#,10,48,38,116#,15,49,16,120#,2,49,39,131#,40,50,21,153#,41,51,42,191#,6,51,43,219#,44,52,45,251#,4

21、6,52,1,339#,47,53,48,410#,49,53,50,590#,51,0,52,1000codefile：11010001011000111110111100010100101110100101010110010111011000111111100100111111111100111010101110111001001001101101010textfile：this program is my favoritecodeprint：11010001011000111110111100010100101110100101010110010111011000111111100100

22、111111111100111010101110111001001001101101010treeprint： # t # f # m # l # w # v # z # k # j # q # x # d # a # o # n # y # p # g # b # i # e # s # r # h # u # c程序截屏：初始化编码解码打印树八、 附录 源代码：huffman.hvoid level(hufftree ht,int y,int l,int lev);void inorder(hufftree ht,file *fp,int k,int a);void select(huff

23、tree ht,int t,int &q1,int &q2);void huffmantree(hufftree ht,char *code,int *w,int n);void coding(hufftree ht,int root,char *hc,sqstack &s);int mygetint(file *fp);stack.htypedef structint weight;char data;int parent,lchild,rchild;htnode;typedef struct lnodechar data;struct lnode *next;lnode,*linklist

24、;typedef htnode *hufftree;typedef char qelemtype; /elemtype 定义为char类型typedef linklist queueptr; /结点指针typedef structqueueptr front; queueptr rear;linkqueue; /链队列定义typedef char selemtype; /elemtype 定义为char类型typedef structselemtype * elem;int stacksize;int top;sqstack;/初始化栈bool initstack_sq(sqstack &s,

25、int msize);bool stackempty_sq(sqstack s);/判断栈是否满/求栈长度int stacklength_sq(sqstack s);/元素入栈bool push_sq(sqstack &s, selemtype e);/元素出栈bool pop_sq(sqstack &s,selemtype &e);/遍历元素bool initqueue_l(linkqueue &q);/判断队列是否为空bool stackfull_sq(sqstack s);bool queueempty_l(linkqueue q);/求队列长度bool gethead_l(linkqu

26、eue q,qelemtype &e);/元素入队列bool enqueue_l(linkqueue &q, qelemtype e);/元素出队列bool dequeue_l(linkqueue &q,qelemtype &e);void strclear(char str);huffman.cpp#include#include#include#includestack.hvoid select(hufftree ht,int t,int &q1,int &q2) /选择权值最小的两个节点 int i,j;for(i=1;i=t*2-1;i+) /q1赋初值if(hti.parent=0)

27、q1=i;break;for(i=1;i=t*2-1;i+) if(hti.weighthtq1.weight&hti.parent=0&hti.weight!=0)q1=i;for(i=1;i=t*2-1;i+)if(hti.parent=0&i!=q1) /q2赋初值q2=i;break;for(j=1;j=t*2-1;j+)if(htj.weighthtq1.weight)q2=j;void huffmantree(hufftree ht,char *code,int *w,int n) /建立哈弗曼树int m=n*2-1,i,s1,s2;for(i=1;i=m;i+)hti.lchi

28、ld=hti.rchild=hti.parent=0;hti.weight=i=n?wi:0;hti.data=i=n?codei:#;for(i=n+1;i=m;i+)select(ht,n,s1,s2);hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;hts1.parent=hts2.parent=i;void coding(hufftree ht,int root,char *hc,sqstack &s) /哈弗曼编码char ch,e;if(root!=0)if(htroot.lchild=0)push_sq

29、(s,0);hcroot=new charstacklength_sq(s);strcpy(hcroot,s.elem);pop_sq(s,ch);push_sq(s,0);coding(ht,htroot.lchild,hc,s);pop_sq(s,e);push_sq(s,1);coding(ht,htroot.rchild,hc,s);pop_sq(s,e);void level(hufftree ht,int y,int l,int lev) /求每个节点层次，赋值给数组levif(y!=0)lev+;ly=lev;level(ht,hty.lchild,l,lev);level(ht

30、,hty.rchild,l,lev);void inorder(hufftree ht,file *fp,int k,int a) /中序遍历打印哈弗曼树int le=0,i;if(k=0) return; elseinorder(ht,fp,htk.rchild,a);le=ak; for(i=0;i=48&s=57) /读取 numj+=s; s=getc(fp);for(k=0;kj;k+) /将读取结果转化成整数 i=i*10;i=i+(numk-48);return i;stack.cpp#include#include#includetypedef structint weight

31、;char data;int parent,lchild,rchild;htnode;typedef htnode *hufftree;typedef struct lnodechar data;struct lnode *next;lnode,*linklist;typedef htnode *hufftree;typedef char qelemtype; /elemtype 定义为char类型typedef linklist queueptr; /结点指针typedef structqueueptr front; queueptr rear;linkqueue; /链队列定义typede

32、f char selemtype; /elemtype 定义为char类型typedef structselemtype * elem;int stacksize;int top;sqstack;/初始队列bool initqueue_l(linkqueue &q)q.front=q.rear=new lnode;/ 给elem指针动态分配msize长度的数组if(!q.front)cerr分配内存错误!next;return i;bool enqueue_l(linkqueue &q, qelemtype e)queueptr p=new lnode;if(!p)return false;p

33、-data=e;p-next=null;q.rear-next=p;q.rear=p;return true;/元素出队列bool dequeue_l(linkqueue &q,qelemtype &e)if(q.front=q.rear)return false;queueptr p=q.front-next;q.front-next=p-next;e=p-data;if(q.rear=p)q.rear=q.front;delete p;return true;/初始化栈bool initstack_sq(sqstack &s,int msize)s.elem=new selemtypems

34、ize;/ 给elem指针动态分配msize长度的数组if(!s.elem)cerr分配内存错误!endl;return false;s.stacksize=msize; /顺序栈的最大容量s.top=-1; / 顺序栈初始时空栈return true;/判断栈是否为空bool stackempty_sq(sqstack s)return (s.top=-1);/判断栈是否满bool stackfull_sq(sqstack s)return(s.top=s.stacksize-1);int stacklength_sq(sqstack s)return s.top+1;/元素入栈bool p

35、ush_sq(sqstack &s, selemtype e)if(stackfull_sq(s)return false;s.elem+s.top=e;return true;/元素出栈bool pop_sq(sqstack &s,selemtype &e)if(stackempty_sq(s)return false;e=s.elems.top-;return true;void strclear(char str)str0=0;huffmanoperate.cpp#include#include#include#includestack.h#includehuffman.hvoid ma

36、in()file *fp,*fp1,*fp2,*fp3,*fp4,*fp5;char ch,choice,e,str30,codeelem30;int n,i,k=0,weight30,ll60;htnode hht60; linkqueue qq;char *hhc;doprintf(请选择要进行的操作（i：初始化哈弗曼树；e：用建立的树进行编码；d：解码文件；p：打印密码；t：打印哈弗曼树；q：终止操作）:);scanf(%c,&choice);fflush(stdin);if(choice=i)printf(输入字符数目:); scanf(%d,&n); fflush(stdin);fo

37、r(i=1;i=n;i+)printf(输入第%d个字符和&权值（逗号分隔）:,i);scanf(%c,%d,&codeelemi,&weighti);fflush(stdin);huffmantree(hht,codeelem,weight,n);if(fp=fopen(hfmtree.txt,w)=null)printf(cant open hfmtree);exit(1);for(i=1;i=n*2-1;i+)fprintf(fp,%c,%d,%d,%d,%d,hhti.data,hhti.lchild,hhti.parent,hhti.rchild,hhti.weight); fput

38、c(n,fp);fclose(fp);else if(choice=e)sqstack ss;initstack_sq(ss,30);hhc=new char *n+1;printf(输入字符数目:); scanf(%d,&n); fflush(stdin);if(fp1=fopen(hfmtree.txt,r)=null)printf(cant open tobetran);exit(1);if(fp2=fopen(codefile.txt,w)=null)printf(cant open codefile);exit(1);if(fp=fopen(tobetran.txt,r)=null)printf(cant open codefile);exit(1); for(i=1;i=n*2-1&ch!=eof;i+) /从哈弗曼树列表文件中读取每个节点信息ch=fgetc(fp1