数据结构 二叉树应用:赫夫曼编码二

      #include <stdio.h>
      #include <stdlib.h>
      #include <string.h>
      #include <malloc.h>
      #define swap(a,b) {int t; t=a; a=b;b=t;}
      typedef struct
      {
     	unsigned int weight;
     	unsigned int parent, lchild, rchild;
      }HTNode, *HuffmanTree;
      typedef char** HuffmanCode;
      void Select(HuffmanTree HT,int n,int &s1,int &s2)
      {
     	int i,k;
     	int j = 0;
     	int *a = (int*)malloc(n * sizeof(int));
     	for (i=1; i<=n; ++i)
      	{
     		if (HT[i].parent == 0)
      		{
      			a[j++] = HT[i].weight;
      		}
      	}
     	for (i=0; i<j-1; i++)
      	{
     		for (k=j-2; k>=i; k--)
      		{
     			if (a[k] > a[k+1])
      			{
       swap(a[k],a[k+1]);
      			}
      		}
      	}
      	s1 = a[0];
      	s2 = a[1];
     	for (i=1; i<=n; ++i)
      	{
     		if (s1 ==(int) HT[i].weight && HT[i].parent == 0)
      		{
      			s1 = i;
     			break;
      		}
      	}
     	for (i=1; i<=n; ++i)
      	{
     		if (s2 == (int) HT[i].weight && HT[i].parent == 0)
      		{
     			if (i != s1)
      			{
       s2 = i;
      break;
      			}
     			else
      			{
      continue;
      			}
      		}
      	}
     	free(a);
      }
      void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
      {
      	HuffmanTree p;
     	int i,m;
     	int s1,s2;
     	char *cd;
     	if (n<=1)
      	{
     		return;
      	}
      	m = 2*n -1;/*n个字符，其赫夫曼树的结点个数为2*n -1*/
      	HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); //0号单元未用
     	for (p = HT+1 , i=1; i<=n; ++i,++p,++w)
      	{
      		p->weight = *w;
      		p->lchild = p->parent = p->rchild = 0;
      	}
     	for (;i<=m; ++i,++p)
      	{
      		p->lchild = p->parent = p->rchild = p->weight = 0;
      	}
     	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;
      	}
      	HC = (HuffmanCode)malloc((n+1) * sizeof(char *));
      	cd = (char*)malloc(n*sizeof(char));
     	int q = m,cdlen = 0;
     	for (i=1; i<=m; i++)
      	{
      		HT[i].weight = 0;
      	}
     	while (q)
      	{
     		if (HT[q].weight == 0)
      		{
      			HT[q].weight = 1;
     			if (HT[q].lchild != 0)
      			{
       q = HT[q].lchild;
       cd[cdlen++] = '0';
      			}
     			else if (HT[q].rchild == 0)
      			{
       HC[q] = (char*)malloc((cdlen+1) * sizeof(char));
       cd[cdlen] = '\0';
      strcpy(HC[q],cd);
      			}
      		}
     		else if (HT[q].weight == 1)
      		{
      			HT[q].weight = 2;
     			if (HT[q].rchild != 0)
      			{
       q = HT[q].rchild;
       cd[cdlen++] = '1';
      			}
      		}
     		else
      		{
      			HT[q].weight = 0;
      			q = HT[q].parent ;
      			--cdlen;
      		}
      	}
     	free(cd);
      }
      int main()
      {
      	HuffmanTree HT;
      	HuffmanCode HC;
     	int i;
     	//int a[] = {5,29,7,8,14,23,3,11};
     	//int a[] = {27,8,15,15,30,5};
     	int a[] = {45,13,12,16,9,5};
     	int n = sizeof(a) / sizeof(a[0]);
      	HuffmanCoding(HT,HC,a,n);
     	for (i=1; i<=n; i++)
      	{
     		printf("%d:%s\n",a[i-1],HC[i]);
      	}
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/17268171