数据结构课程设计哈夫曼编码实验.doc

成绩数据结构设计性实验Huffman编码与译码学 号姓 名班 级设计性实验Huffman编码与译码一实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman树的建立方法，Huffman编码的方法，进而设计出Huffman译码算法，并编程实现。二实验要求：在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。写出技术工作报告并附源程序。三实验内容及任务：1设字符集为26个英文字母，其出现频度如下表所示。51481156357203251频度zyxwvu t字符11611882380频度p21fq15gr47hsonmlkj字符5710332221364186频度iedcba空格字符2建Huffman树； 3利用所建Huffman树对任一字符串文件进行编码即设计一个Huffman编码器；4对任一字符串文件的编码进行译码即设计一个Huffman译码器。实现步骤：1 数据存储结构设计；2 操作模块设计；3 建树算法设计；4 编码器设计；5 译码器设计；四分析以及算法描述1.分析问题1) 首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。2) 认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法1 又给定的n个权值w1，w2，w3，wn构造根节点的二叉树，从而得到一个二叉树森林F=T1，T2，T3，Tn。2 在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。3 在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，将新的二叉树加入到二叉树森林F中。4 重复和，当二叉树森林F只剩下一棵二叉树时，这棵二叉树是所构造的霍夫曼树。3) 练习通过普通树来构造霍夫曼树。4) 根据以上分析过程设计相应的算法。5) 了解霍夫曼树与霍夫曼编码的关系，准备设计相应的算法。2.算法设计 （1） 数据结构 typedef struct int weight; int flag; int parent; int leftChild; int rightChild; HaffNode;typedef struct unsigned int bitMaxN;int start;int weight;Code;void Haffman(int weight,int n,HaffNode haffTree)int i,j,m1,m2,x1,x2;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.rightChild=-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;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.rightChild=x2;void HaffCode(HaffNode haffTree,int n,Code haffCode)Code *cd=(Code *)malloc(sizeof(Code);int i,j,child,parent;for(i=0;istart=n-1;cd-weight=haffTreei.weight;child=i;parent=haffTreechild.parent;while(parent!=-1)if(haffTreeparent.leftChild=child)cd-bitcd-start=0;else cd-bitcd-start=1;cd-start-;child=parent;parent=haffTreechild.parent;for(j=cd-start+1;jbitj;haffCodei.start=cd-start+1;haffCodei.weight=cd-weight;（2）主函数的设计#include #include #define MaxValue 10000#define MaxBit 10#define MaxN 100#include haffMan.hvoid main()int i,j,k,n=27;char s= a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z;int weight=186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1;HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n+1);Code *myHaffCode=(Code *)malloc(sizeof(Code)*n);if(nMaxN)printf(给出的n越界,修改MaxN);exit(0);Haffman(weight,n,myHaffTree);HaffCode(myHaffTree,n,myHaffCode);printf(n-0号空格，1-26号a-z-n);for(i=0;in;i+)for(j=myHaffCodei.start;jn;j+)printf(%-40s,myHaffCodei.bitj);pri