#include<stdio.h>
#include<string.h>
#define N 50    //叶子结点数
#define M 2*N-1 //树中结点总数
#include<iostream>
using namespace std;
typedef struct
{
   char data[5];//结点值
   int weight;  //权重
   int parent;  //双亲结点
   int lchild;  //左孩子结点
   int rchild;  //右孩子节点
}HTNode;
typedef struct
{
	char cd[N]; //存放哈夫曼编码
	int start;  //ch[start..n]存放哈夫曼编码
}HCode;
void CreateHT(HTNode ht[],int n)   //由ht的叶子结点构造完整的哈夫曼编码
{
   int i,k,lnode,rnode;
   int min1,min2;                                //所有节点的相关域置初值-1
   for(i=0;i<2*n-1;i++)
	   ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
   for(i=n;i<2*n-1;i++)                          //构造哈夫曼树的分支结点
   {
     min1=min2=32767;                            //lnode和rnode为最小权重的两个结点位置          
	 lnode=rnode=-1;    
	 for(k=0;k<=i-1;k++)                         //查找最小和次小的结点
		 if(ht[k].parent==-1)                    //只在尚未构造二叉树的结点中查找
		 {if(ht[k].weight<min1)
		 {
		    min2=min1;rnode=lnode;
			min1=ht[k].weight;lnode=k;
		 }

		 else if(ht[k].weight<min2)
		 {
			 min2=ht[k].weight;
			 rnode=k;
		 }
         }
   ht[lnode].parent=i;ht[rnode].parent=i;
   ht[i].weight=ht[lnode].weight+ht[rnode].weight;
   ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)   //由哈夫曼树ht构造哈夫曼编码hcd
{ int i,f,c;
  HCode hc;
  for(i=0;i<n;i++)                                //根据哈夫曼树构造所有叶子结点的哈夫曼编码
  { hc.start=n;c=i;
    f=ht[i].parent;
	while(f!=-1)                                  //循环知道树根结点
	{ if(ht[f].lchild==c)                         //处理左孩子结点
	     hc.cd[hc.start--]='0';                  
	 else                                         //处理右孩子结点
		 hc.cd[hc.start--]='1';
	c=f;f=ht[f].parent;
	}
	hc.start++;                                   //start指向哈夫曼树最开始的字符
	hcd[i]=hc;
  }
}
void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码
{    int i,k; int m=0,j=0;
		int sum=0;
     cout<<"输出哈夫曼编码:"<<endl;
	 for(i=0;i<n;i++)
	{  j=0;
       printf("%s:/t",ht[i].data);
       cout<<ht[i].data<<endl;
	   for(k=hcd[i].start;k<=n;k++)
	   { 
	   printf("%c",hcd[i].cd[k]);
//	   cout<<hcd[i].cd[k]<<endl;
		
	     j++;
	   }
	   m+=ht[i].weight;
	   sum=sum+ht[i].weight*j;
	}
	printf("/n平均长度=%g/n",1.0*sum/m);
	cout<<"平均长度"<<1.0*sum/m<<endl;
}
int main() 
{
	 system("color 00a");
	 int n=15,i;
	 char *str[]={"The","of","a","to ","and","in","that","he","is","at","on","for","His","are","be" };
	 int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
	 HTNode ht[M];
	 HCode  hcd[N];
	 for(i=0;i<n;i++)
	 {
       strcpy(ht[i].data,str[i]);
	   ht[i].weight=fnum[i];
	 }
	 CreateHT(ht,n);       //创建哈夫曼树
	 CreateHCode(ht,hcd,n);//构造哈夫曼树
	 DispHCode(ht,hcd,n);  //输出哈夫曼树 
	 return 1;
}

这个是我去年的课程设计报告，因为有学弟要我就整理了下，功能很简单，就一个加密解密还有求哈夫曼编码，但足够满足老师的要求，现在传给有需要的童鞋参考~

完整的代码及报告

以下是实验报告内容

哈夫曼树的应用——对文件进行解码和译码

一、       需求分析说明

随着信息时代的到来，信息越来越多，如何压缩信息已经是重要课题。特别是多媒体技术的发展，使得信息量大的问题凸显。

哈夫曼编码(Huffman Coding)是一种无损压缩编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去 25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了 3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

当然本软件的目的不在于如何去压缩一个文件信息，而是通过建立哈夫曼树，由哈夫曼树编得二进制码，再译码，来了解哈夫曼树编码实现过程。(庞大的翻译内容会进行报错)

二、       主要功能

1.统计文件中各个字符出现的个数;                      

2.对文件进行处理得到哈夫曼树编码;                   

3.对文件进行加密;                        

4.对文件进行解码  

三、       所运用到的知识点

（1）链式存储结构（用来从文件中读取数据，构造哈夫曼编码）

（2）队列的应用（主要用在解码那一块，从文件中逐个读取字符，进入队列，再一个一个判断是否是哪个编码值）

（3）构造最优二叉树，对树的基本操作

（4）对文件的操作（打开文件，读写文件）

四、核心代码实现

（一）   菜单块

while (i != 0)
	{
		cout << "***********************欢迎使用译码器（解码器）**************************" << endl;
		cout << "                  1.统计文件中各个字符出现的个数;                        " << endl;
		cout << "                  2.对文件进行处理得到哈夫曼树编码;                      " << endl;
		cout << "                  3.对文件进行加密;                                      " << endl;
		cout << "                  4.对文件进行解码                                       " << endl;
		cout << "                  0.退出                                                 " << endl;
		switch (i)
		{
		case 1:
			List.creatlist();
			List.disp();
			List.total(); break;
		case 2:
			L.CreateHT();
			L.CreateHCode();
			L.DispHCode(); break;
		case 3:
			L.CreateHT();
			L.CreateHCode();
			L.Revertext(); break;
			/*	case 0:
			exit(0);*/
		case 4:   /*将二进制转化为字母*/
			L.CreateHT();
			L.CreateHCode();
			L.decode(); break;
		case 0:
			cout << "欢迎下次使用译码器（解码器）" << endl;
			break;
		}
		cout << "请输入您要进行的操作：";
		cin >> i;
		system("cls");
	}

（二）   统计字符

void total()                           //利用一个数组，统计字母出现次数
	{
		linklist *s;
		int j = 0;
		int count[127] = { 0 };             //设置初始化
		s = head->next;
		int num;
		while (s)
		{
			num = s->data;
			if (num != 32)               //不计算空格出现的频度
			{
				count[num - 0]++;
			}
			s = s->next;
		}
		cout << "统计" << endl;
		cout << "|---------------------------------------------|" << endl;
		cout << "|   字母              |               频度    |" << endl;
		for (int i = 0; i < 127; i++)
		{
			if (count[i])
			{
				aa[j].data = i;
				aa[j].weight = count[i];
				j++;
				cout << "|    " << char(i) << "                |            " << setw(6) << count[i] << "     |" << endl;
			}
		}
		Count = j;
		cout << "|---------------------------------------------|" << endl;
		cout << "出现的字母种类为：" << Count << "个" << endl;
		cout << endl;

	}
};

（三）   创建哈夫曼树

void HuffmanClass<T>::CreateHT()               //构造哈夫曼树
{
	int i, k, lnode, rnode;
	double min1, min2;
	for (i = 0; i < (2 * no - 1); i++)                    //所有结点的相关域置初值-1
	{
		ht[i].parent = -1;
		ht[i].lchild = -1;
		ht[i].rchild = -1;
	}
	for (i = no; i < (2 * no - 1); i++)                  //构造哈夫曼树，仅求非叶子结点
	{
		min1 = min2 = 32767.0;                          //初始时置最大权值
		lnode = rnode = -1;                             //lnode和rnode为两个权重最小的节点位置
		for (k = 0; k <= (i - 1); k++)                   //在ht数组中找权值最小的两个结点

		if (ht[k].parent == -1)                      //只在二叉树的根节点中寻找
		{
			if (ht[k].weight < min1)
			{
				min2 = min1;
				rnode = lnode;
				min1 = ht[k].weight;
				lnode = k;
			}
			else if (ht[k].weight < min2)
			{
				min2 = ht[k].weight;
				rnode = k;
			}
		}


		ht[lnode].parent = i;                   //把后面的no-1个非叶子结点处理完毕
		ht[rnode].parent = i;
		ht[i].weight = ht[lnode].weight + ht[rnode].weight;
		ht[i].lchild = lnode;                                 //ht[i]作为双亲结点
		ht[i].rchild = rnode;
	}
}

（四）   得到哈夫曼编码

void HuffmanClass<T>::CreateHCode()                       //根据哈夫曼树求哈夫曼编码
{
	int i, f, c;
	for (i = 0; i < no; i++)                            //遍历下标从0到no-1的叶子结点
	{
		hcd[i].start = no;                              //从hcd[i].cd[no]开始放置哈夫曼编码
		c = i;
		f = ht[i].parent;                               //找其双亲结点
		while (f != -1)                                 //循环直至无双亲结点即到达树根结点
		{
			if (ht[f].lchild == c)                       //当前结点是双亲结点的左孩子结点
			{
				hcd[i].cd[hcd[i].start] = '0';
				/*cout << hcd[i].cd[hcd[i].start]<<endl;*/
			}
			else
			{
				hcd[i].cd[hcd[i].start] = '1';
			}//当前结点是双亲结点的右孩子结点

			hcd[i].start--;
			c = f;
			f = ht[f].parent;                        //再对双亲进行同样的操作
		}
		hcd[i].start++;                   //start指向哈夫曼编码最开始字符
	}
}

（五）   对文件进行加密

void  HuffmanClass<T>::Revertext()
{
	SqQueueClass<char> L;
	L.initQueue();
	FILE *fin, *fout;
	char ch;
	if ((fin = fopen("D:\\test.txt", "r")) == NULL)
	{
		cout << "无法打开此文件" << endl;
		exit(0);
	}
	if ((fout = fopen("D:\\tex.txt", "w")) == NULL)
	{
		cout << "无法打开此文件" << endl;
		exit(0);
	}
	ch = fgetc(fin);//一个一个读出来
	while (!feof(fin))
	{
		for (int i = 0; i < no; i++)
		{
			if (ch == ht[i].data)
			{
				for (int j = hcd[i].start; j <= no; j++)
				{
					cout << hcd[i].cd[j];
					fputc(hcd[i].cd[j], fout);
				}
			}
		}
		ch = fgetc(fin);  //从fin 文件中打开,再次读
	}
	cout << endl << "文件已经读写完毕，这是显示器的输出效果" << endl;
	fclose(fin);
	fclose(fout);
}

（六）   对文件进行解码

void HuffmanClass<T>::decode()//解码
{
	cout << "文件解码为:" << endl;
	int mark = 0;//设置标志
	int q, j, ii, jj, k, tt;
	int kk = 0;
	char temp[MaxQueue][MaxQueue];
	char temp1[MaxQueue][MaxQueue];
	SqQueueClass<char> L;
	L.initQueue();
	FILE *fin;
	char ch;
	if ((fin = fopen("D:\\test1.txt", "r")) == NULL)
	{
		cout << "无法打开此文件" << endl;
		exit(0);
	}
	for (int aa = 0; aa < no; aa++)
	{
		for (int bb = hcd[aa].start; bb <= no; bb++)
		{
			temp1[aa][(bb - hcd[aa].start)] = hcd[aa].cd[bb];
			/*cout << temp1[aa][(bb - hcd[aa].start)] << " ";*/    /*保留*/
		}
	}
	ch = fgetc(fin);//一个一个读出来
	while (!feof(fin))
	{
		mark = 0;
		L.enQueue(ch);//进队

		for (j = 0, q = L.getfront() + 1; q != L.getrear() + 1; j++, q++)    //一个个获得临时的01(temp)序列，以便和哈夫曼编码比较
		{
			temp[kk][j] = L.data[q];
		}
		for (ii = 0; ii < no; ii++)//哈弗曼编码放到二维数组里了
		{
			int zz;
			zz = 0;
			for (jj = 0; jj <= no - hcd[ii].start; jj++)
			{
				if (temp[kk][jj] == temp1[ii][jj])//若两个相等
				{
					zz = zz + 1;
				}

			}
			if (zz == no - hcd[ii].start + 1)
			{
				cout << ht[ii].data;
				mark = 1; break;
			}

		}
		if (mark == 1)
		{
			L.destory();//清空队列
			/*cout << "清空" << endl;*/
		}
		ch = fgetc(fin);  //从fin 文件中打开,再次读
		kk = kk + 1;
	}
	if (L.getfront() != L.getrear())
	{
		cout << "\n以下二进制串输入有错误：";
		for (int j = L.getfront() + 1; j != L.getrear() + 1; j++)
			cout << L.data[j];
	}
	else
		cout << endl;
	cout << endl << "文件已经读写完毕，这是显示器的输出效果" << endl;
	fclose(fin);
}

五、       结果展示

菜单：

计算字符出现的频度：

得到哈夫曼编码：

加密：

解码：

六、       总结

做这个课程设计是熬了两个晚上做出来的，其中有一个如何解密，如何判断从文件读取的数据构成的数组与我的每一个哈夫曼编码值是否相等，因为哈夫曼编码的存储方式是存在数组，且从start元素到no元素才是正确的值，所以非常麻烦。我一直在不停地用循环判断，甚至要重新写我如何得到哈夫曼的编码，因为实在太困难了。索性，学到了一个好方法，就是中断，通过中断可以查看自己的程序走到哪一步了，再跟着步骤和本应该有的步骤进行对比，就很容易发现错误，这一次最大的收获就是学会熟练使用中断。还有可以用到之前学到的知识点，比如这里用了队列进行读取数据，以前从没有想过队列可以这样用。还有要集思广益，不一定去网上找代码就是不好的，因为适合别人的代码不一定适合自己，还是要自己写，主要是学习他们的思路，然后用自己的方法做出来。这个.cpp的功能其实还有缺陷，就是如果我对非常多的‘0’‘1’进行译码是会出现错误，我不知道是什么问题，不过会继续深入，另外还有一个可以提升的地方是对文件的操作应该是让用户自己选择文件而不是固定文件，不过，因为自己的代码太冗余，很难实现这个操作，不过会继续学习如何写出漂亮的代码。

完整的代码：

#include<iostream>
#include<fstream>
#include<iomanip>
#include<string>
using namespace std;
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
#define MaxQueue 100
struct linklist                                        //单链表结点类型
{
	char data;
	linklist *next;
};
struct pindu                                           //每个字母出现的频度结点类型
{
	char data;         //字母           
	int weight;        //权值
};
template <typename T>
struct HTNode                                          //哈夫曼结点类型
{
	T data;//结点值
	double weight;//权值
	int parent;//双亲结点
	int lchild;//左孩子结点
	int rchild;//右孩子结点
};

struct HCode                                           //哈夫曼编码类型
{
	char cd[MaxSize];              //存放当前结点的哈夫曼编码
	int start;                    //用cd[start..no]存放哈夫曼编码,包括start和no
};
class sqlist
{
private:
	linklist *head;
	int Count;                          //计算个数 
public:
	pindu aa[100];                      //存放频度的信息
	sqlist()
	{
		head = new linklist[100];
		head->next = NULL;
		Count = 0;
	}
	void destorysqlist()                     //删除单链表，不能用析构，因为随时不用，会对哈夫曼数的构造造成影响
	{
		linklist *pre, *p;
		pre = head;
		p = pre->next;
		while (p != NULL)
		{
			delete pre;
			pre = p; p = p->next;
		}
		delete pre;
	}
	int getCount()                       //得到权值个数
	{
		linklist *s;
		int j = 0;
		int count[127] = { 0 };             //设置初始化
		s = head->next;
		int num;
		while (s)
		{
			num = s->data;
			if (num != 32)               //不计算空格出现的频度
			{
				count[num - 0]++;
			}
			s = s->next;
		}
		for (int i = 0; i < 127; i++)
		{
			if (count[i])
			{
				aa[j].data = i;
				aa[j].weight = count[i];
				j++;
			}
		}
		Count = j;
		return Count;
	}
	void creatlist()                     //创建单链表，把文件中的字母写进单链表中
	{
		linklist *s, *r;
		r = head;
		FILE *fin;
		char ch;
		/*char filename[100] = { 0 };
		cout << "请输入文件路径：";
		cin >> filename;*/
		if ((fin = fopen("H:\\test.txt", "r")) == NULL)
		{
			cout << "无法打开此文件" << endl;
			exit(0);
		}
		ch = fgetc(fin);
		while (!feof(fin))
		{
			s = new linklist;
			s->data = ch;
			r->next = s;
			r = s;
			ch = fgetc(fin);  //从fin 文件中打开
		}
		r->next = NULL;
		fclose(fin);
		/*	cout << endl;
		cout << endl;*/
	}
	void disp()                                 //输出单链表内容，即文章内容
	{
		cout << endl << "文件内容打开如下" << endl;
		linklist *s;
		s = head->next;
		int count[257] = { 0 };
		while (s)
		{
			cout << s->data;
			s = s->next;
		}
		cout << endl;
	}
	void total()                           //利用一个数组，统计字母出现次数
	{
		linklist *s;
		int j = 0;
		int count[127] = { 0 };             //设置初始化
		s = head->next;
		int num;
		while (s)
		{
			num = s->data;
			if (num != 32)               //不计算空格出现的频度
			{
				count[num - 0]++;
			}
			s = s->next;
		}
		cout << "统计" << endl;
		cout << "|---------------------------------------------|" << endl;
		cout << "|   字母              |               频度    |" << endl;
		for (int i = 0; i < 127; i++)
		{
			if (count[i])
			{
				aa[j].data = i;
				aa[j].weight = count[i];
				j++;
				cout << "|    " << char(i) << "                |            " << setw(6) << count[i] << "     |" << endl;
			}
		}
		Count = j;
		cout << "|---------------------------------------------|" << endl;
		cout << "出现的字母种类为：" << Count << "个" << endl;
		cout << endl;

	}
};

template <typename T>
class SqQueueClass                                        //队列进行解码操作
{
private:
	int front;
	int rear;
public:
	T data[MaxQueue];
	void initQueue()//初始化
	{
		front = rear = 0;
	}
	void destory()//清空队列
	{
		initQueue();
	}
	void enQueue(T e)//进队
	{
		//if ((rear + 1) % MaxQueue == front)//队满
		//	return false;
		rear = (rear + 1) % MaxQueue;
		data[rear] = e;
	}
	void deQueue(T &e)//出队
	{
		/*if (rear == front)
		return false;*/
		front = (front + 1) % MaxQueue;
		e = data[front];
	}
	void disp()
	{
		for (int i = front + 1; i <= rear; i++)
		{
			cout << data[i] << " ";
		}
	}
	int getfront()
	{
		return front;
	}
	int getrear()
	{
		return rear;
	}
};

template <typename T>
class HuffmanClass
{
private:
	int no;                            //权值个数
	HTNode<T> ht[MaxSize];              //存放哈夫曼树
	HCode hcd[MaxSize];                 //存放哈夫曼编码
public:
	HuffmanClass();					            //Setvalue设置初值
	void CreateHT();                             //构造哈夫曼树
	void CreateHCode();                          //根据哈夫曼树求哈夫曼编码
	void DispHCode();                            //输出哈夫曼编码
	void Revertext();                            //将文本转化成二进制代码存入另一个文件中
	void decode();                                  //解码，把二进制转化成文字
};
template <typename T>
HuffmanClass<T>::HuffmanClass()                   //设置初值
{
	pindu str[100];
	sqlist List;//
	List.creatlist();//
	for (int i = 0; i < List.getCount(); i++)
	{
		str[i].data = List.aa[i].data;

		str[i].weight = List.aa[i].weight;
	}
	no = List.getCount();    //权值个数
	for (int i = 0; i <(2 * no - 1); i++)
	{
		ht[i].data = str[i].data;
		ht[i].weight = str[i].weight;
	}
}
template <typename T>

void HuffmanClass<T>::CreateHT()               //构造哈夫曼树
{
	int i, k, lnode, rnode;
	double min1, min2;
	for (i = 0; i < (2 * no - 1); i++)                    //所有结点的相关域置初值-1
	{
		ht[i].parent = -1;
		ht[i].lchild = -1;
		ht[i].rchild = -1;
	}
	for (i = no; i < (2 * no - 1); i++)                  //构造哈夫曼树，仅求非叶子结点
	{
		min1 = min2 = 32767.0;                          //初始时置最大权值
		lnode = rnode = -1;                             //lnode和rnode为两个权重最小的节点位置
		for (k = 0; k <= (i - 1); k++)                   //在ht数组中找权值最小的两个结点

		if (ht[k].parent == -1)                      //只在二叉树的根节点中寻找
		{
			if (ht[k].weight < min1)
			{
				min2 = min1;
				rnode = lnode;
				min1 = ht[k].weight;
				lnode = k;
			}
			else if (ht[k].weight < min2)
			{
				min2 = ht[k].weight;
				rnode = k;
			}
		}


		ht[lnode].parent = i;                   //把后面的no-1个非叶子结点处理完毕
		ht[rnode].parent = i;
		ht[i].weight = ht[lnode].weight + ht[rnode].weight;
		ht[i].lchild = lnode;                                 //ht[i]作为双亲结点
		ht[i].rchild = rnode;
	}
}
template <typename T>
void HuffmanClass<T>::CreateHCode()                       //根据哈夫曼树求哈夫曼编码
{
	int i, f, c;
	for (i = 0; i < no; i++)                            //遍历下标从0到no-1的叶子结点
	{
		hcd[i].start = no;                              //从hcd[i].cd[no]开始放置哈夫曼编码
		c = i;
		f = ht[i].parent;                               //找其双亲结点
		while (f != -1)                                 //循环直至无双亲结点即到达树根结点
		{
			if (ht[f].lchild == c)                       //当前结点是双亲结点的左孩子结点
			{
				hcd[i].cd[hcd[i].start] = '0';
				/*cout << hcd[i].cd[hcd[i].start]<<endl;*/
			}
			else
			{
				hcd[i].cd[hcd[i].start] = '1';
			}//当前结点是双亲结点的右孩子结点

			hcd[i].start--;
			c = f;
			f = ht[f].parent;                        //再对双亲进行同样的操作
		}
		hcd[i].start++;                   //start指向哈夫曼编码最开始字符
	}
}
template <typename T>
void HuffmanClass<T>::DispHCode()
{
	cout << "该文件哈夫曼编码如下" << endl;
	for (int i = 0; i < no; i++)
	{
		cout << ht[i].data << ":";
		for (int j = hcd[i].start; j <= no; j++)                 //因为start一直在变化，一直在减小，存的值是从下往上走的，就是start减小的顺序
		{
			cout << hcd[i].cd[j];
		}
		cout << endl;
	}
}


template <typename T>
void  HuffmanClass<T>::Revertext()
{
	SqQueueClass<char> L;
	L.initQueue();
	FILE *fin, *fout;
	char ch;
	if ((fin = fopen("H:\\test.txt", "r")) == NULL)
	{
		cout << "无法打开此文件" << endl;
		exit(0);
	}
	if ((fout = fopen("H:\\tex.txt", "w")) == NULL)
	{
		cout << "无法打开此文件" << endl;
		exit(0);
	}
	ch = fgetc(fin);//一个一个读出来
	while (!feof(fin))
	{
		for (int i = 0; i < no; i++)
		{
			if (ch == ht[i].data)
			{
				for (int j = hcd[i].start; j <= no; j++)
				{
					cout << hcd[i].cd[j];
					fputc(hcd[i].cd[j], fout);
				}
			}
		}
		ch = fgetc(fin);  //从fin 文件中打开,再次读
	}
	cout << endl << "文件已经读写完毕，这是显示器的输出效果" << endl;
	fclose(fin);
	fclose(fout);
}

template <typename T>
void HuffmanClass<T>::decode()//解码
{
	cout << "文件解码为:" << endl;
	int mark = 0;//设置标志
	int q, j, ii, jj, k, tt;
	int kk = 0;
	char temp[MaxQueue][MaxQueue];
	char temp1[MaxQueue][MaxQueue];
	SqQueueClass<char> L;
	L.initQueue();
	FILE *fin;
	char ch;
	if ((fin = fopen("H:\\test1.txt", "r")) == NULL)
	{
		cout << "无法打开此文件" << endl;
		exit(0);
	}
	for (int aa = 0; aa < no; aa++)
	{
		for (int bb = hcd[aa].start; bb <= no; bb++)
		{
			temp1[aa][(bb - hcd[aa].start)] = hcd[aa].cd[bb];
			/*cout << temp1[aa][(bb - hcd[aa].start)] << " ";*/    /*保留*/
		}
	}
	ch = fgetc(fin);//一个一个读出来
	while (!feof(fin))
	{
		mark = 0;
		L.enQueue(ch);//进队

		for (j = 0, q = L.getfront() + 1; q != L.getrear() + 1; j++, q++)    //一个个获得临时的01(temp)序列，以便和哈夫曼编码比较
		{
			temp[kk][j] = L.data[q];
		}
		for (ii = 0; ii < no; ii++)//哈弗曼编码放到二维数组里了
		{
			int zz;
			zz = 0;
			for (jj = 0; jj <= no - hcd[ii].start; jj++)
			{
				if (temp[kk][jj] == temp1[ii][jj])//若两个相等
				{
					zz = zz + 1;
				}

			}
			if (zz == no - hcd[ii].start + 1)
			{
				cout << ht[ii].data;
				mark = 1; break;
			}

		}
		if (mark == 1)
		{
			L.destory();//清空队列
			/*cout << "清空" << endl;*/
		}
		ch = fgetc(fin);  //从fin 文件中打开,再次读
		kk = kk + 1;
	}
	if (L.getfront() != L.getrear())
	{
		cout << "\n以下二进制串输入有错误：";
		for (int j = L.getfront() + 1; j != L.getrear() + 1; j++)
			cout << L.data[j];
	}
	else
		cout << endl;
	cout << endl << "文件已经读写完毕，这是显示器的输出效果" << endl;
	fclose(fin);
}


void menu()
{
	HuffmanClass <char>L;
	sqlist List;
	int i;
	cout << "***********************欢迎使用译码器（解码器）**************************" << endl;
	cout << "                  1.统计文件中各个字符出现的个数;                        " << endl;
	cout << "                  2.对文件进行处理得到哈夫曼树编码;                      " << endl;
	cout << "                  3.对文件进行加密;                                      " << endl;
	cout << "                  4.对文件进行解码                                       " << endl;
	cout << "                  0.退出                                                 " << endl;
	cout << "请输入您要进行的操作：";
	cin >> i;
	while (i != 0)
	{
		cout << "***********************欢迎使用译码器（解码器）**************************" << endl;
		cout << "                  1.统计文件中各个字符出现的个数;                        " << endl;
		cout << "                  2.对文件进行处理得到哈夫曼树编码;                      " << endl;
		cout << "                  3.对文件进行加密;                                      " << endl;
		cout << "                  4.对文件进行解码                                       " << endl;
		cout << "                  0.退出                                                 " << endl;
		switch (i)
		{
		case 1:
			List.creatlist();
			List.disp();
			List.total(); break;
		case 2:
			L.CreateHT();
			L.CreateHCode();
			L.DispHCode(); break;
		case 3:
			L.CreateHT();
			L.CreateHCode();
			L.Revertext(); break;
			/*	case 0:
			exit(0);*/
		case 4:   /*将二进制转化为字母*/
			L.CreateHT();
			L.CreateHCode();
			L.decode(); break;
		case 0:
			cout << "欢迎下次使用译码器（解码器）" << endl;
			break;
		}
		cout << "请输入您要进行的操作：";
		cin >> i;
		system("cls");
	}
}
int main()
{
	menu();
	system("pause");
	return 0;
}

代码注意事项：

计算哈夫曼树的WPL值     根据给定的n个权值（非负值），计算所构造哈夫曼树的WPL值。

基本要求：    

（1）根据给定的数据，建立哈夫曼树；      

（2）输出每个叶子结点的带权路径长度；      

（3）输出哈夫曼树的WPL值。

测试数据要求：         输入的n个权值之和应为100，且不允许有负值。  

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n 5 //5个英文小写字母（注意，该示例可扩展到所有可显示字符，可自行添加改写），此示例中字符串仅允许包含小写字母
//哈夫曼树相关
//节点定义，使用数组存储链表，指针使用位置索引
typedef struct {
	int weight;
	int parent, lchild, rchild;
}HTNode, *PHTNode, *HTree;
//编码表
typedef char **HCode;
//辅助操作，从1到k中选择两个权重最小的节点
void Select(HTree HT, int k, int &s1, int &s2)
{
	int min, smin; min = smin = 100000; 	
	for(int i = 1; i <= k; i++){
		if(HT[i].parent) continue; //如果已经安排了双亲节点
		if(HT[i].weight < min){
			s2 = s1; smin = min;
			s1 = i;  min = HT[i].weight;
		}
		else if(HT[i].weight < smin){
			s2 = i; smin = HT[i].weight;
		}
	}

	//使得s1小于s2，可使编码较规范，尽量以0结束
	int temp;
	if(s1 > s2){
		temp = s1; s1 = s2; s2 = temp;
	}
}

//根据权重数据构建Huffman树
void ConstructHuffmanTree(HTree &HT, int *w)
{
	int m = 2 * n - 1; //节点数目
	HT = (HTree)malloc((m+1) * sizeof(HTNode)); //分配空间，0号位置不使用
	//初始化各个节点
	int i, s1, s2;
	for(i = 1; i <= n; i++) { HT[i].weight = w[i]; HT[i].parent = HT[i].lchild = HT[i].rchild = 0; }
	for(; i <= m; i++) { HT[i].weight = HT[i].parent = HT[i].lchild = HT[i].rchild = 0; }

	//建立Huffman树
	for(i = n + 1; i <= m; i++){
		Select(HT, i - 1, s1, s2);
		HT[s1].parent = HT[s2].parent = i;
		HT[i].lchild = s1; HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}
//从Huffman树获取编码表
//从根到叶子（递归）,cd保存获取的编码记录
void GetCodeTable(HTree HT, HCode HC, int p, char *cd, int cdlen)
{
	//如果已经到达叶子节点，登记编码
	if(p <= n){
		HC[p] = (char *)malloc((cdlen + 1) * sizeof(char));
		cd[cdlen] = '\0'; strcpy(HC[p], cd);		
	}	
	
	if(HT[p].lchild){ cd[cdlen] = '0'; GetCodeTable(HT, HC, HT[p].lchild, cd, cdlen + 1); } //向左子树前进	
	if(HT[p].rchild){ cd[cdlen] = '1'; GetCodeTable(HT, HC, HT[p].rchild, cd, cdlen + 1);} //向右子树前进	
}
//从叶子到根，教程算法
void GetCodeTable1(HTree HT, HCode &HC)
{
	HC = (HCode)malloc((n+1)*sizeof(char *));
	char *cd = (char *)malloc(n * sizeof(char));
	cd[n -1] = '\0';
	int start, c, f;
	for(int i = 1; i <= n; i++){
		start = n - 1;
		for(c = i, f = HT[i].parent; f; c = f, f = HT[f].parent){
			if(c == HT[f].lchild) cd[--start] = '0';
			else cd[--start] = '1';
		}
		HC[i] = (char *)malloc((n - start) * sizeof(char));
		strcpy(HC[i], cd + start);
	}
	free(cd);
}
 
//从根到叶子（非递归），教程算法，这是模拟递归栈的一种典型方法，需注意
void GetCodeTable2(HTree HT, HCode &HC)
{
	HC = (HCode)malloc((n+1) * sizeof(char *));
	char *cd = (char *)malloc(n * sizeof(char));
	int m = 2 * n - 1, p = m, cdlen = 0;
	//借用weight做左右子树是否已经遍历的标志，注意会破坏原来的weight数据
	for(int i = 1; i <= m; i++) HT[i].weight = 0;
	while(p){
		//左右子树均未访问，访问左子树
		if(HT[p].weight == 0){ 
			HT[p].weight = 1; //设置标志左子树已经访问

			//如果仍未到达叶子节点，继续向下层进发，同时记录编码
			if(HT[p].lchild) { p = HT[p].lchild; cd[cdlen++] = '0'; continue;}

			//否则如果是叶子节点的话登记字符编码（其实在右子树那边检查也可以），否则会继续遍历右子树
			if(!HT[p].rchild){
				HC[p] = (char *)malloc((cdlen + 1) * sizeof(char));
				cd[cdlen] = '\0'; strcpy(HC[p], cd);
			}
			continue;
		}

		//如果左子树已经访问过而右子树没有访问过
		if(HT[p].weight == 1){
			HT[p].weight = 2; //设置左右子树均已经访问过标志
			//如果右子树不为空，继续向下层进发，同时记录编码
			if(HT[p].rchild) { p = HT[p].rchild; cd[cdlen++] = '1'; continue;}	

			//其实在右子树这边登记也可以
			/*else if(!HT[p].lchild){
				HC[p] = (char *)malloc((cdlen + 1) * sizeof(char));
				cd[cdlen] = '\0'; strcpy(HC[p], cd);
			}*/

			continue;
		}

		//如果左右两个子树都已经访问过了，退回到双亲节点（同时重置访问标志，字符记录位置也前移）
		HT[p].weight = 0; --cdlen; p = HT[p].parent;		
	}
}


//输出码表
void PrintCodeTable(HCode HC)
{
	printf("\nThe Code Table:\n");
	for(int i = 1; i <= n; i++){
		printf("路径长度：%d    %c : %s\n",strlen(HC[i]), 'a' + i - 1, HC[i]);
	}
}

//使用码表对字符串编码
void Encode(HCode HC, char *str, char **code)
{
	*code = (char *)malloc(sizeof(char) * 1024); (*code)[0] = '\0';
	int pos = 0; //pos为字符串指针
	while(str[pos]){
		strcat(*code, HC[str[pos++] - 'a' + 1]);
	}
}
//对哈夫曼树进行计算WPL 
int WPL(HCode HC,int w[]){
	int sum=0;
	//int w[] = { 10,30,20,5,35}; 
	for(int i = 1; i <= n; i++)
		sum=sum+strlen(HC[i])*w[i];
	return sum;
}


int main()
{
	//5个英文字符的权重（频率统计）
	int w[] = { 0,5,20,25,5,45}; 
	HTree HT;
	ConstructHuffmanTree(HT, w); //构建Huffman树
	//从树中获取编码表
	HCode HC = (HCode)malloc((n+1) * sizeof(char *));
	char *cd = (char *)malloc(n * sizeof(char));
	int cdlen = 0;
	GetCodeTable(HT, HC, 2 * n - 1, cd, cdlen);		
	PrintCodeTable(HC); //输出编码表
	printf("WPL:%d\n",WPL(HC,w));
	return 0;
}