huffmantree.cpp

数据结构的一个很重要的实验,经本人修改调试通过.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "huffmantree.h"
#include "error_hander.h"

static const char *msg[] = { "Please input a character: ",
                             "Please input its weight: ",
                             "Invalid input!! You should input an integer."};

/* Begin of creat_hufftree 05-10-2 13:10 */
void creat_hufftree(HuffmanTree ht, unsigned n) /* 形成赫夫曼树 */
{
    unsigned i, s1, s2, size = 2 * n - 1;
    
	for ( i = n + 1; i <= size; ++i ) {
		s1 = s2 = 0;
		Select(ht, i, &s1, &s2); /* 选择 parent 为 0，且 weight 最小的两个结点 */
		ht[s1].parent = ht[s2].parent = i;
		ht[i].lchild = s1;
		ht[i].rchild = s2;
		ht[i].weight = ht[s1].weight + ht[s2].weight;
	}
} /* End of creat_hufftree */

/* Begin of destroy_huffcode 05-10-2 14:50 */
void destroy_huffcode(HuffmanCode hc, unsigned n) /* 销毁赫夫曼编码 */
{
     unsigned i;
     
     for ( i = 1; i <= n; ++i ) {
         free(hc[i]);
     }
     free(hc);
} /* End of destroy_huffcode */

/* Begin of encode_hufftree 05-10-2 15:00 */
HuffmanCode encode_hufftree(HuffmanTree ht, unsigned n)
{ /* 从叶子到根逆向求每个字符的赫夫曼编码 */
	char *cd;
	unsigned start, i, child, parent;
	HuffmanCode hc;
	
    hc = (HuffmanCode)malloc( (n + 1) * sizeof *hc ); /* 分配 n 个字符编码的头指针向量 */
	if ( !hc ) {
		return NULL;
    }
    
	cd =(char*)malloc( n * sizeof *cd ); /* 分配编码的工作空间 */
	if ( !cd ) {
        free(hc);
		return NULL;
    }
    
	cd[n-1] = '\0'; /* 编码结束符 */

	for ( i = 1; i <= n; ++i ) { /* 逐个字符求赫夫曼编码 */
		start = n - 1; /* 编码结束位置 */
		for ( child = i, parent = ht[i].parent; parent != 0;
              child = parent, parent = ht[parent].parent ) { /* 从叶子到根逆向求编码 */
			if ( ht[parent].lchild == child ) {
				cd[--start]='0';
            } else {
				cd[--start]='1';
            }
		}
		hc[i] = (char*)malloc( (n - start) * sizeof *hc[i] ); /* 为第i个字符编码分配空间 */
		if ( !hc[i] ) {
            destroy_huffcode( hc, i - 1 );
            free(cd);
			return NULL;
        }
		strcpy(hc[i], &cd[start]);
	}
	
	free(cd); /* 释放工作空间 */	
	return hc;
} /* End of encode_hufftree */
                             
/* Begin of HuffmanTree 05-10-2 12:10 */
HuffmanTree init_hufftree(unsigned n) /* 初始化赫夫曼树 */
{
	int tmp, chk;
    unsigned i, size = 2 * n - 1;
	HuffmanTree ht, p;
	
    ht = (HuffmanTree)malloc( (size + 1) * sizeof *ht ); /* 不使用 0 号单元 */
    if ( !ht ) {
        return NULL;
    }
    
    for ( p = ht + 1, i = 1; i <= n; ++i, ++p) {
		fputs(msg[0], stdout);
		tmp = getchar();
		if ( tmp != '\n' && tmp != EOF ) {
            flush_stdin();
        }
        p->data = tmp;
        
        fputs(msg[1], stdout);
		while ( ( chk = scanf("%u", &p->weight) ) != 1 ) {
            if ( chk != EOF ) {
                flush_stdin();
            }
            printf("%s\n\n%s", msg[2], msg[1]);
        }
        flush_stdin();
		p->lchild = p->parent = p->rchild = 0;
	}
	
	for ( ; i <= size; ++i, ++p ) {
		p->lchild = p->parent = p->rchild = p->weight = 0;
    }
    
    return ht;
} /* End of HuffmanTree */

/* Begin of print_huffcode 05-10-2 15:15 */
void print_huffcode(HuffmanCode hc, HuffmanTree ht, unsigned n) /* 输出赫夫曼编码 */
{
    unsigned i;
	printf("The huffman Code that has just encoded is below:\n");
    
    for ( i = 1; i <= n; ++i ) {
        printf("%c: %s\n", ht[i].data, hc[i]);
    }
} /* End of print_huffcode */

/* Begin of Select 05-10-2 13:00 */
void Select(HuffmanTree p, unsigned i, unsigned *s1, unsigned *s2)
{ /* 选择 parent 为 0，且 weight 最小的两个结点 */
	unsigned j;

	for ( j = 1; j < i; ++j )
	{
		if ( !p[j].parent ) 
		{
			if ( !*s1 ) 
			{
				*s1 = j;
            } 
			else if ( p[*s1].weight > p[j].weight ) 
			{
				*s2 = *s1;
				*s1 = j;
			} 
			else 
			{
				*s2 = j;
            }
		}
		
		if ( *s1 && *s2 ) break;
	}//It seems that it can be improved here!
	
	for ( ++j; j < i; ++j ) 
	{
		if ( !p[j].parent )
		{
			if ( p[*s1].weight > p[j].weight ) 
			{
				*s2 = *s1;
				*s1 = j;
			} else if( p[*s2].weight > p[j].weight ) 
			{
					*s2 = j;
			}
		}
	}
} /* End of Select */