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

#include?“stdafx.h“

//哈夫曼編碼壓縮解壓縮程序.cpp?
#include??
#include??
#include??
#include?

struct?head?
{
????unsigned?char?b;????????//記錄字符在數(shù)組中的位置
????long?count;?????????????//字符出現(xiàn)頻率（權(quán)值）?
????long?parentlchrch;????//定義哈夫曼樹(shù)指針變量
????char?bits[256];?????????//定義存儲(chǔ)哈夫曼編碼的數(shù)組
}?
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請(qǐng)您輸入需要壓縮的文件：“）;?
????gets（filename）;?
????ifp=fopen（filename“rb“）;?
????if（ifp==NULL）?
	{
	???printf（“\n\t文件打開(kāi)失敗!\n\n“）;?
			return;?
	}
	printf（“\t請(qǐng)您輸入壓縮后的文件名：“）;?
????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++;????//字符重復(fù)出現(xiàn)頻率+1
	???flength++;????????????//字符出現(xiàn)原文件長(zhǎng)度+1
	}
	flength--;?
????length1=flength;??????????//原文件長(zhǎng)度用作求壓縮率的分母
????header[c].count--;?
????for（i=0;i<512;i++）?
	{
	???if（header[i].count!=0）?header[i].b=（unsigned?char）i;?
	???/*將每個(gè)哈夫曼碼值及其對(duì)應(yīng)的ASCII碼存放在一維數(shù)組header[i]中，
			??且編碼表中的下標(biāo)和ASCII碼滿(mǎn)足順序存放關(guān)系*/
			else?header[i].b=0;?
			header[i].parent=-1;header[i].lch=header[i].rch=-1;????//對(duì)結(jié)點(diǎn)進(jìn)行初始化
	}?
????for（i=0;i<256;i++）????//根據(jù)頻率（權(quán)值）大小，對(duì)結(jié)點(diǎn)進(jìn)行排序，選擇較小的結(jié)點(diǎn)進(jìn)樹(shù)
	{
	???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;???????//外部葉子結(jié)點(diǎn)數(shù)為n個(gè)時(shí)，內(nèi)部結(jié)點(diǎn)數(shù)為n-1，整個(gè)哈夫曼樹(shù)的需要的結(jié)點(diǎn)數(shù)為2*n-1.
????m=2*n-1;
????for（i=n;i	{
		min1=999999999;???//預(yù)設(shè)的最大權(quán)值，即結(jié)點(diǎn)出現(xiàn)的最大次數(shù)
????????for（j=0;j		{
			if（header[j].parent!=-1）?continue;????
			//parent!=-1說(shuō)明該結(jié)點(diǎn)已存在哈夫曼樹(shù)中，跳出循環(huán)重新選擇新結(jié)點(diǎn)*/
			if（min1>header[j].count）?
			{
				pt1=j;?
				min1=header[j].count;?
				continue;?
			}?
		}
		header[i].count=header[pt1].count;?
????????header[pt1].parent=i;???//依據(jù)parent域值（結(jié)點(diǎn)層數(shù)）確定樹(shù)中結(jié)點(diǎn)之間的關(guān)系
????????header[i].lch=pt1;???//計(jì)算左分支權(quán)值大小
????????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;???//計(jì)算右分支權(quán)值大小
????????header[pt1].parent=i;?
	}
	for（i=0;i	{
		f=i;?
		header[i].bits[0]=0;???//根結(jié)點(diǎn)編碼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）;
			?//依次存儲(chǔ)連接“0”“1”編碼
				header[i].bits[0]=‘0‘;?
			}
			else???//置右分支編碼1
			{
				j=strlen（header[i].bits）;?
				memmove（

?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----

?????文件???????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