//?huffman.cpp?:?Defines?the?entry?point?for?the?console?application.
//

#include?“stdafx.h“

//哈夫曼編碼壓縮解壓縮程序.cpp?
#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（

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????4548??2010-01-11?23:03??huffman\huffman.dsp

?????文件????????522??2010-01-11?23:03??huffman\huffman.dsw

?????文件??????50176??2009-04-13?19:39??huffman\huffman.ncb

?????文件????????248??2009-04-13?19:38??huffman\huffman.plg

?????文件???????1214??2010-01-11?23:03??huffman\ReadMe.txt

?????文件????????294??2010-01-11?23:03??huffman\StdAfx.cpp

?????文件????????667??2010-01-11?23:03??huffman\StdAfx.h

?????文件?????200749??2010-01-13?18:04??huffman\Debug\huffman.exe

?????文件?????252500??2010-01-13?18:04??huffman\Debug\huffman.ilk

?????文件?????186996??2010-01-11?23:04??huffman\Debug\huffman.pch

?????文件?????549888??2010-01-13?18:04??huffman\Debug\huffman.pdb

?????文件???????1600??2010-01-11?23:04??huffman\Debug\StdAfx.obj

?????文件??????41984??2009-04-13?19:38??huffman\Debug\vc60.idb

?????文件??????86016??2010-01-13?18:04??huffman\Debug\vc60.pdb

?????文件??????20086??2010-01-13?18:04??huffman\Debug\huffman.obj

?????目錄??????????0??2010-01-11?23:17??huffman\Debug

?????文件?????103771??2010-01-12?20:01??huffman\11.hub

?????文件???????9960??2010-01-12?21:02??huffman\huffman.cpp

?????文件??????48640??2009-04-13?19:39??huffman\huffman.opt

?????目錄??????????0??2010-01-12?10:28??huffman

-----------?---------??----------?-----??----

??????????????1559859????????????????????20