哈夫曼编码译码课程设计报告材料

实用文档标准《数据结构》课程设计——赫夫曼编码/译码器设计指导教师：李文书、周维达班级：10电信实验班学号：Q10600132姓名：王彬彬实用文档标准一、实验目的1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。2、熟悉掌握一门计算机语言，可以进行数据算法设计。二、实验原理哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。主要流程图如下：开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I2*N?I++编码为1结束否否否右子是否为空是是否否是是是实用文档标准三、实验步骤1：写好流程图，设计实验方案。2：初始化，从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件HuofumanTree中。3：编码。利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。4：译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。5：印代码文件（Print）.将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。6：印哈夫曼树（Treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。具体函数如下：1：Initialization()初始化2：Encoding()编码3：Decoding()译码4：Print_file()打印代码文件5：search(k,j,p)搜索二叉树6：Print_tree()打印二叉树7：menu()主菜单9：main()主函数四、实验结果与分析（1）大致个人测试案例：主界面：初始化：实用文档标准Huofuman.txt初始化存入文件结果如下：编码结果如下：codefile.txt编码存入文件如下：实用文档标准译码结果如下：textfile.txt译码存入文件如下：打印结果如下：打印树结果如下：treeprint.txt存入文件结果如下：实用文档标准（2）本例测试案例_1已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计哈夫曼编码。解：假设八种字符为ABCDEFGH,将各个概率乘以100可得权值为529781423311启动程序，测试得：初始化：编码：实用文档标准译码打印结束：（3）本例测试案例_2用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMEISMYFAVORITE”。字符ABCDEFGHIJKLM频度1886413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161解：先假设空格为#，所以输入字符时，将空格变为#。输入如下：先将从空格到Z输入权值实用文档标准然后对字符进行编码：实用文档标准实用文档标准空格到Z译码然后输入字符串并编码：保存到Codefile.txt中然后将开始译码并结束将译码结果保存到Textfile.txt中实用文档标准五、实验总结从这个课程设计中，我发现了很多问题，包括文件存储，字符串输入等等，最主要的是经历了一次找BUG的过程，当把自己写的代码里的错误一个一个找出来时，是非常非常兴奋的。还是希望能有多这个经历。不喜欢copy，如果copy了，就缺少了一次挑战自己的经历。六、主要代码//Huffman_2.cpp:Definestheentrypointfortheconsoleapplication.//#includestdafx.h#includestdio.h#includestdlib.h#includestring.h#includemath.h#definemaxsize1000#definelen20#definerowsize20//--------初始化-------------//struct{intparent;intlchild,rchild;intweight;}HFM_tree[maxsize];struct{intweight;charhfstr;}HFM_num[maxsize];struct{实用文档标准intstart;intbit[len];}HFM_hf;struct{intstart;charhfch;intbit[len];intlength;}HFM_code[maxsize];intleaves;voidInitialization(){inti,j;FILE*HFM_f;HFM_f=fopen(HuofumanTree.txt,w);if(HFM_f==NULL){printf(createfileerror!\n);}printf(请输入字符集大小:);scanf(%d,&leaves);fprintf(HFM_f,----输入的值-----\n);fprintf(HFM_f,字符大小%4d\n,leaves);fprintf(HFM_f,字符权值\n);for(i=0;ileaves;i++){printf(请输入第%d个字符和其权值:,i+1);scanf(%c,&HFM_num[i].hfstr);scanf(%d,&HFM_num[i].weight);fprintf(HFM_f,%4c,HFM_num[i].hfstr);fprintf(HFM_f,%4d\n,HFM_num[i].weight);//存储字符和权值}//-----建立哈夫曼树-----//for(i=0;imaxsize;i++)//哈夫曼树初始化{HFM_tree[i].parent=-1;HFM_tree[i].lchild=-1;实用文档标准HFM_tree[i].rchild=-1;HFM_tree[i].weight=0;}for(i=0;ileaves;i++){HFM_tree[i].weight=HFM_num[i].weight;}for(i=0;ileaves-1;i++){intm1,m2;intm1_pos,m2_pos;m1=m2=65536;m1_pos=m2_pos=0;for(j=0;jleaves+i;j++){if(HFM_tree[j].weightm1&&HFM_tree[j].parent==-1){m2=m1;m1=HFM_tree[j].weight;m2_pos=m1_pos;m1_pos=j;}else{if(HFM_tree[j].weightm2&&HFM_tree[j].parent==-1){m2=HFM_tree[j].weight;m2_pos=j;}}}HFM_tree[leaves+i].parent=-1;HFM_tree[leaves+i].lchild=m1_pos;HFM_tree[leaves+i].rchild=m2_pos;HFM_tree[m1_pos].parent=leaves+i;HFM_tree[m2_pos].parent=leaves+i;HFM_tree[leaves+i].weight=m2+m1;}//----输出哈夫曼树----//printf(----------------哈夫曼编码--------------\n);printf(parentlchildrchildweight\n);fprintf(HFM_f,-------------哈夫曼编码------------\n);fprintf(HFM_f,parentlchildrchildweight\n);for(i=0;ileaves*2-1;i++)实用文档标准{printf(%8d%8d%8d%8d\n,HFM_tree[i].parent,HFM_tree[i].lchild,HFM_tree[i].rchild,HFM_tree[i].weight);fprintf(HFM_f,%8d%8d%8d%8d\n,HFM_tree[i].parent,HFM_tree[i].lchild,HFM_tree[i].rchild,HFM_tree[i].weight);}printf(\n);fclose(HFM_f);}//--------编码--------------//voidEncoding(){inti,j,p,c,k;FILE*HFM_f=fopen(CodeFile.txt,w);if(HFM_f==NULL){printf(openfileerror!\n);}for(i=0;ileaves;i++){c=i;p=HFM_tree[i].parent;HFM_hf.start=len-1;while(p!=-1){if(HFM_tree[p].lchild==c){HFM_hf.bit[HFM_hf.start]=0;}else{HFM_hf.bit[HFM_hf.start]=1;}--HFM_hf.start;c=p;p=HFM_tree[c].parent;}for(j=HFM_hf.start+1,k=0;jlen;j++,k++){HFM_code[i].bit[k]=HFM_hf.bit[j];实用文档标准}HFM_code[i].length=len-HFM_hf.start-1;HFM_code[i].start=HFM_hf.start+1;}for(i=0;ileaves;i++){HFM_code[i].hfch=HFM_num[i].hfstr;printf(character:%cstart:%dlength:%dCode:,HFM_code[i].hfch,HFM_code[i].start,HFM_code[i].length);for(j=0;jHFM_code[i].length;j++){printf(%d,HFM_code[i].bit[j]);fprintf(HFM_f,%d,HFM_code[i].bit[j]);}printf(\n);}printf(\n);fclose(HFM_f);}//--------译码--------------//voidDecoding(){chara[maxsize];charHFM_dc[maxsize];inti,j,k,p;FILE*HFM_f=fopen(Textfile.txt,w);FILE*hf=fopen(CodeFile.txt,r);if(HFM_f==NULL){printf(openfileerror!\n);}fscanf(hf,%s,a);j=0;p=0;for(i=0;ileaves;i++){k=2*leaves-2;while(HFM_tree[k].lchild!=-1&&HFM_tree[k].rchild!=-1){if(a[j]=='0')k=HFM_tree[k].lchild;if(a[j]=='1')k=HFM_tree[k].rchild;实用文档标准j++;}HFM_dc[p]=HFM_code[k].