华北科技学院计算机系综合性实验报告
《数据结构B》课程综合性实验报告
开课实验室： 基础三 2010 年 12 月 21 日 实验题目 一、实验目的 哈夫曼编码 1、掌握线性链表的插入、删除等算法。 2、掌握Huffman树的概念及构造方法。 3、掌握二叉树的存储结构及遍历算法。 二、设备与环境 微型计算机、Windows 系列操作系统 、Visual C++6.0软件。 三、实验内容 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树。 源代码： #include 华北科技学院计算机系综合性实验报告 ht0[i].data=' '; } printf(\"请输入报文（字母+标点+空格）,按#号结束\\n\\n\"); for(i=1;i<=N;i++) //利用for循环输入报文 { c=getchar(); if(c!='#') { ht[i].data=c; ht[i].weight=1; } else {c=getchar(); i--; break; } } COUNT=i; //记录报文总数 k=1; ht0[1]=ht[1]; for(i=2;i<=COUNT;i++) //统计每种字符的频度（出现次数），即权值 { for(j=1;j<=k;j++) if(ht[i].data==ht0[j].data) { ht0[j].weight++; break; } if(j>k) { k++; ht0[k]=ht[i]; } } COUNT0=k; //记录字符种类数 for(i=k+1;i<=2*k-1;i++) //找权值最小的2个结点开始建立huffman树 { min1=min2=32767; lnode=rnode=0; for(j=1;j 华北科技学院计算机系综合性实验报告 min2=ht0[j].weight; rnode=j; } ht0[lnode].plink=i; ht0[rnode].plink=i; ht0[i].weight=ht0[lnode].weight+ht0[rnode].weight; ht0[i].llink=lnode; ht0[i].rlink=rnode; } count=COUNT; for(i=1;i<=k;i++) //输出huffman树 { countw=ht0[i].weight; ht0[i].weight0=(float)(countw/count); } printf(\"\\n\\n-----------------------------------------------------------------\\n\\n\"); printf(\"\\n\\n 序号 结点值 权值(频度) 频度比例 双亲 左孩子 右孩子\\n\"); for(i=1;i<=2*k-1;i++) printf(\"%-7d%-8c%-7d%-12f%-6d%-7d%d\\n\ht0[i].weight,ht0[i].weight0,ht0[i].plink,ht0[i].llink,ht0[i].rlink); } void CreatCode() //建立huffman编码并输出，非报文 { int i,j,f,c; HCode hc; for(i=1;i<=COUNT0;i++) { hc.start=COUNT0; c=i; f=ht0[i].plink; while(f!=0) { if(ht0[f].llink==c) hc.cd[hc.start--]='0'; else hc.cd[hc.start--]='1'; c=f; f=ht0[f].plink; } hc.start++; hcd[i]=hc; } printf(\"\\n\\n\\n-----------------------------------------------------------------\\n\"); printf(\"\\n\\nhuffman编码为:\\n\"); for(i=1;i<=COUNT0;i++) { printf(\"%c:\ for(j=hcd[i].start;j<=COUNT0;j++) printf(\"%c\ 第 3 页 华北科技学院计算机系综合性实验报告 printf(\"\\n\"); } } void code() //建立报文的编码 { int i,j,k; printf(\"\\n\\n\\n-----------------------------------------------------------------\\n\"); printf(\"\\n\\n报文编码为:(报文总数为：%d)\\n\ for(i=1;i<=COUNT;i++) for(j=1;j<=COUNT0;j++) if(ht[i].data==ht0[j].data) { for(k=hcd[j].start;k<=COUNT0;k++) printf(\"%c\ printf(\" \"); } } void main() //主函数 { char k='y'; while(k=='y') //利用循环实现对多段报文的编码 { CreatHT(); CreatCode(); code(); printf(\"\\n\\n\\n\\n******************************************************************\\n\"); printf(\"\\n------------ 继续(y/n) ------------\\n\\n\"); scanf(\"%c\ getchar(); printf(\"\\n******************************************************************\\n\\n\\n\\n\"); } } 四、实验结果及分析 此哈夫曼编码是根据字符出现频率进行编码，使电文总长最短进行传递。 根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标为“0”，引向其右孩子的分支标为“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。 这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点二叉树形式，这种空间上的消耗带来了算法实现上的便捷。由于对于最后生成的Haffman树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为m个时，内部结点数为m-1，整个Haffman树的需要的结点数为2m-1。 第 4 页 华北科技学院计算机系综合性实验报告 第 5 页 华北科技学院计算机系综合性实验报告 哈夫曼编译exe文件运行图 五、收获和体会 1．首先要熟练掌握二叉树，然后在此基础上掌握理解huffman树和编码。 2．要熟知二叉树的性质，及huffman树没有度为1的结点。从而理解M为什么等于2*N-1。 3．多次体会到getchar();屏蔽回车等无用字符的好处。 4．使用外部变量的确很方便。 其实，程序真的就是理解。我想，对于自己编写的程序，每个设计者头脑中都似乎可以想象到计算机执行的每一步过程，至少，有一个很清晰的流程思路吧。这也是我有时比较喜欢汇编的原因。因为它能单步执行。当运行不正确时，我可以仔细查看哪一步不符合我的要求，从而进行修改。只是想强调的是，我一直很是赞同的话，程序就是理解，理解到每一个细节，甚至每一步。 评定项目 算法正确 程序结构合理 语法、语义正确 实验结果正确 报告规范 A B C D 评定项目 界面美观，布局合理 操作熟练 解析完整 文字流畅 题解正确 A B C D 教师评价其他： 评价教师签名： 年 月 日 第 6 页 华北科技学院计算机系综合性实验报告 第 7 页 因篇幅问题不能全部显示，请点此查看更多更全内容