《哈夫曼树的构造哈夫曼树.doc》由会员分享，可在线阅读，更多相关《哈夫曼树的构造哈夫曼树.doc（9页珍藏版）》请在金锄头文库上搜索。
1、/* * * * * * * * * * * * * * * * * * * * * * * */哈夫曼树的构造哈夫曼树,哈夫曼编码 */* * * * * * * * * * * * * * * * * * * * * * * *#include #include #include #include #include typedef structunsigned int weight; /结点权值 unsigned int parent,lchild,rchild; /结点的父指针，左右孩子指针HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char *H
2、uffmanCode; /动态分配数组存储哈夫曼编码表void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); /生成一棵哈夫曼树void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); /对哈夫曼树进行编码void PrintHuffmanCode(HuffmanCode,unsigned int*,int); /显示哈夫曼编码void Select(HuffmanTree,int,int&,int&); /在数组中寻找权值最小的两个结点void main()HuffmanTree HT;
3、 /哈夫曼树HT HuffmanCode HC; /哈夫曼编码表HC int n,i; /n是哈夫曼树叶子结点数 unsigned int *w; /w存放叶子结点权值 char j=y; textbackground(3); /设定屏幕颜色 textcolor(15); clrscr(); /程序解说 printf(本程序将演示构造哈夫曼树.n); printf(首先输入叶子结点数目.n例如:8n); printf(然后输入每个叶子结点的权值.n); printf(例如:5 29 7 8 14 23 3 11n); printf(程序会构造一棵哈夫曼树并显示哈夫曼编码.n); printf(
4、 5-0110n 29-10n 7-1110n 8-1111n 14-110n); printf( 23-00n 3-0111n 11-010n); while(j!=N&j!=n) printf(请输入叶子结点数目:); scanf(%d,&n); /输入叶子结点数 if(n=1) printf(该数不合理!n);continue; w=(unsigned int*)malloc(n*sizeof(unsigned int); /开辟空间存放权值 printf(请输入各叶子结点的权值:n); for(i=0;in;i+) scanf(%d,&wi); /输入各叶子结点权值 CreateHuf
5、fmanTree(HT,w,n); /生成哈夫曼树 HuffmanCoding(HT,HC,n); /进行哈夫曼编码 PrintHuffmanCode(HC,w,n); /显示哈夫曼编码 printf(哈夫曼树构造完毕，还要继续吗?(Y/N); scanf( %c,&j); void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)/w存放n个结点的权值，将构造一棵哈夫曼树HT int i,m; int s1,s2; HuffmanTree p; if(n=1) return; m=2*n-1; /n个叶子结点的哈夫曼树，有2*n
6、-1个结点 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /开辟2*n各结点空间，0号单元不用 for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iweight=0; p-parent=0; p-lchild=0; p-rchild=0; for(i=n+1;i=m;+i) /建哈夫曼树 Select(HT,i-1,s1,s2); /从HT1.i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 HTs1.parent=i; HTs2.pa
7、rent=i; /修改s1和s2结点的父指针parent HTi.lchild=s1; HTi.rchild=s2; /修改i结点的左右孩子指针 HTi.weight=HTs1.weight+HTs2.weight; /修改权值 void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)/将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中 /方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i,c,f,start; char *cd; HC=(HuffmanCode)malloc(n+1)*sizeof(char *);
8、/分配n个编码的头指针向量 cd=(char *)malloc(n*sizeof(char); /开辟一个求编码的工作空间 cdn-1=0; /编码结束符 for(i=1;i=n;+i) /逐个地求哈夫曼编码 start=n-1; /编码结束位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=0; /若是左孩子编为0 else cd-start=1; /若是右孩子编为1 HCi=(char *)malloc(n-start)*sizeof(char); /为第i个编码分配空间
9、strcpy(HCi,&cdstart); /将编码从cd复制到HC中 free(cd); /释放工作空间void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)/显示有n个叶子结点的哈夫曼树的编码表 int i; printf(HuffmanCode is :n); for(i=1;i=n;i+) printf( %3d-,wi-1); puts(HCi); printf(n);void Select(HuffmanTree HT,int t,int&s1,int&s2)/在HT1.t中选择parent不为0且权值最小的两个结点，
10、其序号分别为s1和s2 int i,m,n; m=n=10000; for(i=1;i=t;i+) if(HTi.parent=0&(HTi.weightm|HTi.weightn) if(ms2) /s1放较小的序号 i=s1;s1=s2;s2=i;#include #include #include #include #include typedef struct unsigned int weight;unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char *HuffmanCode;typedef struc
11、t unsigned int s1;unsigned int s2; MinCode;void Error(char *message);HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n);MinCode Select(HuffmanTree HT,unsigned int n);void Error(char *message) clrscr(); fprintf(stderr,Error:%sn,message); exit(1);HuffmanCode Huffma
12、nCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n) unsigned int i,s1=0,s2=0; HuffmanTree p; char *cd; unsigned int f,c,start,m; MinCode min; if(n=1) Error(Code too small!); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=0;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iweight=0; p-parent=0; p-lchild=0; p-rchild=0; for(i=n+1;i=m;i+) min=Select(HT,i-1); s1=min.s1; s2=min.s2; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.
