尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:240
已运行时间:
目录
  1. 实验内容
  2. 实验要求
  3. 实验代码
  4. 实验结果

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:240
已运行时间:

实验内容

已知某系统在通信联络中只可能出现 n 种字符,其概率从键盘输入。试创建哈夫曼树。

实验要求

1、从键盘输入 n, 以及 n 个字符的概率。
例如:已知某系统在通信联络中只可能出现 n 种字符,其概率分别为   0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11,试设计哈夫曼编码创建哈夫曼树。
2、用顺序存储。
3、输出结果如下
 image.png
交作业时间:下次上机前

实验代码

#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 << "请输入哈夫曼树的叶子结点个数:";
    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';
    }
}

实验结果

image.png

博客内容遵循: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/fyhtb2/

编辑: 部署: 订阅:

评论区

Twikoo 转换 utterances

最新评论

Loading...