哈夫曼编译码器数据结构课程设计

课程设计(论文)题目名称哈夫曼编/译码器课程名称数据结构课程设计学生姓名学号系专业指导教师2012年12摘要随着计算机的普遍应用与日益开展,其应用早已不局限于简单的数值运算,而涉及到问题的分析,数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作.算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论,方法和技术根底.算法与数据结构旨在分析研究计算机加工的数据对象的特性,以便选择适当的数据结构和存储结构,从而使建立在其上的解决问题的算法到达最优.数据结构是在整个计算机科学与技术领域上广泛被使用的术语.它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构.数据结构有逻辑上的数据结构和物理上的数据结构之分.逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排.数据结构是数据存在的形式.《数据结构》主要介绍一些最常用的数据结构,说明各种数据结构内在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率进行简单的分析和讨论.数据结构是介于数学,计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计,数据库,操作系统,编译原理及人工智能等的重要根底,广泛的应用于信息学,系统工程等各种领域.学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理.通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。目录TOC\o"1-2"\h\z\u1问题描述12需求分析13概要设计23．1抽象数据类型定义23．2模块划分34详细设计44．1数据类型的定义44．2主要模块的算法描述55测试分析66课程设计总结9参考文献9附录〔源程序清单〕101问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码〔复原〕。对于双工信道〔即可以双向传输信息的信道〕，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。2需求分析一个完整的系统应具有以下功能：〔1〕I：初始化〔Initialization〕。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。〔2〕E：编码〔Encoding〕。利用已建好的哈夫曼树〔如不在内存，那么从文件htmTree中读入〕，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。〔3〕D：译码〔Decoding〕。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。〔4〕P：印代码文件〔Print〕。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。〔5〕T：印哈夫曼树〔TreePrinting〕。将已在内存中的哈夫曼树以直观的方式〔树或凹入表形式〕显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。[测试数据]〔1〕数据一：某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。〔2〕用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE〞。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811613概要设计3．1抽象数据类型定义ADTStack数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：假设D为空集，那么称为空树。假设D仅为一个数据元素，那么R为空集，否那么R={H}，H是如下的二元关系：〔1〕再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。〔2〕假设D-{root}<>空集，那么存在一个划分D1，D2，···，Dm〔m>0〕。〔3〕对应于D-{root}的划分，H-{<root，X1}，···，<root，Xm>}有唯一的一个划分H1，H2，···，Hm〔m>0〕。根本操作：InitTree(&T)操作结果：构造空树T。DestroyTree(&T)初始条件：树T已存在。操作结果：树T被销毁。ClearTree(&T)初始条件：树T已存在。操作结果：将树T清为空栈。TreeEmpty(T)初始条件：树T已存在。操作结果：假设树T为空，那么返回TRUE，否那么FALSE。TreeDepth(T)初始条件:树T已存在。操作结果：返回T的深度。Root〔T〕初始条件：树T已存在。操作结果：返回树T的根。3．2模块划分本程序包括三个模块：〔1〕主程序模块voidmain(){初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；}〔2〕哈夫曼模块——实现哈夫曼树的抽象数据类型〔3〕求哈夫曼编码模块——实现求哈夫曼编码算法的数据类型4详细设计4．1数据类型的定义〔1〕哈夫曼树类型typedefstruct{//构造树chardata;//结点权值intweight;//权重intparent;//双亲结点intlchild;//左孩子intrchild;//右孩子}HTNode;HTNodeht[30];〔2〕求哈夫曼编码类型typedefstruct{charcd[30];//存放当前结点的哈弗曼编码intstart;//cd[start]~cd[n]存放哈弗曼码}HCode;HCodehcd[30];4．2主要模块的算法描述IIntI,f,c;i++Hc.start++;multiplexi=0hc.start=n;c=i;i<nf!=-1图4.3-2哈夫曼编码算法流程图Inti;scanf(“%d〞,&ht[t].we…i++i<n结束开始图4.3-1主函数流程图5测试分析}6课程设计总结通过这次课程设计使我充分的理解了用哈夫曼树再编码问题中根本原理的应用，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编码问题的程序。虽然此次的程序不是很完备，但是总体还是一个比拟能表达数据结构知识点能力的程序，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到很茫然，无从下手。但是困难是可以解决的，只要通过努力，向老师虚心学习请教，再难的题目也可以自己动手完成。通过这次的数据结构课程设计，我也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。同时也认识到自己的缺乏和缺点，做什么事都需要细心和耐心，并坚持下去，这样才还有一个比拟满意的成果。在此我非常要感谢的是我的指导老师黄同成教授，感谢老师的细心认真的辅导，让我对数据结构这门课程有了跟深刻的认识，同时我还要感谢帮助过我的同学，没有他们的帮助我不肯能完成这样顺利，谢谢！参考文献[1]黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，2023[2]董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：中国电力出版社，2023附录〔源程序清单〕#include<stdio.h>#definen27//叶子数目#definem(2*n-1)//结点总数#definemaxval10000.0#definemaxsize100//哈夫曼编码的最大位数typedefstruct{charch;floatweight;intlchild,rchild,parent;}hufmtree;typedefstruct{charbits[n];//位串intstart;//编码在位串中的起始位置charch;//字符}codetype;voidhuffman(hufmtreetree[]);//建立哈夫曼树voidhuffmancode(codetypecode[],hufmtreetree[]);//根据哈夫曼树求出哈夫曼编码voiddecode(hufmtreetree[]);//依次读入字符，根据哈夫曼树译码voidmain(){printf("——哈夫曼编码——\n");printf("总共有%d个字符\n",n);hufmtreetree[m];codetypecode[n];inti,j;//循环变量huffman(tree);//建立哈夫曼树huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码printf("【输出每个字符的哈夫曼编码】\n");for(i=0;i<n;i++){printf("%c:",code[i].ch);for(j=code[i].start;j<n;j++)printf("%c",code[i].bits[j]);printf("\n");}printf("【读入字符，并进行译码】\n");decode(tree);//依次读入电文，根据哈夫曼树译码}voidhuffman(hufmtreetree[])//建立哈夫曼树{inti,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标floatsmall1,small2,f;charc;for(i=0;i<m;i++)//初始化{tree[i].parent=0;tree[i].lchild=-1;tree[i].rchild=-1;tree[i].weight=0.0;}printf("【依次读入前%d个结点的字符及权值(中间用空格隔开)】\n",n);for(i=0;i<n;i++)//读入前n个结点的字符及权值{printf("输入第%d个字符为和权值",i+1);scanf("%c%f",&c,&f);getchar();tree[i].ch=c;tree[i].weight=f;}for(i=n;i<m;i++)//进行n-1次合并，产生n-1个新结点{p1=0;p2=0;small1=maxval;small2=maxval;//maxval是float类型的最大值for(j=0;j<i;j++)//选出两个权值最小的根结点if(tree[j].parent==0)if(tree[j].weight<small1){small2=small1;//改变最小权、次小权及对应的位置small1=tree[j].weight;p2=p1;p1=j;}elseif(tree[j].weight<small2){small2=tree[j].weight;//改变次小权及位置p2=j;}tree[p1].parent=i;tree[p2].parent=i;tree[i].lchild=p1;//最小权根结点是新结点的左孩子tree[i].rchild=p2;//次小权根结点是新结点的右孩子tree[i].weight=tree[p1].weight+tree[p2].weight;}}//huffmanvoidhuffmancode(codetypecode[],hufmtreetree[])//根据哈夫曼树求出哈夫曼编码//codetypecode[]为求出的哈夫曼编码//hufmtreetree[]为的哈夫曼树{inti,c,p;codetypecd;//缓冲变量for(i=0;i<n;i++){cd.start=n;cd.ch=tree[i].ch;c=i;//从叶结点出发向上回溯p=tree[i].parent;//tree[p]是tree[i]的双亲while(p!=0){cd.start--;if(tree[p].lchild==c)cd.bits[cd.start]='0';//tree[i]是左子树，生成代码'0'elsecd.bits[cd.start]='1';//tree[i]是右子树，生成代码'1'c=p;p=tree[p].parent;}code[i]=cd;//第i+1个字符的编码存入code[i]}}//huffmancodevoiddecode(hufmtreetree[])//依次读入字符，根据哈夫曼树译码{inti,j=0;charb[maxsize];charendflag='2';//电文结束标志取2i=m-1;//从根结点开始往下搜索printf("输入发送的编码(以'2'为结束标志)：");gets(b);printf("译码后的字符为");while(b[j]!='2'){if(b[j]=='0')i=tree[i].lchild;//走向左孩子elsei=tree[i].rchild;//走向右孩子if(tree[i].lchild==-1)//tree[i]是叶结点{printf("%c",tree[i].ch);i=m-1;//回到根结点}j++;}printf