1358 - 算法6-12：自底向上的赫夫曼编码

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 32 MB

在通讯领域，经常需要将需要传送的文字转换成由二进制字符组成的字符串。在实际应用中，由于总是希望被传送的内容总长尽可能的短，如果对每个字符设计长度不等的编码，且让内容中出现次数较多的字符采用尽可能短的编码，则整个内容的总长便可以减少。另外，需要保证任何一个字符的编码都不是另一个字符的编码前缀，这种编码成为前缀编码。

而赫夫曼编码就是一种二进制前缀编码，其从叶子到根（自底向上）逆向求出每个字符的算法可以表示如下：

<span style="font-family:宋体;">在本题中，读入</span><span>n</span><span style="font-family:宋体;">个字符所对应的权值，生成赫夫曼编码，并依次输出计算出的每一个赫夫曼编码。</span>

<span></span>

题目输入

输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。

第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。

题目输出

共n行，每行一个字符串，表示对应字符的赫夫曼编码。

输入/输出样例

输入格式

8
5 29 7 8 14 23 3 11

输出格式

C语言解答

#include<stdio.h>
//#include<conio.h>
#define MAXBIT 1000
#define MAXVALUE 10000
#define MAXLEAF 1000
#define MAXNODE MAXLEAF*2-1
typedef struct
{
    int bit[MAXBIT];
    int start;
}HCodeType;
typedef struct
{
    int weight;
    int parent;
    int Lchild;
    int Rchild;
}HNodeType;
void HuffmanTree(HNodeType HuffNode[MAXNODE],int n)
{
    int i,j,m1,m2,x1,x2;
    for(i=0;i<2*n-1;i++)
    {
        HuffNode[i].weight=0;
        HuffNode[i].parent=-1;
        HuffNode[i].Lchild=-1;
        HuffNode[i].Rchild=-1;
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",&HuffNode[i].weight);
    }
    for(i=0;i<n-1;i++)
    {
        m1=m2=MAXVALUE;
        x1=x2=0;
        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;
            }
        }
        if(x1>x2)
        {
            int temp;
            temp=x1;
            x1=x2;
            x2=temp;
        } 
        HuffNode[x1].parent=n+i;
        HuffNode[x2].parent=n+i;
        HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
        HuffNode[n+i].Lchild=x1;
        HuffNode[n+i].Rchild=x2; 
    }
} 
int main()
{
    HNodeType HuffNode[MAXNODE];
    HCodeType HuffCode[MAXLEAF],cd;
    int i,j,c,p,n;
    scanf("%d",&n);
    HuffmanTree(HuffNode,n);
    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--;
            c=p;
            p=HuffNode[c].parent;
        }
        for(j=cd.start+1;j<n;j++)
        {
            HuffCode[i].bit[j]=cd.bit[j];
        }
        HuffCode[i].start=cd.start;
    }
    for(i=0;i<n;i++)
    {
          for(j=HuffCode[i].start+1;j<n;j++)
        {
            printf("%d",HuffCode[i].bit[j]);
        }
        printf("\n");
    }
//    getch();
    return 0;
}

C++解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAX_TREE_SIZE 100
typedef int Status; /* 函数结果状态代码,如OK等 */
typedef struct {
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */
typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */

int min1(HuffmanTree t,int i) { /* 函数void select()调用 */
	int j,flag;
	unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
	for(j=1;j<=i;j++)
		if(t[j].weight<k&&t[j].parent==0)
			k=t[j].weight,flag=j;
	t[flag].parent=1;
	return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2) {
/* s1为最小的两个值中序号小的那个 */
	int j;
	*s1=min1(t,i);
	*s2=min1(t,i);
	if(*s1>*s2) {
		j=*s1;
		*s1=*s2;
		*s2=j;
	}
}

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) { /* 算法6.12 */
/* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
	int m,i,s1,s2,start;
	unsigned c,f;
	HuffmanTree p;
	char *cd;
	if(n<=1) return;
	m=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).parent=(*p).lchild=(*p).rchild=0;
	}
	for(;i<=m;++i,++p) (*p).parent=0;
	for(i=n+1;i<=m;++i) { /* 建赫夫曼树 */
	/* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
		select(*HT,i-1,&s1,&s2);
		(*HT)[s1].parent=(*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*));
	/* 分配n个字符编码的头指针向量([0]不用) */
	cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
	cd[n-1]='\0'; /* 编码结束符 */
	for(i=1;i<=n;i++) { /* 逐个字符求赫夫曼编码 */
		start=n-1; /* 编码结束符位置 */
		for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
		/* 从叶子到根逆向求编码 */
		if((*HT)[f].lchild==c) cd[--start]='0';
		else cd[--start]='1';
		(*HC)[i]=(char*)malloc((n-start)*sizeof(char));
		/* 为第i个字符编码分配空间 */
		strcpy((*HC)[i],&cd[start]); /* 从cd复制编码(串)到HC */
	}
	free(cd); /* 释放工作空间 */
}

int main() {
	HuffmanTree HT;
	HuffmanCode HC;
	int *w,n,i;
	scanf("%d",&n);
	w=(int*)malloc(n*sizeof(int));
	for(i=0;i<=n-1;i++)
		scanf("%d",w+i);
	HuffmanCoding(&HT,&HC,w,n);
	for(i=1;i<=n;i++) puts(HC[i]);
}

上一题下一题提示代码讨论统计