T1
用顺序存储实现栈的初始化、入栈、出栈、取栈顶、判栈空操作。调用以上操作实现判断从键盘输入的括号序列是否匹配
输入描述
括导序列#(#为括号输入结束符号)
输出描述
匹配或不匹配
输入
{[()]}#
输出
匹配
#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
class Stack {
private:char data[MAX_SIZE];int top;
public:Stack() {top = -1;}void init() {top = -1;}bool push(char item) {if (top == MAX_SIZE - 1) {return false;}data[++top] = item;return true;}char pop() {if (top == -1) {return '\0';}return data[top--];}char peek() {if (top == -1) {return '\0';}return data[top];}bool isEmpty() {return top == -1;}
};
bool isMatchingBrackets(string input) {Stack stack;stack.init();for (char c : input) {if (c == '(' || c == '[' || c == '{') {stack.push(c);}else if (c == ')' || c == ']' || c == '}') {if (stack.isEmpty()) {return false;}char top = stack.pop();if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {return false;}}else if (c == '#') {break;}}return stack.isEmpty();
}
int main() {string input;cin >> input;if (isMatchingBrackets(input)) {cout << "匹配" << endl;}else {cout << "不匹配" << endl;}return 0;
}
T2
患者到医院看病的顺序是，先排队等候，再看病治疗。要求设计个算法，模拟病人等候就诊的过程。其中：“病人到达"用命令“A”(或"a")表示，"护士让下一位就诊”用"N”(或"n")表示，“不再接收病人排队"用“S”(或“s”)表示,
输入描述
A(或a)病历号
N(或n)
S(或s)
X（其他字符）
输出描述
病历号为x的病人就诊
若队列中有数据，输出队首元素，否则输出“无病人就诊”
不再接收病人排队，并输出当前队列中所有病历号
输入命令不合法！
输入
A
123
n
n
a
124
A
125
X
S
输出
病历号为123的病人就诊
无病人就诊
输入命令不合法!
今天不再接收病人排队，下列排队的病人依次就诊：124 125
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_SIZE = 100;
class PatientQueue {
private:int data[MAX_SIZE];int front;int rear;
public:PatientQueue() {front = rear = -1;}bool isEmpty() {return front == -1;}bool isFull() {return (rear + 1) % MAX_SIZE == front;}void enqueue(int patientNumber) {if (isFull()) {cout << "队列已满，无法加入新病人。" << endl;return;}if (isEmpty()) {front = rear = 0;}else {rear = (rear + 1) % MAX_SIZE;}data[rear] = patientNumber;}int dequeue() {if (isEmpty()) {cout << "无病人就诊" << endl;return -1;}int patientNumber = data[front];if (front == rear) {front = rear = -1;}else {front = (front + 1) % MAX_SIZE;}return patientNumber;}void printQueue() {if (isEmpty()) {cout << "当前队列中无病人。" << endl;return;}cout << "今天不再接收病人排队，下列排队的病人依次就诊：";int index = front;while (index != rear) {cout << data[index] << " ";index = (index + 1) % MAX_SIZE;}cout << data[index] << endl;}
};
int main() {PatientQueue queue;char command;int patientNumber;while (true) {cin >> command;if (command == 'A' || command == 'a') {cin >> patientNumber;queue.enqueue(patientNumber);}else if (command == 'N' || command == 'n') {int patient = queue.dequeue();if (patient != -1) {cout << "病历号为" << patient << "的病人就诊" << endl;}}else if (command == 'S' || command == 's') {queue.printQueue();break;}else {cout << "输入命令不合法！" << endl;}}return 0;
}
T3
迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径
输入描述
迷宫宽度W 迷宫高度h
迷宫第一行
迷宫第二行
…
迷宫第n行
输出描述
入口横坐标1 入口纵坐标1
横坐标2 纵坐标2
横坐标3 纵坐标3
横坐标4 纵坐标4
横坐标n-1 纵坐标n-1
…
出口横坐标n 出口纵坐标n
输入
8 10
1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1
输出
3 3
2 3
2 4
2 5
3 5
3 6
3 7
4 7
4 6
4 5
4 4
5 4
6 4
#include <iostream>
#include <list>
using namespace std;struct PosInfo {int px, py;PosInfo(int x, int y) { px = x; py = y; }
};class MG {char** S;int w, h;int in_x, in_y, out_x, out_y;list<PosInfo> s;public:MG(int w, int h) {this->w = w;this->h = h;this->S = new char* [h];for (int i = 0; i < h; i++) {this->S[i] = new char[w];}for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {cin >> S[i][j];if (S[i][j] == '3') {in_y = j;in_x = i;}if (S[i][j] == '4') {out_x = i;out_y = j;}}}seekPath(in_x, in_y); }bool could(int x, int y){return (S[x][y] != '*' && S[x][y] != '1');}bool seekPath(int x, int y) {s.push_front(PosInfo(y, x));if (x == out_x && y == out_y) {if (s.empty()) { cout << "列表为空" << endl; return false; }while (!s.empty()) {cout << s.back().px << " " << s.back().py << endl;s.pop_back();}return true;}if (could(x, y)) {S[x][y] = '1';if (seekPath(x + 1, y)) return true;if (seekPath(x, y - 1)) return true;if (seekPath(x - 1, y)) return true;if (seekPath(x, y + 1)) return true;}s.pop_front();return false;}~MG() {for (int i = 0; i < h; i++) {delete[] S[i];}delete[] S;}
};int main() {int w, h;cin >> w >> h;MG m1(w, h);return 0;
}
T4
设计一个算法找一条从迷宫入口到出口的最短路径
输入描述
迷宫的行和列m n
迷宫的布局
输出描述
最小路径
输入
6 8
0 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0
0 1 0 0 1 1 1 1
0 1 1 1 0 0 1 1
1 0 0 1 1 0 0 0
0 1 1 0 0 1 1 0
输出
(6,8)
(5,7)
(4,6)
(4,5)
(3,4)
(3,3)
(2,2)
(1,1)
#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;struct Point {int x, y;Point(int x, int y) : x(x), y(y) {}
};class MG {int m, n;int** S;vector<Point> path; vector<vector<bool>> visited; public:MG(int m, int n) {this->m = m;this->n = n;S = new int* [m];for (int i = 0; i < m; i++) {S[i] = new int[n];}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> S[i][j];}}visited.resize(m, vector<bool>(n, false));searchPath();printPath();}bool could(int x, int y) {return (x >= 0 && x < m && y >= 0 && y < n && S[x][y] == 0 && !visited[x][y]);}void searchPath() {queue<pair<Point, vector<Point>>> q;q.push({ Point(0, 0), {Point(0, 0)} });visited[0][0] = true;vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, -1}, {1, 1}, {-1, -1}, {-1, 1} };while (!q.empty()) {auto current = q.front();q.pop();Point point = current.first;vector<Point> currentPath = current.second;if (point.x == m - 1 && point.y == n - 1) {path = currentPath; return;}for (auto dir : directions) {int newX = point.x + dir.first;int newY = point.y + dir.second;if (could(newX, newY)) {visited[newX][newY] = true;vector<Point> newPath = currentPath;newPath.push_back(Point(newX, newY));q.push({ Point(newX, newY), newPath });}}}}void printPath() {for (int i = path.size() - 1; i >= 0; --i) {cout << "(" << path[i].x + 1 << "," << path[i].y + 1 << ") " << endl;}}~MG() {for (int i = 0; i < m; i++) {delete[] S[i];}delete[] S;}
};int main() {int m, n;cin >> m >> n;MG m1(m, n);return 0;
}