C++ 哈夫曼编码

发布时间: 更新时间: 总字数:1960 阅读时间:4m 作者: IP上海 分享 网址
专栏文章
  1. 顺序表的基本操作
  2. 链表
  3. C++ 单链表的基本操作
  4. 栈和队列的基本操作
  5. C++ 二叉树的基本操作
  6. 图的基本操作
  7. C++ 哈夫曼编码(当前)
  8. C++ 排序的基本操作
  9. C++ 双向链表的基本操作
  10. 顺序表的基本操作
  11. MFC中如何用ADO连接SQL Server 2005
  12. MFC使用ADO连接SQL Server数据库
  13. VC6 MFC中ClassView视图中无法显示某个类的问题
  14. rose生成C++源代码
  15. 解决<compilation debug="true" targetFramework="4.0"> 问题
  16. Cpp
  17. Cpp
  18. LLVM/Clang 介绍
  19. CMake 使用介绍

哈夫曼编码

实验六:哈夫曼编码

已知某系统在通信联络中只可能出现8种字符,其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计哈夫曼编码。

综合训练:试编写一个将百分制分数转换为五级分制的程序。要求其时间性能尽可能好(即平均比较次数尽可能少)。假设学生成绩的分布情况如下:

分数 0-59 60-69 70-79 80-89 90-100
比例 0.05 0.15 0.4 0.3 0.1

源码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR 0
#define OK 1

typedef int Status;
typedef struct  //声明赫夫曼树的结点
{
    int weight;
    int parent;
    int lchild;
    int rchild;
} Htnode, *Huffmantree;

typedef char ** Huffmancode;//相当于声明一个二维数组,来记录每个权值对应的编码。

void Select (Huffmantree &HT, int t, int &p, int &q); //选择结点中权值最小的两个结点,用p,q来返回。

void creathuffmantree(Huffmantree &HT, Huffmancode &HC, int *w, int n) //创建赫夫曼树。

{
    int m, i, p, q, j, start, s;
    if (n <= 1)
        return;
    m = 2 * n - 1; //当n大于1时,就需要2*n-1个结点
    HT = (Huffmantree)malloc(sizeof(Htnode) * (m + 1)); //因为0不存东西,而从1开始存,所以申请m+1个空间。
    for (i = 1; i <= n; i++) //对叶子结点进行初始化,除权之外全赋值为0。
    {
        HT[i].weight = w[i - 1];
        HT[i].parent = 0;
        HT[i].rchild = 0;
        HT[i].lchild = 0;
    }
    for (i = n + 1; i <= m; i++) //对非叶子结点进行初始化,所有的值全为0
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].rchild = 0;
        HT[i].lchild = 0;
    }

    for (i = n + 1; i <= m; i++) //这是创建树的主要步骤,找出权值和最小的两棵树,再把它们合并成一棵树,依次进行,知道走后还剩仅有的一棵树。
    {
        Select(HT, i - 1, p, q); //这是选择权值最小的两棵树的函数,并用p,q来返回,在上面已经声明过。
        HT[i].weight = HT[p].weight + HT[q].weight; //对刚合并的新树的根结点的权值进行赋值。
        HT[i].lchild = p; //新树的左孩子赋为p;
        HT[i].rchild = q; //新树的右孩子赋为q;
        HT[p].parent = i; //把他们的双亲都赋为i;
        HT[q].parent = i;
    }

    HC = (Huffmancode)malloc(sizeof(char*) * (n + 1)); //申请一个大小为n+1的存放指针的数组。
    char* cd = (char*)malloc(sizeof(char) * n); //申请一个一维数组,作为一个中转站,最后把他复制到HC中的一个数组中。
    for (i = 1; i <= n; i++) //对赫夫曼树的数组从1到n进行依次遍历,这是从叶子结点到根节点。
    {
        start = n - 1; //对这个一位数组进行倒着存,最后正着读取。
        cd[start] = '\0';
        s = i;
        while (HT[s].parent != 0)
        {
            j = s;
            s = HT[s].parent;
            if (HT[s].lchild == j) //如果该结点是双亲结点的左孩子,应该把它赋为0;
                cd[--start] = '0';
            if (HT[s].rchild == j) //如果该结点是双亲结点的右孩子,应该把它赋为1;

                cd[--start] = '1';

        }

        HC[i] = (char *)malloc(sizeof(char) * (n - start));

        strcpy(HC[i], &cd[start]); //把cd数组里的内容复制到HC[i]里,再用cd去盛其他的编码。

    }

    free(cd);//最后可以把cd数组给释放了。

}

void Select (Huffmantree & HT, int t, int &min1, int &min2) //选择结点中权值最小的两个结点,用p,q来返回。

{

    int i = 1, flag = 0;

    while (flag < 2) //这个while循环是为了找出前两棵树的根结点,把他们当成最小的两棵树,以后来做比较,求出最小的两个。

    {

        if (HT[i].parent != 0) //如果不是根结点,继续朝后找,直到找到根结点。

            i++;

        else//如果是根结点,就把他们分别赋给min1和min2.
        {
            if (flag == 0)
                min1 = i;
            else
                min2 = i;
            flag++;
            i++;
        }
    }

    if (HT[min1].weight > HT[min2].weight) //对min1和min2进行比较,把最小的的付给min1,第二小的付给min2.

    {

        t = min1;

        min1 = min2;

        min2 = t;

    }

    while (i <= t) //把以后的各个结点的权值与最小的两个比较,调整下,最后得出的就是最小的两个结点。

    {

        if (HT[i].parent != 0) //如果不是根结点,继续朝后找,直到找到根结点。

            i++;

        else

        {

            if (HT[i].weight <= HT[min1].weight) //如果该结点的权值比最小的结点还小,把最小的两个全重新赋值。

            {

                min2 = min1;

                min1 = i;

            }

            else if (HT[i].weight >= HT[min1].weight && HT[i].weight <= HT[min2].weight) //如果该结点的权值在最小和第二小之间的话,

                //就把第二小的重新赋值。

                min2 = i;

            i++;

        }

    }



}

Status exhuffmantree(Huffmantree &HT, int  m, char *code, int *ex, int &j) //这是解码的函数,m为那棵树的根结点,code是输入的赫夫曼码,

//解码后最后给他存到ex数组中,j为数组的长度。

{

    int i = 0, k = m;

    while (code[i] != '\0') //从根结点到叶子节点去匹配,输出最后的那个权值

    {

        if (code[i] == '0' && HT[k].lchild != 0) //如果code[i]是0,并且左孩子不为0,则继续朝叶子结点找。

        {

            k = HT[k].lchild;

            i++;

        }

        else if (code[i] == '1' && HT[k].rchild != 0) //如果code[i]是1,并且右孩子不为0,则继续朝叶子结点找。

        {

            k = HT[k].rchild;

            i++;

        }

        else if (HT[k].rchild == 0 && HT[k].lchild == 0) //如果是叶子结点,则把它的权值赋给ex[j].

        {

            ex[j] = HT[k].weight;

            j++;

            k = m;

        }

        else//其他的则返回ERROR。

            return ERROR;

    }

    if (HT[k].rchild == 0 && HT[k].lchild == 0) //当跳出循环的时候,说明应该到了叶子结点,如果是叶子结点,则把它的权值赋给ex[j].

    {

        ex[j] = HT[k].weight;

        return OK;

    }

    else//其他的则返回ERROR。

        return ERROR;

}

int main()
{
    Huffmantree HT;
    Huffmancode HC;
    char Code[100];
    int i, n, a[100], b[100], j = 0, t;
    printf("输入叶子结点的个数n为:\n");
    scanf("%d", &n);
    printf("依次输入n个叶子结点的权值为:\n");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    creathuffmantree(HT, HC, a, n);
    printf("输出该赫夫曼树各个叶子结点的编码为:\n");
    for (i = 1; i <= n; i++)
    {
        t = 0;
        while (HC[i][t] != '\0')
        {
            printf("%c", HC[i][t]);
            t++;
        }
        putchar(' ');
    }
    putchar('\n');
    getchar();
    printf("输入该赫夫曼树关联的要译码的code数组:\n");
    gets(Code);

    exhuffmantree(HT, 2 * n - 1, Code, b, j);
    printf("输出解码后的各权值为:\n");
    for (i = 0; i <= j; i++)
        printf("%d ", b[i]);
    putchar('\n');
    return 0;

}
Home Archives Categories Tags Statistics
本文总阅读量 次 本站总访问量 次 本站总访客数