苗火 Nicholas

[Data structures]Huffman

2019-8-7 萧 写技术

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

#define MAX 20
#define INFINIT	65535

typedef struct _HTNode{
	int weight;
	int parent;
	int left;
	int right;
}HTNode;

void HuffmanCoding(HTNode **HT, char ***HC, int *w, int n)
{
	int i;
	int m;
	int ma,mb,mt;
	int sa,sb;
	int j;

	HTNode *p = NULL;
	char **q = NULL;
	char *cd = NULL;
	int start;

	/* Initial the huffman tree */

	m = 2*n-1;
	p = (HTNode *)malloc(sizeof(HTNode)*(m+1));
	*HT = p;
	for(i=1; i<=n; i++){
		p[i].weight = w[i];
		p[i].parent = p[i].left = p[i].right = 0;
	}
	for(;i<=m;i++){
		p[i].weight = 0;
		p[i].parent = p[i].left = p[i].right = 0;
	}

	/* Create the huffman tree */

	for(i=n+1; i<=m; i++){
		/* Select two minimal number from 1 to i-1 */
		ma = mb = INFINIT;
		for(j=1; j<=i-1; j++){
			if(p[j].parent == 0){
				if(mb > p[j].weight){
					mb = p[j].weight;

					sb = j;
				}
				if(ma > mb){
					mt = ma;
					ma = mb;
					mb = mt;

					mt = sa;
					sa = sb;
					sb = mt;
				}		
			}
		}

		p[sa].parent = i;
		p[sb].parent = i;
		p[i].left = sa;
		p[i].right = sb;
		p[i].weight = p[sa].weight + p[sb].weight;
	}


	/* Encode every character from bottom to top.
	 * Of course you can also do it from top to bottom. */

	q = (char **)malloc(sizeof(char *)*(n+1));
	*HC = q;

	cd = (char *)malloc(sizeof(char)*n);
	for(i=1; i<=n; i++){
		start = n-1;
		cd[start] = 0;
		for(j=i; p[j].parent; j=p[j].parent){
			if(p[ p[j].parent ].left == j){
				cd[--start] = '0';
			}else{
				cd[--start] = '1';
			}
		}
		q[i] = (char *)malloc(sizeof(char)*(n-start));
		strcpy(q[i], &cd[start]);
	}

	free(cd);
	cd = NULL;
}

void main()
{
	HTNode *HT;	
	char **HC;

	int weight[] = {-1, 7, 5, 2, 4}; /* From 1 */
	int data[] = {' ', 'a', 'b', 'c', 'd'};
	int n = sizeof(data)/sizeof(int)-1;
	int i,j;

	printf("log.anycle.com\n\n");
	printf("Original data:\n");
	for(i=1; i<=n; i++){
		printf("  %c(%2d)", data[i], weight[i]);
	}
	printf("\n");

	printf("Huffman coding:\n");
	HuffmanCoding(&HT, &HC, weight, n);

	for(i=1; i<=n; i++){
		printf("  %c(%s)", data[i], HC[i]);
	}
	printf("\n");
}

标签: Data Structures data_structures