数据结构实验报告-哈夫曼树

昆明理工大学信息工程与自动化学院学生实验报告〔2011—2012学年第1学期〕课程名称：数据结构-用C语言描述开课实验室：计算中心室2011年月日年级、专业、班学号姓名成绩实验工程名称哈夫曼树指导教师冯松教师评语教师签名：年月日实验内容和目的目的：掌握哈弗曼树的定义和和它生成最优二叉树的性质。内容：1、创立哈弗曼树；2、生成最优二叉树；3、计算权值。二、设计思路〔程序设计框图〕：哈夫曼构造法：根据给定的n个权值w1，w2，w3,......，Wn构成n棵二叉树的森林f={T1，T2，……,Tn}，其中每棵二叉树Ti中都只有一个权值为Wi的根结点。其左右子树均空。在森林F中选择出两棵根结点的权值最小的树，将这两棵树合并成一棵新树，为了保证新树仍然是二叉树，更需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新树的左右孩子，将左右孩子的权值之和作为新树根的权值。对新树的森林F重复2，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。三、所用仪器、材料〔设备名称、型号、规格等〕所用仪器：计算中心310-？；操作系统：WindowsXP；软件平台：Macromedia四、上机操作方法、步骤：翻开计算机：开始菜单 程序MicrosoftVisualC++6.0哈夫曼树构造流程图开始开始输入iI=0,i<2*n-1,i++Huf[i].w=0w.p=-1Huf.lchild=-1Huf.rchild=-1输入huffnode.wI=0,I<n,i++M1=m2=MAX,x1=x2=0M1=m2=huf[i].w.p结束五、源程序与运行结果：源程序：voidhuffmantree(Hnodetypehuffnode[MAXNODE],intn)/*构造哈夫曼树的函数*/{inti,j,m1,m2,x1,x2;for(i=0;i<2*n-1;i++)/*存放哈夫曼树结点的数组huffnode[]初始化*/{huffnode[i].w=0;huffnode[i].p=-1;huffnode[i].lchild=-1;huffnode[i].rchild=-1;}for(i=0;i<n;i++)/*输入入N个叶子节点的权值*/{printf("pleaseinput%dcharacter'sw\n",i);scanf("%d",&huffnode[i].w);}for(i=0;i<n-1;i++)/*开始循环构造哈夫曼树*/{m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j++){if(huffnode[j].w<m1&&huffnode[j].p==-1){m2=m1;x2=x1;m1=huffnode[j].w;x1=j;}elseif(huffnode[j].w<m2&&huffnode[j].p==-1){m2=huffnode[j].w;x2=j;}}huffnode[x1].p=n+i;huffnode[x2].p=n+i;huffnode[n+i].w=huffnode[x1].w+huffnode[x2].w;huffnode[n+i].lchild=x1;huffnode[n+i].rchild=x2;}}运行结果：六、上机实践收获和体会:通过上机对数据结构有了初步的了解和认识，熟悉和初步掌握了哈弗曼树的创立和定义，哈夫曼树的构造方法。了解了树和二叉树是一类具有层次或嵌套关系的非线性结构，被广泛地运用到计算机领域，尤其是二叉树最重要、最常用。以及二叉树的概念