数据结构哈夫曼编码.doc

数据结构实训班级:计科101 姓名:  学号: 完成日期:2012/6/28题目:哈夫曼编码一、问题描述设某编码系统共有n个字符,使用频率分别为{w1,w2,…,wn},设计一个不等长的编码方案,使得该编码系统的空间效率最好。二、基本要求(1)在文件中存储一系列字符代码;(2)编写程序分析文件中各个字符以及每个字符出现的频率;(3)将各个字符及其频率分析成结点以及结点的权值,构造哈弗曼树。(4)分析构造的哈夫曼树,列出相应的哈弗曼编码(5)把生成的编码替换原文件中的字符,并将结果存储到文件中三、实验描述设有10个字符,使用频率分别为10%、5%、7%、8%、15%、6%、18%、5%、3%、13%,这10个结点的权值分别为10、5、7、8、15、6、18、5、3、13、让后构造一颗有10个叶子节点的二叉树四、实验程序#include<>#include<>#include<>intm,s1,s2;typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar*HuffmanCode;//动态分配数组存储哈夫曼编码表voidSelect(HuffmanTreeHT,intn){inti,j;for(i=1;i<=n;i++)if(!HT[i].parent){s1=i;break;}for(j=i+1;j<=n;j++)if(!HT[j].parent){s2=j;break;}for(i=1;i<=n;i++)if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;for(j=1;j<=n;j++)if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;}voidHuffmanCoding(HuffmanTree&HT,HuffmanCodeHC[],int*w,intn){//w存放n个字符的权值(均>0),构造哈夫曼树HT,//并求出n个字符的哈夫曼编码HCinti,j;char*cd;intp;intcdlen;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1;i<=n;i++){//初始化HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;i++){//初始化HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}puts("\n哈夫曼树的构造过程如下所示:");printf("HT初态:\n结点weightparentlchildrchild");for(i=1;i<=m;i++)printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild,