Elian's blog page

朴素模式匹配模式匹配问题字符串模式匹配是在主串 S 中寻找与模式串 T 相同的子串，并返回第一次出现的位置。若不存在，返回 0。 注意： 子串是主串的一部分，一定存在于主串中。 模式串不一定能在主串中找到。 若主串长度为 n，模式串长度为 m，最多需要尝试 n - m + 1 个起始位置。 基本思想朴素算法把主串中每个长度为 m 的候选子串依次与模式串比较： 先比较 S[1..m] 和 T[1..m]。 失配则比较 S[2..m+1] 和 T[1..m]。 继续右移，直到完全匹配或所有候选位置失败。 这种做法没有利用已经匹配过的信息；一旦失配，主串指针会回退到下一轮候选起点。 直接数组实现12345678910111213141516171819int Index(SString s, SString t) { int i = 1; int j = 1; while (i <= s.length && j <= t.length) { if (s.ch[i] == t.ch[j])...

串的存储结构 顺序存储串的顺序存储用一段连续空间保存字符，可分为静态数组实现和动态数组实现。 123456#define MAXLEN 255typedef struct { char ch[MAXLEN + 1]; // ch[0] 可不用，使位序和下标一致 int length;} SString; 教材常用 ch[0] 废弃不用，使第 1 个字符放在 ch[1]，这样“位序”和“数组下标”一致，便于表达 SubString、Index 等算法。 常见顺序存储方案： 方案 做法 特点 ch[0] 存长度 第 0 个单元保存长度 长度受一个字符单元能表示的范围限制 ch[0] 废弃，另设 length 第 1 个单元保存第 1 个字符 教材常用，位序和下标一致 以 '\0' 结尾 C 风格字符串 不直接保存长度，求长需扫描 堆分配存储 动态申请连续空间 更灵活，用完需要释放 堆分配形式： 1234typedef struct { char *ch; int...

串的定义与基本操作串是什么串，也叫字符串，是由零个或多个字符组成的有限序列，常记作： $$S=’a_1a_2\cdots a_n’\quad(n\ge 0)$$ S 是串名。 单引号括起来的字符序列是串值；字符可以是字母、数字、标点或其他字符。 串中字符个数 n 称为串长。 n = 0 时为空串，常记作 $\emptyset$。 注意区分： 概念 含义 空串 长度为 0，不含任何字符 空格串 由一个或多个空格字符组成，长度不为 0 考研语境里，串中字符位置通常从 1 开始计数，而不是从 0 开始。 子串、主串和位置 子串：串中任意个连续字符组成的子序列。 主串：包含该子串的串。 字符在主串中的位置：该字符第一次出现时在串中的序号。 子串在主串中的位置：子串第一个字符在主串中的位置。 例如 T = 'iPhone 11 Pro Max?'： 'iPhone'、'Pro M' 是 T 的子串。 '1' 第一次出现的位置是 8。 '11 Pro' 在 T 中的位置是...

数组存储数组是由相同类型的数据元素构成的有限序列。数组元素大小相同，并且在内存中连续存放，所以可以用起始地址和下标直接计算任意元素的地址。 一维数组设一维数组 A[0...n-1] 的起始地址为 LOC，每个元素占 sizeof(ElemType) 个字节，则： $$LOC(A[i]) = LOC + i \times sizeof(ElemType)$$ 若题目没有特别说明，C 语言数组下标从 0 开始；矩阵题中的行号、列号常从 1 开始。做地址映射题时，先看清下标起点。 二维数组 二维数组本质上仍然存入一维连续内存，关键是确定存储顺序。 设二维数组 b[M][N]，每个元素占 d 个字节，下标从 0 开始。 按行优先存储： $$LOC(b[i][j]) = LOC + (i \times N + j) \times d$$ 按列优先存储： $$LOC(b[i][j]) = LOC + (j \times M + i) \times d$$ 解题要点地址计算题的核心是“目标元素前面已经存了多少个元素”。 行优先：先数完整的前 i...

队列的应用队列 的核心特征是先进先出，适合保存“先到先处理”的对象，也适合按层次、按距离逐步扩展的过程。 树的层次遍历层次遍历从根结点开始，按从上到下、从左到右的顺序访问结点。队列保存“已经发现但还没访问其孩子”的结点。 12345678910111213141516void LevelOrder(BiTree root) { if (root == NULL) return; LinkQueue queue; InitQueue(&queue); EnQueue(&queue, root); while (!QueueEmpty(queue)) { BiTNode *node; DeQueue(&queue, &node); Visit(node); if (node->lchild != NULL) EnQueue(&queue, node->lchild); if (node->rchild !=...

递归与栈递归适合处理“原问题可以转化为同类但规模更小的问题”的场景。递归定义必须同时包含递归体和递归出口，否则调用会无限深入。 递归工作栈函数递归调用时，系统会维护函数调用栈，也称递归工作栈。每进入一层递归，就把该层调用所需的信息压入栈顶；每返回一层，就从栈顶弹出对应信息。 一层递归调用中通常需要保存： 参数值。 局部变量。 返回地址。 调用现场中还需要恢复的信息。 阶乘递归123456int Factorial(int n) { if (n == 0) { return 1; } return n * Factorial(n - 1);} ↻ + − 递归表达式： $$factorial(n)=\begin{cases}n \times factorial(n-1), & n>0 \1, & n=0\end{cases}$$ 调用 Factorial(5) 时，会依次压入 n=5,4,3,2,1,0...

普通矩阵普通矩阵通常直接用二维数组存储。若矩阵为 m 行 n 列，需要存储 m * n 个元素。 描述矩阵元素时常写作 $a_{i,j}$，行列号通常从 1 开始；描述数组位置时通常从 0 开始。 特殊矩阵的压缩存储特殊矩阵仍然存入一维连续内存。只是特殊矩阵中大量元素可由少量信息推出。因此可以压缩存储只保存必要元素，再通过下标映射恢复矩阵位置。 这里规定$a_{k}$是物理存储方式中的第$k$个元素，且$1\leqslant k\leqslant total$ $n$行$n$列对称矩阵对称矩阵满足： $$a_{i,j} = a_{j,i}$$ 只需存储主对角线和一个三角区，共$\frac{n(n+1)}{2}$个元素。 若按行优先存储下三角区和主对角线，且矩阵下标从 1 开始、一维数组 B 下标从 0 开始： $$k = \frac{i(i-1)}{2} + j - 1,\quad i \ge j$$ 若访问上三角区元素 $a_{i,j}$，利用对称性转成 $a_{j,i}$： $$k = \frac{j(j-1)}{2} + i -...

循环队列 为什么需要循环队列普通顺序队列用数组存储。若只让 rear 后移入队、front 后移出队，数组前面被删除的位置会空出来，但 rear 可能已经到数组末尾，造成“假溢出”。 循环队列用模运算把数组逻辑上看成环： 1next = (index + 1) % MaxSize; 基本结构常见约定： 1234567#define MaxSize 10typedef struct { ElemType data[MaxSize]; int front; int rear;} SqQueue; 初始化： 1234void InitQueue(SqQueue *queue) { queue->front = 0; queue->rear = 0;} front 指向队头元素，rear 指向队尾元素的下一个位置。 牺牲一个存储单元的方案 ↻ + − 这种方案用一个空位区分队空和队满： 队空：front == rear 队满：(rear + 1) % MaxSize ==...

双端队列定义双端队列允许在两端插入和删除元素。它比普通 队列 更灵活，也能模拟 栈 的行为。 受限双端队列常考两种变形： 输入受限双端队列：只允许从一端插入，允许从两端删除。 输出受限双端队列：允许从两端插入，只允许从一端删除。 与栈、队列的关系 只在一端插入和删除时，双端队列表现得像栈。 固定一端插入、另一端删除时，双端队列表现得像队列。 普通栈的合法输出序列，在相应的双端队列模型中通常仍合法，但双端队列还可能产生更多序列。 判断输出序列双端队列输出序列题不能直接套 卡特兰数。应根据题目限制模拟两端操作： 确认哪一端允许插入。 确认哪一端允许删除。 按目标输出序列逐个判断当前两端是否能得到目标元素。 若需要继续输入，按输入顺序加入允许插入的一端。 易错点 “输入受限”和“输出受限”是按插入、删除权限命名，不是按队头队尾命名。 普通队列、栈、双端队列都是受限线性表，但限制不同，合法序列集合也不同。

表达式求值三种表达式以二元运算符为例： 中缀表达式：运算符在两个操作数中间，如 A + B。 后缀表达式：运算符在两个操作数后面，如 A B +，也称逆波兰表达式。 前缀表达式：运算符在两个操作数前面，如 + A B，也称波兰表达式。 计算机用栈处理后缀和前缀表达式很方便，因为运算符出现时，它需要的操作数已经在附近。 后缀表达式求值 ↻ + − 从左到右扫描后缀表达式： 遇到操作数，入栈。 遇到运算符，弹出两个操作数。 先弹出的是右操作数，后弹出的是左操作数。 计算结果入栈。 扫描结束后，栈顶就是表达式结果。 12345678910111213141516171819int EvaluatePostfix(Token tokens[], int n) { SqStack stack; InitStack(&stack); for (int i = 0; i < n; i++) { if (tokens[i].kind == OPERAND) { ...