c6_huffman.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
Huffman编码程序
主要是建立Huffman编码和译码
BY：wangyucao
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<cstring>
#include<stack>
#include<stdlib.h>
#include<queue>
#define MAX 125
using namespace std;

struct Node{
	char key;
	int weight;
	Node *lc,*rc;	
};
int n;
Node *HT[MAX];
bool used[MAX];
char code[MAX][MAX];
char code_now[MAX];
ifstream fin("data.in");
ofstream fout("data.out");
Node* Building_HTree()
{
	Node *p;
	int s1,s2,root;
	int now=n;
	while(now>1)
	{
		int i;
		s1=-1;
		s2=-1;
		for(i=0;i<n;i++)            //find the two smallest weight
			if(!used[i])
				if(s1<0 || HT[s1]->weight > HT[i]->weight) s1=i;
		used[s1]=true;
		for(i=0;i<n;i++)            //find the two smallest weight
			if(!used[i])
			if(s2<0 || HT[s2]->weight > HT[i]->weight) s2=i;
	
		p=(Node *)malloc(sizeof(Node));
		p->key='*';
		p->weight=HT[s1]->weight+HT[s2]->weight;
		p->rc=HT[s1];
		p->lc=HT[s2];
		HT[s2]=p;
		now--;
		root=s2;
	}
	return HT[s2];
}
void Coding(Node *Tree,int i)           //遍历霍夫曼树，建立编码表
{
	if(Tree->key!='*') 
		{code_now[i]='\0'; 
	     fout<<Tree->key<<' '<<code_now<<endl;
		 memcpy(code[Tree->key],code_now,sizeof(code_now));
	}
	else{
		code_now[i]='0';
		Coding(Tree->lc,i+1);
		code_now[i]='1';
		Coding(Tree->rc,i+1);
	}
}
void TransCoding(Node *Tree)                 //根据编码表来对文章编码
{
	char ch;
	fin>>ch;
	while(ch!='\n'){
	fout<<code[ch];
	fin.get(ch);}
}
void SearchCoding(Node *Tree)                //利用霍夫曼树来对已编码序列解码
{
	char ch;
	while(!fin.eof()){
	    Node *p=Tree;
	    while(p->key=='*')
		{
		    if(fin.eof()) return;
			fin>>ch;			
			if(ch=='0') p=p->lc;
			else p=p->rc;
		}
		fout<<p->key;
	}
//	fout<<endl;
}
int main()
{
	int i;
	fin>>n;
	Node *HTree;
	memset(used,false,sizeof(used));
	for(i=0;i<n;i++) 
	{
		HT[i]=(Node *)malloc(sizeof(Node));
		fin>>HT[i]->key>>HT[i]->weight;
		HT[i]->lc=NULL;
		HT[i]->rc=NULL;
	}
	HTree=Building_HTree();    //建立霍夫曼树
	Coding(HTree,0);
//	fout<<endl;
	TransCoding(HTree);       //编码
	fout<<endl;
	SearchCoding(HTree);       //解码
	return 0;
}