数据结构哈夫曼编码实验

1、线性表及其应用哈夫曼编码实验四/第一组数 据 结 构课程实验报告 姓名：孙越学号：070612020目 录一、【实验目的】3二、【问题描述】3三、【基本要求】3四、【实验环境】3五、【测试数据及其结果】3六、【实验源代码】5一、【实验目的】设计一个哈夫曼编/译码器。二、【问题描述】利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。三、【基本要求】(1)

2、 i：初始化（initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmtree中。(2) e：编码（encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetran中的正文进行编码，然后将结果存入文件codefile中。(3) d：译码（decoding）。利用已建好的赫夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。(4) p：印代码文件（print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codepri

3、n中。(5) t：印赫夫曼树（tree printing）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件treeprint 中。四、【实验环境】windows xp, vc+6.0五、【测试数据及其结果】六、【实验源代码】#include#include#include#includestruct codechar a;int w;int parent;int lchild;int rchild;void creation(code *p,int n,int m);/建立哈夫曼树void coding(code *p,int n);/编码void

4、 translate(char *hc,code *p,int n);/译码void display(code *p,int n,int m);/输出函数void main()int i,n,m;code *ht;printf(字符的数量:n(请输入一个大于的数字,输入多个数字则按第一个数字运行)n);while(scanf(%d,&n)!=1|n9999)printf(重新输入：n);fflush(stdin);m=2*n-1;ht=(code*)malloc(m+1)*sizeof(code);for(i=1;ia|hti.aa|hti.az)printf(重新输入：n);fflush(s

5、tdin);scanf(%c,&hti.a);printf(输入字符的权值(请输入一个数字):n);while(scanf(%d,&hti.w)!=1|hti.w9999)printf(重新输入：n);fflush(stdin);hti.lchild=0;hti.rchild=0;hti.parent=0;for(i=n+1;i=m;i+)hti.a=*;hti.w=0;hti.lchild=0;hti.rchild=0;hti.parent=0;creation(ht,n,m);printf(请按回车进入哈夫曼树对应界面n);getchar();getchar();system(cls);d

6、isplay(ht,n,m);printf(请按回车进入编码对应界面n);getchar();system(cls);coding(ht,n);getchar();void creation(code *ht,int n,int m)int i,j,m1,m2,t1,t2;for(i=n+1;i=m;i+)j=1;while(htj.parent!=0)j+;t1=htj.w;m1=j;for(j=m1+1;j=m;j+)if(htj.parent=0&htj.w!=0)if(htj.wt1)t1=htj.w;m1=j;htm1.parent=i;hti.lchild=m1;j=1;while

7、(htj.parent!=0)j+;t2=htj.w;m2=j;for(j=m2+1;j=m;j+)if(htj.parent=0&htj.w!=0)if(htj.wt2)t2=htj.w;m2=j;htm2.parent=i;hti.rchild=m2;hti.w=t1+t2;void coding(code *p,int n)int i,c,f;char *hc;char *cd;char ch;int start;hc=(char*)malloc(n+1)*sizeof(char *);cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n

8、;i+)start=n-1;for(c=i,f=pi.parent;f!=0;c=f,f=pf.parent)if(pf.lchild=c)cd-start=0;elsecd-start=1;hci=(char*)malloc(n-start)*sizeof(char);strcpy(hci,&cdstart);free(cd);printf(n输出编码后的结果：n);printf(符号数码n);for(i=1;i=n;i+)printf(n%c%sn,pi.a,hci);printf(是否进行译码操作，是则译码，否则退出程序！n是（输入y/y）否（输入其他字符）n);scanf(%d,&ch);if(ch=y|ch=y)translate(hc,p,n);elseexit(0);void translate(char *hc,code *p,int n)char a10,ch;int i,j,c;doprintf(nnn请输入编码：n);scanf(%s,a);for(i=1;in)printf(编码不存在对应的字符！n);printf(是否继续输入?是（输入y或者y）否(其他）n);fflush(stdin);scanf(%c,&ch);while(ch=y|ch=y);void display(code *p,int n,