//用哈夫曼壓縮文件（C語言）
//利用哈夫曼編碼制作壓縮軟件，內容如下：
#include??
#include??
#include??
#include?

struct?head?
{
	unsigned?char?b;????????//記錄字符在數組中的位置
	long?count;?????????????//字符出現頻率（權值）?
	long?parentlchrch;????//定義哈夫曼樹指針變量
	char?bits[256];?????????//定義存儲哈夫曼編碼的數組
}?
header[512]tmp;

/*壓縮*/
void?compress（）?
{
	char?filename[255]outputfile[255]buf[512];?
	unsigned?char?c;?
	long?ijmnf;?
	long?min1pt1flengthlength1length2;?
	double?div;
	FILE?*ifp*ofp;

	printf（“\t請您輸入需要壓縮的文件：“）;?
	gets（filename）;?
	ifp=fopen（filename“rb“）;?
	if（ifp==NULL）?
	{
		printf（“\n\t文件打開失敗!\n\n“）;?
		return;?
	}
	printf（“\t請您輸入壓縮后的文件名：“）;?
	gets（outputfile）;?
	ofp=fopen（strcat（outputfile“.hub“）“wb“）;?
	if（ofp==NULL）?
	{
		printf（“\n\t壓縮文件失敗!\n\n“）;?
		return;?
	}
	flength=0;?
	while（!feof（ifp））?
	{
		fread（&c11ifp）;?
		header[c].count++;????//字符重復出現頻率+1
		flength++;????????????//字符出現原文件長度+1
	}
	flength--;?
	length1=flength;??????????//原文件長度用作求壓縮率的分母
	header[c].count--;?
	for（i=0;i<512;i++）?
	{
		if（header[i].count!=0）?header[i].b=（unsigned?char）i;?
		/*將每個哈夫曼碼值及其對應的ASCII碼存放在一維數組header[i]中，
		且編碼表中的下標和ASCII碼滿足順序存放關系*/
		else?header[i].b=0;?
		header[i].parent=-1;header[i].lch=header[i].rch=-1;????//對結點進行初始化
	}?
	for（i=0;i<256;i++）????//根據頻率（權值）大小，對結點進行排序，選擇較小的結點進樹
	{
		for（j=i+1;j<256;j++）
		{
			if（header[i].count			{
				tmp=header[i];
				header[i]=header[j];?
				header[j]=tmp;?
			}?
		}?
	}
	for（i=0;i<256;i++）?if（header[i].count==0）?break;?
	n=i;???????//外部葉子結點數為n個時，內部結點數為n-1，整個哈夫曼樹的需要的結點數為2*n-1.
	m=2*n-1;
	for（i=n;i	{
		min1=999999999;???//預設的最大權值，即結點出現的最大次數
		for（j=0;j		{
			if（header[j].parent!=-1）?continue;????
			//parent!=-1說明該結點已存在哈夫曼樹中，跳出循環重新選擇新結點*/
			if（min1>header[j].count）?
			{
				pt1=j;?
				min1=header[j].count;?
				continue;?
			}?
		}
		header[i].count=header[pt1].count;?
		header[pt1].parent=i;???//依據parent域值（結點層數）確定樹中結點之間的關系
		header[i].lch=pt1;???//計算左分支權值大小
		min1=999999999;???
		for（j=0;j		{
			if（header[j].parent!=-1）?continue;?
			if（min1>header[j].count）?
			{
				pt1=j;?
				min1=header[j].count;?
				continue;?
			}?
		}
		header[i].count+=header[pt1].count;?
		header[i].rch=pt1;???//計算右分支權值大小
		header[pt1].parent=i;?
	}
	for（i=0;i	{
		f=i;?
		header[i].bits[0]=0;???//根結點編碼0???
		while（header[f].parent!=-1）?
		{
			j=f;?
			f=header[f].parent;?
			if（header[f].lch==j）???//置左分支編碼0
			{
				j=strlen（header[i].bits）;?
				memmove（header[i].bits+1header[i].bitsj+1）;
				//依次存儲連接“0”“1”編碼
				header[i].bits[0]=‘0‘;?
			}
			else???//置右分支編碼1
			{
				j=strlen（header[i].bits）;?
				memmove（header[i].bits+1header[i].bitsj+1）;?
				header[i].bits[0]=‘1‘;?
			}?
		}?
	}
	fseek（ifp0SEEK_SET）;???//從文件開始位置向前移動0字節，即定位到文件開始位置
	fwrite（&flengthsizeof（int）1ofp）;
	/*用來將數據寫入文件流中，參數flength指向欲寫入的數據地址，
	總

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2017-05-11?17:08??Huffman實現文件壓縮與解壓\
?????文件????????9437??2017-04-21?18:28??Huffman實現文件壓縮與解壓\Huffman.cpp
?????文件????????9134??2010-11-02?22:10??Huffman實現文件壓縮與解壓\I?have?a?dream.txt
?????文件???????66616??2005-11-09?20:04??Huffman實現文件壓縮與解壓\lena.bmp