07.02 Huffman code

One ： Huffman code

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXBIT    100
#define MAXVALUE  10000 
#define MAXLEAF   30
#define MAXNODE   MAXLEAF*2 -1

typedef struct
{
	double weight;
	int parent;
	int lchild;
	int rchild;
	char value;
} HNodeType;        /*  Node structure  */

typedef struct
{
	int bit[MAXBIT];
	int start;
} HCodeType;        /*  Coding structure  */
HNodeType HuffNode[MAXNODE]; /*  Define a node structure array  */
HCodeType HuffCode[MAXLEAF];/*  Define an array of encoded structures */
/*  Construct the Huffman tree  */
void HuffmanTree(HNodeType HuffNode[MAXNODE], int n) {
	/* i、j：  Loop variable ,m1、m2： The weights of two minimum weight nodes in different processes of constructing Huffman tree ,
	   x1、x2： The sequence numbers of two minimum weight nodes in the array in different processes of constructing Huffman tree .*/
	int i, j, x1, x2;
	double m1, m2;
	/*  Initialize the Huffman tree array  HuffNode[]  Node in  */
	for (i = 0; i < 2 * n - 1; i++)
	{
		HuffNode[i].weight = 0;// A weight 
		HuffNode[i].parent = -1;
		HuffNode[i].lchild = -1;
		HuffNode[i].rchild = -1;
	}
	/*  Input  n  Weight of leaf nodes  */
	for (i = 0; i < n; i++)
	{
		cout << "Please input value and weight of leaf node " << i + 1 << endl;
		cin >> HuffNode[i].value >> HuffNode[i].weight;
	}
	/*  structure  Huffman  Trees  */
	for (i = 0; i < n - 1; i++)
	{// perform n-1 The merger 
		m1 = m2 = MAXVALUE;
		/* m1、m2 Two nodes without parent nodes and with the smallest node weight are stored in  */
		x1 = x2 = 0;
		/*  Find out the smallest weight among all nodes 、 Two nodes without parent nodes , And merge them into a binary tree  */
		for (j = 0; j < n + i; j++)
		{
			if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)
			{
				m2 = m1;
				x2 = x1;
				m1 = HuffNode[j].weight;
				x1 = j;
			}
			else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1)
			{
				m2 = HuffNode[j].weight;
				x2 = j;
			}
		}
		/*  Set the two child nodes found  x1、x2  Parent node information of  */
		HuffNode[x1].parent = n + i;
		HuffNode[x2].parent = n + i;
		HuffNode[n + i].weight = m1 + m2;
		HuffNode[n + i].lchild = x1;
		HuffNode[n + i].rchild = x2;
		cout << "x1.weight and x2.weight in round " << i + 1 << "\t" << HuffNode[x1].weight << "\t" << HuffNode[x2].weight << endl; /*  Used for testing  */
	}
}
/*  Huffman tree coding  */
void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n) {
	HCodeType cd;       /*  Define a temporary variable to store the information when solving the code  */
	int i, j, c, p;
	for (i = 0; i < n; i++)
	{
		cd.start = n - 1;
		c = i;
		p = HuffNode[c].parent;
		while (p != -1)
		{
			if (HuffNode[p].lchild == c)
				cd.bit[cd.start] = 0;
			else
				cd.bit[cd.start] = 1;
			cd.start--;        /* Move forward one bit  */
			c = p;
			p = HuffNode[c].parent;    /*  Set the next cycle condition  */
		}
		/*  The coding information of leaf nodes is changed from temporary coding cd It's copied out of , Put in the array of encoded structures  */
		for (j = cd.start + 1; j < n; j++)
			HuffCode[i].bit[j] = cd.bit[j];
		HuffCode[i].start = cd.start;
	}
}
int main()
{
	int i, j, n;
	cout << "Please input n:" << endl;
	cin >> n;
	HuffmanTree(HuffNode, n);  // Construct the Huffman tree 
	HuffmanCode(HuffCode, n);  //  Huffman tree coding 
	// Output all saved Huffman codes with existing codes 
	for (i = 0; i < n; i++)
	{
		cout << HuffNode[i].value << ": Huffman code is: ";
		for (j = HuffCode[i].start + 1; j < n; j++)
			cout << HuffCode[i].bit[j];
		cout << endl;
	}
	return 0;
}