# C++11 数据结构（指针与结构体替代版）讲义

在算法竞赛（如 CSP、NOIP）以及追求高执行效率、较低内存开销的场景中，**使用静态数组与独立函数模拟链表、树和图**是一种常用且有效的实现方式。

本讲义不使用任何原生指针（如 `*`）、智能指针（如 `std::unique_ptr`）或自定义结构体（`struct`），全部改用**多个一维数组（平行数组，Parallel Arrays）**与**全局变量**进行状态维护。这符合 C++11 标准，并能有效规避指针悬挂、内存泄露等常见问题。

---

## 1. 线性结构

### 1.1 静态数组模拟单链表、双向链表、循环链表

用数组模拟链表的核心思想是：用数组下标代替内存地址（指针）。

#### 1. 单链表 (Singly Linked List) 模拟
我们使用两个核心数组：
*   `e[i]`：存储节点 $i$ 的数值（Data）。
*   `ne[i]`：存储节点 $i$ 的下一个节点的下标（Next Pointer）。
*   `head`：头指针变量，存储链表头节点的下标。
*   `idx`：分配器变量，存储当前尚未被使用的最新节点的下标。

##### 核心操作实现
```cpp
#include <iostream>

// C++11 支持 constexpr
constexpr int N = 100010; // 链表最大节点数（C++11 不支持单引号数字分隔符）

int head, e[N], ne[N], idx;

// 初始化
void init() {
    head = -1; // -1 表示空指针
    idx = 0;   // 从下标 0 开始分配节点
}

// 在链表头部插入元素 x
void add_to_head(int x) {
    e[idx] = x;       // 记录当前节点的值
    ne[idx] = head;   // 当前节点的 next 指向原 head
    head = idx;       // head 更新为当前节点
    idx++;            // 分配器后移
}

// 在第 k 个插入的节点后面插入元素 x（k 从 0 开始算）
void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 删除第 k 个插入的节点后面的节点
void remove(int k) {
    ne[k] = ne[ne[k]];
}

// 遍历链表
void print_list() {
    for (int i = head; i != -1; i = ne[i]) {
        std::cout << e[i] << " -> ";
    }
    std::cout << "null" << std::endl;
}
```

#### 2. 双向链表 (Doubly Linked List) 模拟
在双向链表中，每个节点需要两个方向的指针：
*   `e[i]`：存储节点值。
*   `l[i]`：存储节点左侧节点的下标。
*   `r[i]`：存储节点右侧节点的下标。
*   **哨兵节点**：为了简化边界处理，通常固定用 `0` 表示虚拟头节点（head），`1` 表示虚拟尾节点（tail）。`idx` 从 `2` 开始分配。

##### 核心操作实现
```cpp
int e[N], l[N], r[N], idx;

// 初始化
void init_doubly() {
    // 0 是左端点（头哨兵），1 是右端点（尾哨兵）
    r[0] = 1;
    l[1] = 0;
    idx = 2; // 实际节点从 2 开始分配
}

// 在第 k 个插入的节点右侧插入一个新节点（值为 x）
void insert_right(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx++;
}

// 删除第 k 个插入的节点
void remove_node(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
```

#### 3. 循环链表 (Circular Linked List) 模拟
要实现单向循环链表，只需在建立链表时，将最后一个节点的 `ne` 指针指向头节点（或将 `ne[tail] = head`）即可。

---

### 1.2 静态数组模拟栈 (Stack)

栈是一种后进先出 (LIFO) 的结构，用一维数组和整型变量 `tt`（Top Pointer）即可模拟。

```cpp
int stk[N], tt = 0; // tt = 0 表示栈空，元素从 1 开始存储

// 入栈
void push(int x) {
    stk[++tt] = x;
}

// 出栈
void pop() {
    if (tt > 0) tt--;
}

// 获取栈顶元素
int top() {
    return stk[tt];
}

// 判断栈是否为空
bool empty() {
    return tt == 0;
}
```

---

### 1.3 静态数组模拟队列 (Queue)

队列是一种先进先出 (FIFO) 的结构。我们使用 `hh`（Head Pointer）指向队头，`tt`（Tail Pointer）指向队尾的下一个位置。

#### 1. 简易队列
```cpp
int q[N], hh = 0, tt = 0; // [hh, tt) 为队列区间

// 入队
void push_queue(int x) {
    q[tt++] = x;
}

// 出队
void pop_queue() {
    if (hh < tt) hh++;
}

// 获取队头
int front_queue() {
    return q[hh];
}

// 队列是否为空
bool empty_queue() {
    return hh == tt;
}
```

#### 2. 循环队列 (防止内存越界)
若生存周期内有大量的入队和出队操作，需要使用模运算循环利用数组空间：
```cpp
int cq[N], hh = 0, tt = 0; // 数组大小 N

bool cq_push(int x) {
    if ((tt + 1) % N == hh) return false; // 队满
    cq[tt] = x;
    tt = (tt + 1) % N;
    return true;
}

bool cq_pop() {
    if (hh == tt) return false; // 队空
    hh = (hh + 1) % N;
    return true;
}
```

---

## 2. 简单树

### 2.1 树的静态表示法

对于一棵普通的树（度大于2的多叉树），若不用结构体和指针，可以通过**邻接表（链式前向星）**将其子节点存储为拉链结构。此方法将在“第4节 图的基础”中讲解。

在二叉树场景下，我们使用三个平行数组即可完成定义。

---

### 2.2 二叉树定义、性质与静态数组表示

#### 1. 数组表示法 (Parallel Arrays for Binary Tree)
对于一般的二叉树，我们使用如下一维数组：
*   `val[i]`：节点 $i$ 的数值。
*   `l[i]`：节点 $i$ 的左孩子节点的下标。若没有，则设为 `-1`。
*   `r[i]`：节点 $i$ 的右孩子节点的下标。若没有，则设为 `-1`。
*   `root`：记录根节点的下标。
*   `idx`：新节点的分配器。

#### 2. 遍历方式：前序、中序、后序的递归函数实现
无需在结构体中定义成员函数，写成外部递归函数即可：

```cpp
#include <iostream>

constexpr int MAX_NODES = 100010;

int val[MAX_NODES];
int l[MAX_NODES];
int r[MAX_NODES];
int root, idx;

// 初始化树
void init_tree() {
    root = -1;
    idx = 0;
}

// 创建一个新节点
int create_node(int x) {
    val[idx] = x;
    l[idx] = -1;
    r[idx] = -1;
    return idx++;
}

// 前序遍历 (根 -> 左 -> 右)
void pre_order(int u) {
    if (u == -1) return;
    std::cout << val[u] << " ";
    pre_order(l[u]);
    pre_order(r[u]);
}

// 中序遍历 (左 -> 根 -> 右)
void in_order(int u) {
    if (u == -1) return;
    in_order(l[u]);
    std::cout << val[u] << " ";
    in_order(r[u]);
}

// 后序遍历 (左 -> 右 -> 根)
void post_order(int u) {
    if (u == -1) return;
    post_order(l[u]);
    post_order(r[u]);
    std::cout << val[u] << " ";
}
```

---

## 3. 特殊树

### 3.1 完全二叉树的一维数组表示法

完全二叉树因其结构紧凑的性质，**不需要记录任何孩子节点的下标**，仅用一个一维数组 `tree[i]` 就能完整表达整棵树。

#### 1. 索引映射性质与推导（1-Based Indexing）
设根节点存储在数组下标为 `1` 的位置：
*   对于任意一个位于下标 $i$ 的节点：
    *   其**左孩子**位于 $2i$。
    *   其**右孩子**位于 $2i + 1$。
    *   其**双亲（父节点）**位于 $\lfloor i / 2 \rfloor$。
*   **边界判定**：若总节点数为 $n$，如果 $2i > n$，则节点 $i$ 没有左孩子；如果 $2i + 1 > n$，则节点 $i$ 没有右孩子。

#### 2. 位运算
在 C++11 中，可以使用位运算来代替部分乘除法：
*   左孩子位置 $2i \implies$ `i << 1`
*   右孩子位置 $2i + 1 \implies$ `(i << 1) | 1`
*   父节点位置 $\lfloor i/2 \rfloor \implies$ `i >> 1`

---

### 3.2 哈夫曼树 (Huffman Tree) 的构造

哈夫曼树的构造通常涉及不断合并两个最小权值的节点。为了避免使用结构体，我们可以将所有节点（包括叶子节点与合并后的父节点）统一视为数组中的一个索引，并通过 `std::pair` 在优先队列中建立关联。

#### C++11 实现（基于静态数组与 std::pair 优先队列）
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

constexpr int MAX_HUFFMAN_NODES = 200010;

int h_val[MAX_HUFFMAN_NODES]; // 节点的权值
int h_l[MAX_HUFFMAN_NODES];   // 左孩子索引
int h_r[MAX_HUFFMAN_NODES];   // 右孩子索引
int h_idx;                    // 静态节点分配器

// 构造哈夫曼树
int build_huffman(const std::vector<int>& weights) {
    h_idx = 0;
    
    // 优先队列存储 std::pair<int, int> -> {权值, 节点下标}
    // std::greater 默认会对 pair 的第一个成员（权值）进行小顶堆排序
    std::priority_queue<std::pair<int, int>, 
                        std::vector<std::pair<int, int>>, 
                        std::greater<std::pair<int, int>>> pq;
                        
    // 1. 初始化叶子节点
    for (int w : weights) {
        h_val[h_idx] = w;
        h_l[h_idx] = -1;
        h_r[h_idx] = -1;
        pq.push(std::make_pair(w, h_idx)); // C++11 兼容 make_pair
        h_idx++;
    }
    
    // 2. 循环合并最小的两个节点
    while (pq.size() > 1) {
        auto left_node = pq.top(); pq.pop();
        auto right_node = pq.top(); pq.pop();
        
        int w1 = left_node.first;
        int u1 = left_node.second;
        int w2 = right_node.first;
        int u2 = right_node.second;
        
        // 创建新的合并父节点
        h_val[h_idx] = w1 + w2;
        h_l[h_idx] = u1;
        h_r[h_idx] = u2;
        
        pq.push(std::make_pair(h_val[h_idx], h_idx));
        h_idx++;
    }
    
    // 返回根节点的下标
    return pq.top().second;
}
```

---

### 3.3 二叉搜索树 (BST) 的构造与查询

二叉搜索树可以通过平行数组进行插入与检索。

#### C++11 实现
```cpp
int bst_val[MAX_NODES];
int bst_l[MAX_NODES];
int bst_r[MAX_NODES];
int bst_root, bst_idx;

void init_bst() {
    bst_root = -1;
    bst_idx = 0;
}

// 递归插入，利用引用改变上级孩子指针的值
void insert_bst(int& u, int x) {
    if (u == -1) {
        u = bst_idx++;
        bst_val[u] = x;
        bst_l[u] = -1;
        bst_r[u] = -1;
        return;
    }
    if (x < bst_val[u]) {
        insert_bst(bst_l[u], x);
    } else if (x > bst_val[u]) {
        insert_bst(bst_r[u], x);
    }
}

// 检索是否存在该值
bool search_bst(int u, int x) {
    if (u == -1) return false;
    if (bst_val[u] == x) return true;
    return x < bst_val[u] ? search_bst(bst_l[u], x) : search_bst(bst_r[u], x);
}
```

---

## 4. 图的基础

在图论算法中，“邻接表”通常采用一种被称为**“链式前向星”**的静态机制来实现。它使用数组模拟邻接表中的单链表结构，执行效率较为稳定。

### 4.1 邻接矩阵 (Adjacency Matrix)
适合存储稠密图（通常 $V \le 1000$）。
```cpp
constexpr int V_MAX = 1010;
int g[V_MAX][V_MAX]; // 二维邻接矩阵

void add_matrix_edge(int u, int v, int w = 1) {
    g[u][v] = w; // 有向边
}
```

---

### 4.2 链式前向星 (Static Adjacency List)

链式前向星是竞赛中常用的图存储结构。它的本质是给图中的每个顶点 $u$ 都维护一个单链表，这个单链表存储所有从 $u$ 出发的边。

#### 1. 数组定义
*   `h[i]`：指向顶点 $i$ 的第一条边的位置（头指针）。初始化为 `-1`。
*   `to[e]`：第 $e$ 条边指向的终点节点。
*   `w[e]`：第 $e$ 条边的权值。
*   `ne[e]`：与第 $e$ 条边同起点的下一条边的索引位置。
*   `idx`：当前边的分配器（边数）。

#### 2. 核心插边操作推导（头插法）
假设增加一条有向边 $u \to v$，权值为 $weight$：
1. `to[idx] = v`：记录这条边的终点。
2. `w[idx] = weight`：记录这条边的权重。
3. `ne[idx] = h[u]`：新边的 `next` 指向当前 $u$ 顶点的第一条边（头插法）。
4. `h[u] = idx`：将顶点 $u$ 的链表头更新为当前新边。
5. `idx++`：边计数器自增。

#### 3. C++11 链式前向星实现
```cpp
#include <iostream>
#include <algorithm>

constexpr int N_VERTICES = 10010; // 顶点数
constexpr int M_EDGES = 100010;   // 边数

int h[N_VERTICES], to[M_EDGES], w[M_EDGES], ne[M_EDGES], edge_idx;

// 初始化
void init_graph() {
    std::fill(h, h + N_VERTICES, -1);
    edge_idx = 0;
}

// 插入有向边 u -> v
void add_edge(int u, int v, int weight) {
    to[edge_idx] = v;
    w[edge_idx] = weight;
    ne[edge_idx] = h[u];
    h[u] = edge_idx++;
}

// 遍历从点 u 出发的所有边
void traverse(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = to[i];
        int weight = w[i];
        std::cout << u << " -> " << v << " (weight: " << weight << ")" << std::endl;
    }
}
```

---

## 5. 综合练习题与解析

### 练习题 1：约瑟夫环问题的单向循环链表数组实现
**题目描述**：
$n$ 个人围成一圈，顺序排号。从第 1 个人开始报数（从 1 到 $m$ 报数），凡报到 $m$ 的人退出圈子，问最后留下的是原来第几号的那个人？（$1 \le n, m \le 1000$）。

#### 静态数组模拟解析
不使用结构体和指针，可以通过单链表数组 `ne` 来模拟。数组的下标代表当前个人的编号，$ne[i]$ 存储 $i$ 号人后面那个人是谁。

#### C++11 实现
```cpp
#include <iostream>

// 求解函数
int solve_josephus(int n, int m) {
    if (n == 1) return 1;
    
    // 初始化循环链表：ne_list[i] 指向下一个玩家的编号
    int ne_list[1010];
    for (int i = 1; i < n; ++i) {
        ne_list[i] = i + 1;
    }
    ne_list[n] = 1; // 形成闭环，n 指向 1
    
    int prev = n;    // 当前考察节点的前驱
    int curr = 1;    // 当前考察的节点
    
    // 当只剩最后一个节点（即指向自身）时终止
    while (ne_list[curr] != curr) {
        // 报数 m - 1 次以找到要剔除的节点的前驱
        for (int i = 1; i < m; ++i) {
            prev = curr;
            curr = ne_list[curr];
        }
        // 剔除 curr 节点
        ne_list[prev] = ne_list[curr];
        // 移动到被剔除节点的下一个位置
        curr = ne_list[prev];
    }
    return curr;
}

int main() {
    int n = 8, m = 3;
    std::cout << "The survivor of Josephus(" << n << ", " << m << ") is: " 
              << solve_josephus(n, m) << std::endl; // 输出 7
    return 0;
}
```
**解题思路**：
通过静态数组 `ne_list` 的映射关系，我们将人与人之间的物理排布转换为下标跳转。当我们需要剔除节点 `curr` 时，只需要执行 `ne_list[prev] = ne_list[curr]`，让前驱直接跳过 `curr`。相比于普通动态数组，该算法规避了大规模元素移动的开销。

---

### 练习题 2：二叉搜索树（BST）路径最大权值求和
**题目描述**：
给定一个插入序列，构造一棵二叉搜索树（不带结构体，仅通过数组实现），并编写一个递归函数求该树中**从根节点到任意叶子节点的所有路径中，权值和的最大值**。

#### C++11 实现
```cpp
#include <iostream>
#include <algorithm>
#include <vector>

constexpr int MAX_BST_SIZE = 10010;

int tree_val[MAX_BST_SIZE];
int tree_l[MAX_BST_SIZE];
int tree_r[MAX_BST_SIZE];
int tree_root, tree_idx;

// 插入操作
void insert(int& u, int x) {
    if (u == -1) {
        u = tree_idx++;
        tree_val[u] = x;
        tree_l[u] = -1;
        tree_r[u] = -1;
        return;
    }
    if (x < tree_val[u]) {
        insert(tree_l[u], x);
    } else {
        insert(tree_r[u], x);
    }
}

// 递归计算最大路径和
int max_path_sum(int u) {
    if (u == -1) return 0;
    
    // 如果是叶子节点，返回自身权值
    if (tree_l[u] == -1 && tree_r[u] == -1) {
        return tree_val[u];
    }
    
    // 递归获取左右子树的最大路径和
    // 避免负权时误选空节点，空分支权值设为较小的初始值 -2e9
    int left_sum = (tree_l[u] != -1) ? max_path_sum(tree_l[u]) : -2e9; 
    int right_sum = (tree_r[u] != -1) ? max_path_sum(tree_r[u]) : -2e9;
    
    return tree_val[u] + std::max(left_sum, right_sum);
}

int main() {
    tree_root = -1;
    tree_idx = 0;
    
    std::vector<int> inputs = {10, 5, 15, 3, 7, 18};
    for (int x : inputs) {
        insert(tree_root, x);
    }
    
    std::cout << "Maximum root-to-leaf path sum: " 
              << max_path_sum(tree_root) << std::endl; // 10 + 15 + 18 = 43
    return 0;
}
```
**解题思路**：
该题目展示了无结构体、无指针表示下，树的“深度优先搜索”与“状态递归合并”过程。在 `max_path_sum` 函数中，我们自底向上收集左右子树返回的信息。如果左或右孩子为空，由于二叉搜索树的值可能是负数，我们将其贡献值初始为 `-2e9`（极小负数）以防止空子树分支干扰 `std::max` 决策。由于采用了静态一维数组，程序没有堆上动态分配内存带来的开销，有助于提升程序的执行效率。

C++11 数据结构（指针与结构体替代版）讲义

在算法竞赛（如 CSP、NOIP）以及追求高执行效率、较低内存开销的场景中，使用静态数组与独立函数模拟链表、树和图是一种常用且有效的实现方式。

本讲义不使用任何原生指针（如 *）、智能指针（如 std::unique_ptr）或自定义结构体（struct），全部改用多个一维数组（平行数组，Parallel Arrays）与全局变量进行状态维护。这符合 C++11 标准，并能有效规避指针悬挂、内存泄露等常见问题。

1. 线性结构

1.1 静态数组模拟单链表、双向链表、循环链表

用数组模拟链表的核心思想是：用数组下标代替内存地址（指针）。

1. 单链表 (Singly Linked List) 模拟

我们使用两个核心数组： * e[i]：存储节点 $i$ 的数值（Data）。 * ne[i]：存储节点 $i$ 的下一个节点的下标（Next Pointer）。 * head：头指针变量，存储链表头节点的下标。 * idx：分配器变量，存储当前尚未被使用的最新节点的下标。

核心操作实现

#include <iostream>

// C++11 支持 constexpr
constexpr int N = 100010; // 链表最大节点数（C++11 不支持单引号数字分隔符）

int head, e[N], ne[N], idx;

// 初始化
void init() {
    head = -1; // -1 表示空指针
    idx = 0;   // 从下标 0 开始分配节点
}

// 在链表头部插入元素 x
void add_to_head(int x) {
    e[idx] = x;       // 记录当前节点的值
    ne[idx] = head;   // 当前节点的 next 指向原 head
    head = idx;       // head 更新为当前节点
    idx++;            // 分配器后移
}

// 在第 k 个插入的节点后面插入元素 x（k 从 0 开始算）
void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 删除第 k 个插入的节点后面的节点
void remove(int k) {
    ne[k] = ne[ne[k]];
}

// 遍历链表
void print_list() {
    for (int i = head; i != -1; i = ne[i]) {
        std::cout << e[i] << " -> ";
    }
    std::cout << "null" << std::endl;
}

2. 双向链表 (Doubly Linked List) 模拟

在双向链表中，每个节点需要两个方向的指针： * e[i]：存储节点值。 * l[i]：存储节点左侧节点的下标。 * r[i]：存储节点右侧节点的下标。 * 哨兵节点：为了简化边界处理，通常固定用 0 表示虚拟头节点（head），1 表示虚拟尾节点（tail）。idx 从 2 开始分配。

核心操作实现

int e[N], l[N], r[N], idx;

// 初始化
void init_doubly() {
    // 0 是左端点（头哨兵），1 是右端点（尾哨兵）
    r[0] = 1;
    l[1] = 0;
    idx = 2; // 实际节点从 2 开始分配
}

// 在第 k 个插入的节点右侧插入一个新节点（值为 x）
void insert_right(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx++;
}

// 删除第 k 个插入的节点
void remove_node(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

3. 循环链表 (Circular Linked List) 模拟

要实现单向循环链表，只需在建立链表时，将最后一个节点的 ne 指针指向头节点（或将 ne[tail] = head）即可。

1.2 静态数组模拟栈 (Stack)

栈是一种后进先出 (LIFO) 的结构，用一维数组和整型变量 tt（Top Pointer）即可模拟。

int stk[N], tt = 0; // tt = 0 表示栈空，元素从 1 开始存储

// 入栈
void push(int x) {
    stk[++tt] = x;
}

// 出栈
void pop() {
    if (tt > 0) tt--;
}

// 获取栈顶元素
int top() {
    return stk[tt];
}

// 判断栈是否为空
bool empty() {
    return tt == 0;
}

1.3 静态数组模拟队列 (Queue)

队列是一种先进先出 (FIFO) 的结构。我们使用 hh（Head Pointer）指向队头，tt（Tail Pointer）指向队尾的下一个位置。

1. 简易队列

int q[N], hh = 0, tt = 0; // [hh, tt) 为队列区间

// 入队
void push_queue(int x) {
    q[tt++] = x;
}

// 出队
void pop_queue() {
    if (hh < tt) hh++;
}

// 获取队头
int front_queue() {
    return q[hh];
}

// 队列是否为空
bool empty_queue() {
    return hh == tt;
}

2. 循环队列 (防止内存越界)

若生存周期内有大量的入队和出队操作，需要使用模运算循环利用数组空间：

int cq[N], hh = 0, tt = 0; // 数组大小 N

bool cq_push(int x) {
    if ((tt + 1) % N == hh) return false; // 队满
    cq[tt] = x;
    tt = (tt + 1) % N;
    return true;
}

bool cq_pop() {
    if (hh == tt) return false; // 队空
    hh = (hh + 1) % N;
    return true;
}

2. 简单树

2.1 树的静态表示法

对于一棵普通的树（度大于2的多叉树），若不用结构体和指针，可以通过邻接表（链式前向星）将其子节点存储为拉链结构。此方法将在“第4节图的基础”中讲解。

在二叉树场景下，我们使用三个平行数组即可完成定义。

2.2 二叉树定义、性质与静态数组表示

1. 数组表示法 (Parallel Arrays for Binary Tree)

对于一般的二叉树，我们使用如下一维数组： * val[i]：节点 $i$ 的数值。 * l[i]：节点 $i$ 的左孩子节点的下标。若没有，则设为 -1。 * r[i]：节点 $i$ 的右孩子节点的下标。若没有，则设为 -1。 * root：记录根节点的下标。 * idx：新节点的分配器。

2. 遍历方式：前序、中序、后序的递归函数实现

无需在结构体中定义成员函数，写成外部递归函数即可：

#include <iostream>

constexpr int MAX_NODES = 100010;

int val[MAX_NODES];
int l[MAX_NODES];
int r[MAX_NODES];
int root, idx;

// 初始化树
void init_tree() {
    root = -1;
    idx = 0;
}

// 创建一个新节点
int create_node(int x) {
    val[idx] = x;
    l[idx] = -1;
    r[idx] = -1;
    return idx++;
}

// 前序遍历 (根 -> 左 -> 右)
void pre_order(int u) {
    if (u == -1) return;
    std::cout << val[u] << " ";
    pre_order(l[u]);
    pre_order(r[u]);
}

// 中序遍历 (左 -> 根 -> 右)
void in_order(int u) {
    if (u == -1) return;
    in_order(l[u]);
    std::cout << val[u] << " ";
    in_order(r[u]);
}

// 后序遍历 (左 -> 右 -> 根)
void post_order(int u) {
    if (u == -1) return;
    post_order(l[u]);
    post_order(r[u]);
    std::cout << val[u] << " ";
}

3. 特殊树

3.1 完全二叉树的一维数组表示法

完全二叉树因其结构紧凑的性质，不需要记录任何孩子节点的下标，仅用一个一维数组 tree[i] 就能完整表达整棵树。

1. 索引映射性质与推导（1-Based Indexing）

设根节点存储在数组下标为 1 的位置： * 对于任意一个位于下标 $i$ 的节点： * 其左孩子位于 $2i$。 * 其右孩子位于 $2i + 1$。 * 其双亲（父节点）位于 $\lfloor i / 2 \rfloor$。 * 边界判定：若总节点数为 $n$，如果 $2i > n$，则节点 $i$ 没有左孩子；如果 $2i + 1 > n$，则节点 $i$ 没有右孩子。

2. 位运算

在 C++11 中，可以使用位运算来代替部分乘除法： * 左孩子位置 $2i \implies$ i << 1 * 右孩子位置 $2i + 1 \implies$ (i << 1) | 1 * 父节点位置 $\lfloor i/2 \rfloor \implies$ i >> 1

3.2 哈夫曼树 (Huffman Tree) 的构造

哈夫曼树的构造通常涉及不断合并两个最小权值的节点。为了避免使用结构体，我们可以将所有节点（包括叶子节点与合并后的父节点）统一视为数组中的一个索引，并通过 std::pair 在优先队列中建立关联。

C++11 实现（基于静态数组与 std::pair 优先队列）

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

constexpr int MAX_HUFFMAN_NODES = 200010;

int h_val[MAX_HUFFMAN_NODES]; // 节点的权值
int h_l[MAX_HUFFMAN_NODES];   // 左孩子索引
int h_r[MAX_HUFFMAN_NODES];   // 右孩子索引
int h_idx;                    // 静态节点分配器

// 构造哈夫曼树
int build_huffman(const std::vector<int>& weights) {
    h_idx = 0;

    // 优先队列存储 std::pair<int, int> -> {权值, 节点下标}
    // std::greater 默认会对 pair 的第一个成员（权值）进行小顶堆排序
    std::priority_queue<std::pair<int, int>, 
                        std::vector<std::pair<int, int>>, 
                        std::greater<std::pair<int, int>>> pq;

    // 1. 初始化叶子节点
    for (int w : weights) {
        h_val[h_idx] = w;
        h_l[h_idx] = -1;
        h_r[h_idx] = -1;
        pq.push(std::make_pair(w, h_idx)); // C++11 兼容 make_pair
        h_idx++;
    }

    // 2. 循环合并最小的两个节点
    while (pq.size() > 1) {
        auto left_node = pq.top(); pq.pop();
        auto right_node = pq.top(); pq.pop();

        int w1 = left_node.first;
        int u1 = left_node.second;
        int w2 = right_node.first;
        int u2 = right_node.second;

        // 创建新的合并父节点
        h_val[h_idx] = w1 + w2;
        h_l[h_idx] = u1;
        h_r[h_idx] = u2;

        pq.push(std::make_pair(h_val[h_idx], h_idx));
        h_idx++;
    }

    // 返回根节点的下标
    return pq.top().second;
}

3.3 二叉搜索树 (BST) 的构造与查询

二叉搜索树可以通过平行数组进行插入与检索。

C++11 实现

int bst_val[MAX_NODES];
int bst_l[MAX_NODES];
int bst_r[MAX_NODES];
int bst_root, bst_idx;

void init_bst() {
    bst_root = -1;
    bst_idx = 0;
}

// 递归插入，利用引用改变上级孩子指针的值
void insert_bst(int& u, int x) {
    if (u == -1) {
        u = bst_idx++;
        bst_val[u] = x;
        bst_l[u] = -1;
        bst_r[u] = -1;
        return;
    }
    if (x < bst_val[u]) {
        insert_bst(bst_l[u], x);
    } else if (x > bst_val[u]) {
        insert_bst(bst_r[u], x);
    }
}

// 检索是否存在该值
bool search_bst(int u, int x) {
    if (u == -1) return false;
    if (bst_val[u] == x) return true;
    return x < bst_val[u] ? search_bst(bst_l[u], x) : search_bst(bst_r[u], x);
}

4. 图的基础

在图论算法中，“邻接表”通常采用一种被称为“链式前向星”的静态机制来实现。它使用数组模拟邻接表中的单链表结构，执行效率较为稳定。

4.1 邻接矩阵 (Adjacency Matrix)

适合存储稠密图（通常 $V \le 1000$）。

constexpr int V_MAX = 1010;
int g[V_MAX][V_MAX]; // 二维邻接矩阵

void add_matrix_edge(int u, int v, int w = 1) {
    g[u][v] = w; // 有向边
}

4.2 链式前向星 (Static Adjacency List)

链式前向星是竞赛中常用的图存储结构。它的本质是给图中的每个顶点 $u$ 都维护一个单链表，这个单链表存储所有从 $u$ 出发的边。

1. 数组定义

h[i]：指向顶点 $i$ 的第一条边的位置（头指针）。初始化为 -1。
to[e]：第 $e$ 条边指向的终点节点。
w[e]：第 $e$ 条边的权值。
ne[e]：与第 $e$ 条边同起点的下一条边的索引位置。
idx：当前边的分配器（边数）。

2. 核心插边操作推导（头插法）

假设增加一条有向边 $u \to v$，权值为 $weight$： 1. to[idx] = v：记录这条边的终点。 2. w[idx] = weight：记录这条边的权重。 3. ne[idx] = h[u]：新边的 next 指向当前 $u$ 顶点的第一条边（头插法）。 4. h[u] = idx：将顶点 $u$ 的链表头更新为当前新边。 5. idx++：边计数器自增。

3. C++11 链式前向星实现

#include <iostream>
#include <algorithm>

constexpr int N_VERTICES = 10010; // 顶点数
constexpr int M_EDGES = 100010;   // 边数

int h[N_VERTICES], to[M_EDGES], w[M_EDGES], ne[M_EDGES], edge_idx;

// 初始化
void init_graph() {
    std::fill(h, h + N_VERTICES, -1);
    edge_idx = 0;
}

// 插入有向边 u -> v
void add_edge(int u, int v, int weight) {
    to[edge_idx] = v;
    w[edge_idx] = weight;
    ne[edge_idx] = h[u];
    h[u] = edge_idx++;
}

// 遍历从点 u 出发的所有边
void traverse(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = to[i];
        int weight = w[i];
        std::cout << u << " -> " << v << " (weight: " << weight << ")" << std::endl;
    }
}

5. 综合练习题与解析

练习题 1：约瑟夫环问题的单向循环链表数组实现

题目描述： $n$ 个人围成一圈，顺序排号。从第 1 个人开始报数（从 1 到 $m$ 报数），凡报到 $m$ 的人退出圈子，问最后留下的是原来第几号的那个人？（$1 \le n, m \le 1000$）。

静态数组模拟解析

不使用结构体和指针，可以通过单链表数组 ne 来模拟。数组的下标代表当前个人的编号，$ne[i]$ 存储 $i$ 号人后面那个人是谁。

C++11 实现

#include <iostream>

// 求解函数
int solve_josephus(int n, int m) {
    if (n == 1) return 1;

    // 初始化循环链表：ne_list[i] 指向下一个玩家的编号
    int ne_list[1010];
    for (int i = 1; i < n; ++i) {
        ne_list[i] = i + 1;
    }
    ne_list[n] = 1; // 形成闭环，n 指向 1

    int prev = n;    // 当前考察节点的前驱
    int curr = 1;    // 当前考察的节点

    // 当只剩最后一个节点（即指向自身）时终止
    while (ne_list[curr] != curr) {
        // 报数 m - 1 次以找到要剔除的节点的前驱
        for (int i = 1; i < m; ++i) {
            prev = curr;
            curr = ne_list[curr];
        }
        // 剔除 curr 节点
        ne_list[prev] = ne_list[curr];
        // 移动到被剔除节点的下一个位置
        curr = ne_list[prev];
    }
    return curr;
}

int main() {
    int n = 8, m = 3;
    std::cout << "The survivor of Josephus(" << n << ", " << m << ") is: " 
              << solve_josephus(n, m) << std::endl; // 输出 7
    return 0;
}

解题思路：通过静态数组 ne_list 的映射关系，我们将人与人之间的物理排布转换为下标跳转。当我们需要剔除节点 curr 时，只需要执行 ne_list[prev] = ne_list[curr]，让前驱直接跳过 curr。相比于普通动态数组，该算法规避了大规模元素移动的开销。

练习题 2：二叉搜索树（BST）路径最大权值求和

题目描述：给定一个插入序列，构造一棵二叉搜索树（不带结构体，仅通过数组实现），并编写一个递归函数求该树中从根节点到任意叶子节点的所有路径中，权值和的最大值。

C++11 实现

#include <iostream>
#include <algorithm>
#include <vector>

constexpr int MAX_BST_SIZE = 10010;

int tree_val[MAX_BST_SIZE];
int tree_l[MAX_BST_SIZE];
int tree_r[MAX_BST_SIZE];
int tree_root, tree_idx;

// 插入操作
void insert(int& u, int x) {
    if (u == -1) {
        u = tree_idx++;
        tree_val[u] = x;
        tree_l[u] = -1;
        tree_r[u] = -1;
        return;
    }
    if (x < tree_val[u]) {
        insert(tree_l[u], x);
    } else {
        insert(tree_r[u], x);
    }
}

// 递归计算最大路径和
int max_path_sum(int u) {
    if (u == -1) return 0;

    // 如果是叶子节点，返回自身权值
    if (tree_l[u] == -1 && tree_r[u] == -1) {
        return tree_val[u];
    }

    // 递归获取左右子树的最大路径和
    // 避免负权时误选空节点，空分支权值设为较小的初始值 -2e9
    int left_sum = (tree_l[u] != -1) ? max_path_sum(tree_l[u]) : -2e9; 
    int right_sum = (tree_r[u] != -1) ? max_path_sum(tree_r[u]) : -2e9;

    return tree_val[u] + std::max(left_sum, right_sum);
}

int main() {
    tree_root = -1;
    tree_idx = 0;

    std::vector<int> inputs = {10, 5, 15, 3, 7, 18};
    for (int x : inputs) {
        insert(tree_root, x);
    }

    std::cout << "Maximum root-to-leaf path sum: " 
              << max_path_sum(tree_root) << std::endl; // 10 + 15 + 18 = 43
    return 0;
}

解题思路：该题目展示了无结构体、无指针表示下，树的“深度优先搜索”与“状态递归合并”过程。在 max_path_sum 函数中，我们自底向上收集左右子树返回的信息。如果左或右孩子为空，由于二叉搜索树的值可能是负数，我们将其贡献值初始为 -2e9（极小负数）以防止空子树分支干扰 std::max 决策。由于采用了静态一维数组，程序没有堆上动态分配内存带来的开销，有助于提升程序的执行效率。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

入门组大纲2.1.3 数据结构

C++11 数据结构（指针与结构体替代版）讲义

1. 线性结构

1.1 静态数组模拟单链表、双向链表、循环链表

1. 单链表 (Singly Linked List) 模拟

核心操作实现

2. 双向链表 (Doubly Linked List) 模拟

核心操作实现

3. 循环链表 (Circular Linked List) 模拟

1.2 静态数组模拟栈 (Stack)

1.3 静态数组模拟队列 (Queue)

1. 简易队列

2. 循环队列 (防止内存越界)

2. 简单树

2.1 树的静态表示法

2.2 二叉树定义、性质与静态数组表示

1. 数组表示法 (Parallel Arrays for Binary Tree)

2. 遍历方式：前序、中序、后序的递归函数实现

3. 特殊树

3.1 完全二叉树的一维数组表示法

1. 索引映射性质与推导（1-Based Indexing）

2. 位运算

3.2 哈夫曼树 (Huffman Tree) 的构造

C++11 实现（基于静态数组与 std::pair 优先队列）

3.3 二叉搜索树 (BST) 的构造与查询

C++11 实现

4. 图的基础

4.1 邻接矩阵 (Adjacency Matrix)

4.2 链式前向星 (Static Adjacency List)

1. 数组定义

2. 核心插边操作推导（头插法）

3. C++11 链式前向星实现

5. 综合练习题与解析

练习题 1：约瑟夫环问题的单向循环链表数组实现

静态数组模拟解析

C++11 实现

练习题 2：二叉搜索树（BST）路径最大权值求和

C++11 实现