完整数据结构课程设计-电文编码译码哈夫曼编码

福建农林大学计算机与信息学院数据结构课程设计设计哈夫曼编译码器姓名韦邦权专业级计算机科学与技术2013学号13224624班级13052316完成日期

⑤主函数void mainQcharst[MAX]sst[MAX];zint cn

[257];int nJ;printf请输入字符串任意字符:\ngetsst;n=jsqst cn sst;//〃〃〃〃〃〃〃〃〃〃〃〃〃/99fori=0;i99;i++sst[i]=st[i];llllllllllllllllllllllllllllllllllHTNode ht[M];HCode hcd[N];CreateHTht n st cn;///CreateHCodeht hcd n;z foutputHCodehthcd n;z zeditHCodeht hcd n sst;z z zdeHCodeht hcdn sst;/z/

五、调试输出哈夫曼编码请输入字符串《任意字符”Nothing isimpossible输出哈夫曼编码:01111100N11101b11110e111110000h0001110i001010011m010010110101100n;1018oP输出编码结果=s清输入字符串《任意字符兀tLet itbe*输出哈夫曼编码:110•010L011b100e111i101t00输出编码结果:输出译码结果n.情输入字符串（任意字符）THIS PROGRAMIS MVFRAUORITE输出编码结果为输出编译结果为:THIS PROGRAMIS MYFRAUORITEPress anykey tocontinue.附录源程序#include stdio.h#include string.h#define N256#define M2*N-1#define MAX32767typedef struct（char data;int weight;int parent;int Ichild;〃左孩子结点int rchild;〃右孩子结点}HTNode;llllllllllllllllllllllllllltypedef structcharcd[N];〃存放哈夫曼码int start;〃从start开始读cd中的哈夫曼码}HCode;lllllllllllllllllllllllllllllllllllint jsqchar*s,int cnt[],char str[]{char*p;〃gets函数需要int i,j,k;〃义用N表示50叶节点数〃用M表示节点总数当叶节点数位n时总节点数为2n-lfori=l;i=256;i++cnt[i]=O;forp=s;*p!=\0,;p++k=*p;〃结点字符cnt[k]++;〃权值〃双亲结点；j=ofori=lj=0;i=256;i++j++;return j;lllllllllllllllllllllllllllllllllllllllllllllllllll void CreateHTHTNode ht[],int ncharzstr[]Jnt cn[]{forint input=l;input=256;input++〃创建哈夫曼树函数str[input]=input;}int1=0;forint output=l;output=256;output++ifcn[output]!=0{ht[l].data=str[output];〃按字母顺序将出现的字母依次存入数组ht[]ht[l].weight=cn[output];I++;}int i,k,Inode,mode;int minlmin2;zfor i=0;i2*n-l;i++ht[i].parent=ht[i].lchild=ht[i].rchild=O;〃所有结点的相关域置初值0for i=n;i2*n-l;i++〃构造哈夫曼树//int的范围是-32768-32767minl=min2=MAX;//Inode和mode记录最小权值的两个结点位置lnode=rnode=0;for k=0;k=i-l;k++〃选出每次外层循环最小权值的两个结点〃只在尚未构造二叉树的结点中查找if ht[k].parent==O〃比mini小时if ht[k].weightminlmin2=minl;rnode=Inode;minl=ht[k].weight;lnode=k;else if ht[k].weightmin2〃比mini大，比min2小min2=ht[k].weight;rnode=k;ht[lnode].parent=i;ht[rnode].parent=i;〃两个最小节点的父节点是i〃两个最小节点的父节点权值为两个ht[i].weight=ht[lnode].weight+ht[rnode].weight;最小节点权值之和ht[i].lchild=lnode;ht[i].rchild=rnode;〃父节点的左节点和右节点〃〃〃/〃〃〃/〃〃/〃〃〃〃〃〃〃〃〃〃〃〃〃〃/〃〃〃void CreateHCodeHTNodeht[],HCode hcd[],int nint i,p,c;HCode he;for i=0;in;i++〃根据哈夫曼树求哈夫曼编码hc.start=n;〃初始位置c=i;〃从叶子结点ht[i]开始上溯p=ht[i].parent;while p!=0〃循序直到树根结点结束循环hc.cd[hc.start-]=ht[p].lchild==c,O,:,l,;〃左孩子记为0,右孩子记为1；c=pp=ht[p].parent;〃与上句c=i;p=ht[i].parent同义，促进循环//start指向哈夫曼编码hc.cd口中最开始字符；hc.start++hcd[i]=hc;〃〃〃///〃〃/〃〃/〃〃〃〃〃〃〃〃〃〃〃〃〃〃//void outputHCodeHTNodeht[],HCode hcd[]Jnt n〃输出哈夫曼编码的列表int i,k;printfC1输出哈夫曼编码:\n“）;for i=0;in;i++〃输出data中的所有数据,for k=hcd[i].start;k=n;k++〃输出所有data中数据的编码printfn％printf”c”,hcd[i].cd[k];〃从初最开始的字符起输出IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII voideditHCodeHTNode ht[]HCode hcd[],int n,char str[]〃编码函数z{int ij,k;printf（\n输出编码结果:\n“）;for i=0;iMAX;i++for j=O;jn;j++ifstr[i]==ht[j].data〃循环查找与输入字符相同的编号，相同的就输出这个字符的编码for k=hcd[j].start;k=n;k++printf%c”,hcd[j].cd[l|;break;〃输出完成后跳出当前for循环lllllllllllllllllllllllllllllllllllllllllllllvoid deHCodeHTNodeht[],HCode hcd[]int nchar str[]〃译码函数z zprints输出译码结果为:\nchar code[MAX];for i=0;iMAX;i++for j=O;jn;j++ifstr[i]==ht[j].data〃循环查找与输入字符相同的编号相同的就输出这个字符的编码for k=hcd[j].start;k=n;k++m++;break;〃输出完成后跳出当前for循环code[m]=#;〃把要进行译码的字符串存入code数组中whilecode

[0]!=#for i=0;in;i++m=0;//m为想同编码个数的计数器for k=hcd[i].startj=O;k=n;k++j++//j为记录所存储这个字符的编码个数〃当有相同编码时m值加1ifcode[j]==hcd[i].cd[k]m++;〃当输入的字符串与所存储的编码字符串个数相等时ifm==j则输出这个的data数据printfH%c,,ht[i].data;/〃把已经使用过的code数组里的字符串删除forx=0;code[x-j]!=#,;x++code[x]=code[x+j];〃删除j个数，往前移动j位哈夫曼编译码器一.需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术哈夫曼编码是一种编码方式，以哈夫曼树一即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的X哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码树中从根到每个叶子都有一条路径，对路径上的各分支约定〃指向左子树的分支表示码，指向右子树的分支表示“1码,取每条路径上的或的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码哈夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串

二、设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串通常我们把数据压缩的过程称为编码，解压缩的过程称为解码电报通信是传递文字的二进制码形式的字符串但在信息传递时，总希望总长度能尽可能短，即采用最短码假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符，则电文编码总长度为\WiLi若将此对应到二叉树上,Wi为叶结点的权，Li为根结点到叶结点的路径长度那么，\WiLi恰好为二叉树上带权路径长度因此，设计电文总长最短的二进制前缀编码，就是以n种字符printf\n;llllllllllllllllllllllllllllllllllllllllvoid maincharst[MAX]sst[MAX];zint cn

[257];int nJ;p rintf请输入字符串任意字符:\n;getsst;n=jsqst cn,sst;z〃〃〃〃〃〃〃〃〃〃〃/////99fori=0;i99;i++sst[i]=st[i];llllllllllllllllllllllllllllllllllHTNode ht[M];HCode hcd[N];CreateHTht,nstcn;//CreateHCodeht hcdn;z zoutputHCodeht,hcdn;/editHCodehthcdnsst;//zdeHCodeht hcdnsst;///｝欢迎您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！你的意见是我进步的动力，希望您提出您宝贵的意见！让我们共同学习共同进步！学无止境.更上一层楼出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码设计实现的功能）；（）；（）Q哈夫曼树的建立2哈夫曼编码的生成3编码文件的译码

三、概要设计哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码在数据通信中，经常需要将传送的文字转换成由二进制字符

0、1组成的二进制串，称之为编码构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0,右分支代表I,则从根节点到每个叶子节点所经过的路径分支组成的0和I的序列便为该节点对应字符的编码，称之为哈夫曼编码最简单的二进制编码方式是等长编码若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度哈夫曼树课用于构造使电文的编码总长最短的编码方案设计包含的几个方面

①哈夫曼树的建立赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树算法的第二步是将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点显然要进行n-1次合并，所以共产生n-1个新结点，它们都是具有两个孩子的分支结点由此可知，最终求得的哈夫曼树中一共有2n-1个结点，其中n个结点是初始森林的n个孤立结点并且哈夫曼树中没有度数为1的分支结点我们可以利用一个大小为2n-l的一维数组来存储赫夫曼树中的结点定义的结构体类型如下:typedef structchardata;〃结点字符int weight;〃权值int parent;〃双亲结点int Ichild;〃左孩子结点int rchild;〃右孩子结点}HTNode;

②哈夫曼编码要求电文的哈夫曼编码，必须先定义哈夫曼编码类型，根据设计要求和实际需要定义的类型如下typedet struct{char cd[N];//存放编码的数组int start;〃从start开始读cd中的哈夫曼编码}Hcode;//编码结构体类型

③代码文件的译码译码的基本思想是读文件中编码，并与原先生成的哈夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中,详细设计

①字符统计int jsqchar*sjnt cnt[],char str[]{char*p;int ij,k;fori=l;i=256;i++cnt[i]=O;forp=s;*p!=\0,;p++k=*p;cnt[k]++;；j=ofori=lj=0;i=256;i++ifcnt[i]!=Oj++;return j;

②哈夫曼树的算法voidCreateHTHTNodeht[]Jnt n^har str[]Jnt cn[]〃创建哈夫曼树函数{forint input=l;input=256;input++str[input]=input;}int1=0;forint output=l;output=256;output++ifcn[output]!=0{ht[l].data=str[output];〃按字母顺序将出现的字母依次存入数组ht[]ht[l].weight=cn[output];I++;}inti,k,lnode,rnode;int minl,min2;for i=0;i2*n-l;i++〃所有结点的相关域置初值0ht[i].parent=ht[i].lchild=ht[i].rchild=O;〃构造哈夫曼树for i=n;i2*n-l;i++]//int的范围是-32768-32767mini=min2=MAX;//Inode和mode记录最小权值的两个结点位置lnode=rnode=0;〃选出每次外层循环最小权值的两个结点for k=0;k=i-l;k++〃只在尚未构造二叉树的结点中查找if ht[k].parent==O〃比mini小时ifht[k].weightminlmin2=minl;rnode=Inode;minl=ht[k].weight;lnode=k;else ifht[k].weightmin2〃比mini大，比min2小min2=ht[k].weight;rnode=k;ht[lnode].parent=i;ht[rnode].parent=i;〃两个最小节点的父节点是iht[i].weight=ht[lnode].weight+ht[rnode].weight;〃两个最小节点的父节点权值为两个最小节点权值之和ht[i].lchild=lnode;ht[i].rchild=rnode;〃父节点的左节点和右节点

③哈夫曼编码void CreateHCodeHTNodeht[],HCode hcd[],int nHCodehe;for i=0;in;i++〃根据哈夫曼树求哈夫曼编码hc.start=n;〃初始位置c=i;〃从叶子结点ht[i]开始上溯p=ht[i].parent;while p!=0〃循序直到树根结点结束循环hc.cd[hc.start—]=ht[p].lchild==c,O,:,l,;〃左孩子记为0,右孩子记为1；C=pp=ht[p].parent;〃与上句c=i;p=ht[i].parent同义,促进循环hc.start++;//start指向哈夫曼编码hc.cd口中最开始字符hcd[i]=hc;

④哈夫曼译码void deHCodeHTNodeht[]HCode hcd[]int nchar str[]〃译码函数zzzprintf输出译码结果为:\nint i,jkx,m=0;char code[MAX];for i=0;iMAX;i++for j=O;jn;j++ifstr[i]==ht[j].data〃循环查找与输入字符相同的编号，相同的就输出这个字符的编码for k=hcd[j].start;k=n;k++code[m]=hcd[j].cd[k];〃将输出的编码赋值到数组中m++;break;〃输出完成后跳出当前for循环code[m]=#;〃把要进行译码的字符串存入code数组中whilecode

[0]!=,#for i=0;in;i++m=0;//m为想同编码个数的计数器for k=hcd[i].startj=O;k=n;k++j++//j为记录所存储这个字符的编码个数/〃当有相同编码时m值加1ifcode[j]==hcd[i].cd[k]m++;〃当输入的字符串与所存储的编码字符串个数相等时ifm==j则输出这个的data数据printf%c,,ht[i].data;z〃把已经使用过的code数组里的字符串删除forx=0;code[x-j]!=#,;x++〃删除j个数，往前移动j位code[x]=code[x+j];。