数据结构上机复习：核心算法与代码实现

Kruskal 求无向网的最小生成树

输入说明： 第一行为两个正整数 n（1<n<=30）和 m（1<m<100），分别表示顶点数和边数。后面紧跟 m 行数据，每行是一条边的信息，包括三个数字，分别表示该边的两个顶点和边上的权值。

输出说明： 按顺序输出 Kruskal 算法求得的最小生成树的边集，每行一条边，包括三个数字，分别是该边的两个顶点和边上的权值，其中第一个顶点的编号应小于第二个顶点的编号。

示例输入：

8 11
1 2 3
1 4 5
1 6 18
2 4 7
2 5 6
3 5 10
3 8 20
4 6 15
4 7 11
5 7 8
5 8 12

示例输出：

1 2 3
1 4 5
2 5 6
5 7 8
3 5 10
5 8 12
4 6 15

代码实现：

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
};
Edge e[100];
int parent[31];

int cmp(const void* a, const void* b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        if (e[i].u > e[i].v) swap(e[i].u, e[i].v);
    }
    qsort(e, m, sizeof(Edge), cmp);
    for (int i = 1; i <= n; i++) parent[i] = i;
    int cnt = 0;
    for (int i = 0; cnt < n - 1; i++) {
        if (find(e[i].u) != find(e[i].v)) {
            parent[find(e[i].u)] = find(e[i].v);
            cout << e[i].u << " " << e[i].v << " " << e[i].w << endl;
            cnt++;
        }
    }
    return 0;
}

哈希表构造（除留余数法 + 线性探测）

输入说明： 第一行为两个正整数分别为：哈希表表长 m（m<100）和除数 p（p<=m）。后面每一行是一个整数关键字，以 -1 作为输入的结束。

输出说明： 若输入的关键字在哈希表中已存在，则输出该关键字在哈希表中的位置；若不存在且未满，插入并输出位置；若已满，输出"Table full"。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, p;
    cin >> m >> p;
    int table[100];
    for (int i = 0; i < m; i++) table[i] = -1;
    int cnt = 0;
    int key;
    while (cin >> key && key != -1) {
        int h = key % p;
        int pos = h;
        while (table[pos] != -1 && table[pos] != key) {
            pos = (pos + 1) % m;
        }
        if (table[pos] == key) {
            cout << pos << endl;
            continue;
        }
        if (cnt == m - 1) {
            cout << "Table full" << endl;
            break;
        }
        table[pos] = key;
        cnt++;
        cout << pos << endl;
    }
    return 0;
}

快速排序隐含递归树后序遍历

描述： 快速排序递归算法隐含一棵由关键字生成的二叉树（递归树），输出该隐含二叉树的后序遍历序列。（注：划分时以第一关键字为枢轴）

代码实现：

#include <bits/stdc++.h>
using namespace std;

void quickPostOrder(vector<int>& a, int l, int r) {
    if (l > r) return;
    int pivot = a[l];
    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    quickPostOrder(a, l, i - 1);
    quickPostOrder(a, i + 1, r);
    static bool first = true;
    if (!first) cout << " ";
    cout << pivot;
    first = false;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    quickPostOrder(a, 0, n - 1);
    return 0;
}

有序表的合并去重

问题描述： 已知两个有序线性表 L1 和 L2，把 L2 中的元素合并到 L1 中，要求 L1 中数据元素的值仍为单调递增，且无重复元素。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    vector<int> L1(100), L2(100);
    for (int i = 0; i < a; i++) cin >> L1[i];
    for (int i = 0; i < b; i++) cin >> L2[i];
    int i = 0, j = 0;
    bool first = true;
    while (i < a && j < b) {
        int x;
        if (L1[i] < L2[j]) {
            x = L1[i++];
        } else if (L1[i] > L2[j]) {
            x = L2[j++];
        } else {
            x = L1[i];
            i++; j++;
        }
        if (!first) cout << " ";
        cout << x;
        first = false;
    }
    while (i < a) {
        if (!first) cout << " ";
        cout << L1[i++];
        first = false;
    }
    while (j < b) {
        if (!first) cout << " ";
        cout << L2[j++];
        first = false;
    }
    return 0;
}

队列中的元素排序

问题描述： 给定一个队列，请用一系列合法的队列操作函数，将队列中的元素从小到大排序。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    queue<int> q, tmp;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        q.push(x);
    }
    bool first = true;
    while (!q.empty()) {
        int sz = q.size();
        int minVal = q.front();
        for (int i = 0; i < sz; i++) {
            int x = q.front(); q.pop();
            if (x < minVal) minVal = x;
            q.push(x);
        }
        for (int i = 0; i < sz; i++) {
            int x = q.front(); q.pop();
            if (x == minVal) {
                if (!first) cout << " ";
                cout << x;
                first = false;
            } else {
                tmp.push(x);
            }
        }
        q = tmp;
        while (!tmp.empty()) tmp.pop();
    }
    return 0;
}

统计二叉树中的叶子结点数

问题描述： 建立二叉链表，统计二叉树中的叶子结点数并输出。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<char> a(1000);
    char x;
    int n = 1;
    while (cin >> x && x != '#') {
        a[n++] = x;
    }
    int cnt = 0;
    bool first = true;
    for (int i = 1; i < n; i++) {
        if (a[i] == '@') continue;
        bool isleaf = false;
        if (i > (n - 1) / 2) {
            isleaf = true;
        } else if (2 * i < n && 2 * i + 1 < n && a[2 * i] == '@' && a[2 * i + 1] == '@') {
            isleaf = true;
        }
        if (isleaf) {
            if (!first) cout << " ";
            cout << a[i];
            first = false;
            cnt++;
        }
    }
    cout << endl;
    cout << cnt << endl;
    return 0;
}

二叉排序树相关

中序遍历二叉树

代码实现：

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int x) : data(x), left(NULL), right(NULL) {}
};

Node* insertBST(Node* root, int x) {
    if (root == NULL) return new Node(x);
    if (x < root->data) root->left = insertBST(root->left, x);
    else root->right = insertBST(root->right, x);
    return root;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    int n;
    cin >> n;
    Node* root = NULL;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        root = insertBST(root, x);
    }
    inorder(root);
    return 0;
}

二叉排序树的判定

输入格式： 第一行两个数 n, root，接下来共 n 行，第 i 行三个数 val_i、left_i、right_i。

代码实现：

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    int left;
    int right;
};

int n, root;
vector<Node> tree;

bool isBST(int u, long long minVal, long long maxVal) {
    if (u == 0) return true;
    if (tree[u].val <= minVal || tree[u].val >= maxVal) return false;
    return isBST(tree[u].left, minVal, tree[u].val) && isBST(tree[u].right, tree[u].val, maxVal);
}

int main() {
    cin >> n >> root;
    tree.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> tree[i].val >> tree[i].left >> tree[i].right;
    }
    if (isBST(root, LLONG_MIN, LLONG_MAX)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    return 0;
}

循环队列的实现和测试

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef struct {
    ElemType* data;
    int maxSize;
    int rear;
    int length;
} Queue;

int in(Queue* q, ElemType e) {
    if (q->length == q->maxSize) return ERROR;
    q->data[q->rear] = e;
    q->rear = (q->rear + 1) % q->maxSize;
    q->length++;
    return OK;
}

int out(Queue* q, ElemType* e) {
    if (q->length == 0) return ERROR;
    int front = (q->rear - q->length + q->maxSize) % q->maxSize;
    *e = q->data[front];
    q->length--;
    return OK;
}
// ... (其他辅助函数如 createQueue, isEmpty, output 等略)

二分查找

代码实现：

#include <stdio.h>

int biSearch(int n, int a[], int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        printf("%d ", a[mid]);
        if (a[mid] == key) return mid;
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

报数出列问题

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    queue<int> people;
    for (int i = 1; i <= N; i++) people.push(i);
    int round = 1;
    while (people.size() > 3) {
        int k = (round % 2 == 1) ? 2 : 3;
        int count = 1;
        int size = people.size();
        for (int i = 0; i < size; i++) {
            int person = people.front();
            people.pop();
            if (count % k != 0) people.push(person);
            count++;
        }
        round++;
    }
    while (!people.empty()) {
        cout << people.front();
        people.pop();
        if (!people.empty()) cout << " ";
    }
    cout << endl;
    return 0;
}

奇偶序列

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    vector<int> result;
    for (int i = 0; i < n; i += 2) result.push_back(nums[i]);
    for (int i = 1; i < n; i += 2) result.push_back(nums[i]);
    for (int i = 0; i < n; i++) {
        cout << result[i];
        if (i != n - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

判断堆栈出栈序列是否有效

思路： 使用一个栈来模拟操作，根据栈的后进先出特性进行判断。

代码实现：

#include <bits/stdc++.h>
using namespace std;

bool isValidSequence(int n, vector<int>& seq) {
    stack<int> st;
    int current = 1;
    for (int i = 0; i < n; i++) {
        int target = seq[i];
        while (st.empty() || st.top() != target) {
            if (current > n) return false;
            st.push(current);
            current++;
        }
        st.pop();
    }
    return true;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> seq(n);
        for (int i = 0; i < n; i++) cin >> seq[i];
        if (isValidSequence(n, seq)) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

栈容量限制下的出栈序列验证

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int M, N, K;
    cin >> M >> N >> K;
    vector<int> inputSeq(N);
    for (int i = 0; i < N; i++) cin >> inputSeq[i];
    for (int t = 0; t < K; t++) {
        vector<int> outSeq(N);
        for (int i = 0; i < N; i++) cin >> outSeq[i];
        stack<int> st;
        int j = 0;
        bool flag = true;
        for (int i = 0; i < N; i++) {
            st.push(inputSeq[i]);
            if ((int)st.size() > M) {
                flag = false;
                break;
            }
            while (!st.empty() && j < N && st.top() == outSeq[j]) {
                st.pop();
                j++;
            }
        }
        if (flag && st.empty()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

二叉树的不同形态

问题描述： 给定二叉树的层次遍历序列和中序遍历序列，输出从左向右叶子结点以及先序和后序遍历序列。

代码实现：

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(NULL), right(NULL) {}
};

Node* build(vector<int>& lev, vector<int>& in) {
    if (lev.empty() || in.empty()) return NULL;
    int rootVal = lev[0];
    Node* root = new Node(rootVal);
    int pos = 0;
    while (in[pos] != rootVal) pos++;
    vector<int> leftIn(in.begin(), in.begin() + pos);
    vector<int> rightIn(in.begin() + pos + 1, in.end());
    vector<int> leftLev, rightLev;
    unordered_set<int> leftSet(leftIn.begin(), leftIn.end());
    for (int i = 1; i < lev.size(); i++) {
        if (leftSet.count(lev[i])) leftLev.push_back(lev[i]);
        else rightLev.push_back(lev[i]);
    }
    root->left = build(leftLev, leftIn);
    root->right = build(rightLev, rightIn);
    return root;
}

void printLeaves(Node* root, bool& first) {
    if (!root) return;
    if (!root->left && !root->right) {
        if (!first) cout << " ";
        cout << root->val;
        first = false;
        return;
    }
    printLeaves(root->left, first);
    printLeaves(root->right, first);
}

void printPreorder(Node* root, bool& first) {
    if (!root) return;
    if (!first) cout << " ";
    cout << root->val;
    first = false;
    printPreorder(root->left, first);
    printPreorder(root->right, first);
}

void printPostorder(Node* root, bool& first) {
    if (!root) return;
    printPostorder(root->left, first);
    printPostorder(root->right, first);
    if (!first) cout << " ";
    cout << root->val;
    first = false;
}

int main() {
    int n;
    cin >> n;
    vector<int> lev(n), in(n);
    for (int i = 0; i < n; i++) cin >> lev[i];
    for (int i = 0; i < n; i++) cin >> in[i];
    Node* root = build(lev, in);
    bool first = true;
    printLeaves(root, first); cout << endl;
    first = true;
    printPreorder(root, first); cout << endl;
    first = true;
    printPostorder(root, first); cout << endl;
    return 0;
}

是否为堆

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    bool isMaxHeap = true;
    bool isMinHeap = true;
    for (int i = 0; i < n / 2; i++) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n) {
            if (arr[i] < arr[left]) isMaxHeap = false;
            if (arr[i] > arr[left]) isMinHeap = false;
        }
        if (right < n) {
            if (arr[i] < arr[right]) isMaxHeap = false;
            if (arr[i] > arr[right]) isMinHeap = false;
        }
        if (!isMaxHeap && !isMinHeap) break;
    }
    if (isMaxHeap) cout << "Max heap" << endl;
    else if (isMinHeap) cout << "Min heap" << endl;
    else cout << "Not heap" << endl;
    return 0;
}

AOE 网关键路径

问题描述： 计算 AOE 网中的关键路径长度，如果网中有环，则输出"NO"。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> g[i][j];
    }
    vector<int> indegree(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] > 0) indegree[j]++;
        }
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);
    }
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v = 0; v < n; v++) {
            if (g[u][v] > 0 && --indegree[v] == 0) q.push(v);
        }
    }
    if (topo.size() != n) {
        cout << "NO" << endl;
        return 0;
    }
    vector<int> earliest(n, 0);
    for (int u : topo) {
        for (int v = 0; v < n; v++) {
            if (g[u][v] > 0) {
                earliest[v] = max(earliest[v], earliest[u] + g[u][v]);
            }
        }
    }
    cout << earliest[n - 1] << endl;
    return 0;
}

图的广度优先搜索（BFS）

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> graph[i][j];
    }
    vector<bool> visited(n, false);
    vector<int> bfsOrder;
    int componentCount = 0;
    for (int start = 0; start < n; start++) {
        if (!visited[start]) {
            componentCount++;
            queue<int> q;
            q.push(start);
            visited[start] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                bfsOrder.push_back(u + 1);
                for (int v = 0; v < n; v++) {
                    if (graph[u][v] && !visited[v]) {
                        q.push(v);
                        visited[v] = true;
                    }
                }
            }
        }
    }
    for (int i = 0; i < bfsOrder.size(); i++) {
        cout << bfsOrder[i] << (i == bfsOrder.size() - 1 ? "\n" : " ");
    }
    cout << componentCount << endl;
    return 0;
}

图的深度优先搜索（DFS）

代码实现：

#include <bits/stdc++.h>
using namespace std;

void dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& dfsOrder) {
    visited[u] = true;
    dfsOrder.push_back(u + 1);
    for (int v = 0; v < graph.size(); v++) {
        if (graph[u][v] && !visited[v]) dfs(v, graph, visited, dfsOrder);
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> graph[i][j];
    }
    vector<bool> visited(n, false);
    vector<int> dfsOrder;
    int componentCount = 0;
    if (!visited[0]) {
        componentCount++;
        dfs(0, graph, visited, dfsOrder);
    }
    for (int i = 1; i < n; i++) {
        if (!visited[i]) {
            componentCount++;
            dfs(i, graph, visited, dfsOrder);
        }
    }
    bool first = true;
    for (int i = 0; i < dfsOrder.size(); i++) {
        if (!first) cout << " ";
        cout << dfsOrder[i];
        first = false;
    }
    cout << endl;
    cout << componentCount << endl;
    return 0;
}

最短路径（Floyd 算法）

描述： 求图中任意两个顶点之间的最短路径。

核心逻辑：

• next[i][j] 记录从 i 到 j 的最短路径上 i 之后的下一个顶点。
• 外层循环中间顶点 k，逐步考虑能否通过顶点 k 来缩短 i 到 j 的路径。

最小周期串

描述： 如果一个字符串可以由某个长度为 k 的字符串重复多次得到，我们说该串以 k 为周期。输出它的最小周期。

代码实现：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> computeLPS(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    int j = 0;
    for (int i = 1; i < n; i++) {
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

int main() {
    string s;
    if (!(cin >> s)) return 0;
    int n = s.size();
    vector<int> pi = computeLPS(s);
    int l = pi[n - 1];
    int p = n - l;
    if (n % p == 0) cout << p << endl;
    else cout << n << endl;
    return 0;
}

迷宫问题

代码实现：

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> maze;
vector<vector<bool>> visited;
vector<tuple<int, int, int>> path;
bool found = false;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int dir[4] = {1, 2, 3, 4};
int m, n, sx, sy, ex, ey;

void dfs(int x, int y) {
    if (found) return;
    if (x == ex - 1 && y == ey - 1) {
        found = true;
        path.push_back({ex, ey, 1});
        return;
    }
    visited[x][y] = true;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 0 && !visited[nx][ny]) {
            path.push_back({x + 1, y + 1, dir[k]});
            dfs(nx, ny);
            if (found) return;
            path.pop_back();
        }
    }
}

int main() {
    cin >> m >> n >> sx >> sy >> ex >> ey;
    maze.assign(m, vector<int>(n, 0));
    visited.assign(m, vector<bool>(n, false));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) cin >> maze[i][j];
    }
    if (sx == ex && sy == ey) {
        cout << "(" << sx << "," << sy << "," << "1")" << endl;
        return 0;
    }
    path.clear();
    dfs(sx - 1, sy - 1);
    if (!found) {
        cout << "no" << endl;
    } else {
        for (int i = 0; i < path.size(); i++) {
            auto t = path[i];
            cout << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")";
            if (i != path.size() - 1) cout << ",";
        }
        cout << endl;
    }
    return 0;
}

括号匹配（用栈实现）

代码实现：

#include <bits/stdc++.h>
using namespace std;

bool isMatch(const string& expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '{' || c == '[') {
            s.push(c);
        } else if (c == '}' || c == ')' || c == ']') {
            if (s.empty()) return false;
            char topChar = s.top();
            if ((c == '}' && topChar == '{') || (c == ')' && topChar == '(') || (c == ']' && topChar == '[')) {
                s.pop();
            } else {
                return false;
            }
        }
    }
    return s.empty();
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string expr;
        cin >> expr;
        if (isMatch(expr)) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

后缀表达式求值

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.length();
    stack<int> st;
    for (int i = 0; i < n; i++) {
        if (isdigit(str[i])) {
            st.push(str[i] - '0');
        } else {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            int result = 0;
            if (str[i] == '+') result = a + b;
            else if (str[i] == '-') result = a - b;
            else if (str[i] == '*') result = a * b;
            else if (str[i] == '/') result = a / b;
            st.push(result);
        }
    }
    cout << st.top() << endl;
    return 0;
}

前缀表达式求值

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string str;
    cin >> str;
    reverse(str.begin(), str.end());
    int n = str.length();
    stack<int> st;
    for (int i = 0; i < n; i++) {
        if (isdigit(str[i])) {
            st.push(str[i] - '0');
        } else {
            int a = st.top(); st.pop();
            int b = st.top(); st.pop();
            int result = 0;
            if (str[i] == '+') result = a + b;
            else if (str[i] == '-') result = a - b;
            else if (str[i] == '*') result = a * b;
            else if (str[i] == '/') result = a / b;
            st.push(result);
        }
    }
    cout << st.top() << endl;
    return 0;
}

模式匹配

BF 算法

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S, T;
    cin >> S >> T;
    int n = S.length();
    int m = T.length();
    int pos = 0;
    for (int i = 0; i < n; i++) {
        int j = 0;
        while (j < m && S[i + j] == T[j]) j++;
        if (j == m) {
            pos = i + 1;
            break;
        }
    }
    cout << pos << endl;
    return 0;
}

串求 next 数组

代码实现：

#include <bits/stdc++.h>
using namespace std;

vector<int> computeNext(const string& T) {
    int m = T.size();
    vector<int> next(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && T[i] != T[j]) j = next[j - 1];
        if (T[i] == T[j]) j++;
        next[i] = j;
    }
    return next;
}

中心对称的字符串

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    string left = s.substr(0, n / 2);
    int right_start;
    if (n % 2 == 0) right_start = n / 2;
    else right_start = n / 2 + 1;
    string right = s.substr(right_start, n / 2);
    reverse(right.begin(), right.end());
    cout << (left == right ? "YES" : "NO") << endl;
    return 0;
}

约瑟夫环

代码实现：

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int id;
    int key;
    Node* next;
};

Node* createList(int n) {
    Node* head = nullptr;
    Node* p = nullptr;
    for (int i = 1; i <= n; i++) {
        Node* node = new Node;
        node->id = i;
        cin >> node->key;
        if (head == nullptr) {
            head = node;
            node->next = head;
        } else {
            node->next = head;
            p->next = node;
        }
        p = node;
    }
    return head;
}

void josephus(Node* head, int m) {
    Node* p = head;
    Node* pre = nullptr;
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            pre = p;
            p = p->next;
        }
        cout << p->id << " ";
        m = p->key;
        pre->next = p->next;
        p = p->next;
        Node* temp = p;
        delete temp;
    }
    cout << p->id << endl;
    delete p;
}

int main() {
    int n, m;
    cin >> n >> m;
    Node* head = createList(n);
    josephus(head, m);
    return 0;
}

输出完全二叉树的某一层

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    while (cin >> n && n != 0) {
        vector<int> arr(n + 1);
        for (int i = 1; i <= n; i++) cin >> arr[i];
        int d;
        cin >> d;
        int start = pow(2, d - 1);
        int end = pow(2, d) - 1;
        if (start > n) {
            cout << "EMPTY" << endl;
            continue;
        }
        for (int i = start; i <= end && i <= n; i++) {
            if (i != start) cout << " ";
            cout << arr[i];
        }
        cout << endl;
    }
    return 0;
}

最近公共父节点

问题描述： 有一棵无限大的完全二叉树，自上而下、自左而右从 1 开始编号。给定 x 和 y，求它们的最近公共父节点。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    long x, y;
    while (cin >> x >> y) {
        if (x == 0 && y == 0) break;
        while (x != y) {
            if (x > y) x /= 2;
            else y /= 2;
        }
        cout << x << endl;
    }
    return 0;
}

直接插入排序

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    for (int i = 1; i < n; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
        for (int k = 0; k <= i; k++) cout << arr[k] << " ";
        cout << endl;
    }
    return 0;
}