刻意练习-理解哈夫曼树构建哈夫曼表C语言

于 2021-07-24 10:24:07 发布
阅读量646 收藏 1
点赞数
分类专栏： 数据结构/算法/设计模式 刻意练习-编程 文章标签： 算法 数据结构
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/renyongjian1994/article/details/119054048
版权

理解哈夫曼树构建哈夫曼表

一、哈夫曼树的作用

  • 哈夫曼树是一个二叉树，是可以将一些字节重新编码 ，而且能够使用最少的空间。所以也叫最优二叉树。

  • 比如这段字符串

    damainnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaaaayikunnnnnnnnnnnnnnnaaaaaaaaaa

    这是100个字节。但是如果你构造一个表如下：

    haffuman_map haffuman_table[]=
{
	{'n',0b0},
	{'a',0b10},
	{'d',0b11100},
	{'i',0b1101},
	{'y',0b1111},
	{'u',0b11101},
	{'m',0b11001},
	{'k',0b11000},
};

    看出，n只需要一个bit就可以，a只需要两个bit。

    使用这个表压缩这段字符串之后有多大呢？

在这里插入图片描述

压缩之后只有25个字节了。

具体如何压缩，看这里。

二、如何构造哈夫曼树

  • 我也没想到什么好的表达，就把大话数据结构中的描述搬运一下。

    在这里插入图片描述

  • 简单的说，就是不断的找表中权值最小的两个节点，取出来放在最下面，然后把两个节点的权值相加，再放到表中。然后再次排序，取出最小的两个节点。以此类推。直到只有一个节点了，就是根节点。

三、一些问题？

  • 什么是权值？

    在例子中，就是这个字符出现的频率。频数。出现的越多，权值越大。

    这里是100个字节，'n’字符出现了55次，权就是55。

  • 有了哈夫曼树，如何获得编码呢？

    ​ 在这里插入图片描述

    将路径左边定义为0，右边定义为1。然后走过的路径就是编码方式。图中D的编码方式就是00，A的编码方式就是01。

四、抽象

  • 解决问题要分两步，第一步是构建haffuman树。会用到排序算法。我是搬运了我之前写的希尔排序。

    HaffumanNode *CreateHaffumanTree(HaffumanNode **ppArr,int iArrLen)
{
    HaffumanNode *pSmallNode1 = NULL;
    HaffumanNode *pSmallNode2 = NULL;
    HaffumanNode *pNewNode = NULL;
    /*获取数组的有效长度，只有1 的时候，就直接返回*/
    while(GetHaffumanArrEffectiveLen(ppArr,iArrLen) > 1)
    {
        /*先对数组进行排序*/
        ShellSort(ppArr,iArrLen);
        //PrintHaffumanArr(ppArr,iArrLen);
        /*取出最小的两个*/
        pSmallNode1 = ppArr[0];
        pSmallNode2 = ppArr[1];
        
        /*给最小的两个节点创建一个根节点，建立父子关系*/
        pNewNode = CreateHaffumanNode();
        if(pNewNode == NULL)
        {
            return NULL;
        }
        pNewNode->left = pSmallNode1;
        pNewNode->right = pSmallNode2;
        pNewNode->weight = pSmallNode1->weight + pSmallNode2->weight;
        pSmallNode1->parent = pNewNode;
        pSmallNode2->parent = pNewNode;
        
        /*将数组的最小两个节点位置设置成空，并且将新的父节点赋值*/
        SetHaffumanArrNthValue(ppArr,iArrLen,0,NULL);
        SetHaffumanArrNthValue(ppArr,iArrLen,1,pNewNode);
    }
    return pNewNode;
}

  • 第二步是计算路径。因为经历的路径就是这个叶子节点的编码方式。

    哈夫曼树其实就是二叉树，使用先序遍历，中序遍历，后续遍历都可以。

    和普通的遍历不同的是，需要记录下路径。

    我这里使用一个栈来解决这个问题。

    int CreateHaffumanTable(HaffumanNode *head,HaffumanStack *pStack)
{
	/*如果是叶子节点，打印当前的路径，并且返回*/
	if(head->left == NULL && head->right == NULL)
	{
		printf("weight=%d,value=%c\n",head->weight,head->value);
		StackPrint(pStack);
		return -1;
	}
	/*如果路径是在左边，就入栈一个1*/
	StackPush(pStack,'1');
    CreateHaffumanTable(head->left,pStack);
	StackPop(pStack);
	
	/*如果路径是在右边，就入栈一个0*/
	StackPush(pStack,'0');
    CreateHaffumanTable(head->right,pStack);
	StackPop(pStack);
	return 0;
}

五、整理

  • 完整代码

    #include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_HAFFUMAN_CHAR_TYPE (8)
#define MAX_HAFFUMAN_STACK_SIZE (128)

typedef struct HaffumanNode
{
    struct HaffumanNode *parent;
    struct HaffumanNode *left;
    struct HaffumanNode *right;
    int weight;
    int value;
}HaffumanNode;

typedef struct HaffumanCharMap
{
    char chr;
    int weight;
}HaffumanCharMap;

typedef struct HaffumanStack
{
	int qty;
	int size;
	char table[MAX_HAFFUMAN_STACK_SIZE+1];
}HaffumanStack;

HaffumanStack stack;

HaffumanCharMap  gMapList[MAX_HAFFUMAN_CHAR_TYPE] = 
{
    {'n',55},  
    {'a',38},
    {'i',2},
    {'d',1},
    {'m',1},
    {'y',1},
    {'k',1},
    {'u',1},
};

HaffumanNode *HaffumanArr[MAX_HAFFUMAN_CHAR_TYPE] = {NULL};

int StackInit(HaffumanStack *pStack)
{
	pStack->qty = 0;
	pStack->size = MAX_HAFFUMAN_STACK_SIZE;
	memset(pStack->table,0x00,pStack->size);
	return 0;
}

/*栈是否为空*/
int StackIsEmpty(HaffumanStack *pStack)
{
	if(pStack == NULL)
	{
		return 1;
	}
	return pStack->qty == 0;
}

/*栈是否满了*/
int StackIsFull(HaffumanStack *pStack)
{
	if(pStack == NULL)
	{
		return 1;
	}
	return pStack->qty == pStack->size;
}

/*入栈*/
int StackPush(HaffumanStack *pStack,char value)
{
	if(StackIsFull(pStack))
	{
		return -1;
	}
	pStack->table[pStack->qty] = value;
	pStack->qty++;
	return 0;
}

/*出栈*/
char StackPop(HaffumanStack *pStack)
{
	if(StackIsEmpty(pStack))
	{
		return 0;
	}
	char value = pStack->table[pStack->qty-1];
	pStack->table[pStack->qty-1] = '\0';
	pStack->qty--;
	return value;
}

/*打印当前栈区内容*/
int StackPrint(HaffumanStack *pStack)
{
	if(pStack == NULL)
	{
		return -1;
	}
	printf("route is %s\n",pStack->table);
	return 0;
}

/*按照权值排序，如果是空的，则放到最后面*/
int compare(HaffumanNode *a,HaffumanNode *b)
{
    if(a == NULL && b == NULL)
    {
        return 0;
    }
    
    if(a == NULL && b)
    {
        return 1;
    }
    if(a && b==NULL)
    {
        return -1;
    }
    
    if(a->weight > b->weight)
    {
        return 1;
    }
    
    if(a->weight == b->weight)
    {
        return 0;
    }

    return -1;

}

int swap(HaffumanNode **a,HaffumanNode **b)
{
    HaffumanNode *tmp = *a;
    *a = *b;
    *b = tmp;
    return 0;
}

int InsertSort(HaffumanNode **ppArr,int iArrLen,int gap)
{
    int i = 0;
    int j = 0;
    //每个成员都可能是那个3.
    for(i=0;i<iArrLen;i=i+gap)
    {
        //从3的位置往前找。
        for(j=i;j>0;j=j-gap)
        {
            if(compare(ppArr[j],ppArr[j-gap]) < 0)
            {
                //还需继续前移
                swap(&ppArr[j],&ppArr[j-gap]);
            }
            else
            {
                break;
            }
        }
    }
}


int ShellCalculateGap(int src_gap)
{
    return src_gap/2;
}

int ShellSort(HaffumanNode **ppArr,int iArrLen)
{
    int gap = ShellCalculateGap(iArrLen);
    //第一次的gap是 iArrLen/2，算出来的。
    while(gap)
    {
        //使用间距为gap跳着插入，做预处理。如果间距是1了，就会做插入排序。然后就退出了。
        InsertSort(ppArr,iArrLen,gap);
        //重新调整间距
        gap = ShellCalculateGap(gap);
    }
    return 0;
}


HaffumanNode *CreateHaffumanNode()
{
    HaffumanNode *pNode = malloc(sizeof(HaffumanNode));
    if(pNode == NULL)
    {
        return NULL;
    }
    memset(pNode,0x00,sizeof(HaffumanNode));
    return pNode;
}


int DestroyHaffumanNode(HaffumanNode *pNode)
{
    if(pNode)
    {
        free(pNode);
    }
    return 0;
}


int InitHaffumanArr()
{
    int i = 0;
    HaffumanNode *p = NULL;
    for(i = 0;i < sizeof(gMapList)/sizeof(gMapList[0]);i++)
    {
        p = CreateHaffumanNode();
        if(p == NULL)
        {
            exit(1);
        }
        p->left = NULL;
        p->right = NULL;
        p->parent = NULL;
        p->weight = gMapList[i].weight;
        p->value = gMapList[i].chr;
        HaffumanArr[i] = p;
    }
    return 0;
}


int SetHaffumanArrNthValue(HaffumanNode **ppArr,int iArrLen,int index,HaffumanNode *pNode)
{
    if(ppArr == NULL || index < 0 || index >= iArrLen)
    {
        return -1;
    }
    ppArr[index] = pNode;
    return 0;
}


int GetHaffumanArrEffectiveLen(HaffumanNode **ppArr,int iArrLen)
{
    int i = 0;
    int len = 0;
    for(i = 0; i < iArrLen; i++)
    {
        if(ppArr[i] != NULL)
        {
            len++;
        }
    }
    return len;
}

int PrintHaffumanArr(HaffumanNode **ppArr,int iArrLen)
{
    int i = 0;
    for(i = 0; i < iArrLen && ppArr[i] != NULL;i++)
    {
        printf("ppArr[%d].weight=%d,value=%c\n",i,ppArr[i]->weight,ppArr[i]->value);
    }
    return 0;
}

HaffumanNode *CreateHaffumanTree(HaffumanNode **ppArr,int iArrLen)
{
    HaffumanNode *pSmallNode1 = NULL;
    HaffumanNode *pSmallNode2 = NULL;
    HaffumanNode *pNewNode = NULL;
    /*获取数组的有效长度，只有1 的时候，就直接返回*/
    while(GetHaffumanArrEffectiveLen(ppArr,iArrLen) > 1)
    {
        /*先对数组进行排序*/
        ShellSort(ppArr,iArrLen);
        //PrintHaffumanArr(ppArr,iArrLen);
        /*取出最小的两个*/
        pSmallNode1 = ppArr[0];
        pSmallNode2 = ppArr[1];
        
        /*给最小的两个节点创建一个根节点，建立父子关系*/
        pNewNode = CreateHaffumanNode();
        if(pNewNode == NULL)
        {
            return NULL;
        }
        pNewNode->left = pSmallNode1;
        pNewNode->right = pSmallNode2;
        pNewNode->weight = pSmallNode1->weight + pSmallNode2->weight;
        pSmallNode1->parent = pNewNode;
        pSmallNode2->parent = pNewNode;
        
        /*将数组的最小两个节点位置设置成空，并且将新的父节点赋值*/
        SetHaffumanArrNthValue(ppArr,iArrLen,0,NULL);
        SetHaffumanArrNthValue(ppArr,iArrLen,1,pNewNode);
    }
    return pNewNode;
}

int TravelHaffumanTree(HaffumanNode *head)
{
    if(head == NULL)
    {
        return 0;
    }
    printf("weight=%d,value=%c\n",head->weight,head->value);
    TravelHaffumanTree(head->left);
    TravelHaffumanTree(head->right);
    return 0;
}

int CreateHaffumanTable(HaffumanNode *head,HaffumanStack *pStack)
{
	/*如果是叶子节点，打印当前的路径，并且返回*/
	if(head->left == NULL && head->right == NULL)
	{
		printf("weight=%d,value=%c\n",head->weight,head->value);
		StackPrint(pStack);
		return -1;
	}
	/*如果路径是在左边，就入栈一个1*/
	StackPush(pStack,'1');
    CreateHaffumanTable(head->left,pStack);
	StackPop(pStack);
	
	/*如果路径是在右边，就入栈一个0*/
	StackPush(pStack,'0');
    CreateHaffumanTable(head->right,pStack);
	StackPop(pStack);
	return 0;
}

int main(int argc, const char *argv[])
{
	/*初始化一个栈*/
	HaffumanStack stack;
	StackInit(&stack);
	
	/*初始化哈夫曼表*/
    InitHaffumanArr();
    
	/*创建哈夫曼树*/
	HaffumanNode *head = CreateHaffumanTree(HaffumanArr,MAX_HAFFUMAN_CHAR_TYPE);
    
	/*创建的haffuman table*/
    CreateHaffumanTable(head,&stack);
	return 0;
}

六、方法记忆

  • 计算二叉树路径，可以 配合一个栈来解决。

七、参考

  • https://blog.csdn.net/qq_29519041/article/details/81428934
  • 《大话数据结构》
评论 1
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值