哈夫曼树的C语言详解

简介: 哈夫曼树的C语言详解


哈夫曼树的C语言详解
1)一些名词的解释:
路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。
路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。
结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积
2)哈夫曼树的定义:
当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”。

在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。在图 1 中,因为结点 a 的权值最大,所以理应直接作为根结点的孩子结点。
3)构造过程:
对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:
在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。
4)算法实现:
构建哈夫曼树时,需要每次根据各个结点的权重值,筛选出其中值最小的两个结点,然后构建二叉树。

查找权重值最小的两个结点的思想是:从树组起始位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:
如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;
如果介于两个结点权重值之间,替换原来较大的结点;


#include<iostream>
#include<string.h>
#define  MAX 10000 
/*
请输入一段文字:this*program*is*my*favourite
字符和权值信息如下
字符:t  权值:2
字符:h  权值:1
字符:i  权值:3
字符:s  权值:2
字符:*  权值:4
字符:p  权值:1
字符:r  权值:3
字符:o  权值:2
字符:g  权值:1
字符:a  权值:2
字符:m  权值:2
字符:y  权值:1
字符:f  权值:1
字符:v  权值:1
字符:u  权值:1
字符:e  权值:1
********************************
字符编码为:
t:1000
h:11010
i:001
s:1001
*:011
p:11011
r:010
o:1010
g:11100
a:1011
m:1100
y:11101
f:11110
v:11111
u:0000
e:0001
文字编码为:
100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001
********************************
译码:
请输入要译码的二进制字符串,输入'#'结束:100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001#
译码为:
this*program*is*my*favourite
是否继续?(Y/N):
*/
using namespace std;
typedef struct {
    char letter, *code;
    int weight;
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;
int n;
char coding[100];
int Min(HuffmanTree &HT, int i)
{
    int j;
    unsigned int k = MAX;
    int flag;
    for (j = 0; j <= i; ++j)
    {
        if (HT[j].weight < k && HT[j].parent == 0)//用父结点是否为0来判断此结点是否已经被选过  
        {
            k = HT[j].weight;
            flag = j;
        }
    }
    HT[flag].parent = 1;//作个标记,说明已经被选择了,因为在Select函数中要选择权值小的两个结点  
    return flag;
}
void Select(HuffmanTree &HT, int i, int &s1, int &s2)
{
    //在HT[1...i]中选择parent为0且权值最小的两个结点,其序号分别为s1,s2  
    //s1 <= s2  
    s1 = Min(HT, i);
    s2 = Min(HT, i);
}
void CreateHuffmanTree(HuffmanTree &HT, char t[], int w[])
{
    int m;
    int i, s1, s2;
    if (n <= 1)
        return;
    m = 2 * n - 1; //总共需要2n-1个节点
    HT = new HTNode[m + 1];//开辟空间
    for (i = 0; i<n; i++)
    {
        HT[i].code = '\0';
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].letter = t[i];
        HT[i].weight = w[i];
    }
    for (i = n; i <= m; i++)
    {
        HT[i].code = '\0';
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].letter = ' ';
        HT[i].weight = 0;
    }
    cout << "********************************" << endl;
    for (i = n; i<m; i++)
    {
        Select(HT, i - 1, s1, s2);//在n个数中找出权值最小的两个

        HT[s1].parent = i;
        HT[s2].parent = i;//将他们两个的parent节点设置为i;

        HT[i].lchild = s1;
        HT[i].rchild = s2;//把这两个分别当作左右节点
        HT[i].weight = HT[s1].weight + HT[s2].weight;//他们两个的双亲为他们两个的和;

    }
}
void CreatHuffmanCode(HuffmanTree HT)
{
    int start, c, f;
    int i;
    char *cd = new char[n];
    cd[n - 1] = '\0';
    cout << "字符编码为:" << endl;
    for (i = 0; i<n; i++)
    {
        start = n - 1;
        c = i;
        f = HT[i].parent;
        while (f != 0){
            --start;
            if (HT[f].lchild == c){
                cd[start] = '0';
            }
            else{
                cd[start] = '1';
            }
            c = f;
            f = HT[f].parent;
        }
        HT[i].code = new char[n - start];
        strcpy(HT[i].code, &cd[start]);
        cout << HT[i].letter << ":" << HT[i].code << endl;
    }
    delete cd;
}
void HuffmanTreeYima(HuffmanTree HT, char cod[], int b)           //译码
{
    char sen[100];
    char temp[50];
    char voidstr[] = " ";       //空白字符串
    int t = 0;
    int s = 0;
    int count = 0;
    for (int i = 0; i<b; i++)
    {
        temp[t++] = cod[i];     //读取字符
        temp[t] = '\0';        //有效字符串
        for (int j = 0; j<n; j++){        //依次与所有字符编码开始匹配
            if (!strcmp(HT[j].code, temp)){                //匹配成功
                sen[s] = HT[j].letter;    //将字符保存到sen中
                s++;
                count += t;
                strcpy(temp, voidstr);                //将TEMP置空 
                t = 0;          //t置空
                break;
            }
        }
    }
    if (t == 0){     //t如果被置空了,表示都匹配出来了,打印译码
        sen[s] = '\0';
        cout << "译码为:" << endl;
        cout << sen << endl;
    }
    else{                             //t如果没有被置空 , 源码无法被完全匹配
        cout << "二进制源码有错!从第" << count + 1 << "位开始" << endl;
    }
}
int main()
{
    HuffmanTree HT;
    char a[100], buff[1024], p;//a为存放字符 buff为输入的字符串 p为输入译码时的字符 
    int b[100];//存放权值信息 
    int i, j;
    int symbol = 1, x, k; //译码时做判断用的变量  
    cout << "请输入一段文字:";
    cin >> buff;
    int len = strlen(buff);
    for (i = 0; i<len; i++)
    {
        for (j = 0; j<n; j++)
        {
            if (a[j] == buff[i])
            {
                b[j] = b[j] + 1;
                break;
            }
        }
        if (j >= n)
        {
            a[n] = buff[i];
            b[n] = 1;
            n++;
        }
    }
    cout << "字符和权值信息如下" << endl;
    for (i = 0; i<n; i++)
    {
        cout << "字符:" << a[i] << "  权值:" << b[i] << endl;
    }
    CreateHuffmanTree(HT, a, b);
    CreatHuffmanCode(HT);
    cout << "文字编码为:\n";
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (buff[i] == HT[j].letter)
            {
                cout << HT[j].code;
                break;
            }
        }
    }
    cout <<endl<< "********************************" << endl;
    cout << "译码:" << endl;
    while (1)
    {
        cout << "请输入要译码的二进制字符串,输入'#'结束:";
        x = 1;//判断是否有非法字符只能是0 1 
        k = 0;//作为循环变量来使coding【k】=输入的字符 
        symbol = 1;//判断是否输入结束 
        while (symbol){
            cin >> p;
            if (p != '1'&&p != '0'&&p != '#'){ //若存在其它字符,x设为0,表示输入的不是二进制
                x = 0;
            }
            coding[k] = p;
            if (p == '#')
                symbol = 0;  //#号结束标志
            k++;
        }
        if (x == 1){
            HuffmanTreeYima(HT, coding, k - 1);        //进行译码
        }
        else{
            cout << "有非法字符!" << endl;
        }
        cout << "是否继续?(Y/N):";
        cin >> p;
        if (p == 'y' || p == 'Y')
            continue;
        else
            break;
    }
    return 0;
}

相关文章
|
18天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
30 3
|
9天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
28 10
|
3天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
8天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
32 7
|
8天前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
22 4
|
13天前
|
存储 编译器 C语言
C语言函数的定义与函数的声明的区别
C语言中,函数的定义包含函数的实现,即具体执行的代码块;而函数的声明仅描述函数的名称、返回类型和参数列表,用于告知编译器函数的存在,但不包含实现细节。声明通常放在头文件中,定义则在源文件中。
|
19天前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
29 2
|
21天前
|
Java 编译器 C语言
【一步一步了解Java系列】:Java中的方法对标C语言中的函数
【一步一步了解Java系列】:Java中的方法对标C语言中的函数
18 3
|
24天前
|
存储 程序员 编译器
C语言——动态内存管理与内存操作函数
C语言——动态内存管理与内存操作函数
|
24天前
|
C语言
C语言字符(串)函数
C语言字符(串)函数