哈夫曼编码系统C语言实现

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个基于哈夫曼编码的通信系统。 系统应具有以下功能： 1）初始化处理：建立通信系统 2）发送端信息编码 3）接受端信息译码

//代码由Micmia（qq:791713543）编写
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INFOVOL 100
#define TEMP_LIMIT 999
#define TEMPSTR_LIMIT 999
#define W_LIMIT 999
#define SN_LIMIT 100
#define ZH_INFO_LIMIT 999
#define INFOHC_LIMIT 999
#define INFO_LIMIT 999
#define SN_LIMIT 999
#define GREAT 999
#define TIME 500
typedef char *HuffmanCode;
typedef struct{
	int weight;
	int parentlchildrchild;
	char *codechar;
	HuffmanCode hc;
}HuffmanNode*HuffmanTree;
typedef struct{
	char *zh_info;//中文信息
	char *infochar;//信息字符
}Information;
Information infoset[INFOVOL];
//typedef char ** HuffmanCode;
int nl;//定义字符集大小即叶子节点个数n
int ms1s2;//定义哈夫曼树节点总数m
HuffmanTree ht;
//HuffmanCode hc;
void test（）{
	int i;
	printf（“SN\tCODE\tWEIGHT\tPARENT\tLCHILD\tRCHILD\tHUFFMANCODE\n“）;
	for（i=0;i		printf（“%d\t“i）;
		printf（“%s\t“ht[i].codechar）;
		printf（“%d\t“ht[i].weight）;
		printf（“%d\t“ht[i].parent）;
		printf（“%d\t“ht[i].lchild）;
		printf（“%d\t“ht[i].rchild）;
//		if（i		if（i		printf（“\n“）;
	}
}
void build（int _w[]char *_codechar）{
	int itcf;
	char *tempstr;
	void choose（HuffmanTree _htint _i）;
	m=2*n-1;
	ht=（HuffmanTree）malloc（m*sizeof（HuffmanNode））;
	for（i=0;i		ht[i].codechar=（char *）malloc（2*sizeof（char））;
		ht[i].weight=_w[i];
		ht[i].parent=-1;
		ht[i].lchild=0;
		ht[i].rchild=0;
		ht[i].codechar[0]=_codechar[i];
		ht[i].codechar[1]=‘\0‘;
	}
	for（;i		ht[i].codechar=（char *）malloc（2*sizeof（char））;
		ht[i].weight=0;
		ht[i].parent=-1;
		ht[i].lchild=0;
		ht[i].rchild=0;
		ht[i].codechar[0]=‘ ‘;
		ht[i].codechar[1]=‘\0‘;
	}
	for（i=n;i		choose（hti-1）;//ht[0...i-1]中选择parent为-1且weight最小的两个节点，序号分别为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*sizeof（char *））;
	tempstr=（char *）malloc（n*sizeof（char））;
	tempstr[n-1]=‘\0‘;
	for（i=0;i		t=n-1;//编码结束符位置
		for（c=if=ht[i].parent;f!=-1;c=ff=ht[f].parent）{
			if（c==ht[f].lchild）tempstr[--t]=‘0‘;
			else tempstr[--t]=‘1‘;
		}
		hc[i]=（char *）malloc（（n-t）*sizeof（char））;
		strcpy（hc[i]&tempstr[t]）;
	}*/
	//以下从叶子到根逆向求每个字符的哈夫曼编码
	tempstr=（char *）malloc（n*sizeof（char））;//分配求哈夫曼编码的工作空间，哈夫曼编码长度不会超过n
	tempstr[n-1]=‘\0‘;
	for（i=0;i		t=n-1;//编码结束符位置
		for（c=if=ht[i].parent;f!=-1;c=ff=ht[f].parent）{//循环至根节点
			if（c==ht[f].lchild）tempstr[--t]=‘0‘;//如果c（孩子节点）是f（父节点）的左孩子，则记0
			else tempstr[--t]=‘1‘;//如果c（孩子节点）是f（父节点）的右孩子，则记1
		}
		ht[i].hc=（char *）malloc（（n-t）*sizeof（char））;
		strcpy（ht[i].hc&tempstr[t]）;
	}
	free（tempstr）;
}
void count（char *_infocharchar *_codecharint _w[]）{
	int ij;
	for（i=0;i		for（j=0;j			if（_infochar[i]==_codechar[j]）_w[j]=_w[j]+1;//编码字符的对应权值加一
	//printf（“\n“）;for（i=0;i