数据结构哈夫曼编码.doc

Main.c文件如下#include #include #include #include Haffman.h#define MaxBit 100void main(void) Code *d; int i,j,n=26,m,weight26=0; char c,a=97; FILE *fp; /文本文件指针 if(fp=fopen(data.txt,r)=NULL) printf(无法打开此文件n); exit(0); /中止程序 printf(待压缩的英文文本文件为:n); while(!feof(fp) /当扫描文件内容没有结束时 /读取字符并统计每个字符次数 c=fgetc(fp);putchar(c); if(c=a|c=z); c=c-32; for (i=65;i=90;i+) if(c=i) weighti-65+ ; fclose(fp); HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n-1); Code *myHaffCode=(Code *)malloc(sizeof(Code)*n); Haffman(weight,n,myHaffTree); HaffmanCode(myHaffTree,n,myHaffCode); for(m=0;mn;m+) printf(nzimu=%c Weight=%d Code=,a+,myHaffCodem.weight); for(j=myHaffCodem.start;jn;j+) printf(%d,myHaffCodem.bitj); printf(n); 头文件Huffman.h如下#ifndef Haffman_H_INCLUDED#define Haffman_H_INCLUDED#define MaxN 300#define MaxValue 10000typedef struct int weight; /权值 int flag; /标记 int parent; /双亲结点下标 int leftChild; /左孩子下标 int rightChild; /右孩子下标HaffNode; /哈夫曼树的结点结构typedef struct int bitMaxN; /数组 int start; /编码的起始下标 int weight; /字符的权值Code; /哈弗曼编码的结构void Haffman(int weight,int n,HaffNode haffTree)/建立叶节点个数为n，权值数组为weight的哈弗曼树haffTree int i,j,m1,m2,x1,x2; /哈夫曼树haffTree初始化，n个叶节点的二叉树共有2n-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.rightChild=-1; /构造哈弗曼树的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; /将找出两棵权值最小和次小的子树合并为一棵子树 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 HaffmanCode(HaffNode haffTree,int n,Code haffCode)/由n个结点的哈夫曼树构造哈弗曼编码 Code *cd=(Code *)malloc(sizeof(Code); int i,j,child,parent; /求n个叶节点的哈弗曼编码 for(i=0;istart=n-1; /不等长编码的最后一位n-1 cd-weight=haffTreei.weight; /取得编码对应权值 child=i; parent=haffTreechild.parent; /由叶节点向上直到根节点 while(parent!=-1) if(haffTreeparent.leftChild=child) cd-bitcd-start=0; /左孩子分支编码0 else cd-bitcd-start=1; /左孩子分支编码1 cd-start-; child=parent; parent=haffTreechild.parent; for(j=cd-start+1;j