huffman.cpp

在电报收发、数据通信过程中

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n 5
#define m 9
typedef char datatype;
typedef struct
{
	float weight;
	datatype data;
	int lchild,rchild,parent;
}hufmtree;
hufmtree tree[m];
typedef struct
{char bits[n];
int start;
datatype data;
}codetype;
codetype code[n];
void HUFFMAN()
{
	int i,j,p1,p2;
	char ch;
	float small1,small2,f;
	
	
	for(i=0;i<m;i++)
	{tree[i].parent=0;
	tree[i].lchild=0;
	tree[i].rchild=0;
	tree[i].weight=0.0;
	tree[i].data='0';
	}
	printf("输入每个叶子的权值和数据：\n");
	for(i=0;i<n;i++)
	{
		scanf("%f",&f);
		tree[i].weight=f;
		scanf("%s",&ch);
		tree[i].data=ch;
	}
	for(i=n;i<m;i++)
	{
		p1=p2=0;
	    small1=small2=1000.0;
	    for(j=0;j<=i-1;j++)
		if(tree[j].parent==0)
			if(tree[j].weight<small1)
			{
				small2=small1;
			    small1=tree[j].weight;
			    p2=p1;
			    p1=j;
			}else if(tree[j].weight<small2)
			{
				small2=tree[j].weight;
				p2=j;
			}
			tree[p1].parent=i;
			tree[p2].parent=i;
			tree[i].lchild=p1;
			tree[i].rchild=p2;
			tree[i].weight=tree[p1].weight+tree[p2].weight;
	}
	for(i=0;i<n;i++)
	{ printf("lchild=%d,data=%c,weight=%.0f,rchild=%d,parent=%d\n",tree[i].lchild,tree[i].data,tree[i].weight,tree[i].rchild,tree[i].parent);
	}

}
void HUFFMANCODE()
{
	int i,c,p,j;
    codetype cd;
    for(i=0;i<n;i++)
	{
		cd.start=n;
        c=i;
        p=tree[c].parent;
        cd.data=tree[c].data;
        while(p!=0)
		{
			cd.start--;
            if(tree[p].lchild==c) cd.bits[cd.start]='0';
            else cd.bits[cd.start]='1';
            c=p;
            p=tree[c].parent;
		}
        code[i]=cd;
	}
	for(i=0;i<n;i++){
		printf("data=%c,code=",code[i].data);
    for(j=code[i].start;j<n;j++)
	{
		printf("%c",code[i].bits[j]);
	}
	printf("\n");
	}
}
void OUT()
{
	printf("谢谢使用！\n");
}

void  main()
{
	int k;

	while(1)
	{
		printf("         ------------------------------\n");
		printf("         |         哈夫曼树           |\n");
		printf("         |============================|\n");
		printf("         |        1  构造哈夫曼树     |\n");
		printf("         |        2  哈夫曼编码       |\n");
        printf("         |        0  退出程序         |\n");
		printf("         ------------------------------\n");
		printf("         请输入选择的功能号：");
        scanf("%d",&k);
		switch(k)
		{
		case 1:  HUFFMAN();break;
		case 2:  HUFFMANCODE();break;
        case 0:  OUT();exit(1);
                
		}
	}
}