作业二——霍夫曼编码-read.docVIP

作业二——霍夫曼编码 输入： 类似如下的数据文件： // 字符 频率 A 0.05 B 0.03 C 0.29 ….. 输出1： 类似如下的编码表文件： //字符 码字 A 1110 B 110 C 10 ….. 设计思路及程序实现 设计思路： 考虑到整个设计过程中最重要的一步：在一组数据中寻找最小值，为了使得速度加快，将采取堆的设计，具体实现见下面的陈述。 1．数据结构（物理）： 霍夫曼树自然采用二叉树结构，而堆采用以树为元素的堆，下面是具体实现。 struct bintree//用二叉树来模拟霍夫曼编码的生成 { bintree* left;//左子树 bintree* right;//右子树 double weight;//权重 bool tip;//标记是否为字符结点 char chr;//如果是字符结点，保存该结点所代表的字符 }; const Maxmum=128; bintree *mass[Maxmum];//定义一个bintree最小堆 2．输入： 由于规定了输入格式，所以输入处理较死板。唯一值得注意的是由于要与堆相适应，直接将输入的元素附着于堆上。下面是输入的实现。 void inputtree(int n)//输入字符频率 { initmass(); cout请输入字符数：\n; cinn; cout请依序输入这n个字符和频率。字符范围为A--Z.\n; char tempchr; double tempweight; for (int i=1;i=n;i++) { cintempchrtempweight; mass[i]=new bintree; mass[i]-weight=tempweight; mass[i]-chr=tempchr; mass[i]-left=NULL; mass[i]-right=NULL; mass[i]-tip=true;//标记为字符结点 } } 2．堆的使用： 以堆所连树根的权为基准建立最小堆。具体实现如下： void initmass()//堆初始化 { int i; for (i=0;iMaxmum;i++) delete mass[i]; } void insmass(int n)//在前n个元素成堆的情况下，将第n+1个元素入堆 { int j=n+1; bintree* temp=mass[n+1]; while (j1mass[j/2]-weighttemp-weight) { mass[j]=mass[j/2]; j=j/2; } mass[j]=temp; } void delmass(int n)//在前n个元素成堆的情况下，将堆顶元素出堆，置于n位置 { bintree* temp=mass[n]; mass[n]=mass[1]; int j=1; while((j*2nmass[j*2]-weighttemp-weight)||(j*2+1nmass[j*2+1]-weighttemp-weight)) if(j*2+1nmass[j*2+1]-weighttemp-weightmass[j*2]-weighttemp-weight) { mass[j]=mass[j*2+1]; j=j*2+1; } else { mass[j]=mass[j*2]; j=j*2; } mass[j]=temp; } 3．霍夫曼树的建立 采用入堆两个，出堆一个的方法。结束时使mass[1]为根。具体实现如下： void createtree(int n)//根据输入生成霍夫曼二叉树，最终树根为mass[1] { int i; for (i=1;in;i++) insmass(i); bintree* templeft; bintree* tempright; bintree* temptree; i=n; while (i1) { delmass(i); templeft=mass[i]; i--; delmass(i); tempright=mass[i]; temptree=new bintree; temptree-left=templeft; temptree-right=tempright; temptree-tip=false; temptree-weight=templeft-weight+tempright-weight; mass[i]=temptree