huffman哈夫曼树编码译码课程设计报告.docx
- 文档编号:13292392
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:28
- 大小:46.15KB
huffman哈夫曼树编码译码课程设计报告.docx
《huffman哈夫曼树编码译码课程设计报告.docx》由会员分享,可在线阅读,更多相关《huffman哈夫曼树编码译码课程设计报告.docx(28页珍藏版)》请在冰点文库上搜索。
huffman哈夫曼树编码译码课程设计报告
数据结构课程设计
信息科学与工程学院:
学院计算机科学与技术专业:
1601计卓级:
班
号:
学
:
学生姓名指导教师:
23
/1
年月日
题目名称
一、实验内容
哈夫曼编码译码系统
【问题描述】
用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼码的编/译码系统。
【基本要求】
1)初始化。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。
2)编码。
利用已建好的哈夫曼树对输入英文进行编码,编码结果存储在数组中。
3)译码。
利用已建好的哈夫曼树将数组中的代码进行译码,结果存入一个字符数组。
4)输出编码。
将编码结果显示在终端上,每行50个代码。
5)输出哈夫曼树。
将哈夫曼树以直观的方式(树或凹入表形式)显示出来。
【实现提示】
用户界面可以设计为“菜单”方式,再加上一个“退出”功能。
请用户键入一个选择功能符。
此功能执行完毕后再显示此菜单,直至某次用户选择了“退出”为止。
参考教材P240-246
【选做内容】
将哈夫曼树保存到文件中,编码和译码的结果也分别存放在两个文本文件中。
23
/2
二、数据结构设计
储存结构
structHNodeType{//字符结构体类型
intweight;//权
intparent;//双亲位置
intlchild;//左孩子
intrchild;//右孩子
charinf;//字符
};
structHcodeType{
存储编码intbit[MaxBit];//intstart;//起始位置};
三、算法设计
1、在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1。
求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码实际上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的父节点回退到根结点,每回退一步,就走过了哈夫曼的一个分支,从而得到一位哈夫曼编码值。
由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码为所求的高位
2、初始化为从键盘接受字符集大小n,以及n个字符和n个权值。
3、建立哈夫曼编码为使用2中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树,即将HuffNode数组中的各个位置的各个域都填上相关的值,并将这个结构体数组存于文件nodedata.dat中。
voidCreat_Haffmantree(int&n){//建树并输出树
n++;
HNodeType*HaffNode=newHNodeType[2*n-1];
23
/3
inti,j;
intm1,m2,x1,x2;
for(i=0;i<2*n-1;i++){//赋初值
HaffNode[i].weight=0;
HaffNode[i].parent=-1;
HaffNode[i].lchild=-1;
HaffNode[i].rchild=-1;
HaffNode[i].inf='0';
}
for(i=0;i 潣瑵? 请输入字符: < cin>>HaffNode[i].inf; 潣瑵? 请输入该字符的权值: < cin>>HaffNode[i].weight; } HaffNode[n-1].inf='';//最后一个为空格空格权值HaffNode[n-1].weight=120;// 构造哈夫曼树for(i=0;i x1=x2=0; for(j=0;j m2=m1; x2=x1; m1=HaffNode[j].weight; x1=j; }else{ if(HaffNode[j].parent==-1&&HaffNode[j].weight m2=HaffNode[j].weight; 23 /4 x2=j; } } } //合并Huffman树 HaffNode[x1].parent=n+i; HaffNode[x2].parent=n+i; HaffNode[n+i].weight=HaffNode[x1].weight+HaffNode[x2].weight; HaffNode[n+i].lchild=x1; HaffNode[n+i].rchild=x2; HaffNode[n+i].inf=''; } //输出树 潣瑵? 显示存储的哈弗曼树信息: < cout<<权值左孩子右孩子父节点< for(i=0;i<2*n-1;i++){ cout< cout< : right)< cout< : right)< cout< : right)< cout< : right)< } //写入文件 fstreamoutfile1; out(E: \\nodedata.dat,ios: : out|ios: : trunc|ios: : binary);//建立进行写入的文件并清空之前数据 if(! outfile1){//没有创建成功则显示相应信息 cout<< odedata.dat文件不能打开< abort(); } 23 /5 for(i=0;i<2*n-1;i++)//将内存中从HaffNode[i]地址开始的sizeof(HaffNode[i])的内容写入文件中 out((char*)&HaffNode[i],sizeof(HaffNode[i])); out();//关闭文件 delete[]HaffNode; } 中读入相关的字符信息进行哈弗曼编码,然后将结果4、编码系统为从文件nodedata.dat代码串的一一对应关系显示到屏幕上。 1中,同时将字符与0和存入code.dat哈夫曼编码voidHaffCode(int&n){//存储树HNodeType*HaffNode=newHNodeType[Maxnode];//存储编码HcodeType*HaffCode=newHcodeType[Maxleaf];//HcodeTypecd; inti,j,c,p; fstreamin(E: \\nodedata.dat,ios: : in|ios: : binary);//打开文件in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType));//从文件中读取树 in.close();//关闭文件 fstreamoutfile; 建立进行写入的文件out(E: \\codedata.dat,ios: : out|ios: : binary);//进行编码for(i=0;i c=i; p=HaffNode[c].parent; while(p! =-1){ if(HaffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; 23 /6 p=HaffNode[c].parent; } for(j=cd.start+1;j HaffCode[i].bit[j]=cd.bit[j]; HaffCode[i].start=cd.start; } for(i=0;i outfile< for(j=HaffCode[i].start+1;j outfile< } < 字符信息编码信息--for(i=0;i cout< for(j=HaffCode[i].start+1;j 串01cout< } out();//关闭文件 潣瑵? 请输入要编码的字符串,基本元素为(; for(i=0;i cout< cout<<)< charinf[100];//定义输入字符存放数组 getchar(); gets(inf);//读取屏幕字符 intf=strlen(inf); fstreamoutfile1; out(E: \\code.dat,ios: : out|ios: : binary);//建立进行写入的文件 23 /7 if(! outfile1){ cout< < abort(); }else{ cout< 潣瑵? 字符串编码后为: \n; intnum=0; for(intx=0;x for(i=0;i if(inf[x]==HaffNode[i].inf){ for(j=HaffCode[i].start+1;j out((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j])); cout< num++; if(numP==0)cout< } } } } } cout< cout< 潣瑵? 编译后的代码串已经存入code.dat文件中! < cout< out(); delete[]HaffNode; delete[]HaffCode; } 中建立的编码规则将其翻译成字符集1、0、译码系统为接收需要译码的53代码串,按照23 /8 中字符所组成的字符串形式,存入文件text,同时将翻译的结果在屏幕上打印输出。 接受0、1代码串有两种形式,一种是直接输入,一种是从文件中读取。 voiddecode(int&n){ inti; HNodeType*HaffNode=newHNodeType[2*n-1]; fstreaminfile1; in(E: \\nodedata.dat,ios: : in|ios: : binary);//打开文件 if(! infile1){ cout<< odedata.dat文件不能打开< abort(); } for(i=0;i<2*n-1;i++)//从文件里读出Huffman树 in((char*)&HaffNode[i],sizeof(HNodeType)); in();//关闭 inttempcode[100];//定义一个数组存放01串 intnum=0; for(i=0;i<100;i++)//数组初始化 tempcode[i]=-1; HcodeType*Code=newHcodeType[n]; 潣瑵? 请选择要做的操作: < cout<<.输入01串解码< < 从文件中解码cout<<_x0005_. charq; cin>>q; while(q! ='4'&&q! ='5'){ ; 潣瑵? 输入错误请重新输入23 /9 cin>>q; } switch(q){ case'4': { 潣瑵? 请输入要解码的0,1串(按2结束输入): < i=0;chara; while (1){ cin>>a; if(a! ='0'&&a! ='1'&&a! ='2'){ 潣瑵? 输入错误,请重新输入\n; }elsebreak; } if(a=='0'){tempcode[i]=0; } elseif(a=='1'){tempcode[i]=1; } elseif(a=='2'){tempcode[i]=2; } while(tempcode[i]==0||tempcode[i]==1){ i++;num=i; while (1){ cin>>a; if(a! ='0'&&a! ='1'&&a! ='2'){ \n; 潣瑵? 输入错误,请重新输入 }elsebreak; } if(a=='0'){tempcode[i]=0; } elseif(a=='1'){tempcode[i]=1; 23 /10 } elseif(a=='2'){tempcode[i]=2; } } 潣瑵? 输入的编码为: \n; for(i=0;i cout< cout< intm=2*n-2; i=0; 潣瑵? 译码后为: < fstreamoutfile; out(E: \\text,ios: : out);//打开存放翻译结果的文件 if(! outfile){ cout< < abort(); } while(i while(HaffNode[m].lchild! =-1&&HaffNode[m].rchild! =-1){//判断是不 是叶子节点 if(tempcode[i]==0){//0为向左走 m=HaffNode[m].lchild; i++; }elseif(tempcode[i]==1){//1为向右走 m=HaffNode[m].rchild; i++; } } 23 /11 cout< outfile< m=2*n-2; } cout< out(); 潣瑵? 译码后的结果已经存入text中! < delete[]HaffNode;//释放 break; } case'5': { fstreamin读编码 in(E: \\code.dat,ios: : in|ios: : binary); while(! in()){ in((char*)&tempcode[num],sizeof(tempcode[num])); num++; } in(); num--; < 从文件中读出的编码为for(i=0;i cout< 个编码换行50每输出if((i+1)P==0)cout< } cout< intm=2*n-2; i=0; 23 /12 cout< 潣瑵? 译码后为: < fstreamoutfile; out(E: \\text,ios: : out); if(! outfile){ cout< < abort(); } while(i { while(HaffNode[m].lchild! =-1&&HaffNode[m].rchild! =-1){ if(tempcode[i]==0){ m=HaffNode[m].lchild; i++; }elseif(tempcode[i]==1){ m=HaffNode[m].rchild; i++; } } cout< outfile< m=2*n-2; } cout< out();//关闭文件! < 中text delete[]HaffNode;//释放23 /13 break; } } } 四、测试数据及程序运行情况用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码: THISPROGRAMISMYFAVORITE”。 “ABCDEFGHIJKLM字符2057132564132232103211547频度ZVXQRWSTYUNOP字符1 48 8 51 1 57 63 80 15 1 18 23 16 频度 程序运行界面: 树Huffman图2: 程序初始化输出1图: 程序开始界面 1图23 /14 2图23 /15 : 对字符串编码并输出4图: 编码信息输出3图23/16 : 解码系统图6图5: 解码系统 5图图6 23 /17 编Huffman码译退编码系译码系建树 串(文01读出赋初值对已输入的件或键入)字符编码for(i=0;i<2*n-1; 串译码输对01输入字符和权值输出字符与编建树出并保存到文码对应关系 输出Huffman读入一串字符(文件或键入)树 对字符串编码输出并保存到文件 五、实验过程中出现的问题及解决方法Huffman1、用最小堆建立树出现太多错误且过于繁琐不易更改,故改用结构体数组建树。 Huffman、2树输出时,权值大小不同导致显示错乱,故改用输出流控制。 013、编码时出现非字码,原因是定义的存储空间太小。 后多次实验确定合适大小。 23 /18 、编码时读到空格会导致系统停止,后给空格定义了权值。 4dat格式存放数据读取时出现乱码,故改为文件。 5、文件使用txt6、当输出非法字符是会导致系统错乱,后通过修改字符读入方式和循环判定解决问题 六、自我评析与总结的编程以通过本次课程设计,我对哈夫曼树及哈夫曼编码有了更深刻的理解。 同时对C++以及程序及算法的实现和文件的读写产生了比以往更大的兴趣,还学到了许多在处理程序bug美化时的技巧和方法。 如在处理数据时要分配合理的空间,也要及时释放空间。 从刚开始一点头绪都没有,到后来一步步编写成功,查阅了好多资料,也询问了好多同学。 根据老师要求,在译码处不单实现了从键盘读入,同时也实现了从文件读入。 通过这次实验我积累了更多编程的经验。 程序有很多不足的地方,例如程序健壮性不好,二进制读写容易出错等等。 从文件中修改二进制编码功能尝试了很久还是没能完成,没有能实现哈夫曼树的图形化输出,这些都是我们的遗憾。 但是在程序的编写中,我们也完善了很多问题,添加了一些功能,在一定程度上提高了程序的健壮性。 每解决一个问题,我们都会发自内心的感到高兴,这大概就是写程序的乐趣。 通过这次课程设计,让我更好的理解了本学期数据结构的课程知识,也大大提高了我们用编程的能力,我们更加注重添加注释,增强代码的可读性,这都是我们在本次课程设计中c++取得的进步。 七、参考文献清华大学出版社数据结构(面向对象方法与C++语言描述)殷人昆数据结构严蔚敏,吴伟民清华大学出版社 双语版C++语言程序设计电子工业出版社 XX百科CSDN社区 ///源代码 23 /19 #include #include #include #include #include usingnamespacestd; #defineMaxBit50 #defineMaxvalue1000 #defineMaxleaf50 #defineMaxnodeMaxleaf*2-1 structHNodeType{//字符结构体类型 intweight;//权 intparent;//
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- huffman 哈夫曼树 编码 译码 课程设计 报告