哈夫曼树的构造哈夫曼树.doc

/* * * * * * * * * * * * * * * * * * * * * * * */哈夫曼树的构造哈夫曼树,哈夫曼编码 */* * * * * * * * * * * * * * * * * * * * * * * *#include #include #include #include #include typedef structunsigned int weight; /结点权值 unsigned int parent,lchild,rchild; /结点的父指针，左右孩子指针HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char *HuffmanCode; /动态分配数组存储哈夫曼编码表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; /哈夫曼树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( 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); /输入各叶子结点权值 CreateHuffmanTree(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-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.parent=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 *); /分配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个编码分配空间 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且权值最小的两个结点，其序号分别为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 struct 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 HuffmanCoding(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.weight=HTs1.weight+HTs2.weight; printf(HT List:n); printf(Numberttweightttparentttlchildttrchildn); for(i=1;i=m;i+) printf(%dtt%dtt%dtt%dtt%dn, i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); HC=(HuffmanCode)malloc(n+1)*sizeof(char *); 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; else cd-start=1; HCi=(char *)malloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); return HC;MinCode Select(HuffmanTree HT,unsigned int n) unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code; s1=1;s2=1; for(i=1;i=n;i+) if(HTi.parent=0) min=HTi.weight; s1=i; break; tempi=i+; for(;i=n;i+) if(HTi.weightmin&HTi.parent=0) min=HTi.weight; s1=i; for(i=tempi;i=n;i+) if(HTi.parent=0&i!=s1) secmin=HTi.weight; s2=i; break; for(i=1;i=n;i+) if(HTi.weights2) temp=s1; s1=s2; s2=temp; code.s1=s1; code.s2=s2; return code;void main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; clrscr(); printf(Input n:n); scanf(%d,&n); w=(unsigned int *)malloc(n+1)*sizeof(unsigned int *); w0=0; printf(Enter weight:n); for(i=1;i=n;i+) printf(w%d=,i); scanf(%d,&wi); HC=HuffmanCoding(HT,HC,w,n); printf(HuffmanCode:n); printf(NumberttWeightttCoden); for(i=1;i=n;i+) printf(%dtt%dtt%sn,i,wi,HCi); 程序运行：首先用户先输入一个数n，以实现n个节点的Huffman Tree之后输入权值w1wn，注意是unsigned int型数值。然后程序自动生成Huffman Tree的存储形式的一张表格。最后是Huffman Coding。Sample Input:Input n:8Enter weight:w1=5w2=29w3=7w4=8w5=14w6=23w7=3w8=11Sample Output:HT List:Number weight p