还剩11页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
软件学院设计性实验报告专业网络工程年级/班级:2023—2023学年第一学期
一、实验目的理解哈夫曼树的特性及其应用在对哈夫曼树进行理解的基础上,构造哈夫曼树,并用构造的哈夫曼树进行编码和译码;通过该实验,使学生对数据结构的应用有更深层次的理解
二、实验仪器或设备学院提供公共机房,1台/学生微型计算机
三、总体设计(设计原理、设计方案及流程等).问题描述运用哈夫曼编码进行通信可以大大提高信道运用率,缩短信息传输时间,减少传输成本但是,这规定在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据进行译码(解码)对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统试为这样的信息收发站设计一个哈夫曼编/译码系统.一个完整的系统应具有以下功能)初始化(Initialzation)从数据文献DataFiledat中读入字符及每个字符的权值,建立哈夫曼树HuffTree;2)编码(EnCding)o用已建好的哈夫曼树,对文献ToBeTran.dat中的文本进行编码形成报文,将报文写在文献Code.ixl中;3)译码(Decoding)运用己建好的哈夫曼树对文献CdeFi1e.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语言程序inc1udcstring.hinc1udemaHoc.h#includestdio.hinc1udeiostream.hincludemath.hdefineTRUE1ttdefineOK1#defineERROR0typedefstructhardata;intweight;ointparent1childrchi1d;}HTNode*HuffmanTree;typedefchar^*HuffmanCode;voidHuffmanCodingHuffmanTreeHTHuffmanCodeHCchar*dint*wintn〃构造哈弗曼函数HT构造编码HCvoidselectHuffmanTreeHTintnintslints2;式ntmcfj;HuffmanTreep;intis1s2start;char*cd;m=2*n-l;//m为结点数,n为叶子数HT=HuffmanreemaHocm+l*sizeofHTNode;叩=盯;中++;fori=1;iV=n;i++p++//将叶子的值输入HT中p-data=d[i];//={*d*w000};p-weight=w[i];ap—parent=0;p-lchild=0;»p-rchild=0;}fori=n+l;i=m;i++p++//二{#0000op-data=;p—weight=0;p-parent=0;p-1child=0;M»p-rchild=O;}OS1=1;s2=2;fori=n+l;i=m;i++〃构建哈夫曼树se1ectHTi-1s1s2;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;eoHOHuffmanCodemallocn+1*sizeofHuffmanTree;//开辟空间,编码acd=char*mallocn*sizeofchar;cd[nT]=\0;fori=l;i=n;++i°»start=n-l;forc=if=HT[i].parent;f!=0;c=ff=HT[f].parent{lchild==c°cd[start]=O;elsecd[—start]=,1oHC[i]=char*mallocn-start*sizeofchar;strcpyHC[i]cd[start];printf〃%c的编码是,HT[i];putsHC[i];}freecd;}voidselectHuffmanTreeHTintnintslints2//求最小两数ointit;%1=1;os2=2;®whileHT[s1].parent!=0sl++;owhileHT[s2].parent!=0Isl==s28s2++;/*fori=l;i=n;i++°ifHT[si].weightHT[i].weightHT[i].parent==0s2!=i»sl=i;ifHT[s1].weightHT[s2].weightt=sl;sl=s2;s2=t;fori=l;i=n;i++ifsl!=ioo{ifHT[s2].weightHT[i].weightHT[i].parent==Os2=i;}*/fori=l;i=n;i++ifsl!=ii!=s2°{ifHT[i].weightHT[si].weightHT.parent-0i!=s2fHT[sl].weightHT[s2].weights2=s1;sl=i;e1seaifHT[i].weightHT[s2].weightHT[i].parent-Osl!=is2=i;}o}voidtrans1ationIIuffmanTree11Tintnumcharstr
[20];ointit=num;叩rintf〃请输入由0或1组成的编码〃;®cinstr;o//t=HT;//t为树的指向各节点的指针ofori=0;istr1enstr;i++°{ifstr[i]==,0at=HTLt].Ichild;◎else®ifstr[i]二二1,3t=IIT[t].rchild;else2Iif!HT[t].lchildHT[t].rchildprintf%c〃,HT[t].data;gl=num;a}printf〃\n〃;}voidmainvoidHuffmanCodingHuffmanTreeHTHuffmanCodeHCchard口,intw口,intn;voidtranslationHuffmanTreeHTintnum;HuffmanTreeHT=NULL;HuffmanCodeHC=NULL;®chardatan*p*d;int*wweiinum;printfpleaseintputcharacternumber;oscanf%d〃,n;®d=char*ma1locn+l*sizeofchar;ow=int*ma1locn+1*sizeofint;printfH请输入Huffman树中的字符\n〃;fori=1;iV=n;i++cindata;d[i]=data;}oprintf请输入%d次位权\n:〃,n;fori=1;i=n;i++”inwei;w[i]=wei;0num=2*n—1;HuffmanCodingHTHCdwn;translationHTnum;2程序分析此实验是构造哈夫曼树,求出哈夫曼编码然后输出构造哈夫曼树的算法操作时选出两棵根节点的权值最小的一颗树的左右子树,且置新树的根节点的权值为其左右子树上根节点的权值之和,根据哈夫曼树求出带权途径的算法操作是用递归调用的方法在此实验的操作过程中要注意构造哈夫曼树的方法,由于在此操作的过程中用的的指针变量特别多,容易混淆3运营结果举例课程名称数据结构指导教师本组成员学号姓名实验地点实验时间项目名称哈夫曼编/译码系统的设计与实现实验类型设计性。