2023年数据结构哈夫曼树的实验报告

软件学院设计性实验报告专业：网络工程年级/班级:2023—2023学年第一学期课程名称数据结构指导教师本组成员学号姓名实验地点实验时间项目名称哈夫曼编/译码系统的设计与实现实验类型设计性一、实验目的理解哈夫曼树的特性及其应用：在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码;通过该实验，使学生对数据结构的应用有更深层次的理解。二、实验仪器或设备学院提供公共机房，1台/学生微型计算机。三、总体设计（设计原理、设计方案及流程等）.问题描述：运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但是，这规定在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。.一个完整的系统应具有以下功能：）初始化（Initialzation）。从数据文献DataFiledat中读入字符及每个字符的权值，建立哈夫曼树HuffTree;2）编码（EnC。ding）o用已建好的哈夫曼树，对文献ToBeTran.dat中的文本进行编码形成报文，将报文写在文献Code.ixl中；3）译码（Decoding）。运用己建好的哈夫曼树,对文献C。deFi1e.dat中的代码进行解码形成原文，结果存入文献Texlfile.txt中；4）输出（Output）:输出DataFile.dat中出现的字符以及各字符出现的频度（或概率）；输出ToBcTran.dat及其报文Codc.txt；输出CodeFilc.dat及其原文Tcxtfi1e.txt;

五、结果分析与总结1）在做这个实验时前期要做很多准备，由于这个实验操作很复杂，虽然老师已经讲过了大体构思和算法思想，课本上也有相关算法及其伪代码，但翻译成C语言的过程要注意语法等因素，所以要查找一些资料。2）对于不懂得地方要像其他同学虚心请教。3）哈夫曼编码很考验编程者的细心限度，并且涉及的问题也很复杂，培养了我们的细心和耐心。教师署名:

规定:所设计的系统应能在程序执行的过程中,根据实际情况（不同的输入）建立DataFile.dat、ToBeTran.dat和CodeFi1e.dat三个文献，以保证系统的通用性。四、实验环节(涉及重要环节、代码分析等)1)编写C语言程序inc1udc<string.h>inc1ude<maHoc.h>#include<stdio.h>inc1ude<iostream.h>include<math.h>defineTRUE1#define#define#defineI'ALSE#defineI'ALSEttdefineOK1#defineERROR0INFEASIBLEINFEASIBLEINFEASIBLE-1INFEASIBLE-1typedefstruct(hardata;intweight;ointparent,1child,rchi1d;}HTNode,*HuffmanTree;typedefchar^*HuffmanCode；voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,char*d,int*w,intn)〃构造哈弗曼函数HT,构造编码HCvoidselect(HuffmanTreeHT,intn,int&sl,int&s2);式ntm,c,f,j;HuffmanTreep;inti,s1,s2,start；char*cd;m=2*n-l；//m为结点数，n为叶子数HT=(Huffman?ree)maHoc((m+l)*sizeof(HTNode));叩=盯；中++;for(i=1;iV=n;i++,p++)//将叶子的值输入HT中(p->data=d[i]；//={*d,*w,0,0,0};p->weight=w[i];ap—>parent=0；。p->lchild=0；»p->rchild=0;}for(i=n+l;i<=m;i++,p++)//二{'#',0,0,0,0)(op->data=';p—>weight=0；。p->parent=0；p->1child=0;M»p->rchild=O;}OS1=1；s2=2；for(i=n+l;i<=m;i++)〃构建哈夫曼树。se1ect(HT,i-1,s1,s2);HT[i].Ichiid=sl;HT[i].rchi1d=s2；»HT[i].weight=HT[sl].weight+HT[s2].weight;MT[s1].parent=i；HT[s2].parent=i;e)oHO(HuffmanCode)malloc((n+1)*sizeof(HuffmanTree));//开辟空间，编码acd=(char*)malloc(n*sizeof(char));cd[nT]='\0'；for(i=l;i<=n;++i)°(»start=n-l;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)。{。lchild==c)°cd[start]='O';elsecd[—start]=，1)oHC[i]=(char*)malloc((n-start)*sizeof(char))；strcpy(HC[i],&cd[start]);。printf(〃％c的编码是："，HT[i]);。puts(HC[i])；}free(cd)；}voidselect(HuffmanTreeHT,intn,int&sl,int&s2)//求最小两数(ointi,t;%1=1；os2=2;®while(HT[s1].parent!=0)sl++;owhile((HT[s2].parent!=0)I(sl==s2))8s2++;/*for(i=l;i<=n;i++)°(if(HT[si].weight>HT[i].weight&&HT[i].parent==0&&s2!=i)<»sl=i;if(HT[s1].weight>HT[s2].weight)(。t=sl;sl=s2;s2=t;for(i=l;i<=n;i++)(if(sl!=i)oo{。if(HT[s2].weight>HT[i].weight&&HT[i].parent==O)。s2=i;)。}*/for(i=l;i<=n；i++)。(if(sl!=i&&i!=s2)°{if(HT[i].weight<HT[si].weight&&HT.parent-0&&i!=s2)f(HT[sl].weight<HT[s2].weight)s2=s1;

sl=i;)e1seaif(HT[i].weight<HT[s2].weight&&HT[i].parent-O&&sl!=i)。s2=i;。}o})voidtrans1ation(IIuffmanTree11T,intnum)(charstr[20];ointi,t=num;叩rintf(〃请输入由0或1组成的编码：〃)；®cin>>str;o//t=HT；//t为树的指向各节点的指针ofor(i=0;i<(str1en(str))；i++)°{if(str[i]==，0')at=HTLt].Ichild；◎else®if(str[i]二二'1，)3t=IIT[t].rchild;。else2I000000printf（〃编码输入错误00printf（〃编码输入错误”）；(printf("%c〃，HT[t].data);gl=num;a})printf(〃\n〃)；}voidmain()(voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,chard口，intw口，intn);voidtranslation(HuffmanTreeHT,intnum);HuffmanTreeHT=NULL;HuffmanCodeHC=NULL;®chardata,n,*p,*d;int*w,wei,i,num；printf("pleaseintputcharacternumber：");oscanf("%d〃，&n);®d=(char*)ma1loc((n+l)*sizeof(char))；ow=(int*)ma1loc((n+1)*sizeof(int));printf(H请输入Huffman树中的字符：\n〃);for(i=1；iV=n；i++)。cin>>data;d[i]=data;}oprintf("请输入%d次位权\n:〃，n);for(i=1;i<=n;i++)。(”in>>wei;w[i]=wei;0)num=2*n—1;Huffm