哈夫曼编译码---数据结构C语言版课程设计

1《数据结构》课程设计报告设计题目哈夫曼(Huffman)编/译码器学院名称信息工程学院专业班级12计本2姓名张翠翠学号1212210217______2题目：哈夫曼(Huffman)编/译码器一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。二、设计目标帮助学生熟练掌握树的应用和基本操作，重点掌握二叉树的存储，这里以哈夫曼树为设计目标进一步提高学生的设计能力及对树的理解。三、任务要求一个完整的系统应具有以下功能：1)I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。2)E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。3)D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。4)P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。5)T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。四、需求分析利用哈夫曼树(Huffman)编/译码3（一）、初始化哈夫曼树（二）、建立哈夫曼树（三）、对哈夫曼树进行编码（四）、输出对应字符的编码（五）、译码过程五、概要设计哈夫曼树的存储结构描述typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;哈弗曼树的算法voidCreateHT(HTNodeht[],intn)//调用输入的数组ht[],和节点数n{inti,k,lnode,rnode;intmin1,min2;for(i=0;i2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//所有结点的相关域置初值-1for(i=n;i2*n-1;i++)//构造哈夫曼树{min1=min2=32767;//int的范围是-32768—32767lnode=rnode=-1;//lnode和rnode记录最小权值的两个结点位置for(k=0;k=i-1;k++)4{if(ht[k].parent==-1)//只在尚未构造二叉树的结点中查找{if(ht[k].weightmin1)//若权值小于最小的左节点的权值{min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weightmin2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i;//两个最小节点的父节点是iht[i].weight=ht[lnode].weight+ht[rnode].weight;//两个最小节点的父节点权值为两个最小节点权值之和ht[i].lchild=lnode;ht[i].rchild=rnode;//父节点的左节点和右节点}}哈弗曼编码voidCreateHCode(HTNodeht[],HCodehcd[],intn){inti,f,c;5HCodehc;for(i=0;in;i++)//根据哈夫曼树求哈夫曼编码{hc.start=n;c=i;f=ht[i].parent;while(f!=-1)//循序直到树根结点结束循环{if(ht[f].lchild==c)//处理左孩子结点hc.cd[hc.start--]='0';else//处理右孩子结点hc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;//start指向哈夫曼编码hc.cd[]中最开始字符hcd[i]=hc;}}voidDispHCode(HTNodeht[],HCodehcd[],intn)//输出哈夫曼编码的列表{inti,k;printf(输出哈夫曼编码:\n);for(i=0;in;i++)//输出data中的所有数据，即A-Z{printf(%c:\t,ht[i].data);6for(k=hcd[i].start;k=n;k++)//输出所有data中数据的编码{printf(%c,hcd[i].cd[k]);}printf(\n);}}voideditHCode(HTNodeht[],HCodehcd[],intn)//编码函数{charstring[MAXSIZE];inti,j,k;scanf(%s,string);//把要进行编码的字符串存入string数组中printf(\n输出编码结果:\n);for(i=0;string[i]!='#';i++)//#为终止标志{for(j=0;jn;j++){if(string[i]==ht[j].data)//循环查找与输入字符相同的编号，相同的就输出这个字符的编码{for(k=hcd[j].start;k=n;k++){printf(%c,hcd[j].cd[k]);}7break;//输出完成后跳出当前for循环}}}}哈弗曼译码voiddeHCode(HTNodeht[],HCodehcd[],intn)//译码函数{charcode[MAXSIZE];inti,j,l,k,m,x;scanf(%s,code);//把要进行译码的字符串存入code数组中while(code[0]!='#')for(i=0;in;i++){m=0;//m为想同编码个数的计数器for(k=hcd[i].start,j=0;k=n;k++,j++)//j为记录所存储这个字符的编码个数{if(code[j]==hcd[i].cd[k])//当有相同编码时m值加1m++;}if(m==j)//当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据{printf(%c,ht[i].data);8for(x=0;code[x-1]!='#';x++)//把已经使用过的code数组里的字符串删除{code[x]=code[x+j];}}}}主函数voidmain(){intn=26,i;charorz,back,flag=1;charstr[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};//初始化intfnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16};//初始化HTNodeht[M];//建立结构体HCodehcd[N];//建立结构体for(i=0;in;i++)//把初始化的数据存入ht结构体中{ht[i].data=str[i];ht[i].weight=fnum[i];}while(flag)//菜单函数，当flag为0时跳出循环显示部分源程序：9{printf(\n);printf(********************************);printf(\n**1---------------显示编码**);printf(\n**2---------------进行编码**);printf(\n**3---------------进行译码**);printf(\n**4---------------退出**\n);printf(***********************************);printf(\n);printf(请输入选择的编号:);scanf(%c,&orz);switch(orz){case'a':case'A':system(cls);//清屏函数CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf(\n按任意键返回...);getch();system(cls);break;case'b':case'B':system(cls);10printf(请输入要进行编码的字符串(以#结束):\n);editHCode(ht,hcd,n);printf(\n按任意键返回...);getch();system(cls);break;case'c':case'C':system(cls);DispHCode(ht,hcd,n);printf(请输入编码(以#结束):\n);deHCode(ht,hcd,n);printf(\n按任意键返回...);getch();system(cls);break;case'd':case'D':flag=0;break;default:system(cls);}}}六、详细设计字符空格ABCDEFGHIJKLM频186132232102115475715322011度643由上表画出哈夫曼树：由哈夫曼树得出各字符的编码：字符编码字符编码空格10D0001A010E1111B011111F11001C0000G01110关系调用：12该程序的流程图：13开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用selectmin函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点点是否为根结点？左子是否为空？此时编码为0i=2*ni++编码为1结束否否否右子是否为空是是否否是是是14七、测试分析白盒：查看代码完整性白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作。这一方法是把测试对象看作一个打开的盒子，测试人员依据程序内部逻辑结构相关信息，设计或选择测试用例，对程序所有逻辑路径进行测试，通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。黑盒：测试是否可以正确的创建，删除，插入，打印，查找等操作黑盒测试也称功能测试，它是通过测试来检测每个功能是否都能正常使用。在测试中，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和软件功能进行测试。八、使用说明1)输入n个字符的权值2)输入对应的字符3)得出各字符的编码15九、测试数据用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161注：学生在测试数据时，需要写出测试用例和截图十、该程序的源代码#includestdio.h#includestdlib.h//要用system函数要调用的头文件#includeconio.h//用getch()要调用的头文件#includestring.h#def