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

落日映苍穹つ 2022-09-19 01:53 138阅读 0赞

#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;
    }