//?HafuManCode.cpp?:?定義控制臺應用程序的入口點。
//

#include?“stdafx.h“



#include
#include
#include?
using?namespace?std;
#define?n?5??//葉子數目
#define?m?（2*n-1）????//結點總數
#define?maxval?10000.0
#define?maxsize?100???//哈夫曼編碼的最大位數
typedef?struct
{
	char?ch;
	int?weight;
	int?lchildrchildparent;
}hufmtree;
typedef?struct
{
	char?bits[n];???//位串
	int?start;??????//編碼在位串中的起始位置
	char?ch;????????//字符
}codetype;
void?huffman（hufmtree?tree[]）;//建立哈夫曼樹
void?huffmancode（codetype?code[]hufmtree?tree[]）;//根據哈夫曼樹求出哈夫曼編碼
void?encode（codetype?code[]char?string[]）;//電文編碼
void?decode（hufmtree?tree[]）;//依次讀入電文，根據哈夫曼樹譯碼
void?main（）
{
	printf（“????????????????????????????——哈夫曼編碼——\n“）;
	printf（“總共有%d個字符\n“n）;
	hufmtree?tree[m];
	codetype?code[n];
	int?ij;//循環變量
	huffman（tree）;//建立哈夫曼樹
	huffmancode（codetree）;//根據哈夫曼樹求出哈夫曼編碼
	printf（“【輸出每個字符的哈夫曼編碼】\n“）;
	for（i=0;i	{
		printf（“%c:?“code[i].ch）;
		for（j=code[i].start;j			printf（“%c?“code[i].bits[j]）;
		printf（“\n“）;
	}
	printf（“【讀入原文，并進行編碼】\n“）;
	char?string[maxsize];
	gets（string）;
	encode（codestring）;

	printf（“【讀入電文，并進行譯碼】\n“）;
	decode（tree）;//依次讀入電文，根據哈夫曼樹譯碼
	getchar（）;
}
void?huffman（hufmtree?tree[]）//建立哈夫曼樹
{
	int?ijp1p2;//p1p2分別記住每次合并時權值最小和次小的兩個根結點的下標
	int?small1small2f;
	char?c;
	for（i=0;i	{
		tree[i].parent=0;
		tree[i].lchild=-1;
		tree[i].rchild=-1;
		tree[i].weight=0;
	}
	printf（“【依次讀入前%d個結點的字符及權值（中間用空格隔開）】\n“n）;
	for（i=0;i	{
		printf（“輸入第%d個字符為和權值“i+1）;
		scanf（“%c?%d“&c&f）;
		getchar（）;
		tree[i].ch=c;
		tree[i].weight=f;
	}
	for（i=n;i	{
		p1=0;p2=0;
		small1=9999;small2=9999;???//maxval是float類型的最大值
		for（j=0;j			if（tree[j].parent==0）
				if（tree[j].weight				{
					small2=small1;??//改變最小權、次小權及對應的位置
					small1=tree[j].weight;
					p2=p1;
					p1=j;
				}
				else
					if（tree[j].weight					{
						small2=tree[j].weight;??//改變次小權及位置
						p2=j;
					}
					tree[p1].parent=i;
					tree[p2].parent=i;
					tree[i].lchild=p1;??//最小權根結點是新結點的左孩子
					tree[i].rchild=p2;??//次小權根結點是新結點的右孩子
					tree[i].weight=tree[p1].weight+tree[p2].weight;
	}
}//huffman
void?huffmancode（codetype?code[]hufmtree?tree[]）//根據哈夫曼樹求出哈夫曼編碼
	//codetype?code[]為求出的哈夫曼編碼
	//hufmtree?tree[]為已知的哈夫曼樹
{
	int?icp;
	codetype?cd;???//緩沖變量
	for（i=0;i	{
		cd.start=n;
		cd.ch=tree[i].ch;
		c=i;???????//從葉結點出發向上回溯
		p=tree[i].parent;???//tree[p]是tree[i]的雙親
		while（p!=0）
		{
			cd.start--;
			if（tree[p].lchild==c）
				cd.bits[cd.start]=‘0‘;???//tree[i]是左子樹，生成代碼‘0‘
			else
				cd.bits[cd.start]=‘1‘;???//tree[i]是右子樹，生成代碼‘1‘
			c=p;
			p=tree[p].parent;
		}
		code[i]=cd;????//第i+1個字符的編碼存入code[i]
	}
}//huffmancode
void?encode（codetype?code[]char?string[]）
{
	printf（“【輸出編碼結果】\n“）;
	int?length=strlen（string）;

	for（int?k=0;k	{
		f

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

?????文件???????4286??2015-11-01?16:39??HafuManCode.cpp

?????文件??????43740??2015-11-01?16:38??運行結果.png

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

????????????????48026????????????????????2