huffman.cpp

利用哈夫曼编码,可以对一组数据编码和译码

#include "huffman.h"

huffman::huffman()
{
	m_ht = NULL;
	m_hcd = NULL;
}

huffman::~huffman()
{
	if (m_ht != NULL)
	{
		delete m_ht;
	}

	if (m_hcd != NULL)
	{
		delete m_hcd;
	}
}

void huffman::getdata()  
{
  int i;

  cout << "输入需要编码的字符个数:";
  cin >> m_num; 

  m_ht = new huffnode[2 * m_num];

  for (i=1; i<=m_num; i++)
  {    
 	cout << "输入第" << i << "个字符和它的权值:";
	cin >> m_ht[i].data >> m_ht[i].weight;   
  } 
}

void huffman::createhfmtree()  
{
  int i, k, x1, x2, m1, m2;  /* m1为最小权值，x1为其在ht中的下标；m2为第二小权值，x2为其下标 */
 
  for (i=1; i<=2*m_num-1; i++)
  {
	  m_ht[i].parent = m_ht[i].left = m_ht[i].right = 0;  /* 对ht的parent，left，right域进行初始化 */
  }

  for (i=m_num+1; i<=2*m_num-1; i++)
  {
     m1 = m2 = 10000;                   /* m1，m2初值无限大 */
     x1 = x2 = 0;                       /* x1, x2初值为0 */

     for (k=1; k<=i-1; k++)             /* k为可以进行比较的结点的下标 */
	 {
		 if (m_ht[k].parent == NULL) 	/* 当前结点的父结点不存在时 */
		 {
			 if (m_ht[k].weight < m1)   /* 当前结点的权值比最小权值还小时 */
			 {
				 m2 = m1;
				 x2 = x1;
				 m1 = m_ht[k].weight;
				 x1 = k;
			 }
			 else if (m_ht[k].weight < m2)    /* 当前结点的权值比最小权值大但比第二小权值大时 */
			 {
				 m2 = m_ht[k].weight;
				 x2 = k;
			 }
		 }
	 }

     m_ht[x1].parent = i;
     m_ht[x2].parent = i;
     m_ht[i].weight = m_ht[x1].weight + m_ht[x2].weight;
     m_ht[i].left = x1;
     m_ht[i].right = x2;
  }
}

void huffman::disphfcode()  
{
  huffcode d;
  int i,c,f,x,k;

  m_hcd = new huffcode[m_num+1];

  
  for (i=1; i<=m_num; i++)
  {
    d.start = m_num + 1;        /* d.start为栈顶 */
    c = i;                      /* c存放当前结点 */
    f = m_ht[i].parent;         /* f存放当前结点的父结点 */

    while (f != 0)
    {
      if (m_ht[f].left == c)    /* 若当前结点在其父结点的左边时 */
	  {
		  d.cd[--d.start] = '0';
	  }
      else
	  {
		  d.cd[--d.start] = '1'; /* 当前结点在其父结点的右边时 */
	  }

      c = f;                     /*  当前结点的父结点赋予c */
      f = m_ht[f].parent;        /* c的父结点赋予f */
    }

    m_hcd[i] = d;  
  } 
  
  cout << "各字符的human编码如下" << endl;
  
  for(i=1; i<=m_num; i++)  
  {
    cout << m_ht[i].data <<":";
    x = m_hcd[i].start;

	for(k=x; k<=m_num; k++)      /* 通过栈输出哈夫曼编码 */
	{
	   cout << m_hcd[i].cd[k];
	}

	cout << endl;    
  } 
}

void huffman::coding() 
{
  int i,j,n,k,x;
  char string[maxleng];

  cout << "输入要编码的字符串：";
  cin >> string;  
  n = strlen(string);

  cout << "字符串" << string << "的编码是：";

  for(i=0; i<n; i++)
  {
    for(j=1; j<=m_num; j++)  
	{
		if(string[i] == m_ht[j].data)  /* 若输入字符和一个带权结点相同 */
		{
			x = m_hcd[j].start;

			for(k=x; k<=m_num; k++)
			{
				cout << m_hcd[j].cd[k];
			}
		}
	}
  }

  cout << endl;
}

void huffman::decoding() 
{
  int i,j,n,k,x,w;
  char string[maxleng];
  i=0;                                   /* i为string数组的下标 */
  
  cout << "输入要解码的字符串：";
  cin >> string;  
  n=strlen(string);

  cout << "字符串" << string << "的解码是:";
  
  while(i<n)
  {
    for(j=1; j<=m_num; j++)  
      {
        x=m_hcd[j].start;

        for(k=x,w=i; k<=m_num; k++,w++)   /* k为m_hcd[j].cd[]的下标 */
		{
			if(string[w] != m_hcd[j].cd[k])
			{
				break;
			}
		}

		if(k > m_num)
        {
			cout << m_ht[j].data;             
	     	break;
		}
      }

    i = w;
  }  
  cout << endl;
}