1、兩個有序鏈表序列的合并

#include<bits/stdc++.h>
using namespace std;struct node{int num;node* next;
};// 創建鏈表
node* CreatList(){int x;node *head = new node();  // 創建頭節點head->next = NULL;node *tail = head;        // 尾指針初始指向頭節點while(cin >> x && x != -1){node *p = new node();p->num = x;p->next = NULL;tail->next = p;       // 新節點插入到尾部tail = p;             // 尾指針移動到新節點}return head;
}// 合并兩個有序鏈表
node* ListUnion(node* heada, node* headb){node *pa = heada->next;   // 跳過頭節點，指向第一個數據節點node *pb = headb->next;node *dummy = new node(); // 合并后的虛擬頭節點node *pc = dummy;while(pa && pb){if(pa->num <= pb->num){pc->next = pa;pa = pa->next;} else {pc->next = pb;pb = pb->next;}pc = pc->next;        // 移動pc指針}// 連接剩余節點pc->next = pa ? pa : pb;// 釋放原鏈表頭節點delete heada;delete headb;return dummy;
}// 輸出鏈表
void print(node *head){node *p = head->next;     // 跳過頭節點if(!p){                   // 處理空鏈表cout << "NULL";return;}cout << p->num;           // 輸出第一個節點p = p->next;while(p){cout << " " << p->num; // 控制空格輸出p = p->next;}cout << endl;
}int main(){node *heada = CreatList();node *headb = CreatList();node *head = ListUnion(heada, headb);print(head);// 釋放合并后的鏈表while(head){node *temp = head;head = head->next;delete temp;}return 0;
}

2、一元多項式的加法運算

#include<bits/stdc++.h>
using namespace std;
struct node{double xishu;int zhishu;
};
int main(){vector<node>p1,p2,result;int n;cin>>n;for(int i=0;i<n;i++){node t;cin>>t.xishu>>t.zhishu;p1.push_back(t);}int m;cin>>m;for(int j=0;j<m;j++){node t;cin>>t.xishu>>t.zhishu;p2.push_back(t);}int i=0,j=0;while(i<n&&j<m){if(p1[i].zhishu>p2[j].zhishu){result.push_back(p1[i]);i++;}else if(p1[i].zhishu<p2[j].zhishu){result.push_back(p2[j]);j++;}else{double sum=p1[i].xishu+p2[j].xishu;if(sum!=0){result.push_back({sum,p1[i].zhishu});}i++;j++;}}while(i<n)result.push_back(p1[i++]);while(j<m)result.push_back(p2[j++]);for(const auto& term: result){cout<<fixed<<setprecision(2)<<term.xishu<<" "<<term.zhishu<<"\n";}return 0;
}

3、棧操作的合法性

#include<bits/stdc++.h>
using namespace std;bool isValid(string s, int m) {int cnt = 0;for(int i = 0; i < s.length(); i++) {char c = s[i];if(c == 'S') {cnt++;if(cnt > m) {return false;  // 超過最大容量}} else {cnt--;if(cnt < 0) {return false;  // 棧空時出棧}}}return cnt == 0;  // 最終棧必須為空
}int main() {int n, m;cin >> n >> m;for(int i = 0; i < n; i++) {string s;cin >> s;if(isValid(s, m)) {cout << "YES" << endl; } else {cout << "NO" << endl;  }}return 0;
}

4、括弧匹配檢驗

#include<bits/stdc++.h>
using namespace std;bool isValid(string s) {stack<char> st;for(int i = 0; i < s.length(); i++) {char c = s[i];if(c == '(' || c == '[') {st.push(c);} else if(c == ')' || c == ']') {if(st.empty()) {return false;}char top = st.top();st.pop();if((c == ')' && top != '(') || (c == ']' && top != '[')) {return false;}}}return st.empty();
}int main() {string s;cin >> s;if(isValid(s)) {cout << "OK" << endl;} else {cout << "Wrong" << endl;}return 0;
}

5、還原二叉樹

#include<bits/stdc++.h>
using namespace std;struct node{char value;node* left;node* right;// 添加構造函數node(char val) : value(val), left(NULL), right(NULL) {}
};int n;node* buildtree(string pre, string idx){if(pre.empty() || idx.empty()){return NULL;}char vroot = pre[0];node* root = new node(vroot);int idxroot = idx.find(vroot);string leftidx = idx.substr(0, idxroot);string rightidx = idx.substr(idxroot+1);string leftpre = pre.substr(1, leftidx.length());string rightpre = pre.substr(1 + leftidx.length());root->left = buildtree(leftpre, leftidx);root->right = buildtree(rightpre, rightidx);return root;
}// 修正函數名和返回值類型
int treeHeight(node* root){if(root == NULL) return 0;int leftheight = treeHeight(root->left);int rightheight = treeHeight(root->right);return max(leftheight, rightheight) + 1;
}int main(){cin >> n;string pre, idx;cin >> pre >> idx;node* root = buildtree(pre, idx); // 構建二叉樹int h = treeHeight(root); // 調用修正后的函數名cout << h << endl; return 0;
}

6、求先序排列（后中求先）

#include<bits/stdc++.h>
using namespace std;struct node{char value;node* left;node* right;node(char x):value(x),left(NULL),right(NULL){}
};//post表示后序，idx表示中序
node* buildtree(string post, string idx){if(post.empty() || idx.empty()) return NULL;// 后序遍歷的最后一個字符是根節點char rootv = post.back();node* root = new node(rootv);// 在中序遍歷中找到根節點的位置int rootidx = idx.find(rootv);// 分割中序遍歷為左子樹和右子樹string leftidx = idx.substr(0, rootidx);string rightidx = idx.substr(rootidx + 1);// 分割后序遍歷為左子樹和右子樹string leftpost = post.substr(0, leftidx.length());string rightpost = post.substr(leftidx.length(), rightidx.length());// 修正遞歸調用的參數順序：(后序, 中序)root->left = buildtree(leftpost, leftidx);root->right = buildtree(rightpost, rightidx);return root;
}void xianxu(node* root){if(root == NULL) return;  //直接返回，不返回值cout << root->value;xianxu(root->left);xianxu(root->right);
}int main(){string post, idx;  // 修正變量名以反映實際用途cin >> idx >> post;  //先輸入中序，再輸入后序node* root = buildtree(post, idx);xianxu(root);cout << endl;return 0;
}

7、迷宮最短路徑問題

#include <iostream>
#include <queue>
using namespace std;struct node {int r, c, s; // row column step
};int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int b[15][15];
int a[15][15];
int n;int bfs(int x, int y) {queue<node> mg;node q;q.r = x;q.c = y;q.s = 0;b[q.r][q.c] = 1;mg.push(q);while (!mg.empty()) {q = mg.front();mg.pop();if (q.r == n - 2 && q.c == n - 2) {return q.s;}node t;for (int i = 0; i < 4; i++) {t.r = q.r + dir[i][0];t.c = q.c + dir[i][1];if (!b[t.r][t.c] && a[t.r][t.c] == 0 && t.r >= 0 && t.r < n && t.c >= 0 && t.c < n) {b[t.r][t.c] = 1;t.s = q.s + 1;mg.push(t);}}}return -1;
}int main() {cin >> n;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> a[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {b[i][j] = 0;}}int result = bfs(1, 1);if (result == -1) {cout << "No solution\n";} else {cout << result << "\n";}return 0;
}    

8、圖著色問題

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=N*N;
int color[N];
vector<int> g[M];
int v,m,k,n;void add(int a,int b){g[a].push_back(b);g[b].push_back(a);
}
int judge(int cnt){if(cnt!=k)return 0;for(int i=1;i<=v;i++){for(int j=0;j<g[i].size();j++){int t=g[i][j];if(color[i]==color[t])return 0;}}return 1;
}
int main(){cin>>v>>m>>k;while(m--){int a,b;cin>>a>>b;add(a,b),add(b,a);}cin>>n;for(int i=0;i<n;i++){set<int> se;//set具有去重功能for(int j=1;j<=v;j++){cin>>color[j];se.insert(color[j]);} if(judge(se.size()))cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

9、地下迷宮探索

#include <bits/stdc++.h>
using namespace std;const int N = 1005;
int vis[N];
int g[N][N];
stack<int> stk;
int n, m, src;// 深度優先搜索函數
void dfs(int k) {vis[k] = 1;if (vis[src]) cout << k;else cout << " " << k;stk.push(k);for (int i = 1; i <= n; i++) {if (!vis[i] && g[k][i] == 1) {cout << " ";dfs(i);}}stk.pop();if(!stk.empty()){cout<<" "<<stk.top();}
}int main() {memset(vis, 0, sizeof(vis));cin >> n >> m >> src; // n代表節點數，m代表邊數，src代表初末位置 int s, d;for (int i = 1; i <= m; i++) {cin >> s >> d;g[s][d] = g[d][s] = 1;}dfs(src);bool connected = true;for (int i = 1; i <= n; i++) {if (!vis[i]) {connected = false;break;}}if (!connected) cout << " " << 0;return 0;
}