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

作业二——霍夫曼编码-read作业二——霍夫曼编码输入:类似如下的数据文件://…..输出1:类似如下的编码表文件://字符码字A1110B110C10…..设计思路及程序实现设计思路:考虑到整个设计过程中最重要的一步:在一组数据中寻找最小值,为了使得速度加快,将采取堆的设计,具体实现见下面的陈述。1(数据结构(物理):霍夫曼树自然采用二叉树结构,而堆采用以树为元素的堆,下面是具体实现。structbintree//用二叉树来模拟霍夫曼编码的生成{bintree*left;//左子树bintree*right;//右子树doubleweight;//权重booltip;//标记是否为字符结点charchr;//如果是字符结点,保存该结点所代表的字符};constMaxmum=128;bintree*mass[Maxmum];//定义一个bintree最小堆2(输入:由于规定了输入格式,所以输入处理较死板。唯一值得注意的是由于要与堆相适应,直接将输入的元素附着于堆上。下面是输入的实现。voidinputtree(int&n)//输入字符频率{initmass();cout<<"请输入字符数:\n";cin>>n;cout<<"请依序输入这"<<n<<"个字符和频率。字符范围为'A'--'Z'.\n";chartempchr;doubletempweight;for(inti=1;i<=n;i++){cin>>tempchr>>tempweight;mass[i]=newbintree;mass[i]->weight=tempweight;mass[i]->chr=tempchr;mass[i]->left=NULL;mass[i]->right=NULL;mass[i]->tip=true;//标记为字符结点}}2(堆的使用:以堆所连树根的权为基准建立最小堆。具体实现如下:voidinitmass()//堆初始化{inti;for(i=0;i<Maxmum;i++)deletemass[i];}voidinsmass(intn)//在前n个元素成堆的情况下,将第n+1个元素入堆{intj=n+1;bintree*temp=mass[n+1];while(j>1&&mass[j/2]->weight>temp->weight){mass[j]=mass[j/2];j=j/2;}mass[j]=temp;}voiddelmass(intn)//在前n个元素成堆的情况下,将堆顶元素出堆,置于n位置{bintree*temp=mass[n];mass[n]=mass[1];intj=1;while((j*2<n&&mass[j*2]->weight<temp->weight)||(j*2+1<n&&mass[j*2+1]->weight<temp->weight))if(j*2+1<n&&mass[j*2+1]->weight<temp->weight&&mass[j*2]->weight>temp->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]为根。具体实现如下:voidcreatetree(intn)//根据输入生成霍夫曼二叉树,最终树根为mass[1]{inti;for(i=1;i<n;i++)insmass(i);bintree*templeft;bintree*tempright;bintree*temptree;i=n;while(i>1){delmass(i);templeft=mass[i];i--;delmass(i);tempright=mass[i];temptree=newbintree;temptree->left=templeft;temptree->right=tempright;temptree->tip=false;temptree->weight=templeft->weight+tempright->weight;mass[i]=temptree;insmass(i-1);}}:因为上面建立的霍夫曼树深度遍历所得序列不依字母序,而输出要按字母序输出,故先建立霍夫曼编码。为压缩存储,采用二进制向十进制的转化。具体实现如下:longcode[Maxmum];//存储对应字符的编码,用该数的二进制形式表示longdepth[Maxmum];//存储对应字符编码长度voiddeepsearch(bintree*root,longtempcode,longte