main.c

这是计算机体系结构中用哈夫曼编码进行指令编码的程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define BUFFER_SIZE 40
#define MAX_NAME_LEN 24

/*
 * This structure corresponding to a item to be coded.
 * 	freq:	frequence the item appears in.
 * 	name:	item's name.
 */
struct item {
	double freq;
	char name[MAX_NAME_LEN];
	struct item *left;
	struct item *right;
	struct item *next;
	struct item *prev;
};

/*
 * After the items read in they are stored in itemlist. 
 */ 
struct item * itemlist = NULL;

/*
 * The root of the huffman tree.
 */ 
struct item * itemtree = NULL;

/*
 * Allocate space for a item and initialize it to zero.
 */
struct item *newitem()
{
	struct item * pitem = (struct item *)malloc(sizeof(struct item));
	memset(pitem, 0, sizeof(struct item));
	return pitem;
}

/*
 * Add a new item to itemlist.
 */
void listadd(struct item * pitem)
{
	if(itemlist == NULL) {
		itemlist = pitem;
		itemlist->prev = itemlist;
		itemlist->next = itemlist;
		return;
	}
	pitem->next = itemlist;
	pitem->prev = itemlist-> prev;
	itemlist->prev->next = pitem;
	itemlist->prev = pitem;
}

/*
 * Remove the item has smallest frequence from 
 * itemlist and return it.
 */
struct item *listremove()
{
	struct item *min;
	struct item *pitem;

	if(itemlist == NULL)
		return NULL;

	for(min = pitem = itemlist->next; ; pitem = pitem->next) {
		if (pitem->freq < min->freq) min = pitem;
		if(pitem == itemlist) break;
	}

	if(min == itemlist)
		itemlist = min->next;
	min->prev->next = min->next;
	min->next->prev = min->prev;
	if(min->next ==min){
		itemlist = NULL;
	}
	return min;
}

/*
 * Read the items from input and add them to itemlist.
 */
void buildlist(FILE *fp)
{
	char buffer[BUFFER_SIZE];

	while(fgets(buffer,BUFFER_SIZE-1, fp) != NULL) {
		struct item * pitem = newitem();
		strncpy(pitem->name, strtok(buffer, "\t"), MAX_NAME_LEN);
		pitem->freq = atof(strtok(NULL, "\n"));
		listadd(pitem);
	}
}

/*
 * Build the huffman tree.
 * 	Algorithm:
 * 		1. Get the item has smallest frequence from itemlist
 * 		   denote as first.
 * 		2. Get the item has smallest frequence from itemlist again
 * 		   denote as second.
 * 		   	if	second == NUll then terminate.
 * 		   	else	construct a new item without a name and with first
 * 		   		second as its left and right child.
 *				add the new item to the list.
 */
void buildtree()
{
	struct item *first, *second;
	struct item *pitem;

	while(first = listremove()) {
		if((second= listremove()) == NULL) {
			itemtree = first;
			return;
		}
		pitem = newitem();
		pitem->freq = first->freq + second->freq;
		pitem->left = first;
		pitem->right = second;
		listadd(pitem);
	}
}

/*
 * Convert the code to a human readable format.
 */
char* code_to_text(unsigned long code, int level)
{
	int i; 
	static char codestr[65];

	codestr[level]='\0';
	for(i= level-1; i >= 0; --i){
		if(code & 0x1L)
			codestr[i] = '1';
		else 
			codestr[i] = '0';
		code >>= 1;
	}
	return codestr;
}

/*
 * Encode each item has a name according to the huffman tree.
 */ 
void encode(struct item * pitem)
{
	static int level = 0;
	static unsigned long code = 0L;

	if(pitem->name[0] != '\0') {
		fprintf(stdout, "%s :  %s\n", pitem->name, code_to_text(code, level));
		return;
	}
	level++;
	code <<= 1;
	encode(pitem->left);
	code |= 0x1L;
	encode(pitem->right);
	level--;
	code >>= 1;
}

int main(int argc, char *argv[])
{
	FILE *input;
	
	/*
	 * If no file specified, read the frequences
	 * from stdin, else read from the file.
	 * 
	 * 	file foramt: ("NAME"\t"FREQUENCE"\n)*
	 */
	if(argv[1] == NULL)
		input = stdin;
	else if ((input = fopen(argv[1], "r")) == NULL) {
		fprintf(stderr, "ERROR: File %s can't open.", argv[1]);
		exit(1);
	}

	buildlist(input);
	buildtree();
	encode(itemtree);
    double a[10]={0.25,0.20,0.15,0.10,0.08,0.08,0.05,0.04,0.03,0.02};
	double H=0;
	for (i=0;i<10;i++) H=H-a[i]*log(a[i]);
	printf("the avg length of huffman is %10f",H);
	exit(0);
}