哈夫曼数据结构实验报告.doc

数学与计算机学院 哈夫曼 实验报告 年级 学号 姓名 成绩 专业 计算机 实验地点 指导教师 实验项目 哈夫曼编码 实验日期 12月1日 一、实验目的 学习并掌握树的有关操作，和哈夫曼算法程序，并理解哈夫曼编码和译码的有关算法。 二、实验问题描述 在数据通信中，利用哈夫曼编码进行通信可以大大提高通道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传送数据预先编码，在接收端将传来的电文进行译码和复原，从而得到信息。 三、实验步骤 1、实验问题分析 对于哈弗曼树的数据结构问题，哈夫曼涉及到用静态表存储哈弗曼树，将每个需要编码的字符放在一个静态链表里，方便读写。 对于哈夫曼编码效率问题，应使字符出现频率高的编码较短，即放在层次较低处，而频率低的放在层次较高的位置，提高编码效率。 2、功能（函数）设计 功能： 根据用户所输入的字符和权值生成哈夫曼树。 函数原型：haff hnode_creat(int n) 其返回值类型为一个结构体数组。 根据生成的哈夫曼树进行编码。 函数原型：void hnode_getCode(int n) 该函数调用生成树函数，再进行编码操作。 四、实验结果（程序）及分析 一.函数主程序： #include iostream #include string using namespace std; #define maxvalue 100 //定义最大权值 #define maxleaf 100 //定义最大叶子节点 #define maxnode 2*maxleaf-1 //定义最大节点 #define maxbit 50 //定义最大码长 typedef struct { char aim; int weight; int lchild; int rchild; int parent; }hnode,*haff; typedef struct { char aim_; int bit[maxbit]; int flg; }hcode; haff hnode_creat(int n) { hnode haf[maxnode]; for(int p=0;p2*n-1;p++) //初始化哈夫曼表 { haf[p].weight=0; haf[p].parent=-1; haf[p].lchild=-1; haf[p].rchild=-1; } cout请输入n个叶子结点的代表字符和权值...endlendl; for(int q=0;qn;q++) { cout请输入第q+1个叶子结点的代表字符：endl; cinhaf[q].aim; cout请输入haf[q].aim所代表的权值：endl; cinhaf[q].weight; } int m1,m2,x1,x2; //m1记录次小值，m2记录最小值,x1记录次小值序号，x2记录最小值序号 for(int j=0;jn-1;j++) //在原有节点中遍历 { m1=m2=maxvalue; x1=x2=0; for(int i=0;in+j;i++) //找出权值最小的两个节点 { if(haf[i].parent==-1) //确保所检验的非已合并的节点 { if(haf[i].weightm1) //规定权值小的放lchild,权值大的放rchild { m2=m1; x2=x1; m1=haf[i].weight; x1=i; } else if(haf[i].weightm2) { m2=haf[i].weight; x2=i; } } } //合并最小权值的两个节点 haf[x1].parent=n+j; haf[x2].parent=n+j; haf[n+j].weight=haf[x1].weight+haf[x2].weight; haf[n+j].lchild=x1; haf[n+j].rchild=x2; haf[n+j].parent=-1; //标记新生节点，置其双亲为-1 } return haf; } void hnode_getCode(i