哈夫曼树课程设计.doc

中南林业科技大学课程设计报告设计名称： 数据结构课程设计 姓 名： 王昆 学 号： 20094282 专业班级： 2009级软件工程 系 （院）： 计算机与信息工程学院 设计时间： 20102011学年第二学期 设计地点： 电子信息楼 机房 成绩：指导教师评语： 签名： 年 月 日15 数据结构课程设计报告 第 15 页，共 26页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务. 哈夫曼树应用功能： (1) 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；(2) 利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件Cod eFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。(3) 利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。分步实施：1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2） 完成最低要求：完成功能1；3） 进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核3课程设计说明书一 需求分析要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C+知识（本次我将使用C实现），以及丰富的程序调适经验。二 概要设计程序流程图 图 1三 详细设计1、哈夫曼树结点结构定义struct hfmnode char nValue;/节点值 int weight;/权值 int pnIndex;/父结点下标 int lchildIndex,rchildIndex;/左右孩子的结点下标;哈夫曼树类定义class huffmanTreepublic:void code(char nvalue,int w,int n); /对叶子结点编码void decode(char nvalue,char hfmcode,int n);/对叶子结点译码void Output(huffmanTree ht,int n);/输出哈夫曼树/private:hfmnode hfmNode2000;/用数组存储哈夫曼结点void creatHfmTree(char nvalue,int w,int n);/创建哈夫曼树void select(int pos,int &nodeOne,int &nodeTwo);/查询最小的两个结点;2、主要函数及相关功能 1 在数组hfmNode中从O开始到pos位置，查找哈夫曼树外的权值最小的两个结点的位置void huffmanTree:select(int pos,int &nodeOne,int &nodeTwo)2 创建哈夫曼树，nvalue是结点值，w是权值，n是叶子结点的个数void huffmanTree:creatHfmTree(char nvalue,int w,int n)3 求哈夫曼树的编码 nvalue是结点值数组，w是权值数组 n是叶子结点的个数void huffmanTree:code(char nvalue,int w,int n)4 哈夫曼译码 nvalue为结点值数组 hfmcode为哈夫曼编码，n个叶子结点void huffmanTree:decode(char nvalue,char hfmcode,int n)5 检查输入的字符值是否合法bool isChar(const string& str)6 输出哈夫曼树，字符，权值，以及它对应的编码void huffmanTree:Output(huffmanTree ht,int n)3、源程序#includeusing namespace std;struct hfmnode/哈夫曼树结点结构定义char nValue;/节点值int weight;/权值int pnIndex;/父结点下标int lchildIndex,rchildIndex;/左右孩子的结点下标;class huffmanTree/哈夫曼树类定义public:void code(char nvalue,int w,int n); /对叶子结点编码void decode(char nvalue,char hfmcode,int n);/对叶子结点译码void Output(huffmanTree ht,int n);/输出哈夫曼树/private:hfmnode hfmNode2000;/用数组存储哈夫曼结点void creatHfmTree(char nvalue,int w,int n);/创建哈夫曼树void select(int pos,int &nodeOne,int &nodeTwo);/查询最小的两个结点;/在数组hfmNode中从O开始到pos位置，查找哈夫曼树外的权值最小的两个结点的位置void huffmanTree:select(int pos,int &nodeOne,int &nodeTwo)long w1,w2;w1=w2=88888;for(int i=0;i=pos;i+)if(hfmNodei.pnIndex=0)if(hfmNodei.weightw1)w1=hfmNodei.weight;nodeOne=i;for(int j=0;j=pos;j+)if(hfmNodej.pnIndex=0)if(hfmNodej.weightw2&nodeOne!=j)w2=hfmNodej.weight;nodeTwo=j;/创建哈夫曼树，nvalue是结点值，w是权值，n是叶子结点的个数void huffmanTree:creatHfmTree(char nvalue,int w,int n)int pos;for(pos=1;pos=n;pos+)hfmNodepos.nValue=nvaluepos-1;/结点值hfmNodepos.weight=wpos-1;/权值hfmNodepos.pnIndex=hfmNodepos.lchildIndex=hfmNodepos.rchildIndex=0;/设置数组hfmNode中的其他结点for(pos=n+1;pos=2*n-1;pos+)int nodeOne,nodeTwo;select(pos-1,nodeOne,nodeTwo);hfmNodenodeOne.pnIndex=hfmNodenodeTwo.pnIndex=pos;/把hfmNodenodeOne和hfmNodenodeTwo两个结点加入哈夫曼树，设置他们的父结点位置为poshfmNodepos.lchildIndex=nodeOne;/设置pos结点的左孩子为nodeOnehfmNodepos.rchildIndex=nodeTwo;/设置pos结点的右孩子为nodeTwohfmNodepos.weight=hfmNodenodeOne.weight+hfmNodenodeTwo.weight;/设置pos结点的权值为左右孩子权值的和hfmNodepos.pnIndex=0; /pos父结点为0/求哈夫曼树的编码 nvalue是结点值数组，w是权值数组 n是叶子结点的个数void huffmanTree:code(char nvalue,int w,int n)creatHfmTree(nvalue,w,n);int i,j,c,f;int start;char *cd;cd=new charn;/用于存储哈夫曼编码的动态空间cdn-1=0;/编码结束符cout 结点值 编码endl;for(i=1;i=n;i+)/逐个字符求哈夫曼编码start=n-1; /编码结束符位置for(c=i,f=hfmNodei.pnIndex;f!=0;c=f,f=hfmNodef.pnIndex)/从叶子到根逆向求编码if(hfmNodef.lchildIndex=c)cd-start=0;elsecd-start=1;cout nvaluei-1 ;for(j=start;jn;j+)coutcdj;coutendl;delete cd;/释放空间/哈夫曼译码 nvalue为结点值数组 hfmcode为哈夫曼编码，n个叶子结点void huffmanTree:decode(char nvalue,char hfmcode,int n)int i,f;char c;for(i=0;istrlen(hfmcode);)/从根节点往下走的叶子结点/左0右1for(f=2*n-1;hfmNodef.lchildIndex!=0&hfmNodef.rchildIndex!=0;)c=hfmcodei;if(c=1)f=hfmNodef.rchildIndex;i+;elsef=hfmNodef.lchildIndex;i+;couthfmNodef.nValue;/输出找到的叶子结点coutendl;/换行/检查输入的字符值是否合法bool isChar(const string& str) int i ; for(i = 0; i != str.length(); i+) if(!isdigit(stri) continue; elsereturn false; return true;/OUTPUT *OUTPUT output*void huffmanTree:Output(huffmanTree ht,int n)/输出哈夫曼树，cout哈夫曼树储存结构模拟：endl;couthfmNode weight pnIndex lchildIndex rchildIndexendl; for(int i=1;i=2*n-1;i+)/couti hfmNodei.weight hfmNodei.pnIndex hfmNodei.lchildIndex hfmNodei.rchildIndexendl;printf(%4d%12d%10d%14d%16dn,i,hfmNodei.weight,hfmNodei.pnIndex,hfmNodei.lchildIndex,hfmNodei.rchildIndex);/*-Main-*/*-=*/void main() /int i=1;/while(i=1)cout endl;cout *-构造哈夫曼树-*endl;int n=5;/字符和权值个数cout请输入字符集大小n：n;char strn; /strn-1=0;char g;char str22000;/存储哈夫曼编码int w26;huffmanTree obj; cout请输入n个字符值：endlstr;/输入字符不合法while(isChar(str)=0|strlen(str)!=n)coutendl;cout输入错误，请重新输入str;/Output();/int n=strlen(str);coutendl;gocd:cout输入对应权值：endl;for(int i=0;iwi;coutendl;int m;while(1)cout请选择输入0或1：endl;cout*0、模拟输出哈夫曼树*endl;cout*1、进行编码*endl;cout*2、进行译码*m;switch(m)case 0:obj.creatHfmTree(str,w,n);obj.Output(obj,n);/OUTputcoutendl;break;case 1:cout各节点编码如下：endl;obj.code(str,w,n);coutendl;break;case 2: break;default:cout很抱歉，输入错误！请重新输入：endl;if(m=2)break; godc:coutend