哈夫曼编/译码系统的简单设计与实现

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。该代码设计一个哈夫曼编译码系统： （1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； （2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中； （3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中； （4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；

#include
#include
#include
const int maxn=100;

typedef struct Node{
	int weight;//权值
	int parent;//父节点的序号，为0表示根节点
	int lchildrchild;//左右孩子节点的序号，为0的是叶子节点
}HTNode*HuffmanTree;//用来存储每个叶子节点的霍夫曼编码

char HC[maxn][maxn+5];//用来存储每个节点的霍夫曼编码

struct Ans{
	char ch;
	int wet;
}ans[maxn];

//从HT数组的前k个元素中选出weight最小且parent为0的元素，并将该元素的下标返回
int min（HuffmanTree HTint k）
{
	int i=0;
	int min;//用来存放weight最小且parent为0的元素的下标
	int min_weight;//用来存放weight最小且parent为0的元素的weight值的temp

	//注意应先将第一个parent为0的元素的weight值赋给min_weight留作以后比较用
	//不要直接将HT[0].weight赋给min_weight了（这是个常用的技巧）
	while（HT[i].parent!=0） i++;
	min_weight=HT[i].weight;
	min=i;

	//选出weight最小且parent为0的元素，并将其序号赋给min
	for（;i		if（HT[i].weight			min_weight=HT[i].weight;
			min=i;
		}
	}

	//注意，选出weight最小的元素后，将其parent置1，使得下一次求第二小时将其排除在外
	HT[min].parent=1;
	return min;//返回下标
}

void select_min（HuffmanTree HTint kint &min1int &min2）//&为引用
{
	min1=min（HTk）;
	min2=min（HTk）;
}

HuffmanTree create_HuffmanTree（struct Ans *pint n）
{
	//一颗有n个叶子节点的霍夫曼树共有2n-1个节点（特点）
	int total=2*n-1;
	HuffmanTree HT=（HuffmanTree）malloc（total*sizeof（HTNode））;
	if（!HT）{
		printf（“HuffmanTree malloc failed!\n“）;
	}

	int i;
	for（i=0;i		HT[i].parent=0;//parent后面会改变
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].weight=p->wet;
		p++;
	}

	//HT[n]HT[n+1]...HT[2n-2]中存放的是中间构造出的每棵二叉树的根节点
	for（;i		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].weight=0;
	}

	int min1min2;//用来保存每一轮选出的两个weight最小且parent为0的节点下标


	//每一轮比较后选择出min1和min2构成一课二叉树最后构成一棵赫夫曼树
	for（i=n;i		select_min（HTimin1min2）;//寻找i之前的结点
		HT[min1].parent=i;
		HT[min2].parent=i;//两个最小权值的结点构成子树

		//注意这里左孩子和右孩子可以反过来，构成的也是一棵赫夫曼树，只是所得的编码不同
		HT[i].lchild=min1;
		HT[i].rchild=min2;
		HT[i].weight=HT[min1].weight+HT[min2].weight;
	}
	return HT;
}

void HuffmanCoding（HuffmanTree HTint n）
{
	char temp[maxn+5];//临时空间，用来保存每次求得的一个赫夫曼编码串
	temp[maxn]=‘\0‘;//编码结束符，亦是字符数组的结束标志

	//下面求每个字符的赫夫曼编码
	for（int i=0;i		int current=i;//定义当前访问的结点
		int fa=HT[i].parent;//定义当前节点的父节点
		int start=maxn;//每次编码的位置，初始为编码结束符的位置
		//从叶子节点遍历赫夫曼树直到根节点
		while（fa!=0）
		{
			if（HT[fa].lchild==current）
				temp[--start]=‘0‘;
			else temp[--start]=‘1‘;
			current=fa;
			fa=HT[current].parent;
		}
		strcpy（HC[i]temp+start）;//将编码串从最后的start编码~\0复制到HC上
	}
}

int n;//需要编码的字符数
void Initialzation（）
{
	FILE *fp1;
	fp1=fopen（“DataFile.txt““rb“）;
	printf（“从文件DataFile.txt中读取编码的字符种类个数\n“）;
	fscanf（fp1“%d“&n）;

	printf（“以及这%d个字符及其权值（整型）\n“n）;
	for（int i=0;i		fscanf（fp1“ %c %d“&ans[i].ch&ans[i].wet）;//注意%c前面有空格
	}
	HuffmanTree HT=create_HuffmanTree（ansn）;//用数组生成霍夫曼树
	HuffmanCoding（HTn）;//求解每个字符的霍夫曼编码

	printf（“各字符对应权值的霍夫曼编码为（按照输入顺序）:\n“）;
	for（int i=0;i		printf（“%c :“ans[i].ch）;
		puts（HC[i]）;
	}
	fclose（fp1）;
	print

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        551  2017-06-21 15:56  项目四\Code.txt

     文件        551  2017-06-21 14:28  项目四\CodeFile.txt

     文件        124  2017-06-21 14:01  项目四\DataFile.txt

     文件        150  2017-06-21 15:56  项目四\Textfile.txt

     文件        150  2017-06-21 13:59  项目四\ToBeTran.txt

     文件       7030  2017-06-21 15:56  项目四\4.cpp

     文件       5647  2017-06-21 15:56  项目四\4.o

     文件      34210  2017-06-21 15:56  项目四\4.exe

     目录          0  2017-06-21 15:53  项目四

----------- ---------  ---------- -----  ----

                48413                    9