数据结构上机考试的核心复习内容，涵盖二叉树遍历与构建、最小生成树（Kruskal）、哈希表构造、快速排序隐含树、有序表合并、队列排序、栈操作验证、图论算法（BFS/DFS/最短路径/关键路径）以及字符串匹配等经典问题。提供完整的 C++ 代码实现及输入输出示例，帮助理解算法逻辑与边界处理。
struct Node {
int val;
Node* left;
Node* right;
Node(int v) : val(v), left(NULL), right() {}
};
void preorder(Node* root) {
if (!root) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
void postorder(Node* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
#include <queue>
void levelorder(Node* root) {
if (!root) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
输入说明： 第一行为两个正整数 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 网中的关键路径长度，如果网中有环，则输出"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;
}
代码实现：
#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;
}
代码实现：
#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;
}
描述： 求图中任意两个顶点之间的最短路径。
核心逻辑：
next[i][j] 记录从 i 到 j 的最短路径上 i 之后的下一个顶点。描述： 如果一个字符串可以由某个长度为 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;
}
代码实现：
#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;
}
代码实现：
#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;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online