CS3334 数据结构 — 期中复习笔记

涵盖 Lec1–Lec6 全部内容，以 C++98 风格呈现，按数据结构与算法分类讲解。
所有代码片段均已在 ds_impl.cpp 中验证可编译并通过所有测试。
编译命令：g++ -std=c++98 -Wall -o ds_impl ds_impl.cpp

目录

1. 程序复杂度分析
2. 链表 Linked List
3. 栈 Stack
4. 队列 Queue
5. 散列表 Hash Table
6. 二叉树 Binary Tree
7. 二叉搜索树 BST
8. 普通树的二叉表示 General Tree → Binary Tree
9. 堆 Heap
10. 博弈树与图搜索 Game Tree / BFS / DFS

1. 程序复杂度分析

1.1 Big-O、Omega、Theta

常见复杂度排序（从小到大）：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)

1.2 插入排序复杂度分析示例

// Insertion Sort — 分析：外层循环 n-1 次，内层最多 i 次
for (int i = 1; i < n; i++) {
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key) {
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = key;
}
// 最坏情况（逆序）：T(n) = 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)
// 最好情况（已排序）：T(n) = O(n)

2. 链表 Linked List

2.1 基本节点结构

struct Node {
    int   info;   // 数据域
    Node* next;   // 指针域（单链表）
};

2.2 单链表 Singly Linked List

插入节点（在 pNode 之后插入）

void insertNode(Node* pNode, int newInfo) {
    Node* newNode = new Node;
    newNode->info = newInfo;
    newNode->next = pNode->next;  // ① 新节点指向后继
    pNode->next   = newNode;      // ② 前驱指向新节点
}

关键顺序：先连后面，再断前面，否则丢失后继链接。

删除节点（删除 pNode 的后继节点）

void removeNode(Node* pNode) {
    Node* pDel = pNode->next;    // 记录要删除的节点
    pNode->next = pDel->next;    // 绕过被删节点
    delete pDel;                 // 释放内存
}

2.3 虚拟头节点（Dummy Header Node）

在链表头部设置一个不存储实际数据的哨兵节点，使所有插入/删除操作统一，消除对"第一个节点"的特殊判断。

// 初始化：dummy->next = NULL（空链表）
Node* dummy = new Node;
dummy->next = NULL;

// 插入到链表头（即 dummy 之后）
insertNode(dummy, value);

// 遍历（跳过 dummy 本身）
Node* cur = dummy->next;
while (cur != NULL) {
    cout << cur->info << " ";
    cur = cur->next;
}

2.4 双向链表 Doubly Linked List

struct DNode {
    int   info;
    DNode* prev;  // 前驱指针
    DNode* next;  // 后继指针
};

双向链表插入（在 pNode 之后）

void insertDouble(DNode* pNode, int newInfo) {
    DNode* newNode = new DNode;
    newNode->info = newInfo;
    newNode->next = pNode->next;
    newNode->prev = pNode;
    if (pNode->next != NULL)
        pNode->next->prev = newNode;  // 后继的 prev 指向新节点
    pNode->next = newNode;
}

双向链表删除（删除节点 pDel）

void removeDouble(DNode* pDel) {
    if (pDel->prev != NULL)
        pDel->prev->next = pDel->next;
    if (pDel->next != NULL)
        pDel->next->prev = pDel->prev;
    delete pDel;
}

2.5 循环链表 Circular Linked List

• 最后一个节点的 next 指向头节点（或 dummy），形成环。
• 常用尾指针（tail）维护，方便在末尾插入：tail->next = head。

head → [A] → [B] → [C] → (回到 head)

2.6 复杂度对比

3. 栈 Stack

3.1 ADT 定义

栈是后进先出（LIFO）的线性结构。

操作：
  Push(x)  — 入栈
  Pop()    — 出栈并返回栈顶元素
  Top()    — 查看栈顶（不删除）
  IsEmpty() — 判断是否为空

3.2 实现一：固定大小数组

#define MAX_SIZE 100
class MyStack {
private:
    int items[MAX_SIZE];
    int top;       // 指向栈顶元素的下标（空栈时为 -1）
public:
    MyStack() : top(-1) {}

    void Push(int x) {
        if (top == MAX_SIZE - 1) { /* 栈满，错误处理 */ return; }
        items[++top] = x;
    }

    int Pop() {
        if (top == -1) { /* 栈空，错误处理 */ return -1; }
        return items[top--];
    }

    int Top() { return items[top]; }
    bool IsEmpty() { return top == -1; }
};

3.3 实现二：动态数组（自动扩容）

class DynStack {
private:
    int* items;
    int  capacity;
    int  top;
public:
    DynStack(int cap = 10) : capacity(cap), top(-1) {
        items = new int[capacity];
    }
    ~DynStack() { delete[] items; }

    void Push(int x) {
        if (top == capacity - 1) {          // 扩容：申请双倍空间
            int* newItems = new int[capacity * 2];
            for (int i = 0; i <= top; i++)
                newItems[i] = items[i];
            delete[] items;
            items = newItems;
            capacity *= 2;
        }
        items[++top] = x;
    }

    int Pop() { return items[top--]; }
    bool IsEmpty() { return top == -1; }
};

3.4 实现三：链表栈

struct SNode {
    int   info;
    SNode* next;
};

class LinkedStack {
private:
    SNode* head;   // 头节点即栈顶
public:
    LinkedStack() : head(NULL) {}

    void Push(int x) {
        SNode* newNode = new SNode;
        newNode->info = x;
        newNode->next = head;
        head = newNode;
    }

    int Pop() {
        if (head == NULL) return -1;
        int val = head->info;
        SNode* temp = head;
        head = head->next;
        delete temp;
        return val;
    }

    bool IsEmpty() { return head == NULL; }
};

3.5 栈的经典应用

• 括号匹配：遇到左括号入栈，遇到右括号出栈匹配
• 函数调用栈：保存返回地址、局部变量
• 表达式求值：中缀转后缀（逆波兰表达式）
• 非递归树遍历：见第6节

4. 队列 Queue

4.1 ADT 定义

队列是先进先出（FIFO）的线性结构。

操作：
  Enqueue(x) — 入队（队尾）
  Dequeue()  — 出队（队头）并返回值
  IsEmpty()  — 判断是否为空

4.2 实现一：循环数组队列

用取模运算避免"假满"问题。

#define QSIZE 100
class ArrayQueue {
private:
    int items[QSIZE];
    int front;  // 队头下标
    int rear;   // 队尾下一个空位下标
    int count;  // 当前元素个数
public:
    ArrayQueue() : front(0), rear(0), count(0) {}

    void Enqueue(int x) {
        if (count == QSIZE) return;   // 队满
        items[rear] = x;
        rear = (rear + 1) % QSIZE;   // 循环推进
        count++;
    }

    int Dequeue() {
        if (count == 0) return -1;   // 队空
        int val = items[front];
        front = (front + 1) % QSIZE;
        count--;
        return val;
    }

    bool IsEmpty() { return count == 0; }
};

循环数组关键：front 和 rear 均使用 (index + 1) % QSIZE 前进，count 追踪元素数量（区分满/空）。

4.3 实现二：链表队列

struct QNode {
    int   info;
    QNode* next;
};

class LinkedQueue {
private:
    QNode* front;  // 队头
    QNode* rear;   // 队尾
public:
    LinkedQueue() : front(NULL), rear(NULL) {}

    void Enqueue(int x) {
        QNode* newNode = new QNode;
        newNode->info = x;
        newNode->next = NULL;
        if (rear == NULL) {           // 空队列
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    int Dequeue() {
        if (front == NULL) return -1;
        int val = front->info;
        QNode* temp = front;
        front = front->next;
        if (front == NULL) rear = NULL;  // 队列变空
        delete temp;
        return val;
    }

    bool IsEmpty() { return front == NULL; }
};

4.4 优先队列 Priority Queue

元素按优先级而非入队顺序出队，优先级最高（或最低）的元素最先被取出。

• 朴素实现：每次 Dequeue 线性扫描找最优元素，O(n)
• 高效实现：堆（Heap），见第9节，Enqueue/Dequeue 均为 O(log n)

5. 散列表 Hash Table

5.1 核心思想

通过哈希函数 h(key) 将关键字映射到数组下标，实现 O(1) 平均查找。

5.2 常见哈希函数

// 取模法（table_size 取质数，减少碰撞）
int hash(int key, int table_size) {
    return key % table_size;
}

// 字符串哈希（多项式累加）
int hash(const string& key, int table_size) {
    int h = 0;
    for (int i = 0; i < key.length(); i++)
        h = (h * 31 + key[i]) % table_size;
    return h;
}

为什么 table_size 取质数？ 质数能使关键字在散列表中分布更均匀，减少聚集。

5.3 碰撞处理

6. 二叉树 Binary Tree

6.1 术语

6.2 满二叉树 vs 完全二叉树

满二叉树（Full Binary Tree）：每层节点都达到最大数量。

• 高度为 h 的满二叉树共有 2^(h+1) - 1 个节点。

完全二叉树（Complete Binary Tree）：最后一层节点从左到右连续填充，其余层全满。

• n 个节点的完全二叉树高度为 ⌊log₂ n⌋。

6.3 二叉树的性质

• 第 i 层最多有 2^i 个节点（根为第 0 层）
• 高度为 h 的二叉树最多有 2^(h+1) - 1 个节点
• 设叶节点数为 n₀，度为2的节点数为 n₂，则 n₀ = n₂ + 1

6.4 二叉树的存储

数组表示（完全二叉树最优）

节点存于数组 items[0..n-1]，下标关系：

数组: [A, B, C, D, E, F, G]
下标:  0   1   2   3   4   5   6

          A(0)
         /    \
       B(1)   C(2)
      /  \   /  \
    D(3) E(4) F(5) G(6)

链式表示

struct TreeNode {
    int       info;
    TreeNode* left;
    TreeNode* right;
};

class MyTree {
private:
    TreeNode* root;
public:
    MyTree() : root(NULL) {}
    // ...
};

6.5 二叉树基本操作

求树的高度（递归）

// 空树返回 -1，叶节点返回 0
int MyTree::height(TreeNode* node) {
    if (node == NULL)
        return -1;
    int leftH  = height(node->left);
    int rightH = height(node->right);
    return 1 + (leftH > rightH ? leftH : rightH);
}

递归逻辑：树的高度 = 1 + max(左子树高度, 右子树高度)。空树定义高度为 -1，叶节点高度为 0。

统计叶节点数（递归）

int MyTree::countLeaf(TreeNode* node) {
    if (node == NULL)
        return 0;
    if (node->left == NULL && node->right == NULL)
        return 1;                             // 叶节点
    return countLeaf(node->left) + countLeaf(node->right);
}

判断两棵树是否相同（递归）

bool MyTree::equal(TreeNode* a, TreeNode* b) {
    if (a == NULL && b == NULL)
        return true;
    if (a == NULL || b == NULL)
        return false;
    return (a->info == b->info)
        && equal(a->left,  b->left)
        && equal(a->right, b->right);
}

6.6 二叉树遍历

三种递归遍历

// 前序遍历：根 → 左 → 右
void MyTree::PreorderHelper(TreeNode* node) {
    if (node != NULL) {
        cout << node->info << " ";     // 访问根
        PreorderHelper(node->left);
        PreorderHelper(node->right);
    }
}

// 中序遍历：左 → 根 → 右
void MyTree::InorderHelper(TreeNode* node) {
    if (node != NULL) {
        InorderHelper(node->left);
        cout << node->info << " ";     // 访问根
        InorderHelper(node->right);
    }
}

// 后序遍历：左 → 右 → 根
void MyTree::PostorderHelper(TreeNode* node) {
    if (node != NULL) {
        PostorderHelper(node->left);
        PostorderHelper(node->right);
        cout << node->info << " ";     // 访问根
    }
}

记忆技巧：前/中/后序指的是根节点访问的时机（前=最先，中=中间，后=最后），左右子树始终先左后右。

非递归中序遍历（使用指针数组栈）

// 用固定大小的指针数组模拟栈，避免 int/指针 混用
void MyTree::InorderNonRecursive(TreeNode* rootNode) {
    TreeNode* stk[100];   // 直接存 TreeNode*，不做截断转换
    int top = -1;
    TreeNode* cur = rootNode;

    while (cur != NULL || top != -1) {
        // 阶段1：一路向左，沿途压栈
        while (cur != NULL) {
            stk[++top] = cur;
            cur = cur->left;
        }
        // 阶段2：弹出、访问、转向右子树
        cur = stk[top--];
        cout << cur->info << " ";
        cur = cur->right;
    }
}

执行逻辑：

1. 将当前节点及所有左子节点压栈
2. 弹出栈顶节点，访问它
3. 将右子节点设为当前节点，重复步骤1

从遍历序列重建二叉树

已知前序 + 中序 → 唯一确定二叉树

• 前序序列第一个元素是根节点
• 在中序序列中找到根节点，根节点左侧为左子树，右侧为右子树
• 递归地对左右子树重复上述过程

示例：

前序: A B D E C F G
中序: D B E A F C G

根 = A
中序中 A 在第4位：左子树 = {D,B,E}，右子树 = {F,C,G}
左子树前序: B D E → 根 = B，中序 D B E → 左=D，右=E
右子树前序: C F G → 根 = C，中序 F C G → 左=F，右=G

结果：
        A
       / \
      B   C
     / \ / \
    D  E F  G

7. 二叉搜索树 BST

7.1 定义

二叉搜索树满足：

• 每个节点的值 > 其左子树所有节点的值
• 每个节点的值 < 其右子树所有节点的值
• 左右子树本身也是 BST

中序遍历 BST 得到有序序列（升序）。

7.2 BST 查找

TreeNode* MyBST::search(TreeNode* node, int key) {
    if (node == NULL)       return NULL;   // 未找到
    if (key == node->info)  return node;   // 找到
    if (key < node->info)
        return search(node->left, key);    // 在左子树查找
    else
        return search(node->right, key);   // 在右子树查找
}

7.3 BST 插入

TreeNode* MyBST::insert(TreeNode* node, int key) {
    if (node == NULL) {                   // 找到插入位置
        TreeNode* newNode = new TreeNode;
        newNode->info  = key;
        newNode->left  = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (key < node->info)
        node->left  = insert(node->left,  key);
    else if (key > node->info)
        node->right = insert(node->right, key);
    // key == node->info：重复，不插入
    return node;
}

7.4 BST 删除（三种情况）

待删除节点为 D

情况1：D 是叶节点（无子节点）

直接删除 D，将父节点对应的子指针设为 NULL。

// parent->left = NULL; 或 parent->right = NULL;
delete D;

情况2：D 只有一个子树

用 D 的唯一子树的根替代 D 的位置（"绕过"D）。

// 若 D 只有右子树
if (parent->left == D)
    parent->left = D->right;
else
    parent->right = D->right;
delete D;

情况3：D 有两个子树

找到 D 的中序后继（右子树中最左边的节点，即右子树中值最小的节点）。
将 D 的值替换为中序后继的值。
然后删除中序后继节点（该节点至多只有一个右子节点，转化为情况1或2）。

TreeNode* MyBST::deleteNode(TreeNode* node, int key) {
    if (node == NULL) return NULL;

    if (key < node->info) {
        node->left = deleteNode(node->left, key);
    } else if (key > node->info) {
        node->right = deleteNode(node->right, key);
    } else {
        // 找到要删除的节点
        if (node->left == NULL) {       // 情况1或情况2（无左子树）
            TreeNode* temp = node->right;
            delete node;
            return temp;
        } else if (node->right == NULL) { // 情况2（无右子树）
            TreeNode* temp = node->left;
            delete node;
            return temp;
        } else {                        // 情况3：找中序后继
            // 找右子树最左节点
            TreeNode* successor = node->right;
            while (successor->left != NULL)
                successor = successor->left;
            node->info = successor->info;           // 替换值
            node->right = deleteNode(node->right, successor->info); // 删后继
        }
    }
    return node;
}

7.5 BST 复杂度

最坏情况：按升序或降序插入所有元素，BST 退化为一条链（相当于链表），此时所有操作变为 O(n)。

8. 普通树的二叉表示 General Tree → Binary Tree

8.1 思路

普通树中每个节点可能有任意多个子节点，存储不便。

转换方法：用两个指针替代"子节点列表"：

• firstChild：指向第一个子节点
• nextSibling：指向下一个兄弟节点

8.2 节点结构

struct TreeNode {
    int       element;
    TreeNode* firstChild;    // 长子
    TreeNode* nextSibling;  // 下一个兄弟
};

8.3 转换示例

普通树：
        A
      / | \
     B  C  D
    /\     |
   E  F    G

二叉表示（firstChild-nextSibling）：
A.firstChild = B
B.nextSibling = C
C.nextSibling = D
B.firstChild = E
E.nextSibling = F
D.firstChild = G

可视化为二叉树（左=firstChild，右=nextSibling）：

A
|
B → C → D
|         |
E → F     G

9. 堆 Heap

9.1 定义

最小堆（Min-Heap） 是满足以下条件的完全二叉树：

1. 结构性质：是完全二叉树（用数组紧凑存储）
2. 堆序性质：每个节点的值 ≤ 其所有子节点的值（根节点为最小值）

最大堆（Max-Heap） 类似，但每个节点的值 ≥ 其子节点。

9.2 数组表示

堆用数组存储，下标关系与完全二叉树相同：

• Left(i) = 2i + 1，Right(i) = 2i + 2，Parent(i) = (i-1)/2

9.3 堆的 ADT

#define TOTAL_SLOTS 100

class MyHeap {
private:
    int size;
    int items[TOTAL_SLOTS];
public:
    MyHeap() : size(0) {}
    void Insert(int key);
    int  DeleteMin();
};

9.4 Insert — 上浮（Float Up）

算法：

1. 将新元素放在数组末尾（items[size]）
2. 与父节点比较，若小于父节点则交换（上浮）
3. 重复步骤2，直到满足堆序或到达根节点

void MyHeap::Insert(int key) {
    int i = size;
    items[i] = key;                        // ① 放入末尾
    while (i != 0 && items[i] < items[(i-1)/2]) {  // ② 与父节点比较
        // 交换
        int temp       = items[i];
        items[i]       = items[(i-1)/2];
        items[(i-1)/2] = temp;
        i = (i-1)/2;                       // ③ 上移一层
    }
    size++;
}

时间复杂度：O(log n)（上浮最多 log n 层）

示例：插入 3 到 [1, 5, 7, 8, 9] 中：

初始: [1, 5, 7, 8, 9], 插入3 → [1, 5, 7, 8, 9, 3]
3 与父节点 items[(5-1)/2]=items[2]=7 比较: 3<7, 交换 → [1, 5, 3, 8, 9, 7]
3 与父节点 items[(2-1)/2]=items[0]=1 比较: 3>1, 停止
最终: [1, 5, 3, 8, 9, 7]

9.5 DeleteMin — 下沉（Sink Down）

算法：

1. 记录并移除根节点（最小值）
2. 将最后一个元素移到根位置，size--
3. 将根与较小的子节点比较，若大于子节点则交换（下沉）
4. 重复步骤3，直到满足堆序或到达叶节点

int MyHeap::DeleteMin() {
    if (size == 0) return -1;

    int value = items[0];              // ① 记录最小值
    size--;
    items[0] = items[size];            // ② 末尾元素移到根

    // ③ 下沉（sink down）
    int hole  = 0;
    int temp  = items[hole];
    int child;
    for (; hole * 2 + 1 < size; hole = child) {
        child = hole * 2 + 1;          // 左子节点
        // 选较小的子节点
        if (child + 1 < size && items[child + 1] < items[child])
            child++;
        if (items[child] < temp)
            items[hole] = items[child]; // 子节点上移
        else
            break;
    }
    items[hole] = temp;                // ④ 放入最终位置
    return value;
}

时间复杂度：O(log n)

示例：从 [1, 5, 3, 8, 9, 7] 删除最小值：

取出根 1，末尾元素 7 放到根: [7, 5, 3, 8, 9]
7 与左子5、右子3比较，选较小的右子3: 7>3，交换 → [3, 5, 7, 8, 9]
7 到达叶节点位置，停止
最终: [3, 5, 7, 8, 9]，返回 1

9.6 堆操作复杂度总结

10. 博弈树与图搜索 Game Tree / BFS / DFS

10.1 博弈树 Game Tree

博弈树用于双人零和博弈（如象棋、井字棋）的决策分析：

• MAX 层：当前玩家选择最大化自身得分的走法
• MIN 层：对手选择最小化当前玩家得分的走法
• 两者交替

10.2 Minimax 算法

minimax(node, depth, isMaxPlayer):
  若 node 是叶节点或 depth == 0:
    返回评估值（heuristic value）

  若 isMaxPlayer:
    best = -∞
    对每个子节点 child:
      val = minimax(child, depth-1, false)
      best = max(best, val)
    返回 best

  否则（MIN 玩家）:
    best = +∞
    对每个子节点 child:
      val = minimax(child, depth-1, true)
      best = min(best, val)
    返回 best

10.3 广度优先搜索 BFS（使用队列）

BFS 按层次展开，逐层访问节点（等同于层次遍历）。

// 用指针数组实现循环队列，直接存 TreeNode*
void BFS(TreeNode* root) {
    if (root == NULL) return;

    TreeNode* q[100];       // 指针队列
    int front = 0, rear = 0;
    q[rear++] = root;       // 根节点入队

    while (front != rear) {
        TreeNode* node = q[front++];
        cout << node->info << " ";    // 访问当前节点

        if (node->left  != NULL) q[rear++] = node->left;
        if (node->right != NULL) q[rear++] = node->right;
    }
}

特点：

• 使用 FIFO 队列
• 按层次顺序访问（第0层→第1层→第2层…）
• 适合寻找最短路径

10.4 深度优先搜索 DFS

DFS 沿路径尽可能深入，退回后再探索其他路径。

树中的 DFS 等价于前序遍历：

void DFS(TreeNode* node) {
    if (node == NULL) return;
    cout << node->info << " ";   // 访问节点（前序位置）
    DFS(node->left);
    DFS(node->right);
}

也可用显式栈实现非递归 DFS：

// 同样用指针数组栈，避免 int/指针 混用
void DFS_stack(TreeNode* root) {
    if (root == NULL) return;

    TreeNode* stk[100];
    int top = -1;
    stk[++top] = root;

    while (top != -1) {
        TreeNode* node = stk[top--];
        cout << node->info << " ";

        // 先压右子节点，再压左子节点（保证左子先被访问）
        if (node->right != NULL) stk[++top] = node->right;
        if (node->left  != NULL) stk[++top] = node->left;
    }
}

10.5 BFS vs DFS 对比

附录：常见考点速查

链表

• 插入时先连后继，再接前驱
• 虚拟头节点消除边界特殊处理
• 双向链表删除时需更新 prev 和 next 两侧

栈 / 队列

• 栈：LIFO，Push/Pop 在同一端
• 队列：FIFO，Enqueue 在队尾，Dequeue 在队头
• 循环数组：用 (index+1) % SIZE 推进，count 区分满空

二叉树

• 高度 h 的满二叉树：2^(h+1) - 1 个节点
• 数组下标：Left=2i+1，Right=2i+2，Parent=(i-1)/2
• 前序第一个 = 根，中序中根的左侧 = 左子树
• 非递归中序：左走到底压栈 → 弹出访问 → 转右子树

BST

• 中序遍历 = 升序序列
• 删除3种情况：无子 → 直接删；一子 → 绕过；两子 → 换中序后继再删后继

堆

• 最小堆：父 ≤ 子（根是最小值）
• Insert：放末尾 → 上浮（与父比较交换）
• DeleteMin：取根 → 末尾放根 → 下沉（与较小子比较交换）
• 两者均为 O(log n)

遍历