某张期中考试试卷

问题

什么是抽象数据类型（ADT）？并用 C++ 的类声明定义“复数”的抽象数据类型，具体实现以下功能：

  1. 复数由浮点数的实部和虚部表示。
  2. 提供以下三种构造函数：
    • 缺省构造函数（无参）。
    • 构造函数：实部赋值为一个双精度浮点数，虚部置为 0。
    • 构造函数：实部和虚部分别由两个双精度浮点数赋值。
  3. 定义操作复数的成员函数，包括：获取和修改复数的实部和虚部、加法（+）、减法（-）、乘法（*）、除法（/）。
  4. 重载流插入运算符（<<）输出复数。

答案

以下是 C++ 实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
using namespace std;

// 复数的抽象数据类型定义
class Complex {
private:
    double real; // 实部
    double imag; // 虚部

public:
    // 构造函数
    Complex() : real(0), imag(0) {} // 缺省构造函数
    Complex(double r) : real(r), imag(0) {} // 实部赋值，虚部为0
    Complex(double r, double i) : real(r), imag(i) {} // 实部和虚部都赋值

    // 获取实部和虚部
    double getReal() const { return real; }
    double getImag() const { return imag; }

    // 修改实部和虚部
    void setReal(double r) { real = r; }
    void setImag(double i) { imag = i; }

    // 运算符重载: 加法
    Complex operator+(const Complex &other) const {
        return Complex(real + other.real, imag + other.imag);
    }

    // 运算符重载: 减法
    Complex operator-(const Complex &other) const {
        return Complex(real - other.real, imag - other.imag);
    }

    // 运算符重载: 乘法
    Complex operator*(const Complex &other) const {
        return Complex(
            real * other.real - imag * other.imag,
            real * other.imag + imag * other.real
        );
    }

    // 运算符重载: 除法
    Complex operator/(const Complex &other) const {
        double denominator = other.real * other.real + other.imag * other.imag;
        return Complex(
            (real * other.real + imag * other.imag) / denominator,
            (imag * other.real - real * other.imag) / denominator
        );
    }

    // 重载输出流运算符
    friend ostream& operator<<(ostream &os, const Complex &c) {
        os << c.real;
        if (c.imag >= 0) os << "+";
        os << c.imag << "i";
        return os;
    }
};

// 测试代码
int main() {
    Complex c1; // 缺省构造
    Complex c2(5.0); // 只有实部
    Complex c3(3.0, 4.0); // 实部和虚部都赋值

    cout << "c1 = " << c1 << endl;
    cout << "c2 = " << c2 << endl;
    cout << "c3 = " << c3 << endl;

    // 运算测试
    Complex sum = c2 + c3;
    Complex diff = c2 - c3;
    Complex prod = c2 * c3;
    Complex quot = c2 / c3;

    cout << "c2 + c3 = " << sum << endl;
    cout << "c2 - c3 = " << diff << endl;
    cout << "c2 * c3 = " << prod << endl;
    cout << "c2 / c3 = " << quot << endl;

    return 0;
}

解释

  1. 抽象数据类型（ADT）
    • 抽象数据类型是一种数学模型和一组操作的定义，与具体的实现无关。
    • 例如，复数是一种 ADT，可以通过数学表示 a + bi，其操作包括加减乘除。
  2. 实现说明
    • 构造函数：提供三种不同的构造方法，满足灵活初始化需求。
    • 成员函数：提供获取和修改复数的功能，让用户可以对实部和虚部单独操作。
    • 运算符重载：实现复数之间的基本四则运算。
    • 流插入运算符重载：让复数以直观格式输出，例如 3+4i。
  3. 测试代码
    测试了构造函数、加减乘除运算和输出的正确性，确保实现符合需求。

运行结果示例：

1
2
3
4
5
6
7
c1 = 0+0i  
c2 = 5+0i  
c3 = 3+4i  
c2 + c3 = 8+4i  
c2 - c3 = 2-4i  
c2 * c3 = 15+20i  
c2 / c3 = 1.4-0.8i

问题

  1. 在函数 d 中加入计数器 count，计算程序执行的次数。
  2. 化简程序，保持计数器 count 值不变。
  3. 确定程序执行结束时 count 的值。
  4. 使用执行频度的方法计算程序步数，并画出程序步数统计表。

解答

(1) 插入计数器 count

原程序加入计数器后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void d(ArrayElement x[], int n) {
    int count = 0; // 初始化计数器
    int i = 1;

    // 第一段循环：do-while
    do {
        x[i] += 2;
        count++;    // 更新计数器
        i += 2;
    } while (i <= n);

    // 第二段循环：while
    i = 1;
    while (i <= (n / 2)) {
        x[i] += x[i + 1];
        count++;    // 更新计数器
        i++;
    }

    cout << "Count = " << count << endl;
}

(2) 化简程序

分析循环结构并化简：

  1. 第一段循环
    • 初始值：i = 1。
    • 步长：i += 2。
    • 条件：i <= n。
    • 执行次数：\(\lceil \frac{n}{2} \rceil\)。
  2. 第二段循环
    • 初始值：i = 1。
    • 步长：i++。
    • 条件：\(i \leq \frac{n}{2}\)。
    • 执行次数：\(\lfloor \frac{n}{2} \rfloor\)。

化简后的程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void d(ArrayElement x[], int n) {
    int count = 0; // 初始化计数器
    for (int i = 1; i <= n; i += 2) {
        x[i] += 2;
        count++;    // 更新计数器
    }

    for (int i = 1; i <= (n / 2); i++) {
        x[i] += x[i + 1];
        count++;    // 更新计数器
    }

    cout << "Count = " << count << endl;
}

(3) 程序执行结束时的 count 值

  1. 第一段循环：执行次数为 \(\lceil \frac{n}{2} \rceil\)。
  2. 第二段循环：执行次数为 \(\lfloor \frac{n}{2} \rfloor\)。

总计：
$ = + = n $
因此，程序结束时 count = n。

(4) 程序步数统计与表格

根据执行频度分析：

  • 第一段循环：
    • 循环次数：\(\lceil \frac{n}{2} \rceil\)。
    • 每次循环：1 次条件判断，1 次赋值，1 次加法。
    • 总步数：\((\lceil \frac{n}{2} \rceil + 1) + 2 \cdot \lceil \frac{n}{2} \rceil = 3 \cdot \lceil \frac{n}{2} \rceil + 1\)。
  • 第二段循环：
    • 循环次数：\(\lfloor \frac{n}{2} \rfloor\)。
    • 每次循环：1 次条件判断，1 次加法，1 次赋值。
    • 总步数：\((\lfloor \frac{n}{2} \rfloor + 1) + 2 \cdot \lfloor \frac{n}{2} \rfloor = 3 \cdot \lfloor \frac{n}{2} \rfloor + 1\)。
  • 总步数：
    $ T(n) = (3 + 1) + (3 + 1) = 3n + 2 $

程序步数统计表

代码块 操作类型 频度 总步数
第一段循环体 条件判断、赋值 \(\lceil \frac{n}{2} \rceil\) \(3 \cdot \lceil \frac{n}{2} \rceil\)
第二段循环体 条件判断、赋值 \(\lfloor \frac{n}{2} \rfloor\) \(3 \cdot \lfloor \frac{n}{2} \rfloor\)
合计 \(3n + 2\)

结论

  1. 程序 count 值为 $ n $。
  2. 程序步数 $ T(n) = 3n + 2 $。
  3. 化简后的程序保持相同的 count 值，并优化代码结构。

问题

编写算法 frequency，用于统计输入字符串中各个不同字符出现的频度。并提供测试数据验证算法的正确性。

解答

(1) 算法设计

思路：

  1. 使用一个哈希表（如 std::unordered_map）记录字符频率。
  2. 遍历输入字符串，更新每个字符的频率。
  3. 输出结果，显示每个字符及其对应的频率。

(2) 代码实现

以下是 C++ 的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <unordered_map>
#include <string>

void frequency(const std::string& input) {
    std::unordered_map<char, int> freqMap; // 用于存储字符及其频率

    // 遍历字符串，统计频率
    for (char ch : input) {
        if (ch != ' ') { // 忽略空格
            freqMap[ch]++;
        }
    }

    // 输出结果
    std::cout << "Character frequencies:" << std::endl;
    for (const auto& pair : freqMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}

int main() {
    std::string testInput = "hello world";
    std::cout << "Input: " << testInput << std::endl;
    frequency(testInput);
    return 0;
}

(3) 测试数据与结果

测试输入：

1
hello world

输出结果：

1
2
3
4
5
6
7
8
9
Input: hello world
Character frequencies:
h: 1
e: 1
l: 3
o: 2
w: 1
r: 1
d: 1

测试分析：

  • 输入字符串 "hello world" 中，字符 'l' 出现 3 次，字符 'o' 出现 2 次，其余字符如 'h'、'e'、'w' 等都出现 1 次。
  • 程序正确统计了每个字符的频率。

(4) 算法解释

  1. 输入：接受一个字符串作为输入。
  2. 处理：
    • 使用哈希表（std::unordered_map）存储字符与频率的对应关系。
    • 遍历字符串时，忽略空格字符，逐一更新哈希表中字符的计数值。
  3. 输出：依次打印每个字符及其出现的频率。
  4. 时间复杂度：
    • 遍历字符串：\(O(n)\)，其中 \(n\) 为字符串长度。
    • 更新哈希表：平均 \(O(1)\) 操作，整体复杂度仍为 \(O(n)\)。
  5. 空间复杂度：哈希表需要额外的 \(O(k)\) 空间，其中 \(k\) 是字符串中不同字符的个数。

结论

该算法简单高效，能够快速统计输入字符串中每个字符的频率，并将结果输出。测试数据验证了算法的正确性，适用于字符频率统计的常见应用场景，例如文本分析和数据压缩等。

问题

编写一个算法，用于在带表头结点的单链表中查找第 \(i\) 个结点。如果找到，返回其地址；如果找不到，则返回 0。

解答

(1) 算法思路

  1. 链表结构：使用一个带表头结点的单链表，头结点不存储有效数据。
  2. 遍历链表：从头结点的下一个结点开始，遍历链表，计数到第 \(i\) 个结点时返回该结点地址。
  3. 边界检查：
    • 如果 \(i \leq 0\)，立即返回 0。
    • 如果链表长度小于 \(i\)，返回 0。

(2) C++代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std;

// 单链表结点定义
struct ListNode {
    int data;           // 数据域
    ListNode* next;     // 指针域
};

// 在带表头结点的单链表中寻找第 i 个结点
ListNode* findNode(ListNode* head, int i) {
    if (i <= 0) return nullptr; // 无效位置返回 0
    ListNode* current = head->next; // 跳过表头结点
    int index = 1; // 计数器，表示当前是第几个结点

    // 遍历链表
    while (current != nullptr) {
        if (index == i) {
            return current; // 找到第 i 个结点
        }
        current = current->next; // 移动到下一个结点
        index++;
    }

    return nullptr; // 找不到第 i 个结点
}

// 测试函数
int main() {
    // 构建链表：头结点 -> 1 -> 2 -> 3 -> nullptr
    ListNode* head = new ListNode{0, nullptr}; // 表头结点
    ListNode* node1 = new ListNode{1, nullptr};
    ListNode* node2 = new ListNode{2, nullptr};
    ListNode* node3 = new ListNode{3, nullptr};
    head->next = node1;
    node1->next = node2;
    node2->next = node3;

    // 测试查找
    int position = 2;
    ListNode* result = findNode(head, position);
    if (result) {
        cout << "The data at position " << position << " is: " << result->data << endl;
    } else {
        cout << "Node at position " << position << " not found." << endl;
    }

    return 0;
}

(3) 测试数据与结果

  1. 测试用例 1
    • 输入链表：头结点 -> 1 -> 2 -> 3 -> nullptr
    • 查找位置：2
    • 输出：The data at position 2 is: 2
  2. 测试用例 2
    • 输入链表：头结点 -> 1 -> 2 -> 3 -> nullptr
    • 查找位置：4
    • 输出：Node at position 4 not found.
  3. 测试用例 3
    • 输入链表：头结点 -> 1 -> 2 -> 3 -> nullptr
    • 查找位置：0
    • 输出：Node at position 0 not found.

(4) 算法分析

  1. 输入：一个带表头结点的单链表，以及待查找的位置 \(i\)。
  2. 输出：返回第 \(i\) 个结点的地址，或 0 表示未找到。
  3. 时间复杂度：
    • 最坏情况需要遍历整个链表，时间复杂度为 \(O(n)\)，其中 \(n\) 是链表长度。
  4. 空间复杂度：
    • 仅使用一个指针变量和计数器，空间复杂度为 \(O(1)\)。

结论

该算法能高效地在带表头结点的单链表中查找第 \(i\) 个结点，返回其地址或 0 表示未找到。测试验证了代码的正确性，且算法的复杂度适合处理一般场景。

问题

  1. 编号为 1, 2, 3, 4, 5, 6 的六辆列车顺序进入栈式结构站台，可能的出栈序列有多少种？

解答

(1) 可能的出栈序列总数

对于一个栈式结构，可能的出栈序列数等价于给定序列的 栈的排列数，可由 卡特兰数计算。对于 \(n = 6\)，卡特兰数公式如下：

$ C_n = $

计算 \(C_6\)：

$ C_6 = = = 132 $

因此，可能的出栈序列总数为 132 种。

问题

给定整数数组 $ A[n] $，需要实现以下递归算法：

  1. 求数组 $ A $ 中的最大整数。
  2. 求数组 $ A $ 中 $ n $ 个整数的和。
  3. 求数组 $ A $ 中 $ n $ 个整数的平均值。

答案与解释

(1) 求数组 $ A $ 中的最大整数

思路：通过递归比较数组元素，逐步缩小问题规模到只有一个元素，返回其最大值。

代码实现：

1
2
3
4
5
6
int findMax(int A[], int n) {
    if (n == 1)  // 递归基准：只有一个元素时，直接返回
        return A[0];
    // 比较最后一个元素与前 n-1 个元素的最大值
    return std::max(A[n - 1], findMax(A, n - 1));
}

解释：

  1. 当 $ n = 1 $ 时，数组只剩下一个元素，直接返回该元素。
  2. 否则，递归比较最后一个元素与前 $ n-1 $ 个元素的最大值。

(2) 求 $ n $ 个整数的和

思路：逐步将问题分解为当前数组元素加上剩余元素之和，递归到只有一个元素时返回该值。

代码实现：

1
2
3
4
5
6
int sumArray(int A[], int n) {
    if (n == 0)  // 递归基准：数组为空时，和为 0
        return 0;
    // 当前元素加上剩余部分的和
    return A[n - 1] + sumArray(A, n - 1);
}

解释：

  1. 当 $ n = 0 $ 时，数组为空，返回和为 0。
  2. 否则，将最后一个元素与前 $ n-1 $ 个元素的和相加。

(3) 求 $ n $ 个整数的平均值

思路：通过递归求和，然后用总和除以 $ n $ 得到平均值。

代码实现：

1
2
3
4
5
6
double averageArray(int A[], int n) {
    if (n == 0)  // 边界情况：避免除以零
        return 0.0;
    // 求和并除以元素个数
    return static_cast<double>(sumArray(A, n)) / n;
}

解释：

  1. 调用已实现的求和函数 sumArray 计算数组总和。
  2. 将总和除以 $ n $ 得到平均值。

示例测试

测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int findMax(int A[], int n);
int sumArray(int A[], int n);
double averageArray(int A[], int n);

int main() {
    int A[] = {3, 5, 1, 8, 2};
    int n = sizeof(A) / sizeof(A[0]);

    cout << "数组中最大值: " << findMax(A, n) << endl;
    cout << "数组元素之和: " << sumArray(A, n) << endl;
    cout << "数组元素平均值: " << averageArray(A, n) << endl;

    return 0;
}

输入数组：

1
A = {3, 5, 1, 8, 2}

输出结果：

1
2
3
数组中最大值: 8
数组元素之和: 19
数组元素平均值: 3.8

小结

  1. 递归优点：算法逻辑清晰，自然分解问题，代码简洁。
  2. 递归缺点：当数组过大时，递归调用栈可能耗尽，效率不如迭代实现。
  3. 实现改进：实际应用中，可以使用迭代方式以提高效率，减少栈空间占用。

问题

Josephus问题描述：

  • $ n $：总人数，围坐在一个圆桌周围。
  • $ s $：从第 $ s $ 个人开始报数。
  • $ m $：报数到第 $ m $ 人时，该人出局。
  • 每次出局后，从出局的下一个人开始继续报数，直到所有人出局为止。

任务：以 $ n = 9 $, $ s = 1 $, $ m = 5 $ 为例，人工模拟该过程，并输出出局顺序。

求解过程

  1. 初始状态：9 个人编号为 $ {1, 2, 3, 4, 5, 6, 7, 8, 9} $。
  2. 从第 $ s = 1 $ 个人开始数，数到第 $ m = 5 $ 人时，出局。
  3. 出局后从下一个人继续报数，重复步骤直到所有人出局。

人工模拟过程

  1. 初始人数：$ {1, 2, 3, 4, 5, 6, 7, 8, 9} \(。 **从第 1 个人开始报数**：\) 1 $。第 5 个人出局。

    出局序列：$ {5} $
    剩余：$ {1, 2, 3, 4, 6, 7, 8, 9} $。

  2. 继续报数，从第 6 个人开始：
    $ 6 $。第 1 个人出局。

    出局序列：$ {5, 1} $
    剩余：$ {2, 3, 4, 6, 7, 8, 9} $。

  3. 继续报数，从第 2 个人开始：
    $ 2 $。第 7 个人出局。

    出局序列：$ {5, 1, 7} $
    剩余：$ {2, 3, 4, 6, 8, 9} $。

  4. 继续报数，从第 8 个人开始：
    $ 8 $。第 4 个人出局。

    出局序列：$ {5, 1, 7, 4} $
    剩余：$ {2, 3, 6, 8, 9} $。

  5. 继续报数，从第 6 个人开始：
    $ 6 $。第 3 个人出局。

    出局序列：$ {5, 1, 7, 4, 3} $
    剩余：$ {2, 6, 8, 9} $。

  6. 继续报数，从第 6 个人开始：
    $ 6 $。第 6 个人出局。

    出局序列：$ {5, 1, 7, 4, 3, 6} $
    剩余：$ {2, 8, 9} $。

  7. 继续报数，从第 8 个人开始：
    $ 8 $。第 9 个人出局。

    出局序列：$ {5, 1, 7, 4, 3, 6, 9} $
    剩余：$ {2, 8} $。

  8. 继续报数，从第 2 个人开始：
    $ 2 $。第 2 个人出局。

    出局序列：$ {5, 1, 7, 4, 3, 6, 9, 2} $
    剩余：$ {8} $。

  9. 最后只剩下 8 个人。

最终出局顺序：$ {5, 1, 7, 4, 3, 6, 9, 2, 8} $。

小结

Josephus问题特点：

  1. 问题的核心是循环结构，可以通过队列或数组模拟。
  2. 每次选择出局的人后，重新调整开始点，循环递归直到完成。
  3. 时间复杂度：人工模拟为 $ O(n m) $。

问题

要求改写顺序栈的 Push(x) 成员函数，并在栈满时执行 stackFull() 操作进行栈满处理。栈满时的处理方式是：

  • 动态创建一个比原来栈数组大两倍的新数组。
  • 将原来栈数组中的元素复制到新数组的前 MaxSize 个位置。
  • 代替原来的栈数组为新数组。

解答

顺序栈的基本结构

顺序栈通常由一个固定大小的数组和一个指向栈顶的指针来实现。我们定义栈的结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;           // 存储栈元素的数组
    int top;            // 栈顶指针
    int MaxSize;       // 当前栈的大小
    int capacity;      // 栈的最大容量

public:
    Stack(int size);    // 构造函数，初始化栈
    ~Stack();           // 析构函数，释放内存
    void Push(int x);   // 进栈操作
    int Pop();          // 出栈操作
    bool isFull();      // 判断栈是否满
    bool isEmpty();     // 判断栈是否空
    void stackFull();   // 栈满时的处理函数
};

Stack::Stack(int size) {
    MaxSize = size;
    capacity = MaxSize;
    arr = new int[MaxSize];  // 动态分配内存
    top = -1;                // 初始化栈顶为-1，表示栈为空
}

Stack::~Stack() {
    delete[] arr;   // 释放动态分配的内存
}

bool Stack::isFull() {
    return top == MaxSize - 1;  // 栈满时栈顶指针为MaxSize-1
}

bool Stack::isEmpty() {
    return top == -1;  // 栈为空时栈顶指针为-1
}

void Stack::stackFull() {
    // 栈满时，扩展栈的大小，扩展为原大小的两倍
    int newCapacity = 2 * MaxSize;  // 新容量是原来的两倍
    int* newArr = new int[newCapacity];  // 创建新的数组

    // 将原数组中的元素复制到新数组
    for (int i = 0; i < MaxSize; i++) {
        newArr[i] = arr[i];
    }

    // 释放原数组的内存
    delete[] arr;

    // 更新栈的容量和指针
    arr = newArr;
    MaxSize = newCapacity;  // 更新栈的最大容量
    capacity = newCapacity; // 更新栈的实际容量
}

void Stack::Push(int x) {
    // 判断栈是否满，若满则执行栈满处理
    if (isFull()) {
        stackFull();
    }

    // 将元素压入栈顶
    arr[++top] = x;
}

int Stack::Pop() {
    if (isEmpty()) {
        cout << "Stack is empty!" << endl;
        return -1;  // 返回-1表示栈为空
    }

    return arr[top--];  // 返回栈顶元素并将栈顶指针向下移动
}

说明：

  1. 栈的初始化和扩展：
    • 栈初始化时，MaxSize 为栈的初始容量。
    • 如果栈满，在 Push(x) 函数中调用 stackFull() 函数。stackFull() 函数会将栈容量扩展为原来的两倍，并将原来栈中的元素复制到新的数组中。
  2. 进栈操作：
    • 在 Push(x) 操作中，首先检查栈是否已满（调用 isFull()）。如果栈已满，调用 stackFull() 扩展栈的容量。
    • 然后将元素压入栈顶（arr[++top] = x）。
  3. 栈满处理：
    • stackFull() 中创建一个新的比原来大两倍的数组，并将原栈的数据复制过去。然后更新栈的容量和 MaxSize。
  4. 析构函数：
    • 在栈销毁时，通过 delete[] arr 释放动态分配的内存。

测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
    Stack s(5);  // 初始栈大小为5

    // 压入元素
    for (int i = 1; i <= 10; i++) {
        s.Push(i);
        cout << "Pushed " << i << endl;
    }

    // 出栈操作
    while (!s.isEmpty()) {
        cout << "Popped " << s.Pop() << endl;
    }

    return 0;
}

输出示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Pushed 1
Pushed 2
Pushed 3
Pushed 4
Pushed 5
Pushed 6
Pushed 7
Pushed 8
Pushed 9
Pushed 10
Popped 10
Popped 9
Popped 8
Popped 7
Popped 6
Popped 5
Popped 4
Popped 3
Popped 2
Popped 1

小结：

  • 当栈满时，stackFull() 操作会扩展栈的容量，确保栈可以继续存储更多元素。
  • 动态扩展栈数组的容量是一种常见的处理栈满情况的方法。

问题

要求建立一个继承结构，以栈、队列和优先级队列为派生类，并建立它们的抽象基类 Bag 类。统一命名各派生类的操作，包含以下方法：

  • 插入操作：Add
  • 删除操作：Remove
  • 存取操作：Get 和 Put
  • 初始化操作：MakeEmpty
  • 判空操作：Empty
  • 判满操作：Full
  • 计数操作：Length

请写出各个类的声明。

解答

首先，我们需要设计一个抽象基类 Bag，然后为栈、队列和优先级队列类分别定义继承该基类的类。各类的操作（如 Add、Remove 等）应按照给定的要求进行统一命名。下面是具体实现：

1. 抽象基类 Bag 声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

// 抽象基类 Bag
class Bag {
public:
    virtual void Add(int x) = 0;      // 插入操作
    virtual void Remove() = 0;         // 删除操作
    virtual int Get() = 0;             // 存取操作
    virtual void Put(int x) = 0;       // 存取操作
    virtual void MakeEmpty() = 0;      // 初始化操作
    virtual bool Empty() const = 0;    // 判空操作
    virtual bool Full() const = 0;     // 判满操作
    virtual int Length() const = 0;    // 计数操作

    virtual ~Bag() {}                  // 虚析构函数
};

Bag 类是一个纯虚类，定义了所有派生类需要实现的接口。

2. 栈类 Stack 声明

栈类继承自 Bag 类，使用数组或链表实现栈的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Stack : public Bag {
private:
    int* arr;            // 栈数组
    int top;             // 栈顶指针
    int capacity;        // 栈的最大容量

public:
    Stack(int size);      // 构造函数
    ~Stack();             // 析构函数

    void Add(int x) override;      // 插入操作
    void Remove() override;        // 删除操作
    int Get() override;            // 存取操作
    void Put(int x) override;      // 存取操作
    void MakeEmpty() override;     // 初始化操作
    bool Empty() const override;   // 判空操作
    bool Full() const override;    // 判满操作
    int Length() const override;   // 计数操作
};

3. 队列类 Queue 声明

队列类继承自 Bag 类，实现队列的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Queue : public Bag {
private:
    int* arr;            // 队列数组
    int front;           // 队首指针
    int rear;            // 队尾指针
    int capacity;        // 队列的最大容量

public:
    Queue(int size);      // 构造函数
    ~Queue();             // 析构函数

    void Add(int x) override;      // 插入操作
    void Remove() override;        // 删除操作
    int Get() override;            // 存取操作
    void Put(int x) override;      // 存取操作
    void MakeEmpty() override;     // 初始化操作
    bool Empty() const override;   // 判空操作
    bool Full() const override;    // 判满操作
    int Length() const override;   // 计数操作
};

4. 优先级队列类 PriorityQueue 声明

优先级队列继承自 Bag 类，使用堆（如二叉堆）或其他方式实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class PriorityQueue : public Bag {
private:
    int* arr;            // 优先级队列数组
    int capacity;        // 队列的最大容量
    int length;          // 队列的当前长度

public:
    PriorityQueue(int size);    // 构造函数
    ~PriorityQueue();           // 析构函数

    void Add(int x) override;      // 插入操作
    void Remove() override;        // 删除操作
    int Get() override;            // 存取操作
    void Put(int x) override;      // 存取操作
    void MakeEmpty() override;     // 初始化操作
    bool Empty() const override;   // 判空操作
    bool Full() const override;    // 判满操作
    int Length() const override;   // 计数操作
};

各派生类的操作解释：

  1. Add: 将元素插入容器。在栈中，元素插入栈顶；在队列中，元素插入队尾；在优先级队列中，元素按优先级插入。

  2. Remove: 从容器中移除元素。在栈中，移除栈顶元素；在队列中，移除队首元素；在优先级队列中，移除优先级最高的元素。

  3. Get/Put: 用于访问或修改容器中的元素，Get 用来获取元素，Put 用来更新元素（虽然通常可以通过 Add 和 Remove 来实现访问操作，但这里为统一操作命名）。

  4. MakeEmpty: 初始化操作，清空容器。

  5. Empty: 判空操作，返回容器是否为空。

  6. Full: 判满操作，判断容器是否已满。

  7. Length: 计数操作，返回容器中的元素个数。

结论：

这个继承结构为栈、队列和优先级队列提供了统一的接口，通过基类 Bag 提供的虚函数进行实现。每个派生类根据其数据结构（栈、队列、优先级队列）实现具体的插入、删除、存取等操作。

问题

设计一个函数实现带表头结点的双向链表的 Locate 操作。链表的每个结点有四个数据成员：指向前驱结点的指针 prior、指向后继结点的指针 next、存放数据的成员 data 和访问频度 freq。所有结点的 freq 初始时为 0。每当进行一次 Locate(L, x) 操作时，令元素值为 x 的结点的访问频度 freq 加 1，并将该结点前移到与它的访问频度相等的结点后面，使链表始终保持按访问频度递减的顺序排列，使得频繁访问的结点总是靠近表头。

解答与解释

为了实现这个操作，我们需要：

  1. 查找元素 x: 遍历链表，找到元素值为 x 的结点。
  2. 增加访问频度: 将找到的结点的 freq 值加 1。
  3. 将结点前移: 结点按其频度递减的顺序排列，因此要将该结点移到它访问频度相等的结点后面，即链表中的某个位置。这个步骤需要操作结点的前驱和后继指针，确保链表的连接关系保持正确。

我们可以按以下步骤设计 Locate(L, x) 函数：

代码设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
using namespace std;

struct Node {
    int data;       // 存放数据
    int freq;       // 存放访问频度
    Node* prior;    // 指向前驱结点
    Node* next;     // 指向后继结点
};

class DoublyLinkedList {
public:
    Node* head; // 表头结点

    // 构造函数
    DoublyLinkedList() {
        head = new Node(); // 创建表头结点
        head->next = nullptr;
        head->prior = nullptr;
    }

    // Locate操作
    void Locate(int x) {
        Node* cur = head->next;  // 从表头开始查找
        Node* target = nullptr;

        // 查找值为x的结点
        while (cur != nullptr) {
            if (cur->data == x) {
                target = cur;
                break;
            }
            cur = cur->next;
        }

        if (target == nullptr) {
            cout << "Element not found!" << endl;
            return;
        }

        // 增加访问频度
        target->freq++;

        // 将target结点前移到正确位置
        Node* prevNode = target->prior;
        while (prevNode != nullptr && prevNode->freq < target->freq) {
            prevNode = prevNode->prior;
        }

        // 如果找到了可以插入的位置
        if (prevNode != nullptr) {
            // 将target结点移到prevNode后面
            if (target->prior != nullptr) {
                target->prior->next = target->next;
            }
            if (target->next != nullptr) {
                target->next->prior = target->prior;
            }
            
            target->prior = prevNode;
            target->next = prevNode->next;
            if (prevNode->next != nullptr) {
                prevNode->next->prior = target;
            }
            prevNode->next = target;
        }
    }

    // 打印链表
    void printList() {
        Node* cur = head->next;
        while (cur != nullptr) {
            cout << "(" << cur->data << ", " << cur->freq << ") ";
            cur = cur->next;
        }
        cout << endl;
    }
};

int main() {
    DoublyLinkedList L;

    // 示例：手动创建一些节点
    Node* n1 = new Node();
    n1->data = 1;
    n1->freq = 0;
    L.head->next = n1;
    n1->prior = L.head;

    Node* n2 = new Node();
    n2->data = 2;
    n2->freq = 0;
    n1->next = n2;
    n2->prior = n1;

    Node* n3 = new Node();
    n3->data = 3;
    n3->freq = 0;
    n2->next = n3;
    n3->prior = n2;

    // 调用Locate操作，进行测试
    L.Locate(2); // 对元素2进行Locate操作
    L.printList(); // 打印链表

    L.Locate(3); // 对元素3进行Locate操作
    L.printList(); // 打印链表

    L.Locate(2); // 对元素2进行Locate操作
    L.printList(); // 打印链表

    return 0;
}

解释

  1. 查找目标结点: Locate 函数首先遍历链表，查找数据值为 x 的结点。
  2. 增加频度: 一旦找到目标结点，将其访问频度 freq 增加 1。
  3. 前移结点: 接着，链表中结点的顺序要根据频度重新排序。我们将目标结点前移，直到它的位置合适，即比它频度小的结点都在它的后面。
  4. 调整链表指针: 当结点位置变化时，我们需要正确地调整前驱 (prior) 和后继 (next) 指针。

测试

通过对 Locate 函数的测试，可以验证元素是否按照访问频度递减的顺序排列。每次对某个元素执行 Locate 操作时，频度增加，并将该结点移到合适的位置。

小结

通过上述设计和实现，Locate 操作不仅能够增加频度，还能确保链表始终保持按访问频度递减的顺序排列，使得频繁访问的结点靠近表头。

问题

假设有一个二叉树，前序序列、后序序列和中序序列的定义如下：

  • 前序遍历：根—左子树—右子树
  • 中序遍历：左子树—根—右子树
  • 后序遍历：左子树—右子树—根

根据这些定义，解答如下：

  1. 若前序序列与后序序列相同，那么树的结构是怎样的？
  2. 若中序序列与后序序列相同，那么树的结构是怎样的？
  3. 若前序序列与中序序列相同，那么树的结构是怎样的？

解答与解释

1. 若前序序列与后序序列相同

  • 前序遍历：首先访问根结点，然后访问左子树，再访问右子树。
  • 后序遍历：首先访问左子树，然后访问右子树，最后访问根结点。

当前序序列与后序序列相同时，二叉树的结构非常特殊。前序和后序的遍历顺序要求每个结点首先访问根结点，然后是左子树或右子树。因此，只有在以下两种情况下，前序和后序序列才会完全相同：

  • 空树：没有任何结点时，前序和后序都为空。
  • 只有根结点的二叉树：这种树没有子树，因此前序和后序遍历的顺序是完全一致的。

例如，对于一个只有根结点的树：

1
1

前序和后序遍历都是 [1]。

2. 若中序序列与后序序列相同

  • 中序遍历：首先访问左子树，然后访问根结点，最后访问右子树。
  • 后序遍历：首先访问左子树，然后访问右子树，最后访问根结点。

当中序序列与后序序列相同时，树的结构也有特定要求。由于中序和后序的遍历顺序不同，只有每个结点至多只有左子树的树才能同时满足这两个序列。具体来说，树的每个结点只能有一个左子结点，右子结点不存在，否则中序和后序序列将不一致。

例如，对于一个树：

1
2
3
4
5
    1
   /
  2
 / 
3

中序和后序遍历都是 [3, 2, 1]。

3. 若前序序列与中序序列相同

  • 前序遍历：首先访问根结点，然后访问左子树，再访问右子树。
  • 中序遍历：首先访问左子树，然后访问根结点，最后访问右子树。

当前序序列与中序序列相同时，树的结构要求每个结点至多只有右子树。这是因为前序遍历首先访问根结点，然后是左子树或右子树，若中序和前序相同，那么根结点必须直接在前序和中序的相同位置，这只能通过每个结点只有右子树来实现。

例如，对于一个树：

1
2
3
4
5
1
 \
  2
   \
    3

前序和中序遍历都是 [1, 2, 3]。

总结

  1. 前序序列与后序序列相同：树只能是空树或只有根结点的树。
  2. 中序序列与后序序列相同：树只能是每个结点至多只有左子树的树。
  3. 前序序列与中序序列相同：树只能是每个结点至多只有右子树的树。