【数据结构1-1】线性表P3156 【深基15.例1】询问学号#include stdio.h int main() { int n, m, a[2000000]; scanf(%d %d, n, m); for (int i 0; i n; i) scanf(%d, a[i]); for (int i 0; i m; i) { int j; scanf(%d, j); printf(%d\n, a[j - 1]); } return 0; }P3613 【深基15.例2】寄包柜// #include stdio.h // 这道题显然不能模拟因为会浪费很多空间 // 考虑稀疏矩阵的三元表虽然依然会有一个TLE // int main() { // int n, q, a[100000][3] {0}, index 0; // 跟踪操作 // scanf(%d %d, n, q); // for (int i1 0; i1 q; i1) { // int p, i, j, k; // scanf(%d, p); // if (p 1) { // scanf(%d %d %d, i, j, k); // a[index][0] i; a[index][1] j; a[index][2] k; // index; // continue; // } // scanf(%d %d, i, j); // // 查找一定是之前操作过的 // // 考虑重复存所以从后往前找 // for (int j1 index - 1; j1 0; --j1) { // if (a[j1][0] i a[j1][1] j) { printf(%d\n, a[j1][2]); break; } // } // } // return 0; // } #include stdio.h #include string.h #define N 2000003 // 用静态数组 开放寻址 int key1[N], key2[N], val[N]; // key1柜子, key2格子 int cnt 0; // 找位置返回数组下标 int find(int i, int j) { int h (i * 100003L j) % N; // 乘大质数把i j拉开减少碰撞 while (key1[h]) { if (key1[h] i key2[h] j) return h; h (h 1) % N; // 线性探测 } return h; } int main() { int n, q; scanf(%d %d, n, q); while (q--) { int p, i, j, k; scanf(%d, p); if (p 1) { scanf(%d %d %d, i, j, k); int pos find(i, j); key1[pos] i; key2[pos] j; val[pos] k; continue; } scanf(%d %d, i, j); int pos find(i, j); printf(%d\n, val[pos]); } return 0; }P1449 后缀表达式#include stdio.h // 后缀表达式栈的经典应用 int main() { int nums[50] {0}, top 0, num 0; char temp; while ((temp getchar()) ! ) { if (temp 0 temp 9) { num num * 10 temp - 0; continue; } else if (temp .) { nums[top] num; num 0; continue; } // 遇到操作符时取出两根操作数压入计算后的结果 int num1 nums[--top], num2 nums[--top]; switch(temp) { case : num num2 num1; break; case -: num num2 - num1; break; case *: num num2 * num1; break; case /: num num2 / num1; break; } nums[top] num; num 0; } printf(%d, nums[0]); return 0; }P1996 约瑟夫问题#include stdio.h int main() { int p[101] {0}, n, m, out 0; scanf(%d %d, n, m); int i 0, cnt 1; while (out ! n) { if (i n) i 0; // 循环 if (p[i] 1) { // 已出圈 i; continue; } if (cnt m) { printf(%d , i 1); out; cnt 0; p[i] 1; } i; cnt; } return 0; }P1160 队列安排用数组存关系而非模拟因为操作都只改关系而并不关心节点本身。#include stdio.h int pre[100005], nxt[100005]; // i号左/右是谁 int removed[100005] {0}; void insert(int i, int k, int p) { if (p 0) { // i 插入到 k 左边 pre[i] pre[k]; pre[k] i; nxt[i] k; nxt[pre[i]] i; } else { nxt[i] nxt[k]; nxt[k] i; pre[i] k; pre[nxt[i]] i; } } int main() { int n; scanf(%d, n); // 初始只有 1 号 pre[1] 0; nxt[1] 0; for (int i 2; i n; i) { int k, p; scanf(%d %d, k, p); insert(i, k, p); } int m; scanf(%d, m); while (m--) { int x; scanf(%d, x); removed[x] 1; } // 找队头 int cur 1; while (pre[cur] ! 0) cur pre[cur]; // 从左到右输出 while (cur ! 0) { if (!removed[cur]) printf(%d , cur); cur nxt[cur]; } return 0; }P1540 [NOIP 2010 提高组] 机器翻译#include stdio.h // 先进先出循环队列 int a[101] {0}, size 0; int m, res 0; int find(int word) { for (int i 0; i size; i) { int index i % m; if (a[index] word) return index; } return -1; } int main() { int n; scanf(%d %d, m, n); for (int i 0; i n; i) { int word; scanf(%d, word); if (find(word) -1) { res; a[size % m] word; size; } } printf(%d, res); return 0; }P2058 [NOIP 2016 普及组] 海港#include stdio.h #define MAXSIZE 300001 #define DIFF 86400 // 只需记录当前24h内的乘客国籍 int main() { int n, t, k, x, res 0; int q[MAXSIZE][2], front 0, rear 0; // 到达时间国籍 int nation[100001] {0}; scanf(%d, n); for (int i 0; i n; i) { scanf(%d %d, t, k); // 出队 for (; front ! rear q[front][0] t - DIFF; front) { nation[q[front][1]]--; if (nation[q[front][1]] 0) res--; } // 入队 while (k--) { scanf(%d, x); q[rear][0] t; q[rear][1] x; if (nation[x] 0) res; nation[x]; } printf(%d\n, res); } return 0; }P1241 括号序列#include stdio.h // 栈 标记数组 int main() { char s[105]; int stack[105], top 0; int matched[105] {0}; // 标记哪些位置已经配对 scanf(%s, s); for (int i 0; s[i]; i) { if (s[i] ( || s[i] [) { stack[top] i; // 存下标不是存字符 continue; } if (top 0) { int last stack[top - 1]; if ((s[last] ( s[i] )) || (s[last] [ s[i] ])) { matched[last] 1; matched[i] 1; top--; } // 不匹配就不管留着后面补 } } // 输出遍历原串没配对的位置前后补括号 for (int i 0; s[i]; i) { if (!matched[i]) { // 前面补对应的左括号 if (s[i] ) || s[i] ]) { printf(%c, s[i] ) ? ( : [); } } putchar(s[i]); if (!matched[i]) { // 后面补对应的右括号 if (s[i] ( || s[i] [) { printf(%c, s[i] ( ? ) : ]); } } } return 0; }P2234 [HNOI2002] 营业额统计这道题链表会比数组慢因为链表花大量时间在“从头遍历找插入位置”上而数组用二分查找 连续内存移动反而总耗时更少。// 链表版 #include stdio.h #include stdlib.h typedef struct Node{ int data; struct Node *next; }Node; int insert(Node *head, int x) { Node *cur head-next, *prev head; while (cur x cur-data) { cur cur-next; prev prev-next; } // 此时 prev x cur if (cur x cur-data) return 0; Node *newNode (Node*)malloc(sizeof(Node)); newNode-data x; newNode-next cur; prev-next newNode; if (cur NULL) return x - prev-data; if (prev head) return cur-data - x; return cur-data - x x - prev-data ? cur-data - x : x - prev-data; } // 需要找到前i天中最接近第i天营业额的值 - 插入排序链表 int main() { int n, res 0; scanf(%d, n); Node *head (Node*)malloc(sizeof(Node)); head-next NULL; head-data 0; while (n--) { int temp; scanf(%d, temp); res insert(head, temp); } printf(%d, res); return 0; }// 数组版 #include stdio.h #include stdlib.h int a[40000], cnt 0; // 二分找插入位置 int insert(int x) { if (cnt 0) { a[0] x; cnt 1; return x; } int l 0, r cnt - 1, pos cnt; while (l r) { int m (l r) 1; if (a[m] x) l m 1; else r m - 1; } pos l; int min 1 30; if (pos 0 x - a[pos - 1] min) min x - a[pos - 1]; if (pos cnt a[pos] - x min) min a[pos] - x; // 插入往后移 for (int i cnt; i pos; i--) a[i] a[i - 1]; a[pos] x; cnt; return min; } int main() { int n, x, res 0; scanf(%d, n); while (n--) { scanf(%d, x); res insert(x); } printf(%d, res); return 0; }P4387 【深基15.习9】验证栈序列#include stdio.h int sq[100001] {0}, s[100001] {0}; int main() { int q, n; scanf(%d, q); while (q--) { scanf(%d, n); for (int i 0; i n; i) scanf(%d, sq[i]); // 第i个数出栈时前i-1个数一定都已入栈 int temp, begin 0, top 0, flag 1; for (int i 0; i n; i) { scanf(%d, temp); if (top 0 s[top - 1] temp) { top--; continue; } while (begin n sq[begin] ! temp) s[top] sq[begin]; if (begin n) { flag 0; } // 这里注意千万不要break因为还需要把这一串的输入读完...在这卡了好久orz begin; } if (flag top 0) printf(Yes\n); else printf(No\n); } return 0; }