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;
}