图片来源
1800 字
9 分钟
【数据结构】特殊线性表
代码会在结束后更新。
题也是很简单，但是，太恶心了，🤮。
- 题面：来给我实现个栈，你不需要知道我怎么用，你不需要知道我的下标从哪里开始，不需要知道栈顶存不存元素，但是你要给我写对！
- 题面：我有一个中缀表达式，你给我转成后缀，你只需要知道你的式子里可包含
+ - * / ( )，式子长度不大于 20。 - 题面：我有两个矩阵，给我乘一下，你不需要知道矩阵的大小，但是你占用的内存必须小于 64 MB。
没做之前看上面的话可能感觉不出什么，等你做完了之后，你一定会幡然醒悟。
不要惊讶于下面的一些突然冒出来的结论，因为题目没说，但是据我尝试也只能这样。
函数题
观前提醒，我的能正常通过代码在自测区复制样例然后跑自测全是 TLE，不要怀疑自己，可能就是题目或者评测机的问题。
在一个数组中实现两个堆栈
逻辑上很好实现，从两边往中间存就行。Top1 初始值赋 -1, Top2 初始值赋 MaxSize，否则 MLE。
Stack CreateStack( int MaxSize ) { Stack st = (Stack)malloc(sizeof(struct SNode)); st->MaxSize = MaxSize; st->Top1 = -1, st->Top2 = MaxSize; st->Data = (ElementType *)malloc(sizeof(ElementType) * MaxSize); return st;}
bool Push( Stack S, ElementType X, int Tag ) { if (S->Top1 + 1 == S->Top2) { printf("Stack Full\n"); return false; } if (Tag == 1) { S->Data[++S->Top1] = X; } else { S->Data[--S->Top2] = X; } return true;}
ElementType Pop( Stack S, int Tag ) { if (Tag == 1) { if (S->Top1 == -1) { printf("Stack 1 Empty\n"); return ERROR; } return S->Data[S->Top1--]; } else { if (S->Top2 == S->MaxSize) { printf("Stack 2 Empty\n"); return ERROR; } return S->Data[S->Top2++]; }}另类堆栈
我没能理解到这个另类堆栈到底怎么另类了，我就是正常的写了一个栈，我越想让他按照题意另类，他越MLE。
bool Push( Stack S, ElementType X ) { if (S->Top == S->MaxSize) { printf("Stack Full\n"); return false; } S->Data[++S->Top] = X; return true;}
ElementType Pop( Stack S ) { if (!S->Top) { printf("Stack Empty\n"); return ERROR; } return S->Data[S->Top--];}另类循环队列
这道题不怎么毒，按要求模拟就行。
bool AddQ( Queue Q, ElementType X ) { if (Q->Count == Q->MaxSize) { printf("Queue Full\n"); return false; } Q->Data[(Q->Front + Q->Count) % Q->MaxSize] = X; Q->Count++; return true;}
ElementType DeleteQ( Queue Q ) { if (Q->Count == 0) { printf("Queue Empty\n"); return ERROR; } int res = Q->Data[Q->Front]; Q->Front = (Q->Front + 1) % Q->MaxSize; Q->Count --; return res;}Deque
Push 和 Pop 是左端，Inject 和 Eject 是右端，按要求模拟即可。
Deque CreateDeque() { Deque q = malloc(sizeof(struct DequeRecord)); PtrToNode h = malloc(sizeof(struct Node)); h->Next = h->Last = NULL; q->Front = q->Rear = h; return q;}
int Push( ElementType X, Deque D ) { PtrToNode t = malloc(sizeof(struct Node)); t->Element = X; t->Last = D->Front; t->Next = D->Front->Next; if (t->Next == NULL) D->Rear = t; if (D->Front->Next) D->Front->Next->Last = t; D->Front->Next = t; return 1;}
ElementType Pop( Deque D ) { if (D->Front->Next == NULL) return ERROR; int res = D->Front->Next->Element; PtrToNode t = D->Front->Next; t->Last->Next = t->Next; if (t->Next) t->Next->Last = t->Last; if (t == D->Rear) D->Rear = D->Front; free(t); return res;}
int Inject( ElementType X, Deque D ) { PtrToNode t = malloc(sizeof(struct Node)); t->Element = X; D->Rear->Next = t; t->Last = D->Rear; t->Next = NULL; D->Rear = t; return 1;}
ElementType Eject( Deque D ) { if (D->Front == D->Rear) return ERROR; int res = D->Rear->Element; PtrToNode t = D->Rear; D->Rear = D->Rear->Last; D->Rear->Next = NULL; free(t); return res;}编程题
出栈序列的合法性
每一条都开个栈模拟即可，栈容量超了，或者对应元素取不出来都直接判 NO，其他情况判 YES。
#include <iostream>
using namespace std;
const int N = 1010;int a[N], st[N], tp;int n, m, k;
bool check() { tp = 0; for (int i = 1, j = 0; i <= n; ++i) { if (a[i] > j) { while (a[i] != j) { st[++tp] = ++j; if (tp > m) { return false; } } tp--; } else if (tp && st[tp] == a[i]) tp--; else return false; } return true;}
int main() { scanf("%d%d%d", &m, &n, &k); while (k--) { for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); if (check()) printf("YES\n"); else printf("NO\n"); } return 0;}表达式转换
简要说一下流程，开一个栈存积攒的运算符
- 遇到数字直接输出；
- 遇到 ‘
(’直接入栈，初始化 ‘)’ 优先级最低； - 遇到运算符：
- 检查栈顶，如果优先级相等或更高就先弹栈输出栈顶，直到栈空或者栈顶优先级严格低于当前运算符，
- 当前运算符入栈；
- 遇到 ‘
)’，弹栈输出，直到栈顶为 ‘(’，再弹一次不输出。
最后把栈里面剩下的运算符全部输出。
如果发现调怎么调都过不去，请测试这组数据是否正确
输入
-1+(-2+3.001)-123/0.123输出
-1 -2 3.001 + + 123 0.123 / -#include <iostream>#include <sstream>#include <stack>
using namespace std;
stack<char> op;bool first = true;
int w(char c) { if (c == '+' || c == '-') return 1; else if (c == '*' || c == '/') return 2; else return 0;}
void calc() { if (first) first = true; else cout << ' '; cout << op.top() ; op.pop();}
int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); string s; getline(cin, s); stringstream ss(s); bool f = true; char c; while (ss.peek() != EOF) { if (isdigit(ss.peek())) { if (first) first = false; else cout << ' '; while (ss.peek() != EOF && (isdigit(ss.peek()) || ss.peek() == '.')) { ss >> c; cout << c; } f = false; if (ss.peek() == EOF) break; } else { ss >> c; if (c == '(') { f = true; op.push(c); } else if (c == ')') { while (op.top() != '(') calc(); op.pop(); f = false; } else if (f) { if (first) first = false; else cout << ' '; if (c == '-') cout << c; while (ss.peek() != EOF && (isdigit(ss.peek()) || ss.peek() == '.')) { ss >> c; cout << c; } f = false; } else { while (!op.empty() && w(op.top()) >= w(c)) calc(); op.push(c); f = true; } } } while (!op.empty()) calc(); cout << endl; return 0;}稀疏矩阵的处理
不要尝试动态开数组，会 MLE，时间复杂度可以亏，但是空间一定得开小一点，实测嵌套 map 可以过，2 ms，600 KB。
#include <iostream>#include <map>#include <tuple>#include <vector>
using namespace std;
struct Matrix { int n, m; map<int, map<int, int>> val;
void input() { int k; scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < k; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); val[x - 1][y - 1] = z; } }
Matrix rev() { Matrix b = {m, n}; for (auto [x, mp] : val) { for (auto [y, z] : mp) { b.val[y][x] = z; } } return b; }
void print(bool f) { if (f) { printf(" "); for (int i = 0; i < m; ++i) printf("%4d", i + 1); printf("\n"); for (int i = 0; i < n; ++i) { printf("%4d", i + 1); for (int j = 0; j < m; ++j) { if (val.find(i) != val.end() && val[i].find(j) != val[i].end()) printf("%4d", val[i][j]); else printf(" 0"); } printf("\n"); } } else { vector<tuple<int, int, int>> v; for (auto [x, mp] : val) { for (auto [y, z] : mp) { if (z) v.emplace_back(x + 1, y + 1, z); } } printf("Rows=%d,Cols=%d,r=%ld\n", n, m, v.size()); for (auto [x, y, z] : v) printf("%d %d %d\n", x, y, z); } }};
Matrix operator +(Matrix a, Matrix b) { Matrix c = {a.n, b.m}; for (int i = 0; i < a.n; ++i) { for (int j = 0; j < a.m; ++j) { bool va = a.val.find(i) != a.val.end() && a.val[i].find(j) != a.val[i].end(), vb = b.val.find(i) != b.val.end() && b.val[i].find(j) != b.val[i].end(); if (va && vb) { c.val[i][j] = a.val[i][j] + b.val[i][j]; } else if (va) c.val[i][j] = a.val[i][j]; else if (vb) c.val[i][j] = b.val[i][j]; } } return c;}
Matrix operator *(Matrix a, Matrix b) { Matrix c = {a.n, b.m}; for (int i = 0; i < a.n; ++i) { for (int j = 0; j < b.m; ++j) { for (int k = 0; k < a.m; ++k) { bool va = a.val.find(i) != a.val.end() && a.val[i].find(k) != a.val[i].end(), vb = b.val.find(k) != b.val.end() && b.val[k].find(j) != b.val[k].end(); if (va && vb) c.val[i][j] += a.val[i][k] * b.val[k][j]; } } } return c;}
int main() { char s[2]; Matrix a, b; a.input(), b.input(); scanf("%s", s); printf("The transformed matrix is:\n"); a.rev().print(s[0] == 'H'); if (a.n != b.n || a.m != b.m) printf("Can not add!\n"); else { printf("The added matrix is:\n"); (a + b).print(s[0] == 'H'); } if (a.m != b.n) printf("Can not multiply!\n"); else { printf("The product matrix is:\n"); (a * b).print(s[0] == 'H'); } return 0;}部分信息可能已经过时
