数据结构合集 - Drawrain's Blog

数据结构实践#

实践一#

A. 新朋友人数#

题目描述#

新年快到了，天勤准备搞一个聚会。已经知道现有会员 N 人，把会员从 1 到 N 编号，其中会长的号码是 N 号。

凡是和会长是老朋友的，那么该会员的号码肯定和 N 有大于 1 的公约数，否则都是新朋友。

现在会长想知道究竟有几个新朋友，请编程计算。

本题本质是求欧拉函数 phi(N)，也就是小于 N 且与 N 互质的正整数个数。

输入#

第一行是测试数据的组数 CN，接着有 CN 行正整数 N，表示会员人数。

输出#

对于每一个 N，输出一行新朋友的人数。

样例输入#

样例输出#

解题思路#

如果一个编号 x 和会长编号 N 互质，即：

1
gcd(x, N) = 1

那么这个人就是新朋友

因此答案就是欧拉函数 phi(N)

因为题目中 N < 32768，可以提前预处理出所有 phi 值。初始化时令 phi[i] = i，然后用筛法枚举质因子，遇到质因子 p 时更新：

1
phi[j] = phi[j] / p * (p - 1)

最终代码#

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
int main(){
5
    const int max = 32768;
6
    vector<int> p(max +1);
7
    for(int i = 0; i <= max; i++){
8
        p[i] = i;
9
    }
10
    p[1] = 1;
11
    for(int i = 2; i <= max; i++){
12
        if(p[i] == i){
13
            for(int j = i; j <= max; j += i){
14
                p[j] = p[j] / i * (i - 1);
15
            }
16
        }
17
    }
18
    int cn;
19
    cin >> cn;
20
    while (cn--){
21
        int n;
22
        cin >> n;
23
        cout << p[n] << endl;
24
    }
25
    return 0;
26
}

B. 互质整数个数#

题目描述#

给你一个正整数 n，请问有多少个比 n 小的且与 n 互质的正整数？

两个整数互质的意思是，这两个整数没有比 1 大的公约数。

输入#

输入包含多组测试数据。

每组输入是一个正整数 n，n <= 1000000000。

当 n = 0 时，输入结束。

输出#

对于每组输入，输出比 n 小的且与 n 互质的正整数个数。

样例输入#

样例输出#

解题思路#

本题仍然是求欧拉函数 phi(n)。

不过本题的 n 最大可以到 1000000000，不能像 A 题一样预处理到 n，所以需要对每个输入的 n 单独分解质因数。

欧拉函数公式为：

1
phi(n) = n * (1 - 1 / p1) * (1 - 1 / p2) * ...

其中 p1, p2, ... 是 n 的不同质因子。

最终代码#

1
#include <iostream>
2
using namespace std;
3
#define int long long
4
int p(int n) {
5
    int ans = n;
6

7
    for (int i = 2; i * i <= n; ++i) {
8
        if (n % i == 0) {
9
            ans = ans / i * (i - 1);
10
            while (n % i == 0) {
11
                n /= i;
12
            }
13
        }
14
    }
15
    if (n > 1) {
16
        ans = ans / n * (n - 1);
17
    }
18
    return ans;
19
}
20
signed main() {
21
    int n;
22
    while (cin >> n && n != 0) {
23
        cout << p(n) << endl;
24
    }
25

26
    return 0;
27
}

C. 约瑟夫问题#

题目描述#

n 个人围成一圈，按 1 到 n 的顺序编号。

从第一个人开始报数，从 1 到 m 报数，凡报到 m 的人退出圈子，问最后留下的是原来的第几号。

输入#

首先输入两个正整数 n 和 m。

n 表示 n 个人围成一个圈子，n >= 2。

m 表示从 1 报数到 m 的人退出，1 <= m。

输出#

输出最后剩下的人的编号。

样例输入#

1
2 3

样例输出#

1
2

解题思路#

经典约瑟夫问题

用 0 开始编号时，设 f(i) 表示 i 个人时最后留下来的人的编号

递推公式为：

1
f(1) = 0
2
f(i) = (f(i - 1) + m) % i

最后题目编号从 1 开始，所以输出：

1
f(n) + 1

最终代码#

1
#include <iostream>
2
using namespace std;
3
#define int long long
4
signed main() {
5
    int n, m;
6
    cin >> n >> m;
7
    int ans = 0;
8
    for (int i = 1; i <= n; ++i) {
9
        ans = (ans + m) % i;
10
    }
11
    cout << ans + 1 << endl;
12
    return 0;
13
}

D. 十进制转 R 进制#

题目描述#

编写程序演示把一个 10 进制整数转换为 R 进制的转换结果。

超过 9 的数字符号显示为 A、B、C... 等字母。

输入#

输入正整数 N 和 R，空格分隔。

N 是输入的十进制数，R 是需要转换的进制数，2 <= R <= 20。

输出#

输出将 10 进制整数转换为 R 进制后的结果。

样例输入#

1
10 16

样例输出#

1
A

解题思路#

进制转换使用“除 R 取余法”：

每次用 N % R 得到当前最低位。
再令 N = N / R。
重复直到 N 为 0。
因为先得到的是低位，所以需要用栈逆序输出。

例如 10 转 16 进制：

1
10 % 16 = 10

10 对应十六进制字符 A。

最终代码#

1
#include <iostream>
2
#include <stack>
3
using namespace std;
4
#define int long long
5
signed main() {
6
    int n, r;
7
    cin >> n >> r;
8
    char digit[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
9
    stack<char> s;
10
    if (n == 0) {
11
        cout << 0 << endl;
12
        return 0;
13
    }
14
    while (n > 0) {
15
        s.push(digit[n % r]);
16
        n /= r;
17
    }
18
    while (!s.empty()) {
19
        cout << s.top();
20
        s.pop();
21
    }
22
    cout << endl;
23
    return 0;
24
}

E. 整数求和式的计算#

题目描述#

输入两个整数的求和式，比如 1+2=，输出求和式和对应结果。

输入#

一个求和式，形如：

1
a+b=

输出#

输出求和式及对应结果。

样例输入#

1
1+2=

样例输出#

1
1+2=3

解题思路#

输入格式固定为：

1
整数 + 整数 =

所以可以直接依次读入：

1
a、+、b、=

然后输出原式以及 a + b 的结果。

最终代码#

1
#include <iostream>
2
using namespace std;
3
#define int long long
4
signed main() {
5
    int a, b;
6
    char plus, equal;
7
    cin >> a >> plus >> b >> equal;
8
    cout << a << plus << b << equal << a + b << endl;
9
    return 0;
10
}

F. 波兰表达式#

题目描述#

波兰表达式是一种把运算符前置的算术表达式。

例如普通表达式：

1
2 + 3

它的波兰表示法为：

1
+ 2 3

波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序。

例如：

1
(2 + 3) * 4

它的波兰表示法为：

1
* + 2 3 4

本题求解波兰表达式的值，其中运算符包括 + - * / 四个。

输入#

输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。

输出#

输出为一行，表达式的值，保留 6 位小数。

样例输入#

1
* + 11.0 12.0 + 24.0 35.0

样例输出#

1
1357.000000

解题思路#

波兰表达式具有天然递归结构：

1
运算符 左表达式 右表达式

所以可以从左往右读入。

如果读到的是数字，直接返回它的值。

如果读到的是运算符，就递归计算它后面的两个表达式，然后根据运算符进行计算。

例如：

1
* + 11.0 12.0 + 24.0 35.0

可以理解为：

1
(11.0 + 12.0) * (24.0 + 35.0)

结果为：

1
23.0 * 59.0 = 1357.0

最终代码#

1
#include <iostream>
2
#include <iomanip>
3
#include <string>
4
using namespace std;
5
double solve() {
6
    string s;
7
    cin >> s;
8
    if (s == "+" || s == "-" || s == "*" || s == "/") {
9
        double a = solve();
10
        double b = solve();
11
        if (s == "+") {
12
            return a + b;
13
        }
14
        if (s == "-") {
15
            return a - b;
16
        }
17
        if (s == "*") {
18
            return a * b;
19
        }
20
        return a / b;
21
    }
22
    return stod(s);
23
}
24
signed main() {
25
    cout << fixed << setprecision(6) << solve() << endl;
26
    return 0;
27
}

G. 合并队列#

题目描述#

上体育课的时候，老师已经把班级同学排成了两个队列，而且每个队列都是按照从低到高排好队。

现在需要把两个队列合并，合并后需要保证还是从低到高排列。

请编程实现合并队列。

输入#

第 1 行为 n，表示开始排成的每个队列的长度。

第 2、3 行分别是代表从小到大的 n 个整数，每行的整数之间用一个空格间隔。

输出#

输出占一行，为从小到大的整数，每个整数之间间隔一个空格。

样例输入#

样例输出#

1
1 2 3 3 4 5 6 8 9 15

解题思路#

因为两个队列本来就是从小到大排列的，所以不需要重新排序。

每次只需要比较两个队首元素：

1
a.front()
2
b.front()

哪个小，就先输出哪个，并让它出队。

如果一个队列已经为空，就直接输出另一个队列剩下的所有元素。

最终代码#

1
#include <iostream>
2
#include <queue>
3
using namespace std;
4
#define int long long
5
signed main() {
6
    int n;
7
    cin >> n;
8
    queue<int> a, b;
9
    for (int i = 0; i < n; ++i) {
10
        int x;
11
        cin >> x;
12
        a.push(x);
13
    }
14
    for (int i = 0; i < n; ++i) {
15
        int x;
16
        cin >> x;
17
        b.push(x);
18
    }
19
    while (!a.empty() || !b.empty()) {
20
        int x;
21
        if (b.empty() || (!a.empty() && a.front() <= b.front())) {
22
            x = a.front();
23
            a.pop();
24
        } else {
25
            x = b.front();
26
            b.pop();
27
        }
28
        cout << x;
29
        if (!a.empty() || !b.empty()) {
30
            cout << ' ';
31
        }
32
    }
33
    cout << endl;
34
    return 0;
35
}

实践二#

A. 子串个数#

题目描述#

给你若干个字符串，请编程输出每个字符串的子串个数。

字符串中不含空格，长度最大为 1000。

输入#

输入包含若干个字符串。

每个字符串占一行。

输出#

对应每一行的字符串，输出该字符串子串的个数。

样例输入#

1
abc
2
apple
3
software

样例输出#

解题思路#

一个长度为 n 的字符串，非空连续子串的个数为：

1
n * (n + 1) / 2

例如长度为 3 的字符串 abc，非空子串有 6 个

但是样例中 abc 的答案是 7，说明本题把空串也算作一个子串，所以最终答案为：

1
n * (n + 1) / 2 + 1

最终代码#

1
#include <iostream>
2
#include <string>
3
using namespace std;
4
int main() {
5
    string s;
6
    while (cin >> s) {
7
        int n = s.size();
8
        cout << n * (n + 1) / 2 + 1 << endl;
9
    }
10
    return 0;
11
}

B. 模式串#

题目描述#

给你一个目标串，请查找在目标串中是否存在模式串。

如果存在，就输出第一个模式串在目标串中出现的位置。

输入#

输入占两行。

第一行是目标串，长度小于 1000。

第二行是模式串，长度小于 100。

输出#

输出模式串在目标串中出现的位置，即模式串匹配到目标串时第一个字符在目标串中的位置。

注意位置从 1 开始。

如果不能匹配，输出 0。

样例输入#

1
appleorange
2
orange

样例输出#

1
6

解题思路#

本题可以使用朴素字符串匹配

从目标串的每一个位置开始，依次和模式串中的字符进行比较

如果模式串的所有字符都能匹配成功，就说明找到了第一次出现的位置，输出当前下标加 1

如果所有位置都尝试后仍然无法匹配，则输出 0

因为目标串长度小于 1000，模式串长度小于 100，朴素匹配的复杂度完全可以通过。

最终代码#

1
#include <iostream>
2
#include <string>
3
using namespace std;
4
int main() {
5
    string s, p;
6
    cin >> s >> p;
7
    int ans = 0;
8
    for (int i = 0; i + p.size() <= s.size(); ++i) {
9
        int flag = 1;
10
        for (int j = 0; j < p.size(); ++j) {
11
            if (s[i + j] != p[j]) {
12
                flag = 0;
13
                break;
14
            }
15
        }
16
        if (flag) {
17
            ans = i + 1;
18
            break;
19
        }
20
    }
21
    cout << ans << endl;
22
    return 0;
23
}

C. 主对角线上的数据和#

题目描述#

在一个 N 行 N 列的方阵中，从左上角到右下角这一斜线上有 N 个数据元素。

这个斜线称为方阵的主对角线。

给你一个方阵，请求方阵主对角线上数据的和。

输入#

第一行是 N，表示下面是一个 N 阶方阵。

接下来 N 行，每行有 N 个用空格隔开的正整数。

输出#

输出 N 阶方阵主对角线上数据的和。

样例输入#

样例输出#

1
6

解题思路#

主对角线上的元素满足行号和列号相同

如果用 i 表示行号，j 表示列号，那么主对角线元素满足：

1
i == j

因此读入整个矩阵时，只需要把 i == j 的元素累加到答案中即可

最终代码#

1
#include <iostream>
2
using namespace std;
3
int main() {
4
    int n;
5
    cin >> n;
6
    int ans = 0;
7
    for (int i = 0; i < n; ++i) {
8
        for (int j = 0; j < n; ++j) {
9
            int x;
10
            cin >> x;
11
            if (i == j) {
12
                ans += x;
13
            }
14
        }
15
    }
16
    cout << ans << endl;
17
    return 0;
18
}

D. 顺时针排螺旋阵#

题目描述#

给你一个 N 行 N 列的方格矩阵，从外圈按顺时针依次填写自然数。

这会构成一个螺旋阵，请编程实现。

输入#

输入一个正整数 N。

其中 N < 100。

输出#

输出符合题意的螺旋阵。

样例输入#

1
5

样例输出#

1
1 2 3 4 5
2
16 17 18 19 6
3
15 24 25 20 7
4
14 23 22 21 8
5
13 12 11 10 9

解题思路#

螺旋阵的填写顺序可以看成四个方向不断循环：

1
右、下、左、上

用两个方向数组表示每次移动时行和列的变化：

1
dx = {0, 1, 0, -1}
2
dy = {1, 0, -1, 0}

从左上角开始填入 1，每次尝试向当前方向走一步

如果下一步越界，或者下一步的位置已经填过数字，就改变方向

一直填到 n * n 为止

最终代码#

1
#include <iostream>
2
using namespace std;
3
int main() {
4
    int n;
5
    cin >> n;
6
    int a[105][105] = {};
7
    int dx[4] = {0, 1, 0, -1};
8
    int dy[4] = {1, 0, -1, 0};
9
    int x = 0, y = 0, d = 0;
10
    for (int i = 1; i <= n * n; ++i) {
11
        a[x][y] = i;
12
        int nx = x + dx[d];
13
        int ny = y + dy[d];
14
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] != 0) {
15
            d = (d + 1) % 4;
16
            nx = x + dx[d];
17
            ny = y + dy[d];
18
        }
19
        x = nx;
20
        y = ny;
21
    }
22
    for (int i = 0; i < n; ++i) {
23
        for (int j = 0; j < n; ++j) {
24
            if (j) {
25
                cout << " ";
26
            }
27
            cout << a[i][j];
28
        }
29
        cout << endl;
30
    }
31
    return 0;
32
}

E. 汉诺塔游戏中的移动#

题目描述#

有三根标为 A、B、C 的柱子。

A 柱子上从上到下按金字塔状依次叠放着 n 个半径从 1 厘米到 n 厘米的圆盘。

要求把 A 上的所有盘子移动到柱子 C 上，中间可以临时放在 B 上。

每次移动时，每一根柱子上都不能出现大盘子在小盘子上方的情况。

请用最少的移动次数完成，并输出每次移动过程。

输入#

输入一行整数 n，表示盘子数。

其中 n < 64。

输出#

把 A 上的所有盘子移动到柱子 C 上，每次只能移动一个盘子。

每次移动占一行。

每行第一个数表示第几步移动，第二个数表示移动的盘子的半径，然后输出从哪个柱子移动到哪个柱子。

样例输入#

1
2

样例输出#

1
1 1 A->B
2
2 2 A->C
3
3 1 B->C

解题思路#

汉诺塔递归问题

要把 n 个盘子从 A 移到 C，可以分成三步：

1
1. 先把上面的 n - 1 个盘子从 A 移到 B
2
2. 把第 n 个盘子从 A 移到 C
3
3. 再把 n - 1 个盘子从 B 移到 C

递归函数可以设计为：

1
hanoi(n, a, b, c)

表示借助柱子 b，把 n 个盘子从柱子 a 移到柱子 c

每移动一次，就让步数加 1 并输出当前移动过程

最终代码#

1
#include <iostream>
2
using namespace std;
3
#define int long long
4
int cnt = 0;
5
void hanoi(int n, char a, char b, char c) {
6
    if (n == 0) {
7
        return;
8
    }
9
    hanoi(n - 1, a, c, b);
10
    cout << ++cnt << " " << n << " " << a << "->" << c << endl;
11
    hanoi(n - 1, b, a, c);
12
}
13
signed main() {
14
    int n;
15
    cin >> n;
16
    hanoi(n, 'A', 'B', 'C');
17
    return 0;
18
}

F. 树的先根遍历#

题目描述#

已知一棵树的节点间关系，请编程实现该树的先根遍历。

每个节点用不同的大写字母表示，节点数小于 26，且树的度小于 5。

输入#

输入包含若干行。

每行描述一组双亲节点和孩子节点的关系序偶对。

输出#

输出该树的先根遍历序列，序列中每个字母用空格隔开。

样例输入#

1
B E
2
B F
3
A B
4
A C

样例输出#

1
A B E F C

解题思路#

先根遍历的顺序是：

1
先访问根节点，再从左到右访问每一棵子树

输入给出的是父子关系。

可以用邻接表 g 保存每个节点的孩子节点，并用 hasfa 标记某个节点是否有父亲

读入结束后，没有父亲的节点就是根节点

找到根节点之后进行深度优先搜索，进入一个节点时先把它加入答案，再递归遍历它的孩子

最终代码#

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
vector<int> g[26];
5
int vis[26], hasfa[26];
6
vector<char> ans;
7
void dfs(int u) {
8
    ans.push_back(char(u + 'A'));
9
    for (int i = 0; i < g[u].size(); ++i) {
10
        dfs(g[u][i]);
11
    }
12
}
13
int main() {
14
    char a, b;
15
    while (cin >> a >> b) {
16
        int x = a - 'A';
17
        int y = b - 'A';
18
        g[x].push_back(y);
19
        vis[x] = vis[y] = 1;
20
        hasfa[y] = 1;
21
    }
22
    int root = -1;
23
    for (int i = 0; i < 26; ++i) {
24
        if (vis[i] && !hasfa[i]) {
25
            root = i;
26
            break;
27
        }
28
    }
29
    if (root != -1) {
30
        dfs(root);
31
    }
32
    for (int i = 0; i < ans.size(); ++i) {
33
        if (i) {
34
            cout << " ";
35
        }
36
        cout << ans[i];
37
    }
38
    cout << endl;
39
    return 0;
40
}

G. 树的后根遍历#

题目描述#

已知一棵树的节点间关系，请编程实现该树的后根遍历序列。

每个节点用不同的大写字母表示，节点数小于 26，且树的度小于 5。

输入#

输入包含若干行。

每行描述一组双亲节点和孩子节点的关系序偶对。

输出#

输出该树的后根遍历序列，序列中每个字母用空格隔开。

样例输入#

1
B E
2
B F
3
A B
4
A C

样例输出#

1
E F B C A

解题思路#

后根遍历的顺序是：

1
先从左到右访问每一棵子树，最后访问根节点

建树方式和 F 题相同

用邻接表保存孩子节点，用 hasfa 标记节点是否有父亲

读入完成后，没有父亲的节点就是根节点

进行深度优先搜索时，先递归访问所有孩子，最后再把当前节点加入答案

最终代码#

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
vector<int> g[26];
5
int vis[26], hasfa[26];
6
vector<char> ans;
7
void dfs(int u) {
8
    for (int i = 0; i < g[u].size(); ++i) {
9
        dfs(g[u][i]);
10
    }
11
    ans.push_back(char(u + 'A'));
12
}
13
int main() {
14
    char a, b;
15
    while (cin >> a >> b) {
16
        int x = a - 'A';
17
        int y = b - 'A';
18
        g[x].push_back(y);
19
        vis[x] = vis[y] = 1;
20
        hasfa[y] = 1;
21
    }
22
    int root = -1;
23
    for (int i = 0; i < 26; ++i) {
24
        if (vis[i] && !hasfa[i]) {
25
            root = i;
26
            break;
27
        }
28
    }
29
    if (root != -1) {
30
        dfs(root);
31
    }
32
    for (int i = 0; i < ans.size(); ++i) {
33
        if (i) {
34
            cout << " ";
35
        }
36
        cout << ans[i];
37
    }
38
    cout << endl;
39
    return 0;
40
}

实践三#

A. 二叉链表存储的二叉树#

题目描述#

给出一个按照先序遍历得到的字符串，其中空格表示空子节点，大写字母表示非空节点。

要求根据这个字符串建立二叉树，并分别输出：

先序遍历结果
第一种非递归中序遍历结果
第二种非递归中序遍历结果

每个非空节点后面输出一个空格。

输入#

输入只有一行，包含一个字符串 S。

字符串中空格代表空节点，大写字母代表节点内容，长度不超过 100。

输出#

输出三行。

第一行为先序遍历序列。

第二行为第一种中序遍历序列。

第三行为第二种中序遍历序列。

样例输入#

1
ABC  DE G  F

样例输出#

1
A B C D E G F
2
C B E G D F A
3
C B E G D F A

解题思路#

因为输入字符串本身就是带空节点标记的先序序列，所以可以按照先序递归建树：

如果当前字符是空格，说明当前位置是空子树
如果当前字符是大写字母，就新建节点
递归建立左子树
递归建立右子树

建树完成后，先序遍历可以直接递归输出。

中序遍历使用两种非递归写法，核心都借助栈模拟递归过程。

本题要特别注意：输入中的空格是有效字符，不能用 cin >> s，应该用 getline(cin, s) 读取整行。

最终代码#

1
#include <iostream>
2
#include <string>
3
#include <stack>
4
using namespace std;
5
struct BiTNode {
6
    char data;
7
    BiTNode *lchild, *rchild;
8
};
9
string s;
10
int pos = 0;
11
BiTNode* create() {
12
    if (pos >= s.size()) {
13
        return NULL;
14
    }
15
    char ch = s[pos++];
16
    if (ch == ' ') {
17
        return NULL;
18
    }
19
    BiTNode* t = new BiTNode;
20
    t->data = ch;
21
    t->lchild = create();
22
    t->rchild = create();
23
    return t;
24
}
25
void preorder(BiTNode* t) {
26
    if (t) {
27
        cout << t->data << " ";
28
        preorder(t->lchild);
29
        preorder(t->rchild);
30
    }
31
}
32
void inorder1(BiTNode* t) {
33
    stack<BiTNode*> st;
34
    while (t || !st.empty()) {
35
        if (t) {
36
            st.push(t);
37
            t = t->lchild;
38
        } else {
39
            t = st.top();
40
            st.pop();
41
            cout << t->data << " ";
42
            t = t->rchild;
43
        }
44
    }
45
}
46
void inorder2(BiTNode* t) {
47
    stack<BiTNode*> st;
48
    st.push(t);
49
    while (!st.empty()) {
50
        while (st.top()) {
51
            st.push(st.top()->lchild);
52
        }
53
        st.pop();
54
        if (!st.empty()) {
55
            t = st.top();
56
            st.pop();
57
            cout << t->data << " ";
58
            st.push(t->rchild);
59
        }
60
    }
61
}
62
int main() {
63
    getline(cin, s);
64
    BiTNode* t = create();
65
    preorder(t);
66
    cout << endl;
67
    inorder1(t);
68
    cout << endl;
69
    inorder2(t);
70
    cout << endl;
71
    return 0;
72
}

B. 哈夫曼树#

题目描述#

第一行输入一个数 n，表示叶节点的个数。

接着输入 n 个叶节点的权值，需要用这些叶节点生成哈夫曼树，并输出所有叶子节点的路径长度与权值乘积之和，也就是哈夫曼树的带权路径长度。

输入#

输入包含多组数据。

每组第一行输入一个数 n，接着输入 n 个叶节点权值。

其中 2 <= n <= 1000，叶节点权值不超过 100。

输出#

对于每组数据，输出哈夫曼树的带权路径长度。

样例输入#

样例输出#

解题思路#

哈夫曼树的构造规则是：每次选取权值最小的两个节点合并。

合并出的新节点权值为两个节点权值之和，并重新放回集合中。

在这个过程中，每一次合并产生的代价都会计入最终答案。

因此可以使用小根堆维护当前所有节点权值：

将所有叶节点权值加入小根堆
每次取出两个最小值 a 和 b
将 a + b 加到答案中
再把 a + b 放回堆中
堆中只剩一个节点时结束

最终代码#

1
#include <iostream>
2
#include <queue>
3
#include <vector>
4
using namespace std;
5
int main() {
6
    int n;
7
    while (cin >> n) {
8
        priority_queue<int, vector<int>, greater<int> > q;
9
        for (int i = 0; i < n; ++i) {
10
            int x;
11
            cin >> x;
12
            q.push(x);
13
        }
14
        int ans = 0;
15
        while (q.size() > 1) {
16
            int a = q.top();
17
            q.pop();
18
            int b = q.top();
19
            q.pop();
20
            ans += a + b;
21
            q.push(a + b);
22
        }
23
        cout << ans << endl;
24
    }
25
    return 0;
26
}

C. 树的遍历#

题目描述#

已知二叉树中所有键值都是不同的正整数。

如果给出前序遍历和中序遍历，或者给出后序遍历和中序遍历，都可以唯一确定一棵二叉树。

但是如果只给出前序遍历和后序遍历，二叉树不一定唯一。

现在给出一棵二叉树的前序序列和后序序列，要求输出一组可行的中序遍历序列。

如果这棵树唯一，输出 Yes；否则输出 No。

输入#

第一行输入正整数 N，表示二叉树中的节点总数。

第二行输入前序遍历序列。

第三行输入后序遍历序列。

输出#

第一行输出 Yes 或 No。

如果树唯一，输出 Yes；否则输出 No。

第二行输出对应的中序遍历序列，数字之间用一个空格隔开，行尾不能有多余空格。

样例输入#

1
7
2
1 2 3 4 6 7 5
3
2 6 7 4 5 3 1

样例输出#

1
Yes
2
2 1 6 4 7 3 5

解题思路#

前序遍历的第一个节点一定是当前子树的根。

后序遍历的最后一个节点也一定是当前子树的根。

在当前区间中，如果节点数大于 1，那么后序序列中根节点前面的那个节点可以看作右子树的根。

找到这个右子树根在前序序列中的位置，就可以把前序序列分成左子树和右子树两部分。

如果当前根节点下面只有一棵子树，那么这棵子树既可以看作左子树，也可以看作右子树，因此二叉树不唯一。

递归过程中按照：

1
左子树 -> 根节点 -> 右子树

把节点加入答案，就能得到一组合法的中序遍历序列。

最终代码#

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
vector<int> pre, post, in;
5
bool flag = true;
6
void dfs(int pl, int pr, int pol, int por) {
7
    if (pl > pr) return;
8
    if (pl == pr) {
9
        in.push_back(pre[pl]);
10
        return;
11
    }
12
    int rightRoot = post[por - 1], k = pl;
13
    while (pre[k] != rightRoot) k++;
14
    int rightSize = pr - k + 1;
15
    if (rightSize == pr - pl) flag = false;
16
    dfs(pl + 1, k - 1, pol, por - rightSize - 1);
17
    in.push_back(pre[pl]);
18
    dfs(k, pr, por - rightSize, por - 1);
19
}
20
int main() {
21
    int n;
22
    cin >> n;
23
    pre.resize(n), post.resize(n);
24
    for (int i = 0; i < n; ++i) cin >> pre[i];
25
    for (int i = 0; i < n; ++i) cin >> post[i];
26
    dfs(0, n - 1, 0, n - 1);
27
    cout << (flag ? "Yes" : "No") << endl;
28
    for (int i = 0; i < n; ++i) {
29
        if (i) cout << " ";
30
        cout << in[i];
31
    }
32
    cout << endl;
33
    return 0;
34
}

D. 最短路径#

题目描述#

一个迷宫地图中，多个房间由单向通道相连。

房间号从 1 到 N 依次编号。

给出所有单向通道及其长度，求起点房间到终点房间之间的最短路径长度。

输入#

第一行输入房间数 N 和单向通道数 M。

接下来 M 行，每行输入三个整数 x y z，表示存在一条从 x 到 y 的单向通道，长度为 z。

最后一行输入 start 和 end，表示起点和终点。

输出#

输出起点房间到终点房间的最短路径长度。

如果没有通路，输出 STOP。

样例输入#

样例输出#

1
12

解题思路#

本题是带正权边的单源最短路径问题。

因为通道长度都是正数，所以可以使用 Dijkstra 算法。

用邻接表保存有向边，dis[i] 表示从起点到房间 i 的当前最短距离。

再用小根堆每次取出当前距离最小的房间进行松弛：

1
if (dis[v] > dis[u] + w)
2
    dis[v] = dis[u] + w

最后如果终点距离仍然是无穷大，说明无法到达，输出 STOP。

最终代码#

1
#include <iostream>
2
#include <queue>
3
#include <vector>
4
using namespace std;
5
struct Edge {
6
    int to;
7
    int w;
8
};
9
const int INF = 114514;
10
int main() {
11
    int n, m;
12
    cin >> n >> m;
13
    vector<Edge> g[105];
14
    for (int i = 0; i < m; ++i) {
15
        int x, y, z;
16
        cin >> x >> y >> z;
17
        g[x].push_back({y, z});
18
    }
19
    int start, end;
20
    cin >> start >> end;
21
    vector<int> dis(n + 1, INF);
22
    vector<int> vis(n + 1, 0);
23
    priority_queue<
24
        pair<int, int>,
25
        vector<pair<int, int> >,
26
        greater<pair<int, int> >
27
    > q;
28
    dis[start] = 0;
29
    q.push({0, start});
30
    while (!q.empty()) {
31
        int u = q.top().second;
32
        q.pop();
33

34
        if (vis[u]) {
35
            continue;
36
        }
37
        vis[u] = 1;
38
        for (int i = 0; i < g[u].size(); ++i) {
39
            int v = g[u][i].to;
40
            int w = g[u][i].w;
41

42
            if (dis[v] > dis[u] + w) {
43
                dis[v] = dis[u] + w;
44
                q.push({dis[v], v});
45
            }
46
        }
47
    }
48
    if (dis[end] == INF) {
49
        cout << "STOP" << endl;
50
    } else {
51
        cout << dis[end] << endl;
52
    }
53
    return 0;
54
}

E. 最小生成树#

题目描述#

给出一个无向图的邻接矩阵。

矩阵中第 i 行第 j 个数如果不为 0，表示第 i 个顶点和第 j 个顶点之间有直接连接，且代价为该数。

0 表示没有直接连接。

要求使用最小生成树思想，输出连接所有顶点所需要的最小总代价。

输入#

第一行输入正整数 n，表示图中共有 n 个顶点。

接下来 n 行，每行输入 n 个整数，表示无向图的邻接矩阵。

输入保证矩阵对称，并且图只有一个连通分量。

输出#

输出一个整数，表示最小生成树的总代价。

样例输入#

样例输出#

1
6

解题思路#

本题使用 Prim 算法。

先从 1 号顶点开始，把它加入生成树集合。

lowcost[i] 表示当前生成树集合连接到顶点 i 的最小边权。

每一轮选择一个未加入生成树、且 lowcost 最小的顶点加入答案，然后用这个新加入的顶点更新其他顶点的 lowcost。

因为题目保证图连通，所以最终一定能加入所有顶点。

最终代码#

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
int main() {
5
    int n;
6
    cin >> n;
7
    vector<vector<int> > a(n + 1, vector<int>(n + 1));
8
    for (int i = 1; i <= n; ++i) {
9
        for (int j = 1; j <= n; ++j) {
10
            cin >> a[i][j];
11
        }
12
    }
13
    vector<int> lowcost(n + 1, -1);
14
    vector<int> vis(n + 1, 0);
15
    vis[1] = 1;
16
    for (int i = 1; i <= n; ++i) {
17
        if (a[1][i] != 0) {
18
            lowcost[i] = a[1][i];
19
        }
20
    }
21
    int ans = 0;
22
    for (int i = 1; i < n; ++i) {
23
        int k = 0;
24

25
        for (int j = 1; j <= n; ++j) {
26
            if (!vis[j] && lowcost[j] != -1) {
27
                if (k == 0 || lowcost[j] < lowcost[k]) {
28
                    k = j;
29
                }
30
            }
31
        }
32
        vis[k] = 1;
33
        ans += lowcost[k];
34
        for (int j = 1; j <= n; ++j) {
35
            if (!vis[j] && a[k][j] != 0) {
36
                if (lowcost[j] == -1 || lowcost[j] > a[k][j]) {
37
                    lowcost[j] = a[k][j];
38
                }
39
            }
40
        }
41
    }
42
    cout << ans << endl;
43
    return 0;
44
}

实践四#

数据结构作业#

作业一#

A. 查成绩#

题目描述#

期末考试结束后，数学老师给出了班里同学们的数学成绩，为了快速查成绩，请编程帮助查成绩。

输入#

第一行为 N，N < 1000，表示班级人数。

第一行后有 N 行，每行两个部分，一个是学号，一个是成绩。

最后一行是要查找成绩同学的学号。

输出#

输出要查找同学的成绩。

样例输入#

样例输出#

1
95

解题思路#

用两个数组分别保存学号和成绩。读入要查询的学号后，从前往后顺序查找，如果当前学号和目标学号相同，就输出对应的成绩并结束。

最终代码#

1
#include <iostream>
2
#include <string>
3
using namespace std;
4
int main(){
5
    int N;
6
    cin >> N;
7
    string id[1000];
8
    int score[1000];
9
    for(int i = 0; i < N; i++)
10
        cin >> id[i] >> score[i];
11
    string ids;
12
    cin >> ids;
13
    for(int i = 0; i < N; i++)
14
        if(ids == id[i]){
15
            cout << score[i] << endl;
16
            break;
17
        }
18
    return 0;
19
}

B. 插入数据#

题目描述#

已有一个整数序列，现在要在不同的位置插入一些整数，请输出插入数据后的序列。

输入#

第一行是 N，N < 1000，表示原序列中元素的个数。

第二行是 N 个整数。

第三行是要插入的元素个数 M，M < 1000。

第四行开始有 M 行，每行是一对数据 k 和 x，表示要在原序列第 k 个位置插入整数 x。

输出#

输出插入元素后的整数序列。

样例输入#

样例输出#

1
11 1 2 33 3 4 5

解题思路#

使用 vector 保存原整数序列。每次插入时使用 insert 函数。

因为题目给出的 k 是相对于原序列的位置，而前面已经插入了 i 个元素，所以第 i 次插入时，实际插入位置为：

1
k - 1 + i

最终代码#

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
int main(){
5
    int N;
6
    cin >> N;
7
    vector<int> num(N);
8
    for(int i = 0; i < N; i++)
9
        cin >> num[i];
10
    int M;
11
    cin >> M;
12
    for(int i = 0; i < M; i++){
13
        int k,x;
14
        cin >> k >> x;
15
        num.insert(num.begin() + k - 1 + i, x);
16
    }
17
    int len = num.size();
18
    for(int i = 0; i < len; i++)
19
        cout << num[i] << (i + 1 < len ? " " : "\n");
20
    return 0;
21
}

C. 二路归并#

题目描述#

有两个按元素值递增有序的整数顺序表 A 和 B，设计一个算法将顺序表 A 和 B 的全部元素合并到一个递增有序顺序表 C 中，并依次输出 C 中的元素。

输入#

输入占两行，依次是 A 和 B 的序列，元素个数都小于 100。

输出#

依次输出 C 中的元素。

样例输入#

样例输出#

1
1 1 2 2 3 3 4 4 5 6

解题思路#

两个序列本身已经递增有序，所以可以用双指针

令 i 指向 A 的当前位置，j 指向 B 的当前位置。每次比较 A[i] 和 B[j]，把较小的元素放入 C。如果其中一个序列已经全部放入 C，就把另一个序列剩下的元素全部加入

本题没有给出每行元素个数，所以使用 getline 读入整行，再手动扫描字符串得到整数

最终代码#

1
#include <iostream>
2
#include <vector>
3
#include <string>
4
using namespace std;
5
void getnum(string s, vector<int> &num){
6
    int n = s.length();
7
    for(int i = 0; i < n; i++){
8
        if(s[i] == ' ')
9
            continue;
10
        int x = 0,flag = 1;
11
        if(s[i] == '-'){
12
            flag = -1;
13
            i++;
14
        }
15
        while(i < n && s[i] >= '0' && s[i] <= '9'){
16
            x = x * 10 + s[i] - '0';
17
            i++;
18
        }
19
        num.push_back(x * flag);
20
    }
21
}
22
int main(){
23
    string s;
24
    vector<int> A,B,C;
25
    getline(cin, s);
26
    getnum(s, A);
27
    getline(cin, s);
28
    getnum(s, B);
29
    int i = 0,j = 0;
30
    int n = A.size(),m = B.size();
31
    while(i < n && j < m){
32
        if(A[i] <= B[j])
33
            C.push_back(A[i++]);
34
        else
35
            C.push_back(B[j++]);
36
    }
37
    while(i < n)
38
        C.push_back(A[i++]);
39
    while(j < m)
40
        C.push_back(B[j++]);
41
    int k = C.size();
42
    for(int i = 0; i < k; i++)
43
        cout << C[i] << (i + 1 < k ? " " : "\n");
44
    return 0;
45
}

D. 最大值个数#

题目描述#

有一个整数单链表 L，其中可能存在多个值相同的结点，设计一个算法查找 L 中最大值结点的个数。

输入#

输入单链表 L 中的元素，个数不定。

输出#

输出最大值结点的个数。

样例输入#

1
1 2 3 4 5 5 20 20 1 2 3 4 5

样例输出#

1
2

解题思路#

题目描述的是单链表，本质操作就是从头到尾遍历一次

读入过程中维护两个变量：

1
maxn 表示当前最大值
2
cnt  表示当前最大值出现次数

如果读到的新元素比 maxn 大，就更新 maxn，并把 cnt 重置为 1。如果读到的新元素等于 maxn，就让 cnt 加 1

最终代码#

1
#include <iostream>
2
using namespace std;
3
int main(){
4
    int x,maxn = 0,cnt = 0;
5
    bool flag = false;
6
    while(cin >> x){
7
        if(!flag || x > maxn){
8
            maxn = x;
9
            cnt = 1;
10
            flag = true;
11
        }
12
        else if(x == maxn)
13
            cnt++;
14
    }
15
    cout << cnt << endl;
16
    return 0;
17
}

E. 约瑟夫问题#

题目描述#

有 n 个小孩围成一圈，给他们从 1 开始依次编号。从编号为 1 的小孩开始报数，数到第 m 个小孩出列，然后从出列的下一个小孩重新开始报数。如此反复直到所有的小孩全部出列为止，求整个出列序列。

输入#

输入占一行，为 n 和 m，其中 n < 100，0 < m < n。

输出#

输出整个出列序列。

样例输入#

1
6 5

样例输出#

1
5 4 6 2 3 1

解题思路#

用 vector 保存当前还在圈中的小孩编号。

设当前报数起点下标为 k，当前剩余人数为 len，则每次出列的小孩下标为：

1
k = (k + m - 1) % len

删除当前小孩后，k 正好指向下一个开始报数的人

最终代码#

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
int main(){
5
    int n,m;
6
    cin >> n >> m;
7
    vector<int> num(n),ans;
8
    for(int i = 0; i < n; i++)
9
        num[i] = i + 1;
10
    int k = 0;
11
    while(!num.empty()){
12
        int len = num.size();
13
        k = (k + m - 1) % len;
14
        ans.push_back(num[k]);
15
        num.erase(num.begin() + k);
16
    }
17
    for(int i = 0; i < n; i++)
18
        cout << ans[i] << (i + 1 < n ? " " : "\n");
19
    return 0;
20
}

F. 括号配对#

题目描述#

设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对。假设表达式中可能含有圆括号 ()、中括号 [] 和大括号 {}。

输入#

输入占一行，为含有三种括号的表达式，最长 100 个符号。

输出#

匹配时输出 YES。

小括号不匹配输出 NO1，中括号不匹配输出 NO2，大括号不匹配输出 NO3。

样例输入#

1
{([a])}

样例输出#

1
YES

解题思路#

使用字符数组模拟顺序栈

遇到左括号时，将它入栈。遇到右括号时，检查栈顶是否是对应的左括号。如果栈为空，或者栈顶括号类型不对应，就说明不匹配，按照当前右括号类型输出对应的 NO

扫描结束后，如果栈为空，说明全部括号匹配；如果栈不为空，就根据栈顶剩余的左括号类型输出对应结果

最终代码#

1
#include <iostream>
2
#include <string>
3
using namespace std;
4
void print(char c){
5
    if(c == '(' || c == ')')
6
        cout << "NO1" << endl;
7
    else if(c == '[' || c == ']')
8
        cout << "NO2" << endl;
9
    else
10
        cout << "NO3" << endl;
11
}
12
int main(){
13
    string s;
14
    getline(cin, s);
15
    char st[105];
16
    int top = -1;
17
    int n = s.length();
18
    for(int i = 0; i < n; i++){
19
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
20
            st[++top] = s[i];
21
        else if(s[i] == ')'){
22
            if(top == -1){
23
                print(s[i]);
24
                return 0;
25
            }
26
            if(st[top] != '('){
27
                print(st[top]);
28
                return 0;
29
            }
30
            top--;
31
        }
32
        else if(s[i] == ']'){
33
            if(top == -1){
34
                print(s[i]);
35
                return 0;
36
            }
37
            if(st[top] != '['){
38
                print(st[top]);
39
                return 0;
40
            }
41
            top--;
42
        }
43
        else if(s[i] == '}'){
44
            if(top == -1){
45
                print(s[i]);
46
                return 0;
47
            }
48
            if(st[top] != '{'){
49
                print(st[top]);
50
                return 0;
51
            }
52
            top--;
53
        }
54
    }
55
    if(top == -1)
56
        cout << "YES" << endl;
57
    else
58
        print(st[top]);
59
    return 0;
60
}

G. 后缀表达式#

题目描述#

给出一个中缀表达式，输出该表达式的后缀表达式。

输入#

输入占一行，为一个中缀表达式。运算符只有 +、-、*、/，最多 1000 个字符。

输出#

输出后缀表达式。

样例输入#

1
(56-20)/(4+2)

样例输出#

1
56 20 - 4 2 + /

解题思路#

中缀表达式转后缀表达式可以使用运算符栈

处理规则如下：

如果遇到操作数，直接加入答案
如果遇到左括号，直接入栈
如果遇到右括号，就一直弹出栈顶运算符，直到遇到左括号
如果遇到普通运算符，就弹出栈顶优先级大于等于当前运算符的运算符，然后再把当前运算符入栈
扫描结束后，将栈中剩余运算符依次弹出

样例中有多位数，所以扫描操作数时，需要把连续的数字或字母作为一个整体

最终代码#

1
#include <iostream>
2
#include <string>
3
#include <vector>
4
using namespace std;
5
int priority(char c){
6
    if(c == '+' || c == '-')
7
        return 1;
8
    if(c == '*' || c == '/')
9
        return 2;
10
    return 0;
11
}
12
bool isop(char c){
13
    return c == '+' || c == '-' || c == '*' || c == '/';
14
}
15
bool isnum(char c){
16
    return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
17
}
18
int main(){
19
    string s;
20
    getline(cin, s);
21
    vector<string> ans;
22
    char st[1005];
23
    int top = -1;
24
    int n = s.length();
25
    for(int i = 0; i < n; i++){
26
        if(s[i] == ' ')
27
            continue;
28
        if(isnum(s[i])){
29
            string t;
30
            while(i < n && isnum(s[i])){
31
                t += s[i];
32
                i++;
33
            }
34
            i--;
35
            ans.push_back(t);
36
        }
37
        else if(s[i] == '(')
38
            st[++top] = s[i];
39
        else if(s[i] == ')'){
40
            while(top != -1 && st[top] != '('){
41
                string t;
42
                t += st[top--];
43
                ans.push_back(t);
44
            }
45
            if(top != -1)
46
                top--;
47
        }
48
        else if(isop(s[i])){
49
            while(top != -1 && st[top] != '(' && priority(st[top]) >= priority(s[i])){
50
                string t;
51
                t += st[top--];
52
                ans.push_back(t);
53
            }
54
            st[++top] = s[i];
55
        }
56
    }
57
    while(top != -1){
58
        if(st[top] != '('){
59
            string t;
60
            t += st[top];
61
            ans.push_back(t);
62
        }
63
        top--;
64
    }
65
    int k = ans.size();
66
    for(int i = 0; i < k; i++)
67
        cout << ans[i] << (i + 1 < k ? " " : "\n");
68
    return 0;
69
}

H. 字符串反转#

题目描述#

小 C 很喜欢倒着写单词。现在给你一行小 C 写的文本，你需要把每个单词都反转并输出。

输入#

输入包含多组测试样例。

第一行为一个整数 T，代表测试样例的数量，后面跟着 T 个测试样例。

每个测试样例占一行，包含多个单词，一行最多有 1000 个字符。

输出#

对于每一个测试样例，输出转换后的文本。

样例输入#

1
3
2
olleh !dlrow
3
I ekil .bulcmca
4
I evol .mca

样例输出#

1
hello world!
2
I like acmclub.
3
I love acm.

解题思路#

逐行读取字符串，使用 word 临时保存当前单词

如果当前字符不是空格，就加入 word。如果遇到空格，就把 word 倒序输出，然后输出空格，并清空 word

一行结束后，还需要把最后一个单词倒序输出

标点符号也属于单词的一部分，所以会随着单词一起反转

最终代码#

1
#include <iostream>
2
#include <string>
3
using namespace std;
4
int main(){
5
    int T;
6
    cin >> T;
7
    string s;
8
    getline(cin, s);
9
    while(T--){
10
        getline(cin, s);
11
        string word;
12
        int n = s.length();
13
        for(int i = 0; i < n; i++){
14
            if(s[i] == ' '){
15
                int len = word.length();
16
                for(int j = len - 1; j >= 0; j--)
17
                    cout << word[j];
18
                word = "";
19
                cout << " ";
20
            }
21
            else
22
                word += s[i];
23
        }
24
        int len = word.length();
25
        for(int j = len - 1; j >= 0; j--)
26
            cout << word[j];
27
        cout << endl;
28
    }
29
    return 0;
30
}