前言
计划更新23王道数据结构所有课后代码习题的实现，虽然考试写的一般都是伪代码，但是强迫症的我还是全部实现了一遍，仓库在这里
代码是用 C++ 写的，全部可以编译运行，尽量包含暴力解和最优解（考试时间不够可以直接怼一个暴力上去，稳拿一半分以上）。
持续更新，目前更新进度：
- 线性表 14/14
- 链表 25/25
- 栈 3/3
- 队列
- ...
仅供参考！ 会包含一些考试不让写的语法，可能也会有一些错误。
3.1.5, 3
- 题中明确写出栈的初态终态均为空，所以入栈次数和出栈次数应该相同
- 将入栈记为+1，出栈-1，最终结果为0则合法，中间过程中如果有<0的情况即为不合法
- 时间复杂度O(n)，空间复杂度O(1)
bool isValid(string str) { int cnt = 0; for (int i = 0; i < str.length(); i++) { if (str[i] == 'I') cnt++; if (str[i] == 'O') cnt--; if (cnt < 0) return false; } if (cnt == 0) return true; return false; } 复制代码
4
- 中心对称
- 遍历，用栈存储前一半元素，然后对比后一半元素
- 只需要注意奇偶数个元素的判定即可
- 时间复杂度O(n)，空间复杂度O(n/2)
bool isSymmetry(LinkList L, int n) { char stk[n/2]; // 字符栈 LNode *p = L->next; // 1.存入链表前一半的元素 for (int i = 0; i < n/2; i++) { stk[i] = p->data; p = p->next; } // 2.如果链表元素个数为奇数，则中间元素不用比较 if (n % 2 == 1) p = p->next; // 3.对比后半部分 for (int i = n/2 - 1; i >= 0; i--) { if (stk[i] != p->data) return false; p = p->next; } return true; } 复制代码
5
- 共享顺序栈，关键在于两个站入栈和出栈的判定，s1是传统意义上的栈，入栈时栈顶指针+1，s2则相反，入栈时栈顶指针-1，同理可得出栈
- 注意“入栈判满，出栈判空”即可
- 栈满的判断方法是
top2-top1 == 1
#define maxsize 100 typedef struct { int stack[maxsize]; int top1; int top2; } stk; // 栈的初始化 void initStack(stk &s) { s.top1 = -1; s.top2 = maxsize; } // 判断栈空 bool isEmpty(stk &s, int num) { if (num != 1 && num != 2) { cout << "栈号输入错误" << endl; return false; } if (num == 1) return s.top1 == -1; return s.top2 == maxsize; } // 判断栈满 bool isFull(stk &s) { if (s.top2 - s.top1 == 1) return true; return false; } // 入栈 bool push(stk &s, int num, int x) { if (num != 1 && num != 2) { cout << "栈号输入错误" << endl; return false; } if (isFull(s)) { cout << "栈满" << endl; return false; } if (num == 1) s.stack[++s.top1] = x; else s.stack[--s.top2] = x; return true; } // 出栈 bool pop(stk &s, int num, int &x) { if (num != 1 && num != 2) { cout << "栈号输入错误" << endl; return false; } if (isEmpty(s, num)) { cout << "栈空" << endl; return false; } if (num == 1) x = s.stack[s.top1--]; else x = s.stack[s.top2++]; return true; }
