**
 
哈夫曼树（编码及译码）
 
**
 初学数据结构哈夫曼树（小菜鸟），借用了一些经典教材案例，编译软件为vs2013，有问题能指点，当然不喜勿喷哦，谢谢大家。
 此程序是利用哈夫曼树实现对文本文件的加密与解密，程序所能达到的内容：使用从文件中读取显示原文本文件、使用哈夫曼树编码对文本文件进行加密、使用哈夫曼表显示字符编码、显示加密文件、使用哈夫曼树译码文本文件解密、显示解密文件、这些程序执行完以后，退出系统。主要包含以下内容：
 1.输入文件所存在的位置；
 2.进入主菜单界面，显示所有可操作的选项；
 3.显示jiemi.txt文件的内容；
 4.对文件进行加密，将其与字符转换为二进制编码；
 5.对文件进行解密，将二进制编码写入；
 6.从文件中读取二进制编码转换为字符，再写入文件；
 7.退出系统。
 原文件内容：
 
构建哈夫曼树
 
从文件中读入字符个数，判定权值最大值，因为了方便给构建哈夫曼树，每个节点的权值相差为1，也就是{1 2 3 4 5 ……n}第一步先取两个最小权值作为左右子树构造一个新树，取1，2构成新树，其结点为1+2=3 虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，再根据第二步，取最小的两个权值构成新树，再不断重复步骤建立哈夫曼树。
 
void Great(hufmantree &ht, int n)//n为从文件中读入字符的个数
{
	int m, S1, i, S2;
	m = 2 * n - 1;
	for (i = n + 1; i <= m; ++i)
	{

		select(ht, i - 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;
}
 
实现哈夫曼编码
 
void HuffmanCode(hufmantree ht, int n, huffmancode &hc)
{
	char *cd;
	int strat;
	hc = new char*[n + 1];
	cd = new char[n];
	cd[n - 1] = '\0';//最后一个给‘\0’
	int c, i, f;
	for (i = 1; i <= n; ++i)
	{
		strat = n - 1;//确定最后一个
		c = i;
		f = ht[i].parent;//f—>第i个的节点的双亲
		while (f != 0)
		{
			--strat;//cd倒数第二个空
			if (ht[f].lchild == c)//看看左边有没有孩子
				cd[strat] = '0';
			else cd[strat] = '1';//右边有没有孩子
			c = f; f = ht[f].parent;//回到双亲，f->i的双亲


		}
		hc[i] = new char[n - strat];
		strcpy_s(hc[i], strlen(cd) + 1, &cd[strat]);
	}

//	delete cd;
}
 
实现哈夫曼译码
 
void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100])
{
	cout << endl;
	int d, i = 1, j;
	char *cd;
	d = n * 2 - 1;
	cd = new char[n];
	char c;
	for (i = 1; i <= n; i++)
	{
		strcpy_s(cd, strlen(hc[i]) + 1, hc[i]);//从hc里把编码调过来
	for (j = 0; j <strlen(cd); j++)
		{
			c = cd[j];
			if (c == '0')
			{
				d = ht[d].lchild;/如果是0往走孩子走

			}
			if (c == '1')
			{

				d = ht[d].rchild;//如果是1往右孩子走
			}
		}
	cout << ht[d].weight << "   " << ht[d].zifu<<endl;
		d = n * 2 - 1;
	}
	delete cd;
	//往文件里写入编译好的字符
	char bf[100];
for (i = 0; i < n;i++)
	bf[i] = '\0';
	FILE *fp = fopen(b, "w+");
	for (i = 1; i <= n; i++)
	if (ht[i].zifu != '\0')
	{
		bf[i - 1] = ht[i].zifu;
		fprintf_s(fp,"%c", bf[i-1]);
		}
	
	fclose(fp);
}
 
**
 
完整代码
 
**
 
#include <iostream>
#include <string>
using namespace std;
typedef char elemtype;
typedef int status;
typedef char **huffmancode;
typedef struct
{
	char zifu;
	status weight;
	status parent, lchild, rchild;
}hufman, *hufmantree;
void Great(hufmantree &ht, int n);
status  chushihua(hufmantree &ht, char a[100],int n);
status select(hufmantree ht, int m, int &S1, int &S2);
void HuffmanCode(hufmantree ht, int n, huffmancode &hc);
void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100]);

void Zifubianma(huffmancode hc, int n, char a[]);
status wenben(char a[]);
void jiemi(hufmantree ht,  int n);
void Menu();
status duxu(char a[],char b[100]);
void xianshi(huffmancode hc, int n, char b[100]);
	int main()
{
		hufmantree ht;
		huffmancode hc;
		char a[100];
		char b[100];
		int  n;
	    n=duxu(a,b);
	    chushihua(ht, a,n);
		Great(ht, n);
		while (1)
		{
			Menu();
			printf("输入要做的操作：（1-7）：  \n");
			int x;
			cin >> x;
			switch (x)
			{
			case 1:wenben(a); break;
			case 2: HuffmanCode(ht, n, hc); system("pause"); break;
			case 3:Zifubianma(hc, n,a); system("pause"); break;
			case 4:xianshi(hc,n,b);system("pause");break; 
			case 5: jiemi(ht,  n); system("pause"); break;
			case 6:HuffmanCoding(ht, n, hc,b); system("pause"); break;
			case 7:
			case 0:exit(0);

			}
			system("cls");
		}

		return 0;
	}
	

void Menu()
{
	printf_s("\n\t\t         ---------------------超级文件加密系统-------------------\n");
	printf_s("\n\t\t\t ψ卍ψ                   0.退出                    ψ卍ψ\n");
	printf_s("\n\t\t\t ψ卍ψ                   1.显示原文本文件          ψ卍ψ\n");
	printf_s(" \n\t\t\t ψ卍ψ                   2.文本文件加密            ψ卍ψ    \n");
	printf_s(" \n\t\t\t ψ卍ψ                   3.显示字符编码            ψ卍ψ\n");
	printf_s(" \n\t\t\t ψ卍ψ                   4.显示加密文件            ψ卍ψ \n");
	printf_s("\n\t\t\t ψ卍ψ                   5.文本文件解密            ψ卍ψ \n ");
	printf_s(" \n\t\t\t ψ卍ψ                   6.显示解密文件            ψ卍ψ \n");
	printf_s(" \n\t\t\t ψ卍ψ                   7.退出系统                ψ卍ψ \n");
	printf_s("\n\t\t         --------------------------------------------------------\n");
}
status wenben(char a[])
{
	int i;
	for (i = 0; i <= strlen(a) - 1; i++)
cout << a[i];
	system("pause");
	return 0;

}
status duxu(char a[],char b[100])
{
	
	cout << "输入文件所在位置"<<endl;
	gets(b);
	FILE *fp = fopen(b, "r");
	int i=100;
fgets(a,i, fp);

	fclose(fp);
	i = 0; 
	while (a[i] !='\0')
	{
		i++;
	}
	
	return i;
}
status  chushihua(hufmantree &ht,char a[100],int n)
{
	int  i, m;
	//cin >> n;/*输入结点1--n之间的节点*/
	m = 2 * n - 1;/*m用于开辟两倍的ht的空间*/
	ht = new hufman[m + 1];/*同上*/
	for (i = 1; i <= m; i++)
	{
		ht[i].parent = 0; ht[i].lchild = 0; ht[i].rchild = 0;
		ht[i].zifu = '0';
	}

	for (i = 1; i <= n; i++)
	{
			
		 ht[i].weight=i;/*输入前几个节点的权值课本p138*/	
		ht[i].zifu = a[i-1];
	}

	return n;
}
void Great(hufmantree &ht, int n)
{
	int m, S1, i, S2;
	m = 2 * n - 1;
	for (i = n + 1; i <= m; ++i)
	{
		
		select(ht, i - 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;

	}
	

}status select(hufmantree ht, int m, int &S1, int &S2)
{
	int j;
	for (j = 1; j <= m; j++)
	{
		if (ht[j].parent == 0)
		{
			S1 = j;
			break;
		}
	}
	for (j = 1; j <= m; j++)
	{
		if (ht[j].parent == 0 && j != S1)
		{
			S2 = j;
			break;
		}
	}
	for (j = 1; j <= m; j++)
	{



		if (ht[j].parent == 0 && ht[j].weight < ht[S1].weight)
		{
			S1 = j;
	
		}

	}
	for (j = 1; j <= m; j++)
	{

		if (ht[j].parent == 0 && j != S1&&ht[j].weight < ht[S2].weight)//双亲为0j不等于上
		{
			S2 = j;
			}


	}
	return 0;
}


void HuffmanCode(hufmantree ht, int n, huffmancode &hc)
{
	char *cd;
	int strat;
	hc = new char*[n + 1];
	cd = new char[n];
	cd[n - 1] = '\0';//最后一个给o
	int c, i, f;
	for (i = 1; i <= n; ++i)
	{
		strat = n - 1;//确定最后一个
		c = i;
		f = ht[i].parent;//f—>第i个的节点的双亲
		while (f != 0)
		{
			--strat;//cd倒数第二个空
			if (ht[f].lchild == c)//看看左边有没有孩子
				cd[strat] = '0';
			else cd[strat] = '1';//右边有没有孩子
			c = f; f = ht[f].parent;//回到双亲，f->i的双亲


		}
		hc[i] = new char[n - strat];
		strcpy_s(hc[i], strlen(cd) + 1, &cd[strat]);
	}
	cout << "文本文件加密成功！";
//	delete cd;
}
void jiemi(hufmantree ht ,int n){
	printf_s("   显示字符编码(哈夫曼表)\n");cout << "位置 右子树 左子树 双亲 对应字符"<<endl;
	int i; for (i = 1; i <= 2 * n - 1; i++)
	{
		
		printf_s("%2d", i);
		printf_s("%6d%6d%6d%6c\n", ht[i].rchild, ht[i].lchild, ht[i].parent, ht[i].zifu);
	}
	
	cout << "解密成功!";
}
void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100])
{
	cout << endl;
	int d, i = 1, j;
	char *cd;
	d = n * 2 - 1;
	cd = new char[n];
	char c;
	for (i = 1; i <= n; i++)
	{
		strcpy_s(cd, strlen(hc[i]) + 1, hc[i]);

	for (j = 0; j <strlen(cd); j++)
		{
			c = cd[j];
			if (c == '0')
			{
				d = ht[d].lchild;

			}
			if (c == '1')
			{

				d = ht[d].rchild;
			}
		}
	cout << ht[d].weight << "   " << ht[d].zifu<<endl;
		d = n * 2 - 1;
	}
	delete cd;
	char bf[100];

	for (i = 0; i < n;i++)
	bf[i] = '\0';
	FILE *fp = fopen(b, "w+");
	for (i = 1; i <= n; i++)
	if (ht[i].zifu != '\0')
	{
		bf[i - 1] = ht[i].zifu;
		fprintf_s(fp,"%c", bf[i-1]);
		}
	
	fclose(fp);
}
void Zifubianma(huffmancode hc, int n, char a[])
{
	printf_s("   显示字符编码\n");
	int i; for (i = 1; i <= n; i++)
	{
		cout << a[i - 1] << "  " << hc[i] << endl;
	}
}
void xianshi(huffmancode hc, int n,char b[100])
{
	int i;

	printf_s("\n         4. 显示加密文件\n");
FILE *fp = fopen(b, "w+");
	for (i = 1; i <= n; i++)
	{
		cout <<hc[i];	fputs(hc[i], fp);	
	}
fclose(fp);
}

哈夫曼编码的设计与应用
 
问题需求分析
 
用哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码(有时也称为霍夫曼编码)。
 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。
 
数据结构的定义
 
哈夫曼树结构体包含如下内容：节点权重，当前节点的父节点，左右子树，节点信息。
 哈夫曼编码结构体包含如下内容：存编码的数组，编码数组的开始标志。
 
功能详细设计
 
构建哈夫曼树：使用一维数组，每个节点存储权重，父节点，左子树，右子树，以及数值的信息。遍历整个数组，根据每个节点的权重去找到最小以及第二小的节点，然后对各自的父节点，左右子树赋值，建立两个节点的联系将他们的联系填入该结构体数组中。
 哈夫曼树如下图:
 a权重45; b权重15; c权重12; d权重16; e权重9; f权重5
 
 哈夫曼树结构体数组如下图(使用a, b, 58举例):
 
 根据哈夫曼树建立哈夫曼编码：从树的根节点开始，根据每个叶子节点与父节点之间的联系，使用哈夫曼编码结构体中的编码数组储存树种每个叶子节点的编码, 往左边遍历是0, 往右边遍历是1, 举例: a, 由建立好的哈夫曼树可得, 当遍历查找到a的时候, a到root的路径是: 100->86->58->a, 所以可得编码就是000;
 
根据哈夫曼编码将指定的编码转化为字符串：读取到哈夫曼编码后，当编码为0表示节点是左子树，当编码为1的时候表示右子树，根据已经建立好的哈夫曼树，利用顺序遍历的方式，根据左0右1，寻找哈夫曼树中的叶子节点，当某一节点在哈夫曼树中左右子树都为空的时候，表示该节点即使叶子节点，然后输出对应叶子节点在哈夫曼编码数组中的位置, 其原理与编码的方式恰恰相符, 而是根据01数字查找对应的叶子节点.
 
函数调用图:
 
 
编写代码体会
 
遇到的问题是数组下标没有弄好,导致建立哈夫曼树时出现各种错误, 进行编码过程没有将lchild与rchild的”变化写在一起”导致出现错误,其实最大的问题是:没有将代码的逻辑思路考虑清楚,还有边界条件值,最蠢的是没有打一下草稿,写一下伪代码,把程序的思想理解,导致编程的过程中出现各种问题,以后写代码之前还是把逻辑理清楚再动手写代码,最后再将代码写到电脑上测试。
 
完整代码
 
#include<iostream>
#include<string>
#include<fstream> 
using namespace std;
struct Htnode{
	int weight,parent,lchild,rchild;
	char c; 
};
struct Htcode{
	int bit[25],start;
};
int type(int a[]){
	string s;
	int sum = 0; 
	cout<<"输入需要编码的字符串"<<endl;
	cin>>s;
	for(int i = 0; i < s.size(); i++){
		a[s[i]-'a']++;
	}
	cout<<"出现的字母种类以及频率:"<<endl; 
	for(int i = 0; i < 26; i++){
		if(a[i] != 0){
			char c = char(i+'a');
			cout<<"i:"<<i<<" c:"<<c<<":"<<a[i]/(s.size()*1.0)<<endl;
			sum++;	
		}
	}
	return sum;
} 
//通过数组的方式构建哈夫曼树 
void HufmanTree(Htnode h[],int n, int a[]){
	int i,j,max1,max2,x1,x2;
	for(i=0;i<2*n;i++){
		h[i].weight=0;
		h[i].parent=-1;
		h[i].lchild=-1;
		h[i].rchild=-1;
		h[i].c='\0';
	}
	for(i=0;i<26;i++){
		if(a[i] != 0){
			h[i].c = i + 'a';
			h[i].weight = a[i]; 
		}
	}
	for(i=0;i<n-1;i++){
		max1=1000,max2=1000;
		x1=-1,x2=-1; 
		for(j=0;j<n+i;j++){
			if(h[j].weight<max1 && h[j].parent==-1){
				max2=max1;
				x2=x1;
				max1=h[j].weight;
				x1=j;
			}else if(h[j].weight<max2 && h[j].parent==-1){
				max2=h[j].weight;
				x2=j;
			}
		}
		//根据每个节点信息, 将其信息存储到节点数组中
		h[x1].parent=n+i; h[x2].parent=n+i; 
		h[n+i].weight=h[x1].weight+h[x2].weight;
		h[n+i].lchild=x1;h[n+i].rchild=x2;
	}
	for (i=0;i<2*n-1;i++){
		cout<<h[i].weight<<" "<<h[i].parent<<" "<<h[i].lchild<<" "<<h[i].rchild<<" "<<h[i].c<<endl; 
	}
}
//哈夫曼编码
//根据叶子节点的位置, 将其path路径01数字填充到编码数组中
void  HuffmandeCode(Htnode h[], int n, int a[], Htcode hcode[]){
	HufmanTree(h, n, a);
	ofstream out;
	out.open("HuffmandeCode.txt", ios::out);
	int i,j;
	for(i=0;i<n;i++){
		j=0;
		int parent=h[i].parent;//记录当前节点的父亲 
		int c=i;
		while(c!=-1){//parent造成根节点不会被访问 
			hcode[i].bit[j++]=h[parent].lchild==c?0:1;//从叶子节点到根节点, 应该使用栈结构 
			c=parent;
			parent=h[parent].parent;
		}
		hcode[i].start=j-1;
	}
	for(i=0;i<n;i++){
		cout<<h[i].c<<":";
		for(j=hcode[i].start-1;j>=0;j--){
			cout<<hcode[i].bit[j];
			out<<hcode[i].bit[j];
		}
		cout<<endl;
	}
	out.close(); 
}
string load(){
	ifstream in("HuffmandeCode.txt");
	string str;
	char buffer[256];
	if(!in.is_open()){
		cout<<"加载文件错误"<<endl; 
		return NULL;
	} 
	cout << "载入编码文件" << endl;
	in.getline(buffer, 100, ' ');
	return string(buffer);
}

//哈夫曼译码
void  HuffmanenCode(string s,int n,Htnode h[]){
	int i=0,j=0,lchild=2*n-2,rchild=2*n-2;
	while(s[i]!='\0'){
		if(s[i]=='0'){
		//出现的问题是,最初将lchild,rchild分开计算,导致在左右子树间相互变化出现
		//lchild,rchild不同同时表示同一个节点,最后想到lchild=rchild就能解决问题
			lchild=h[lchild].lchild;
			rchild=j=lchild;
		}
		if(s[i]=='1'){
			rchild=h[rchild].rchild;
			lchild=j=rchild;
		}
		if(h[lchild].lchild==-1 && h[rchild].rchild==-1){
			cout<<h[j].c;
			lchild=rchild=2*n-2;
			j=0;
		}
		i++;
	}
}
int main(){
	Htnode h[30];
	Htcode hcode[10];
	int a[26]={0};
	string s;
	int n = type(a);
	cout<<"n:"<<n<<endl;
	HuffmandeCode(h, n, a, hcode);
	HuffmanenCode(load(),n,h);
	return 0;
}
 
上面有错, 还请指出, 如果认为我写的还不错, 还请点个赞, 多多支持一下, O(∩_∩)O~~

​
#include <stdio.h>
#include <stdlib.h>       //malloc函数和free()函数用到 
#include <string.h>      //strcpy函数用到 
#define N 30             //最大的叶子数目 
#define M 2*N-1         // 最大的结点个数(N个度为0的叶子结点，N-1个度为2的叶子节点) 
#define K 30             //要译码的01字符序列，最多30位 
#define MAXINT  32767         //32767


//三叉链表结点结构 
typedef struct
{
    int weight;               //结点的权值 
    int parent,Lchild,Rchild;	//结点的双亲，左孩子，右孩子 
}HTNode;


//search函数声明 
void search(HTNode huff[],int c,int *s1,int *s2);     //在前m项中找最小的权值和次小的权值 


//建立哈夫曼树 
void crthuff(HTNode huff[],int w[],int n)      //HTNode结构体数组huff[]，每个结点的权值数组w，n个有效的叶子结点 
{
	int i;
	int s1,s2;               //声明语句给s1与s2分配了存储空间，s1是权值最小的结点的下标，s2是权值次小的结点的下标 
	int m=2*n-1;              //有效的结点总数为m
	for(i=1;i<=n;i++)         //huff[]数组与w[]数组都是从下标1开始的 
	huff[i]={w[i],0,0,0};     //初始化前n个叶子结点(记住这种给结构体数组赋值的方法) 
	for(i=n+1;i<=m;i++)       
	huff[i]={0,0,0,0};        //初始化从下标n+1到m的节点 
	for(i=n+1;i<=m;i++)        
	{                          
	    search(huff,i-1,&s1,&s2);   //在前i-1项中找权值最小的结点,传数组的时候只写数组名,&s1指的是下标的地址
	//	printf("最小权值的下标为:s1=%d s2=%d",s1,s2); 
	//    printf("最小的两个权值是%d %d",huff[s1].weight,huff[s2].weight);
	    huff[i].weight=huff[s1].weight+huff[s2].weight;
	    huff[i].Lchild=s1;       
	    huff[i].Rchild=s2;     
	    huff[s1].parent=i;
	    huff[s2].parent=i;
	}  
}



//找最小权值的两个节点，记住这个找最小的两个数的方法 
void search(HTNode huff[],int c,int *s1,int *s2)    //在数组的前c项中找,指针变量s1与s2,传过来的是下标的地址 
{                                                   //在该函数中 *s1是m1在数组中的下标，*s2是m2在数组中的下标
	int i,m1,m2;         //m1存放最小的权值，m2存放次小的权值
	m1=m2=MAXINT;          //先让m1与m2赋成最大 
	for(i=1;i<=c;i++)
	{
		if(huff[i].weight<m1&&huff[i].parent==0)
		{
			m2=m1;                      //让次小的m2等于m1 
			m1=huff[i].weight;          //huff[i]的权值比最小的还小，就让记录最小的m1等于huff[i].weight 
			*s2=*s1;                   //*s1与*s2在最开始声明的时候就是有值的，只不过该值是随机产生的，第一次进入该循环的时候，下标*s2被赋予的*s1是一个随机的数 
			*s1=i;                      //m1的下标*s1等于i 
		}
		else if(huff[i].weight<m2&&huff[i].parent==0) 
		{
			m2=huff[i].weight;
			*s2=i;
		} 
	}
}


//哈夫曼编码函数
char ** crthuffcode(HTNode huff[],int n)      //n个叶子结点,对每一个叶子结点都需要编码,因为返回值的数组名是一个指针的指针，所以前面是char ** 
{
	char **hc;                     
//	char *hc[n];                   //字符型的指针数组hc,数组中的每个元素都是一个指向字符串的指针变量 
	int i,start,c,p;                  
	char *cd;                       //字符型的指针变量
	cd=(char *)malloc(n*sizeof(char));    //malloc函数的返回值是一个（指向已申请空间的起始地址的）指针，cd指向可用空间的起始地址，这里的n是因为一个字符的编码序列，它的长度不超过叶子结点个数n
	hc=(char **)malloc(n*sizeof(char*));  //给hc这个二重指针分配空间， 
	cd[n-1]='\0';                     //从后向前逐位求编码 ，首先最后一位放编码结束符,留给编码字符的空间是n-1位 
	for(i=1;i<=n;i++)               //对每一个叶子结点都需要编码
	{
	    start=n-1;                    //n-1处存的是'\0' 
	    c=i;                         //c记录当前结点
		p=huff[i].parent;             //p记录当前结点的双亲 
	    while(p!=0)
        {
             	start--;              //从下标为n-2处开始存编码 
        	   if(huff[p].Lchild==c) 
        	   {
			       cd[start]='0';
		       }
		       else
		       {
			       cd[start]='1';
			   }
			       c=p;                  //当前结点为p
				   p=huff[p].parent;     //把当前结点的双亲赋给p
		}                                   //哈夫曼树的根节点的双亲为0 
		hc[i]=(char *)malloc((n-start)*sizeof(char));     //hc[i]，数组的第i号元素是一个字符型的指针变量，是一个指向第i号字符串的首地址 
		strcpy(hc[i],&cd[start]);            //从cd[start]指向的字符开始复制给hc[i]，一直复制直到遇到第一个'\0'为止，被复制的字符数组
//		printf("%p %s\n", &hc[i], hc[i]);
//		printf("%c:",'A'+i-1);
//		printf("%s\n",hc[i]); 
	}                                          //a与b是两个数组的数组名，在strcpy函数中，这样用strcpy(a,b);把b数组赋值到a数组里。 
    	free(cd);
    //	printf("%p\n", hc);
    	return hc;                      //数组名是二重指针，该函数的返回值是char ** 
}
		

void print(char **hc,int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
//		printf("i=%d\n",i);
//		printf("这里：%s\n",hc[1]);
		printf("%c:\n",'A'+i-1);
		printf("%s\n",hc[i]);
//	    printf按%s输出时,遇到'\0'即停止输出 
	}	
}
//for(i=1;i<=n;i++)
//{
//	switch(i)
//	{
//			case 1:printf("%s",hc[1]);break;
//			case 2:printf("%s",hc[2]);break;
//			case 3:printf("%s",hc[3]);break;
//			case 4:printf("%s",hc[4]);break;
//			case 5:printf("%s",hc[5]);break;
//			case 6:printf("%s",hc[6]);break;
//	}
//   
// } 
//}


//给定字符串求其对应的编码串		       
void word(char s[],char **hc,int n)            //s是传过来的待编码的字符串，n是叶子节点 
{
    int i;
    for(i=0;s[i];i++)                             //'\0'的逻辑值为0 
    {
        for(int j=1;j<n+1;j++)
        { 
            if(s[i]=='A'+j-1)
			 {
			 printf("%s",hc[j]);
			// printf("这里：%s",hc[2]);
			 break;
			 }
	    } 
    }
    printf("\n");
}
 
 
//哈夫曼树译码（从上到下） 
 void huffdecode(HTNode huff[],char yima[],int f,int n)
{
	int x=2*n-1;
	for(int i=0;i<f;i++)
	{
		if(yima[i]=='0') 
		{
			x=huff[x].Lchild;
		}
		else if(yima[i]=='1') 
		{
			x=huff[x].Rchild;
		}
	    if(huff[x].Lchild==0)
		{
			printf("%c",'A'+x-1);
			x=2*n-1;
		}
	}
}

 
int main()
{
	int i,j; 
	int n=6;
	int f=0;        //记录待译编码有多少个字符 
	int w[N+1];          //权值数组，最多有N个叶子结点 
	char yima[K];       //待译码的01字符序列 
	char bianma[K];      //带编码的字符串 
	char ** hc;        
	HTNode huff[2*n];     //定义一个哈夫曼树的结构体数组，本来大小是2*n-1,但是该数的0号单元不使用，从下标1开始到2*n-1结束       
	for(i=1;i<=n;i++) 
	{
	    scanf("%d",&w[i]);            //读入权值  
    }
    getchar();
    gets(bianma);                 //gets()按回车键产生一个换行符，电脑会读取换行符之前的所有字符，并在这些字符后添加一个'\0' 
    gets(yima);
    f=strlen(yima);               //strlen测的是字符数组有效的长度 
    crthuff(huff,w,n);            //建立哈夫曼树   
    hc=crthuffcode(huff,n);            //给哈夫曼树编码函数，返回值是指针数组名，是一个二重指针
//	for(int  i = 1; i <= n; i++){
//		printf("%p %s\n", &hc[i], hc[i]);
//	
//	}
		for(i=1;i<=n;i++)
	{
//		printf("i=%d\n",i);
//		printf("这里：%s\n",hc[1]);
	//	printf("main:%c:\n",'A'+i-1);
		printf("这里：%s\n",hc[i]);
//	    printf按%s输出时,遇到'\0'即停止输出 
	}	
	//print(hc,n);     
    word(bianma,hc,n);              //给定字符串求其编码 
	huffdecode(huff,yima,f,n);        //译码     
    return 0;
}
	
//3 4 10 8 6 5
//BEE
//0010000100111101	

​
 
在crthuffcode(HTNode huff[],int n)函数中，如果定义的是char **hc;定义了一个二重指针，那么在函数中应该首先hc=(char **)malloc(n*sizeof(char*));也就是应该首先给hc这个二重指针开辟空间，也就是给n个指向字符串的指针变量来分配空间，malloc函数的返回值是一个指针，指向该n个指针变量的首地址。
 如果在该函数中，定义的是char *hc[n];并且没有hc=(char **)malloc(n*sizeof(char*));这句话，那么后面的hc[i]=(char *)malloc((n-start)*sizeof(char)); 这个语句只是在给每个指针变量所指向的字符串分配空间，而不是对该指针变量分配空间。所以该字符型指针数组中的每个元素还是没有一个明确的地址，只是一个在函数中的局部变量数组，那么在退出该函数的时候，这个局部变量数组会被释放，该数组的每个元素，即字符型的指针变量将丢失，在主函数中调用该函数时，除了第一个hc[1]有明确的指向外，其他的hc[i]所指向的都是不确定的字符。
 运行结果：
 

简单哈夫曼树的建立，及其编码、译码的详解和实现
 
基本术语
 
二叉树的带权路径长度
 
二叉树中所有叶子结点的带权路径长度之和
 
根到结点的路径长度
 
从根到结点的路径上的分支数
 
哈夫曼树二叉树
 
又称最优二叉树，是一带权路径长度最短的二叉树。
 
 
 
例：设结点a、b、c、d的权值分别为1、3、5、7，
 二叉树（1）的带权路径长度=31+33+25+17=29
 二叉树（2）的带权路径长度=21+23+25+27=32
 二叉树（3）的带权路径长度=21+33+35+17=33
 
 

 
 
 在所有可以构建的二叉树中，（1）的带权路径长度是最短，所以（1）是最优二叉树。
 
 
所以，那么问题来了。
 怎么构建哈夫曼树呢？
 
构建哈夫曼树
 
算法
 
 
根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树只含一个带权的根结点，其左右子树均空；
 
 
在F中选两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和；
 
 
在F中删除这两棵二叉树，同时将新得到的二叉树加入F ；
 
 
重复2和3，直到F只含一棵二叉树，此即最优二叉树。
 代码如下：
 
 
    //HT为哈夫曼树，MIN为一结构体的命名。
    for (int i = num + 1; i <= m; i++)
    {
        MIN min;
        min=Select(HT,i-1);//选择并比较F中两权值最小的两个二叉树
        HT[min.s1].parent = i;
        HT[min.s2].parent = i;
        HT[i].lchild = min.s1;//权值小的二叉树作为新生二叉树的左子树
        HT[min.s1].num = "0";
        HT[i].rchild = min.s2;//权值大的二叉树作为新生二叉树的右子树
        HT[min.s2].num = "1";
        HT[i].weight = HT[min.s1].weight + HT[min.s2].weight;//新生的二叉树权值为其左、右子树之和
        HT[i].data = -1;
    }
    
 
译码
 
输入一串字符，将他们用哈夫曼码的形式输出。
 
string estring;//创建一个字符串类型的数据，用于存储哈夫曼码
for(int i = 0;i <= s.size(); i++)
{
    for(int x = 1; x <= m; x++)
    {
        if(hft[x].data == s[i])//将所选的字符与哈夫曼树中的字符进行对比
        {
            estring = estring + hft[x].num;//将哈夫曼码连接起来
            x = m;
        }
    }
}
 
选中要编译字符串中的一个字符；
将选中的字符与哈夫曼树中的每个字符进行对比；
若两字符相等，则将哈夫曼中字符的哈夫曼码连接至estring（要输出的字符串）后。
待要编译的字符串全部编译完成，则输出estring。
 
解码
 
输入一串哈夫曼码，将其解码变成一串字符。
 
string estring;//创建一个字符串类型的数据，用于存储解码得出的字符
    int pos = 0, first = 0;
    for(int x = 0; x <= s.size(); x++)
    {
        pos++;
        for(int i = 1; i <= m; i++)
        {
            if(hft[i].num == s.substr(first, pos))//first为从第几个字符开始截取，pos为截取几个字符。
            //哈夫曼树中的哈夫曼码与选中的哈夫曼码进行对比
            {
                cout<<hft[i].data;
                first = pos + first;//将字符连接起来
                pos = 0;
            }
        }
    }
 
输入一串哈夫曼码；
将first指向第一个字符，代表从这个字符开始，pos赋值为1（代表选取一个字符），将选取得到的字符与哈夫曼树中的每个哈夫曼码进行对比；
如果两字符相等，将此哈夫曼码相对应的字符直接输出，first 指向pos+first字符处，pos变为1；若不相等，pos+1，接着进行比较。
直到译码结束。
 
这一部分虽然编译成功了，但是思路简单，时间复杂度太大了，资源浪费太多。如果大家有好点的算法或思路，请大家在评论区说一下哦。
 
完整的代码
 
#include<iostream>
#include<string>
#include<string.h>
using namespace std;

//哈夫曼树的存储结构
typedef struct
{
    char data;   //存储数据
    int weight;  //结点的权重
    string num;  //存放哈夫曼码
    int parent, lchild, rchild;  //结点的双亲、左孩子、右孩子的下标
} HTNode,*HuffmanTree;

//两个最小结点
typedef struct
{
    int s1;
    int s2;
} MIN;

//选择结点权值最小的两个结点
MIN Select(HuffmanTree HT, int n)
{
    int min, secmin,s1,s2;
    min = 10000;
    secmin = 10000;
    MIN code;
    s1 = 1;
    s2 = 1;
    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0 && (HT[i].weight<min))
        {
            min = HT[i].weight;
            s1 = i;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0 && (HT[i].weight<secmin) && (i != s1))
        {
            secmin = HT[i].weight;
            s2 = i;
        }
    }
    code.s1 = s1;
    code.s2 = s2;
    return code;

}

//将哈夫曼码存储在结构体num中
void putlorinnum(HuffmanTree &hft, int num)
{
    for(int i = num; i >= 1; i--)
    {
        if(hft[hft[i].parent].parent)
        {
        hft[i].num = hft[hft[i].parent].num + hft[i].num;
        }
    }
}


//创造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int num)
{

    int m;
    m = 2 * num - 1;
    HT = new HTNode[m + 1];   //分配空间
    for (int i = 1; i <= m; i++)   //初始化
    {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    cout << "请输入每个数据及其权值：" << endl;
    for (int i = 1; i <= num; i++)
    {
        cin >> HT[i].weight;
        cin>>HT[i].data;
    }

    for (int i = num + 1; i <= m; i++)  //构建哈夫曼树
    {
        MIN min;
        min=Select(HT,i-1);      //选择二叉树
        HT[min.s1].parent = i;
        HT[min.s2].parent = i;
        HT[i].lchild = min.s1;
        HT[min.s1].num = "0";
        HT[i].rchild = min.s2;
        HT[min.s2].num = "1";
        HT[i].weight = HT[min.s1].weight + HT[min.s2].weight;
        HT[i].data = -1;
    }
    putlorinnum(HT, m);   
    for (int i = 1; i <= m; i++)  //进行每个字符哈夫曼码的输出
    {
        if(HT[i].data != -1)
        {
            cout<<HT[i].data<<" 权重为"<<HT[i].weight<<"  ，哈夫曼码为："<<HT[i].num<<endl;

            cout<<endl;
        }
    }
}

//将一串字符编译成哈夫曼码
void changchartohft(HuffmanTree hft, string s, int m)
{
    string estring;
    for(int i = 0;i <= s.size(); i++)
    {
        for(int x = 1; x <= m; x++)
        {
            if(hft[x].data == s[i])//查找哈夫曼树中相应的字符
            {
                estring = estring + hft[x].num;//哈夫曼码连接起来
                x = m;
            }
        }
    }
    cout<<estring<<endl;
    return;
}



//将一串哈夫曼码解译成一串字符
void changhfttochar(HuffmanTree hft, string s, int m)
{
    string estring;
    int pos = 0, first = 0;
    for(int x = 0; x <= s.size(); x++)
    {
        pos++;
        for(int i = 1; i <= m; i++)
        {
            if(hft[i].num == s.substr(first, pos))//将截取的字符串和哈夫曼中哈夫曼码近行对比
            {
                cout<<hft[i].data;
                first = pos + first;
                pos = 0;
            }
        }
    }
    cout<<endl;
}

int main()
{
    int num;  //结点的个数
    string s1, s2;
    cout << "请输入哈夫曼树叶子结点的个数：";
    cin >> num;
    //创造哈夫曼树
    HuffmanTree HT;
    CreateHuffmanTree(HT, num);
    
    while(1)//设置一个循环，可以选择性进行某些步骤。
    {
        int q;
        cout<<"----------------------"<<endl;
        cout<<"编译：1"<<endl;
        cout<<"解码：2"<<endl;
        cout<<"(其他按键结束)"<<endl;
        cout<<"输入要进行的操作："<<endl;
        cin>>q;
        
        if(q==1)
        {
                cout<<"输入想要编译的一串字符"<<endl;
                cin>>s1;
                changchartohft(HT, s1, num);
        }
        else if(q==2)
        {
                cout<<"输入想要解码的一串数字"<<endl;
                cin>>s2;
                changhfttochar(HT, s2, num);
        }
        else
            break;
    }
    return 0;
}
 
此程序在Code::Blocks上可成功运行。
 
 输入输出形式如上图。