Elian's blog page

链栈定义链栈是用链式存储实现的 栈。通常把链表头部作为栈顶，因为头插和头删都只需要 O(1)。 1234typedef struct StackNode { ElemType data; struct StackNode *next;} StackNode, *LinkStack; 不带头结点时，空栈可表示为： 1LinkStack top = NULL; 进栈进栈等价于单链表头插： 123456789bool Push(LinkStack *top, ElemType value) { StackNode *newNode = (StackNode *)malloc(sizeof(StackNode)); if (newNode == NULL) return false; newNode->data = value; newNode->next = *top; *top = newNode; return true;} 先让 newNode->next...

链队列定义链队列是用链式存储实现的 队列。通常设置队头指针 front 和队尾指针 rear。 带头结点的链队列结构： 123456789typedef struct LinkNode { ElemType data; struct LinkNode *next;} LinkNode;typedef struct { LinkNode *front; LinkNode *rear;} LinkQueue; 带头结点初始化12345678bool InitQueue(LinkQueue *queue) { LinkNode *head = (LinkNode *)malloc(sizeof(LinkNode)); if (head == NULL) return false; head->next = NULL; queue->front = head; queue->rear = head; return...

括号匹配基本思路括号匹配使用 栈 保存尚未匹配的左括号。扫描字符串时： 遇到左括号，入栈。 遇到右括号，检查栈顶左括号是否匹配。 匹配则弹出栈顶；不匹配则失败。 扫描结束后，栈为空才表示全部匹配。 失败情况括号匹配失败通常有三类： 扫描到右括号时栈空：右括号多了。 栈顶左括号与当前右括号类型不匹配：括号交叉或类型错误。 扫描结束后栈非空：左括号多了。 也可以记成三种错误：右括号单身、左右括号不匹配、左括号单身。 C 代码1234567891011121314151617181920212223bool IsMatchingPair(char left, char right) { return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' &&...

队列的定义与基本操作 定义队列是只允许在一端插入、在另一端删除的 线性表。 允许删除的一端称为队头。 允许插入的一端称为队尾。 没有元素的队列称为空队列。 队列的核心性质是先进先出：先进入队列的元素先离开队列，简称 FIFO。 基本操作 InitQueue(&Q)：初始化队列。 DestroyQueue(&Q)：销毁队列。 EnQueue(&Q, x)：入队。若队列未满，将 x 加入，使其成为新的队尾。 DeQueue(&Q, &x)：出队。若队列非空，删除队头元素，并用 x 返回。 GetHead(Q, &x)：读队头元素，但不删除。 QueueEmpty(Q)：判断队列是否为空。 队列与栈的区别栈 的插入和删除发生在同一端，后进先出。队列的插入和删除发生在两端，先进先出。 做题时不要只看“受限线性表”这个共同点，要看插入端和删除端是否相同。 常见实现队列可以用顺序存储或链式存储实现。顺序队列如果直接用数组并不断移动队头，会浪费前端空间；实际考查重点通常是 循环队列。链式存储实现见 链队列。

顺序栈定义顺序栈用一组连续存储单元存放栈中元素，本质上是用数组实现 栈。 常见约定：top 指向栈顶元素。 123456#define MaxSize 50typedef struct { ElemType data[MaxSize]; int top;} SqStack; 初始化时令 top = -1，表示栈中没有元素。 123void InitStack(SqStack *stack) { stack->top = -1;} 进栈 ↻ + − Push(&S, x) 的关键是先判断栈满，再移动 top，最后写入新元素： 123456bool Push(SqStack *stack, ElemType value) { if (stack->top == MaxSize - 1) return false; stack->top++; stack->data[stack->top] = value; return...

共享栈核心思想共享栈让两个 顺序栈 共享同一个数组。一个栈从数组低地址端向高地址端增长，另一个栈从高地址端向低地址端增长。 1234567#define MaxSize 100typedef struct { ElemType data[MaxSize]; int top0; int top1;} SharedStack; 初始化： 1234void InitSharedStack(SharedStack *stack) { stack->top0 = -1; stack->top1 = MaxSize;} 判满条件两个栈顶相邻时，数组中没有空位： 1stack->top0 + 1 == stack->top1 若省略结构体访问写法，判满条件也可记为 top0 + 1 == top1。 这是共享栈最重要的条件。 进栈12345678910111213bool Push0(SharedStack *stack, ElemType value) { if...

栈的定义与基本操作 定义栈是只允许在一端进行插入和删除操作的 线性表。允许操作的一端称为栈顶，另一端称为栈底。没有元素的栈称为空栈。 栈的核心性质是后进先出：后进入栈的元素先出栈，简称 LIFO。 基本操作 InitStack(&S)：初始化栈，构造空栈。 DestroyStack(&S)：销毁栈，释放占用空间。 Push(&S, x)：进栈。若栈未满，将 x 加入并成为新栈顶。 Pop(&S, &x)：出栈。若栈非空，删除栈顶元素，并用 x 返回。 GetTop(S, &x)：读栈顶。若栈非空，用 x 返回栈顶元素，但不删除。 StackEmpty(S)：判断栈是否为空。 栈顶访问栈的使用场景中通常只关心栈顶元素，不能直接访问栈底或中间元素。若题目允许任意位置访问，那就不是普通栈的操作模型。 Pop 和 GetTop 的区别很常考： Pop 会删除栈顶元素。 GetTop...

出栈序列与卡特兰数问题模型给定 n 个不同元素按固定顺序进栈，每个元素都必须进栈一次、出栈一次，问可能得到多少种合法出栈序列。这个数量就是第 n 个卡特兰数。 定义卡特兰数最核心的是它描述的一类结构：空结构算一种；任意非空结构都能唯一拆成“左边一个同类结构 + 右边一个同类结构”。 对一个含有 n 对 push-pop 的非空合法序列，最左边一定是一个 push。这个 push 会被后面某个唯一的 pop 匹配。若这一对 push/pop 内部包住了 i 对 push-pop，那么这一对结束后右侧就剩下 n - 1 - i 对 push-pop。 即 $$\text{push}\ (i\text{ pairs})\ \text{pop}\ (n-1-i\text{ pairs})$$ 也就是： 第一段 i 对 push-pop 是外层第一对 push/pop 里面包住的部分； 第二段 n - 1 - i 对 push-pop 是外层第一对结束后右侧剩下的部分； 两段都必须仍然是合法的同类序列。 即：一个规模为 n 的合法序列，被第一对匹配的 push/pop 切成一个规模为...

算法的基本概念定义算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。 程序可以理解为：数据结构 + 算法。数据结构负责把现实问题中的信息组织到计算机中，算法负责高效处理这些信息以解决问题。 算法必须具备的特性 有穷性：算法必须在执行有穷步后结束，且每一步都在有穷时间内完成。算法必须有穷，程序可以长期运行。 确定性：每条指令含义明确；相同输入只能得到相同输出。 可行性：算法中的操作都能通过已经实现的基本运算执行有限次完成。 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。 好算法追求的目标 正确性：能正确解决问题。 可读性：便于人理解、检查和维护。 健壮性：遇到非法输入时能适当处理，而不是产生无意义结果。 高效率与低存储量需求：时间复杂度和空间复杂度尽量低。 描述方式算法可以用自然语言、伪代码、程序代码、流程图等方式描述。关键不是形式，而是步骤必须无歧义，并能在有限步骤内完成。 关联评价算法时，先确认它满足算法的基本特性，再看正确性、可读性、健壮性、时间效率和空间需求。

循环链表 循环单链表循环单链表将表尾结点的 next 指针指向头结点，而不是 NULL。 带头结点循环单链表的空表通常满足： L->next == L 12345678910bool InitCLinkList(LinkList *L) { *L = (LNode *)malloc(sizeof(LNode)); if (*L == NULL) return false; (*L)->next = *L; return true;}bool Empty(LinkList L) { return L->next == L;} 特点：从任意结点出发，沿 next 指针可以回到起点并访问其他结点；从尾部到头部为 O(1)。 ↻ + − 尾指针的价值很多链表操作发生在头部或尾部。循环单链表中，若让 L 指向表尾结点，则： 找尾结点：O(1)。 找头结点：L->next，O(1)。 在表头或表尾插入更方便。 代价是插入、删除时要维护尾指针是否变化。 若 tail...