【数据结构】第5章树和二叉树实验7：哈夫曼树

「爱情、让人受尽委屈。」 2022-11-29 03:08 134阅读 0赞

【哈夫曼树】实验报告+完整代码

--------------------

题目: 哈夫曼树

## 一、实验目的和要求 ##

（1）熟悉C++的上机环境，进一步掌握C++的结构特点；  
（2）掌握哈夫曼树。

## 二、实验环境 ##

Windows10, CodeBlocks.

## 三、实验内容及实施 ##

【实验内容】  
实验7：已知某系统在通信联络中只可能出现n种字符，其概率从键盘输入。试创建哈夫曼树。  
要求:  
1、从键盘输入n, 以及n个字符的概率。  
例如：已知某系统在通信联络中只可能出现n种字符，其概率分别为 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，试设计哈夫曼编码创建哈夫曼树。  
2、用顺序存储。  
3、输出结果如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]

【程序流程】

#include <bits/stdc++.h>
    using namespace std;
    
    int n, m, s1, s2;
    typedef struct HTNode
    {
        
        int weight, parent, lchild, rchild, pos;
        bool operator<(const HTNode &a)const
       {
        
           return a.weight < weight;
       }
    }HTNode, *HuffmanTree;
    
    priority_queue<HTNode>P;
    
    void Select(HuffmanTree &HT, int ii, int &s1, int &s2)
    {
        
        HTNode t = P.top();
        s1 = t.pos;
        P.pop();
        t = P.top();
        s2 = t.pos;
        P.pop();
    }
    
    void CreateHuffmantree(HuffmanTree &HT, int n)
    {
        
        if(n <= 1)
            return;
        m = 2 * n - 1;
        HT = new HTNode[m + 1];
        for(int i = 1; i <= m; i++)
        {
        
            HT[i].parent = 0;
            HT[i].lchild = 0;
            HT[i].rchild = 0;
        }
        for(int i = 1; i <= n; ++i)
        {
        
            cin >> HT[i].weight;
            HT[i].pos = i;
            P.push(HT[i]);
        }
        for(int 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;
            HT[i].pos = i ;
            P.push(HT[i]);
        }
    }
    
    int main()
    {
        
        HuffmanTree HT;
        cout << "开始构建哈夫曼树" << '\n' << "请输入哈夫曼树的叶子结点个数：";
        cin >> n;
        cout << "请输入每个叶子结点的权值：" << '\n';
        CreateHuffmantree(HT, n);
        for(int i = 1; i <= 2 * n - 1; ++i)
        {
        
            cout << "结点序号 " << i << " 权重 " << HT[i].weight
            << " parent " << HT[i].parent << " lchild " << HT[i].lchild
            << " rchild " << HT[i].rchild << '\n';
        }
        return 0;
    }
    /*
    8
    5 29 7 8 14 23 3 11
    */

## 四、实验结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 1]

## 五、实验讨论 ##

（1）熟悉了C++的上机环境，进一步掌握C++的结构特点；  
（2）掌握了哈夫曼树。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/6bea957216a947749c7a1747408cd788.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/401048c7c18e4372a061b2075b9bf4c0.png