bianma.cpp

数据结构

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#define MAXSIZE 1000
static int n=29;
static int m=2*n-1;
typedef struct
{
	char data;
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

char words[29] = {'a','b','c','d','e','f','g','h',
                'i','j','k','l','m','n','o','p','q','r',
                's','t','u','v','w','x','y','z',' ',',','.'};

static int w[29]={12,23,65,7,1,87,35,45,98,21,11,100,57,39,90,9,102,66,75,20,87,33,44,67,67,91,123,28};

void Select(HuffmanTree HT,int i,int &s1,int &s2)
{//从建好的树中选出两个最小的数
	int p1,p2;
	p1=p2=32767;
	s1=s2=0;
	for(int j=1;j<=i;j++)
	{
		if(HT[j].parent==0)
		{
			if(HT[j].weight<p1)
			{
				p2=p1; p1=HT[j].weight;
				s2=s1;s1=j;
			}
			else
			{
				if(HT[j].weight<p2)
				{
					p2=HT[j].weight;
					s2=j;
				}
			}
		}
	}
}//Select()
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC)
{  //建哈夫曼树和求哈夫曼编码
	int i,s1,s2,start,c,f;
    HuffmanTree p;
	if(n<=1)
		return;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	char *w=words;
	for(p=HT+1,i=1;i<=n;++i,++p,++w)//对树的结点赋初值			
	{ 
		p->data=*w;
		p->weight=*w;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
	}
	for(;i<=m;++i,++p)			
	{ 
		p->data=NULL;
		p->weight=0;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
	}
	for(i=n+1;i<=m;++i)//建哈夫曼树
	{ 
		Select(HT,i-1,s1,s2);//选出两个最小的结点
		HT[s1].parent=i; HT[s2].parent=i;
		HT[i].lchild=s1; HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	/*==========求出哈夫曼编码==================*/
        HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
        char *cd;
       cd=(char *)malloc(n*sizeof(char));
       cd[n-1]='\0';
      for(i=1;i<=n;++i)
	  { 
		  start=n-1;
      for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
        if(HT[f].lchild==c)   //判断当前结点是左孩子还是右孩子
           cd[--start]='0';
         else
           cd[--start]='1';
        HC[i]=(char*)malloc((n-start)*sizeof(char));
       strcpy(HC[i],&cd[start]);
       printf("\nHT[%d]-- %c 的哈夫曼码为: %s",i,HT[i].data,HC[i]);
	  }
	  printf("\n");
	free(cd);
} //HuffmanCoding()

void Tran_StrCode(HuffmanTree HT,char str[],HuffmanCode HC)
{//对输入的字符译码
	int strnum=strlen(str);
	for(int i=0;i<strnum;i++)
	{
		if(str[i]!='\0')
		{
			for(int j=1;j<=n;j++)
			{	
				if((str[i]==HT[j].data)||(str[i]==(HT[j].data-32)))
				printf("%s\t",HC[j]);
			}
		}
	}
	printf("\n");
}//Tran_StrCode()

void Tran_BinaryCode(HuffmanTree HT,HuffmanCode HC)
{ //对输入的二进制码译为字符
	int i=m;
	char b[200];
	
	printf("输入一串二进制编码(0，1以外的数结束)：");
	gets(b);
	int length=strlen(b);
	printf("译码为：");
	for(int j=0;j<length;j++)
		{
			if(b[j]=='0')
				i=HT[i].lchild;
			else 
				i=HT[i].rchild;
			if(HT[i].lchild==0)
			{
				printf("%c",HT[i].data);
				i=m;
			}
		}
	printf("\n");
}//Tran_BinaryCode()

void main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	HuffmanCoding(HT,HC);
	char str[MAXSIZE];
	printf("输入一串字符以编码：\n");
	gets(str);
	printf("编码内容为：\n");
	Tran_StrCode(HT,str,HC);
	Tran_BinaryCode(HT,HC);
}