数据结构-实验四-Haffman编码.docx

数据结构实验报告实验四：Haffman编码姓 名： 周 成 学 号： 13083511 专 业： 软件工程 任 课 教 师： 马慧珠 2013年12 月12日1.实验名称：Haffman编码2.实验目的: 了解前缀编码的概念，理解数据压缩的基本方法；掌握Huffman编码的设计思想并能熟练应用。3.实验要求：对有字符集A，B，C，D，各字符在电文中出现的次数集为1,3,4,7；要求编程实现Huffman树的构造，并在此基础上编程实现Huffman编码。4.实验内容：学会haffman编码的思想。程序首先建立结构体，定义结构体成员，权值、双亲结点，左孩子结点右孩子结点等等。然后依据书上的哈夫曼编码实现：理论分析图： 5.实验程序代码及运行结果：Haffman.h头文件typedef structint weight; /权值int flag; /标记?int parent; /双?亲节点?下?标int leftChild; /左孩子下?标int ringhtChild; /右孩子下?标HaffNode; /哈t夫曼树的?结点?结构1typedef structint bitMaxN; /数y组int start; /编码?的?起e始?下?标int weight; /字?符?的?权值Code; /哈t夫曼编码?的?结构1void Haffman(int weight,int n,HaffNode haffTree)/建立叶?节点?个?数y为an权值数y组为aweight的?哈t夫曼树haffTreeint i,j,m1,m2,x1,x2;/哈t夫曼树haffTree初?始?化。n个?叶?节点?的?二t叉?树共2有D2n-1个?节点?for(i=0;i2*n-1;i+)if(in) haffTreei.weight=weighti;else haffTreei.weight=0;haffTreei.parent=-1;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.ringhtChild=-1;/构1造哈t夫曼树haffTree的?n-1个?非?叶?结点?for(i=0;in-1;i+)m1=m2=MaxValue;x1=x2=0;for(j=0;jn+i;j+)if(haffTreej.weightm1&haffTreej.flag=0)m2=m1;x2=x1;m1=haffTreej.weight;x1=j;else if(haffTreej.weightm2&haffTreej.flag=0)m2=haffTreej.weight;x2=j;/将?找出?的?两?棵?权值最?小?的?子树合?并为a一?棵?子树haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1;haffTreen+i.weight=haffTreex1.weight+haffTreex2.weight;haffTreen+i.leftChild=x1;haffTreen+i.ringhtChild=x2;void HaffmanCode(HaffNode haffTree,int n,Code haffCode)Code *cd=(Code *)malloc(sizeof(Code);int i,j,child,parent; /*求n个?叶?结点?的?哈t夫曼编码?*/for(i=0;istart=n-1; /*不?等长编码?的?最?后一?位?为an-1*/cd-weight=haffTreei.weight; /*取?得?编码?对?应|的?权值*/child=i;parent=haffTreechild.parent;/*由叶?结点?向上?直到?根结点?*/while(parent!=-1)if(haffTreeparent.leftChild=child)cd-bitcd-start=0; /*左孩子分?支编码?0*/elsecd-bitcd-start=1; /*右孩子分?支编码?1*/cd-start-;child=parent;parent=haffTreechild.parent;for(j=cd-start+1;jbitj; /*保存?每?个?叶?结点?的?编码?*/haffCodei.start=cd-start+1; /*保存?叶?结点?编码?的?起e始?位?*/haffCodei.weight=cd-weight; /*保存?对?应|的?权值*/主程序：#include stdafx.h#include#include#define MaxValue 10000 /*设定的?权值最?大值*/#define MaxBit 10 /*设定的?最?大编码?位?数y*/#define MaxN 100 /*设定的?最?大结点?个?数y*/#include Haffman.h /*包含?文?件tHaffman.h*/void main(void)int i,j,n=4;int weight=1,3,4,7;HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n+1);Code *myHaffCode=(Code *)malloc(sizeof(Code)*n);if(nMaxN)printf(给?出?的?n越?界?，?修T改?MaxN值！?n);exit(0);Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode); /*输?出?每?个?叶?结点?的?哈t夫曼编码?*/for(i=0;in;i+)printf(Weight=%d Code=,myHaffCodei.weight);for(j=myHaffCodei.start;jn;j+)printf(%d,myHaffCodei.bitj);printf(n);实验截图：6.实验总结Haffman编码的课程设计对我来说都是一个不小的提高，哲学上说：实践是检验真理正确性的唯一标准，尤其是学编程，自己不动手操作，只看书永远都编不出像Windows之类的东西，正如老师说的那样，课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更是编程技术的提升，当自己编的多了，就会开始摸索