huffman.c

数据结构源码合集

#include <stdio.h>
#include <stdlib.h>

typedef struct node *link;
struct node
{
	int f;
	link l, r;
};

int N;
link *h;

link NODE(int f, link l, link r)
{
	link t = malloc(sizeof *t);
	t->f = f;
	t->l = l;
	t->r = r;

	return t;
}

void get_freq(void)
{
	int i, f;
	scanf("%d", &N);
	h = malloc(N * sizeof(link));
	for(i = 0; i < N; i++)
	{
		scanf("%d", &f);
		h[i] = NODE(f, NULL, NULL);
	}
	h--;
}

void swap(int i, int j)
{
	struct node tmp_node;
	tmp_node = *h[i];
	*h[i] = *h[j];
	*h[j] = tmp_node;
}

int less(int i, int j)
{
	return (h[i]->f < h[j]->f);
}

void sift_down(int k, int n)
{
	int j;
	while((2 * k) <= n)
	{
		j = 2 * k;
		if(((j + 1) < n) && less(j + 1, j))
			j++;
		if(!less(j, k))
			break;
		swap(k, j);
		k = j;
	}
}

void sift_up(int k)
{
	int j;
	while(k > 1)
	{
		j = k / 2;
		if(less(k, j))
			swap(k, j);
		k = j;
	}
}

void pq_init(void)
{
	int i;
	for(i = N / 2; i >= 1; i--)
		sift_down(i, N);
}

link get_min(void)
{
	swap(1, N);
	sift_down(1, --N);

	return h[N + 1];
}

void insert(link t)
{
	h[++N] = t;
	sift_up(N);
}

void pre_order(link t)
{
	if(t)
	{
		printf("(");
		printf("%d", t->f);
		pre_order(t->l);
		pre_order(t->r);
		printf(")");
	}
	else
		printf("()");
}

int main(void)
{
	get_freq();
	pq_init();
	while(N > 1)
	{
		link t1 = get_min();
		link t2 = get_min();
		insert(NODE((t1->f + t2->f), t1, t2));
	}
	printf("\\tree ");
	pre_order(h[1]);
	puts("");

	return 0;
}