Huffman树.doc

Huffman树#include #include #include #define MAX_INT 99999/赫夫曼树和赫夫曼编码的存储表示typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表int min(HuffmanTree t,int i) int j,flag; int k=MAX_INT; / 取k为不小于可能的值 for(j=1; j=i; j+) if(tj.weightk&tj.parent=0) k=tj.weight; flag=j; tflag.parent=1; return flag;/ s1为最小的两个值中序号小的那个void select(HuffmanTree t,int i,int &s1,int &s2) s1=min(t,i); s2=min(t,i);void PrintTreeNonRecursive(HuffmanTree &HT,HuffmanCode &HC, int n) int i, c, cdlen; char *cd; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 c=2*n-1; cdlen=0; for(i=1; i0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCvoid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2; HuffmanTree p; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1; i=n; +i,+p,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(; i=m; +i,+p) (*p).parent=0; / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 for(i=n+1; i=m; +i) / 建赫夫曼树 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; PrintTreeNonRecursive(HT, HC, n);void Add(int a,int b,int &n) int iUpperCase26,s,j,k; char ch; int i; for(i=0;i26;i+) iUpperCasei=0; i=0; while(i=A&ch=Z) s=ch-A; +iUpperCases; i+; i=0; for(j=0;i0) aj=iUpperCasei; bj=i; j+; n=j; for(i=0;in-1;i+) for(k=0;kn-1-i;k+) if(akak+1) s=ak; ak=ak+1; ak+1=s; s=bk; bk=bk+1; bk+1=s; int main() HuffmanTree HT; HuffmanCode HC; int *p,n,i; int a26,b26; scanf(%d,&n); Add(a,b,n); p=(int *)malloc(n*sizeof(int); for(i=0;in;i+) *(p