该代码採用二叉树结合双向链表实现了限制长度的最优Huffman编码，本文代码中的权重所有採用整数值表示。http://pan.baidu.com/s/1mgHn8lq

算法原理详见：

演示样例：符号ABCDE的权重分别为10,6,2,1,1

　　　不限制长度的最优Huffman编码为A:0,B:10,C:110,D:1110,E:1111，平均码长为1.8bits/symbol;

　　　限制长度3的最优Huffman编码为  A:0,B:100,C:101,D:110,E:111，  平均码长为2.0bits/symbol;

限制长度最优Huffman编码实现代码例如以下:

//Reference:A fast algorithm for optimal length-limited Huffman codes.pdf,http://pan.baidu.com/s/1o6E19Bs//author:by Pan Yumin.2014-06-18//with the method of BinaryTree and linked-list#include 
     
      #include 
      
       #include 
       
        #define  MaxSymbols 256	//the Maximum Number of Symbols#define  MaxHuffLen	16	//the Limited Lengthtypedef unsigned char boolean;#ifndef FALSE			//in case these macros already exist#define FALSE	0		//values of boolean#endif#ifndef TRUE#define TRUE	1#endiftypedef struct __Node{	int width;	int weight;	int index;	int depth;	struct __Node *prev;	//double linked list	struct __Node *next;	//double linked list	struct __Node *left;	//left child	struct __Node *right;	//right child}Node;typedef struct __HuffTable{	unsigned int index;	unsigned int len;	unsigned int code;}HuffTable;//Test memory leak/*int g_malloc = 0,g_free = 0;void* my_malloc(int size){	g_malloc++;	return malloc(size);}void my_free(void *ptr){	if(ptr){		g_free++;		free(ptr);		ptr = NULL;	}}#define malloc my_malloc#define free my_free*///Get the smallest term in the diadic expansion of Xint GetSmallestTerm(int X){	int N=0;	while((X & 0x01) == 0){		X >>= 1;		N++;	}	return 1<
        
         left == NULL && head->right == NULL){		if(isDelete)			Flag[head->depth*Symbols+head->index] = 0;		else			Flag[head->depth*Symbols+head->index] = 1;	}	if(head->left){		deleteNode(head->left,Flag,Symbols,isDelete);	}	if(head->right){		deleteNode(head->right,Flag,Symbols,isDelete);	}	free(head);	head = NULL;}//N:the Num of nodevoid Package_Merge(Node *head,Node **tail,int minWidth,unsigned char * Flag,int Symbols){	Node *tmp = NULL,*node_1 = NULL,*node_2 = NULL;	Node *node_P_head = NULL,*node_P_tail = NULL;		//node_P_tail not store data,node_P_head store data	Node *node_head = head;								//the head of 2*minWidth	//package	node_P_tail = (Node *)malloc(sizeof(Node));	memset(node_P_tail,0,sizeof(Node));	node_2 = node_P_tail;	node_1 = (*tail)->prev;	for(;node_1 != NULL && node_1 != head; node_1=(*tail)->prev){		if(node_1->width == minWidth){			tmp = (Node*)malloc(sizeof(Node));			tmp->right = node_1->next;				//insert from right to left,so the weight from small to large			tmp->left = node_1;			tmp->width = 2*minWidth;			tmp->weight = node_1->weight+node_1->next->weight;			tmp->next = node_2;			tmp->prev = NULL;			node_2->prev = tmp;			node_2 = tmp;			*tail = node_1->prev;	(*tail)->next = NULL;		//two intervals		}else{			break;		}	}	node_P_head = node_2;	if(*tail != head && (*tail)->width == minWidth){	//if the number of minwidth is odd,delete the max weight item of minwidth		*tail = (*tail)->prev;		deleteNode((*tail)->next,Flag,Symbols,TRUE);		(*tail)->next = NULL;	}	//find the range of 2*minWidth	node_1 = *tail;	for(;node_1 != head && node_1->width == 2*minWidth;node_1 = node_1->prev){	}	node_head = node_1;		//the head of 2*minWidth, node_head not store 2*minWidth	//merge	node_1 = node_head->next;	node_2 = node_P_head;	for(;node_1 != NULL && node_2 != node_P_tail;){		if(node_1->weight >= node_2->weight){			node_1 = node_1->next;		}else{		//insert to the major list			node_1->prev->next = node_2;			node_2->prev = node_1->prev;			node_1->prev = node_2;			node_2 = node_2->next;			node_2->prev->next = node_1;			node_2->prev = NULL;		}	}	if(node_1 == NULL){		//insert list 2 to the major list		(*tail)->next = node_2;		node_2->prev = *tail;		*tail = node_P_tail->prev;		(*tail)->next = NULL;		free(node_P_tail);	node_P_tail = NULL;	}else{		free(node_P_tail);	node_P_tail = NULL;	}}//N:the Num of nodeint LengthLimitedHuffmanCode(Node *head,Node *tail,int X,unsigned char * Flag,int Symbols){	int minwidth,r;	while(X>0){		minwidth = GetSmallestTerm(X);		if( head->next == NULL)		//I empty			return -1;		r = tail->width;				//Just for Huffman Code,else r = GetMinWidth(head);		if(r>minwidth){			return -2;		}else if(r == minwidth){			tail = tail->prev;			deleteNode(tail->next,Flag,Symbols,FALSE);			tail->next = NULL;			X = X-minwidth;		}else{			Package_Merge(head,&tail,r,Flag,Symbols);		}			}	return 0;}void PrintHuffCode(HuffTable Huffcode){	int i;	for(i=Huffcode.len-1;i>=0;i--){		printf("%d",(Huffcode.code>>i) & 0x01);	}}void GenerateHuffmanCode(HuffTable *HuffCode,unsigned char *Flag,int L,int Symbols,int *SortIndex){	char Code[17];	int Pre_L = 0;	int i=0,j=0;	unsigned int codes[MaxHuffLen+2]={0},rank[MaxHuffLen+1] = {0};	//rank: the number of symbols in every length	//find the first code	for(i=0;i
         
           (1<
          
            (1<
           
            prev = node; tmp->next = NULL; tmp->left = NULL; tmp->right = NULL; tmp->width = 1<<(MaxHuffLen-i-1); tmp->weight = Freq[j]; tmp->index = j; tmp->depth = i; node->next = tmp; node = tmp; } } tail = node; //tail Ret = LengthLimitedHuffmanCode(head,tail,(Symbols-1)<
            
             int main(){ //int Freq[MaxSymbols] = {1,25,3,4,9,6,4,6,26,15,234,4578}; //weight is not zero. int Freq[MaxSymbols] = {10,6,2,1,1}; //weight is not zero. GenLenLimitedOptHuffCode(Freq,5); return 0;}
            
           
          
         
        
       
      
     

执行上述程序输出结果例如以下所看到的：