【算法笔记自学】第 7 章提高篇（1）—

7.1栈的应用

#include <iostream>
#include <string>
#include <stack>
using namespace std;int main() {int n, x;string action;cin >> n;stack<int> s;for (int i = 0; i < n; i++) {cin >> action;if (action == "push") {cin >> x;s.push(x);} else {if (s.empty()) {cout << -1 << endl;} else {cout << s.top() << endl;s.pop();}}}return 0;
}

#include <iostream>
#include <string>
using namespace std;string toPostfixExpr(string infixExpr) {string result = "";result += infixExpr[0];for (int i = 2; i < infixExpr.length(); i += 4) {result += " ";result += infixExpr[i + 2];result += " ";result += infixExpr[i];}return result;
}int main() {string expr;getline(cin, expr);cout << toPostfixExpr(expr);return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>
using namespace std;struct Node {int num;char op;bool isOp;
};map<char, int> priority;vector<Node> toNodeVector(string expr) {vector<Node> nodes;for (int i = 0; i < expr.length(); i++) {if (expr[i] == ' ') {continue;}if (expr[i] >= '0' && expr[i] <= '9') {Node numNode;numNode.isOp = false;numNode.num = expr[i] - '0';nodes.push_back(numNode);} else {Node opNode;opNode.isOp = true;opNode.op = expr[i];nodes.push_back(opNode);}}return nodes;
}vector<Node> toPostfixVector(vector<Node> infix) {vector<Node> postfix;stack<Node> opStack;for (int i = 0; i < infix.size(); i++) {if (infix[i].isOp) {while (!opStack.empty() && priority[infix[i].op] <= priority[opStack.top().op]) {postfix.push_back(opStack.top());opStack.pop();}opStack.push(infix[i]);} else {postfix.push_back(infix[i]);}}while (!opStack.empty()) {postfix.push_back(opStack.top());opStack.pop();}return postfix;
}int main() {priority['+'] = priority['-'] = 0;priority['*'] = priority['/'] = 1;string expr;getline(cin, expr);vector<Node> infix = toNodeVector(expr);vector<Node> postfix = toPostfixVector(infix);for (int i = 0; i < postfix.size(); i++) {if (postfix[i].isOp) {cout << postfix[i].op;} else {cout << postfix[i].num;}if (i < (int)postfix.size() - 1) {cout << " ";}}return 0;
}

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <stack>
using namespace std;struct Node {int num;char op;bool isOp;
};map<char, int> priority;vector<Node> toNodeVector(string expr) {vector<Node> nodes;for (int i = 0; i < expr.length(); i++) {if (expr[i] == ' ') {continue;}if (expr[i] >= '0' && expr[i] <= '9') {Node numNode;numNode.isOp = false;numNode.num = expr[i] - '0';nodes.push_back(numNode);} else {Node opNode;opNode.isOp = true;opNode.op = expr[i];nodes.push_back(opNode);}}return nodes;
}double eval(vector<Node> postfix) {stack<double> numStack;for (int i = 0; i < postfix.size(); i++) {if (!postfix[i].isOp) {numStack.push(postfix[i].num);} else {double num2 = numStack.top();numStack.pop();double num1 = numStack.top();numStack.pop();if (postfix[i].op == '+') {numStack.push(num1 + num2);} else if (postfix[i].op == '-') {numStack.push(num1 - num2);} if (postfix[i].op == '*') {numStack.push(num1 * num2);} if (postfix[i].op == '/') {numStack.push(num1 / num2);}}}return numStack.top();
}int main() {priority['+'] = priority['-'] = 0;priority['*'] = priority['/'] = 1;string expr;getline(cin, expr);vector<Node> postfix = toNodeVector(expr);printf("%.2f", eval(postfix));return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>
using namespace std;struct Node {int num;char op;bool isOp;
};map<char, int> priority;vector<Node> toNodeVector(string expr) {vector<Node> nodes;for (int i = 0; i < expr.length(); i++) {if (expr[i] == ' ') {continue;}if (expr[i] >= '0' && expr[i] <= '9') {Node numNode;numNode.isOp = false;numNode.num = expr[i] - '0';nodes.push_back(numNode);} else {Node opNode;opNode.isOp = true;opNode.op = expr[i];nodes.push_back(opNode);}}return nodes;
}vector<Node> toPostfixVector(vector<Node> infix) {vector<Node> postfix;stack<Node> opStack;for (int i = 0; i < infix.size(); i++) {if (infix[i].isOp) {while (!opStack.empty() && priority[infix[i].op] <= priority[opStack.top().op]) {postfix.push_back(opStack.top());opStack.pop();}opStack.push(infix[i]);} else {postfix.push_back(infix[i]);}}while (!opStack.empty()) {postfix.push_back(opStack.top());opStack.pop();}return postfix;
}double eval(vector<Node> postfix) {stack<double> numStack;for (int i = 0; i < postfix.size(); i++) {if (!postfix[i].isOp) {numStack.push(postfix[i].num);} else {double num2 = numStack.top();numStack.pop();double num1 = numStack.top();numStack.pop();if (postfix[i].op == '+') {numStack.push(num1 + num2);} else if (postfix[i].op == '-') {numStack.push(num1 - num2);} if (postfix[i].op == '*') {numStack.push(num1 * num2);} if (postfix[i].op == '/') {numStack.push(num1 / num2);}}}return numStack.top();
}int main() {priority['+'] = priority['-'] = 0;priority['*'] = priority['/'] = 1;string expr;getline(cin, expr);vector<Node> infix = toNodeVector(expr);vector<Node> postfix = toPostfixVector(infix);printf("%.2f", eval(postfix));return 0;
}

7.2队列的应用

#include <iostream>
#include <string>
#include <queue>
using namespace std;int main() {int n, k;cin >> n;string action;queue<int> q;for (int i = 0; i < n; i++) {cin >> action;if (action == "push") {cin >> k;q.push(k);} else {if (q.empty()) {cout << -1 << endl;} else {cout << q.front() << endl;q.pop();}}}return 0;
}

#include <cstdio>
#include <queue>
using namespace std;int main() {int n, x;scanf("%d", &n);queue<int> q;for (int i = 0; i < n; i++) {scanf("%d", &x);q.push(x);}while (q.size() > 1) {int front1 = q.front();q.pop();int front2 = q.front();q.pop();q.push(front1 + front2);}printf("%d", q.front());return 0;
}

#include <cstdio>
#include <queue>
using namespace std;int main() {int n, k;scanf("%d%d", &n, &k);queue<int> q;for (int i = 1; i <= n; i++) {q.push(i);}while (!q.empty()) {for (int i = 0; i < k - 1; i++) {int front = q.front();q.pop();q.push(front);}printf("%d", q.front());q.pop();if (!q.empty()) {printf(" ");}}return 0;
}

7.3链表处理

#include <cstdio>const int MAXN = 100;struct Node {int data, next;
} nodes[MAXN];int main() {int n, first, id;scanf("%d%d", &n, &first);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int current = first;while (current != -1) {printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);current = nodes[current].next;}return 0;
}

#include <cstdio>const int MAXN = 100;struct Node {int data, next;
} nodes[MAXN];int main() {int n, first, id;scanf("%d%d", &n, &first);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int current = first;int num=0;while (current != -1) {//printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);current = nodes[current].next;num++;}printf("%d",num);return 0;
}

#include <cstdio>const int MAXN = 1024;struct Node {int data, next;
} nodes[MAXN];int main() {int n, first, id;scanf("%d%d", &n, &first);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int num=0;int current = first;scanf("%d",&num);for (int i = 0; i < num; i++) {scanf("%d", &id);scanf("%d", &nodes[id].data);nodes[id].next=current;current=id;}while (current != -1) {printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);current = nodes[current].next;}return 0;
}

#include <cstdio>const int MAXN = 100;struct Node {int data, next;
} nodes[MAXN];int main() {int n, first, k, id;scanf("%d%d%d", &n, &first, &k);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int current = first, last = 0;while (current != -1) {if (nodes[current].data == k) {if (current == first) {first = nodes[current].next;}nodes[last].next = nodes[current].next;current = nodes[last].next;} else {last = current;current = nodes[current].next;}}current = first;while (current != -1) {printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);current = nodes[current].next;}return 0;
}

#include <cstdio>const int MAXN = 100;struct Node {int data, next;
} nodes[MAXN];int main() {int n, first, id;scanf("%d%d", &n, &first);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int current = first, last = -1;while (current != -1) {int next = nodes[current].next;nodes[current].next = last;last = current;current = next;}current = last;while (current != -1) {printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);current = nodes[current].next;}return 0;
}

#include <cstdio>const int MAXN = 100;
const int MAXV = 1000 + 1;struct Node {int data, next;
} nodes[MAXN];bool needDelete[MAXV] = {false};int main() {int n, first, id;scanf("%d%d", &n, &first);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int current = first, last = -1;while (current != -1) {if (needDelete[nodes[current].data]) {nodes[last].next = nodes[current].next;current = nodes[current].next;} else {needDelete[nodes[current].data] = true;last = current;current = nodes[current].next;}}current = first;while (current != -1) {printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);current = nodes[current].next;}return 0;
}

#include <cstdio>const int MAXN = 100;struct Node {int data, next;
} nodes[MAXN];int main() {int n, first, id;scanf("%d%d", &n, &first);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int fast = first, slow = first;while (nodes[fast].next != -1 && nodes[nodes[fast].next].next != -1) {slow = nodes[slow].next;fast = nodes[fast].next;fast = nodes[fast].next;}if (nodes[fast].next == -1) {printf("%.1f", (double)nodes[slow].data);} else {printf("%.1f", (nodes[slow].data + nodes[nodes[slow].next].data) / 2.0);}return 0;
}

#include <cstdio>const int MAXN = 100;struct Node {int data, next;
} nodes[MAXN];int main() {int n, first, k, id;scanf("%d%d%d", &n, &first, &k);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int fast = first;while (k--) {fast = nodes[fast].next;}int slow = first;while (fast != -1) {slow = nodes[slow].next;fast = nodes[fast].next;}printf("%d %d %d", slow, nodes[slow].data, nodes[slow].next);return 0;
}

#include <cstdio>const int MAXN = 100;struct Node {int data, next;
} nodes[MAXN];int reverseList(int first) {int current = first, last = -1;while (current != -1) {int next = nodes[current].next;nodes[current].next = last;last = current;current = next;}return last;
}bool judgePalindrome(int head1, int head2) {while (head2 != -1) {if (nodes[head1].data != nodes[head2].data) {return false;}head1 = nodes[head1].next;head2 = nodes[head2].next;}return true;
}int main() {int n, first, id;scanf("%d%d", &n, &first);for (int i = 0; i < n; i++) {scanf("%d", &id);scanf("%d%d", &nodes[id].data, &nodes[id].next);}int fast = first, slow = first;while (nodes[fast].next != -1 && nodes[nodes[fast].next].next != -1) {slow = nodes[slow].next;fast = nodes[fast].next;fast = nodes[fast].next;}int headOfSecondPart = reverseList(nodes[slow].next);bool isPalindrome = judgePalindrome(first, headOfSecondPart);nodes[slow].next = reverseList(headOfSecondPart);printf(isPalindrome ? "Yes" : "No");return 0;
}