哈夫曼编码.cpp

来自「数据结构课程实验中所编的判断哈夫曼编码.参考可用」· C++ 代码 · 共 76 行

#include "stdio.h"
#include "iostream.h"
#include <malloc.h>
#include <conio.h>
#define NULL 0
#define MAX 100
#define LEN sizeof (struct HuffmanTree)

struct HuffmanTree{
	char data;
	struct HuffmanTree *right,*left,*parent;
};


HuffmanTree *CreateHumanTree(){          //建立哈夫曼树
    HuffmanTree *b,*a,*HT;
	char A[MAX]={NULL},e;int B[MAX]={NULL},i=0,j=0,k=0,l=0,m;
	cout<<"请输入要进行编码的字符:"<<endl;
	e=getchar();
	while(e!='\n')A[i]=e,i++,e=getchar();
    for(j=0;j<i;j++)
		cout<<"请为你输入第"<<j+1<<"的个字符权值:"<<endl,scanf("%d",&B[j]);
	k=B[0];          
	
	for(j=0;j<i;j++)
		if(B[j]!=NULL&&k>B[j])k=B[j],l=j;	
	HT=(struct HuffmanTree *)malloc(LEN);//开辟一个新单元	  
	HT->data=A[l]; HT->left=NULL;HT->right=NULL;
	 B[l]=NULL;			 
	 for(m=1;m<i;m++){
		 j=0;
		 while(B[j]==NULL&&j<i)j++;
		 k=B[j];l=j;
	    for(j=0;j<i;j++)
			if(B[j]!=NULL&&k>B[j])k=B[j],l=j;
	 a=(struct HuffmanTree *)malloc(LEN);//开辟一个新单元     
	 a->data=A[l];B[l]=NULL;a->left=NULL;a->right=NULL;
     b=(struct HuffmanTree *)malloc(LEN);//开辟一个新单元
	 b->left=a;a->parent=b;b->right=HT;HT->parent=b;
     HT=b;
	 }
return HT; 
}



void HuffmanCode(HuffmanTree *HT){//生成哈夫曼编码
    int i=0,j; 	
     if(HT->left==NULL)cout<<HT->data<<"的哈夫曼编码是:0\n";//当只有一个结点的时候编码为“0”
     else{
loop:	if(HT->left!=NULL){
		HT=HT->left;i++;
    cout<<HT->data<<"的哈夫曼编码是:";
	for(j=1;j<i;j++)cout<<"1";
	cout<<"0\n";
	HT=HT->parent;HT=HT->right;
	goto loop;}	
	cout<<HT->data<<"的哈夫曼编码是:";
	for(j=0;j<i;j++)cout<<"1";
	 }	
}


void main(){
	HuffmanTree *HT;	
    HT=CreateHumanTree();
	HuffmanCode(HT);
	cout<<"\n完成"<<endl;
	getch(); 	
}