哈夫曼树与哈夫曼编码

代码及报告都有 [问题描述] 　　已知n个字符在原文中出现的频率，求它们的哈夫曼编码。 [基本要求] 　　1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法6.12） 　　2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。 对给定的待编码字符序列进行编码。 [选作内容] 　　１. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。 译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。 　4. 打印 Huffman树。 ［测试数据］ 利用教材P.148 例6－2中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为 “CFBABBFHGH”(也可自己设定数据进行测试)。

#include
#include 
typedef struct {
    int weight;
    int parentlchildrchild;
	char elem;
}HTNode*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表
////////////////////////求赫夫曼编码
void Select（HuffmanTree &HTint nint *s1int *s2）
{
   int i min;
   for（i=1;i<=n;i++）
   {
	if（HT[i].parent==0）
	{
		min=i;
		i=n+1;
	}
   }
   for（i=1;i<=n;i++）
   {
	if（HT[i].parent==0）
	{  if（HT[i].weight	    min=i;
	}
   }
	*s1=min;
   for（i=1; i<=n; i++）
   {
    if（HT[i].parent == 0 && i!=*s1）
	{
     min = i;
     i = n+1;
	}
   }
    for（i=1;i<=n;i++）
   {
	if（HT[i].parent==0&&i!=*s1）
	{   if（HT[i].weight	  min=i;
	}
	}
   *s2=min;
}
////////////////////
void Huffmantree（HuffmanTree &HTint*wint nchar *e）
{ //w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
	int mis1s2;
	if（n<=1） return;
	m=2*n-1;//总的结点
	HT=new HTNode[m+1];
	for（i=1;i<=n;++i）
	{/*1-n号放叶子结点，初始化*/
		HT[i].weight=w[i];
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].parent=0;
		HT[i].elem=e[i];
	}
	for（i=n+1;i<=m;++i） 
	{/*非叶子结点初始化*/
        HT[i].weight=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].parent=0;
		HT[i].elem=0;
	}
	    cout<<“HT的初态为：“<		cout<<“weight“<<“  “<<“parent“<<“  “<<“lchild“<<“  “<<“rchild“<	for（i=1;i<=m;i++）//打印空赫夫曼树
	{     
		cout<	}

	for（i=n+1;i<=m;++i）
	{//在HT[1……i]选择parent为0且weight最小的两个
        Select（HTi-1&s1&s2）;
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	 cout<<“HT的终态为：“<	 	cout<<“weight“<<“  “<<“parent“<<“  “<<“lchild“<<“  “<<“rchild“<	for（i=1;i<=m;i++）//打印赫夫曼树
	{ 
		cout<	}
}
////////////////////////////////////////////////////////
void CHuffmancode（HuffmanTree &HTHuffmanCode &HCint n）
{   

	char *cd;
    int cfstar;
	HC=new char*[n+1];
	cd=new char[n];
	cd[n-1]=‘\0‘;//编码结束符

		for（int i=1;i<=n;++i）
		{
			star=n-1; //从右向左逐位存放编码，首先存放编码结束符
	for（c=if=HT[i].parent;f!=0;c=ff=HT[f].parent）//从叶子到根结点求编码
				if（HT[f].lchild==c）
					cd[--star]=‘0‘; //左分支标0
				else 
					cd[--star]=‘1‘;//右分支标1
				HC[i]=new char[n-star]; //为第i个编码分配空间
				strcpy（HC[i]&cd[star]）;//从cd复制编码串到HC
		}
		delete cd;//释放工作空间
  for（i=1;i<=n;i++）
	   cout<}
////////////////////////////
void main（）
{
    HuffmanTree HT; 
    HuffmanCode HC; 
	int *w;//表示权值
	char *e;
	char c;
	int inmwei;
	cout<<“请输入赫夫曼树的叶子节点数目n：“;
	cin>>n;
	w=new int[n+1];//开辟n+1个数组空间
	e=new char[n+1];
	for（i=1;i<=n;i++）
	{
		cout<<“请输入第“<		cin>>c;
		e[i]=c;
		cout<<“请输入第“<		cin>>wei;
		w[i]=wei;

	}
   Huffmantree（HTwne）;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2012-05-07 16:32  实验四-hfm编码\
     文件        3367  2012-05-04 12:39  实验四-hfm编码\1.cpp
     目录           0  2012-05-07 16:27  实验四-hfm编码\Debug\
     文件       14133  2012-05-07 16:25  实验四-hfm编码\Debug\1.obj
     文件      213043  2012-05-07 16:25  实验四-hfm编码\Debug\hfm_5_4.exe
     文件      284328  2012-05-07 16:25  实验四-hfm编码\Debug\hfm_5_4.ilk
     文件      250296  2012-05-04 00:11  实验四-hfm编码\Debug\hfm_5_4.pch
     文件      533504  2012-05-04 12:39  实验四-hfm编码\Debug\hfm_5_4.pdb
     文件       41984  2012-05-07 16:25  实验四-hfm编码\Debug\vc60.idb
     文件       61440  2012-05-04 12:39  实验四-hfm编码\Debug\vc60.pdb
     文件        4290  2012-05-04 00:14  实验四-hfm编码\hfm_5_4.dsp
     文件         520  2012-05-04 00:11  实验四-hfm编码\hfm_5_4.dsw
     文件       41984  2012-05-07 16:26  实验四-hfm编码\hfm_5_4.ncb
     文件       48640  2012-05-07 16:26  实验四-hfm编码\hfm_5_4.opt
     文件         880  2012-05-07 16:25  实验四-hfm编码\hfm_5_4.plg
     文件      292864  2012-05-04 16:17  实验四-hfm编码\王宁实验四__哈夫曼树与哈夫曼编码.doc