梦里京华

用户名：508304482

访问量：8697

签　名：

等　　级
排　　名	876
经　　验	3561
参赛次数	4
文章发表	18
年　　龄	0
在职情况	学生
学　　校	XJTU
专　　业

　　自我简介：

TA的其他文章

数据结构-平衡二叉树的基本操作-题解(C++代码)
浏览：505

数据结构-行编辑程序-题解(C++代码)
浏览：345

数据结构-表达式求值-题解(C++代码)
浏览：289

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

数据结构-自底向上的赫夫曼编码-题解(C++代码)

　　作者: 梦里京华　　　　发表时间：2020-03-13 20:16:32 浏览：828　|　评论：0　

原题链接：数据结构-自底向上的赫夫曼编码

```cpp
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Node
{
    int weight = 0;
    int parent = 0;
    int lchild = 0;
    int rchild = 0;
};
typedef Node *PN;
void select(PN &pn, int e, int &s1, int &s2);
void init(PN &pn, int &n);
void createTHTree(PN &pn, int n);
void coding(PN &pn, int n, vector<string> &v);
void tranverse(vector<string> &v);
int main()
{
    PN pn;
    int n;
    vector<string> v;
    init(pn, n);
    createTHTree(pn, n);
    coding(pn, n, v);
    tranverse(v);
    delete [] pn;
    system("pause");
    return 0;
}

void init(PN &pn, int &n)
{
    cin >> n;
    pn = new Node[2 * n];
    for (int i = 1; i <= n; ++i)
    {
        cin >> pn[i].weight;
    }
}

void createTHTree(PN &pn, int n)
{
    int s1, s2;
    for (int i = n + 1; i <= 2 * n - 1; ++i)
    {
        select(pn, i - 1, s1, s2);
        pn[s1].parent = i;
        pn[s2].parent = i;
        pn[i].lchild = s1;
        pn[i].rchild = s2;
        pn[i].weight = pn[s1].weight + pn[s2].weight;
    }
}

void select(PN &pn, int e, int &s1, int &s2)
{
    int i = 1;
    while (pn[i].parent&&i<=e)//注意是pn[i].parent而不是！pn[i].parent
    {
        ++i;
    }
    s1 = i++;
    while (pn[i].parent&&i<=e)
    {
        ++i;
    }
    s2 = i++;
    if (pn[s1].weight > pn[s2].weight)//注意这里的判断条件是pn[s1].weight > pn[s2].weight而不是s1>s2;
    {
        int t;
        t = s1;
        s1 = s2;
        s2 = t;
    }
    for (; i <= e; ++i)
    {
        if (pn[i].parent)
            continue;
        else
        {
            if (pn[i].weight < pn[s1].weight)
            {
                s2 = s1;
                s1 = i;
                continue;//注意如果不加continue，会影响 else if (pn[i].weight < pn[s2].weight)的判断。
            }
            else if (pn[i].weight < pn[s2].weight)
                s2 = i;
        // 不能写成pn[i].weight > pn[s2].weight&&pn[i].weight < pn[s2].weight.
        //要考虑pn[i].weight == pn[s2].weight的情况。
        }
    }
    if (s1 > s2)
    {
        int t = s2;
        s2 = s1;
        s1 = t;
    } //让下标小的为s1,而不是权重小的为s1。从而使左孩子为下标小的，而不是权重小的。参考书上149页。
}

void coding(PN &pn, int n, vector<string> &v)
{
    for (int i = 1; i <= n; ++i)
    {
        string str;
        int j = i;
        int k = pn[i].parent;
        while (k)
        {
            pn[k].lchild == j ? str += "0" : str += "1";
            j = k;
            k = pn[k].parent;
        }
        reverse(str.begin(),str.end());
        v.push_back(str);
    }
}

void tranverse(vector<string> &v)
{
    int len = v.size();
    for (int i = 0; i < len; ++i)
    {
        cout << v[i] << endl;
    }
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

梦里京华

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-分段函数（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

第一

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

数据结构-自底向上的赫夫曼编码-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C二级辅导-计负均正（C语言代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

1011题解

陶陶摘苹果2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

母牛的故事（C语言代码）

明明的随机数（C语言代码）

梦里京华

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-分段函数 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

第一

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

数据结构-自底向上的赫夫曼编码-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C二级辅导-计负均正 （C语言代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

1011题解

陶陶摘苹果2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

母牛的故事 （C语言代码）

明明的随机数 （C语言代码）

C二级辅导-分段函数（C语言代码）

　　评论区

C二级辅导-计负均正（C语言代码）

母牛的故事（C语言代码）

明明的随机数（C语言代码）