#线性表

#考点定位

• 所属大纲章节：线性表的定义和基本操作、顺序表与链表
• 常见题型：选择题（操作边界条件、移动次数计算、存储密度、各链表变体适用场景）；算法设计大题（几乎每年一道，链表/顺序表上的原地操作）
• 考查频率：高。选择题每年 1-2 道，算法大题高频命题区

工程直觉迁移：动态数组 vs linked list 的取舍你天天在做，工程上链表因缓存不友好已基本被弃用——但考试恰恰偏爱考链表（指针操作可控、能出设计题），必须按考纲把指针边界练到肌肉记忆。

#核心讲解：顺序表与链表的考点对比

#插入/删除移动次数计算（高频计算题）

设表长 $$，各位置等概率：

分步示例（插入 $$，$$，元素 $$）：

选择题变式："在等概率下，插入时平均移动多少个元素？"答 $$（不是 $$）；"删除时"答 $$（不是 $$）。这是最经典的计算陷阱。

#按位查找

• 顺序表：L.data[i-1]，$$。选择题坑：位序（1 起）与数组下标（0 起）的换算。
• 单链表：从头遍历，第 $$ 个结点需走 $$ 步，$$。按值查找两者都需 $$。

#链表变体的操作边界

#单链表

结构定义（考试作答时的标准写法）：

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

关键边界规则：

1. 带头结点 vs 不带头结点：头结点使"在第 1 位插入/删除"与中间位置逻辑统一，考试题默认带头结点，题目说不带头结点时要单独处理首元结点（这是高频陷阱）。
2. 插入的指针顺序：在 p 之后插入 s，必须先接后断： s->next = p->next; p->next = s;（顺序颠倒则丢失后半段）
3. 删除：p->next = p->next->next; 前需暂存被删结点 q = p->next; 以便 free(q)。
4. 头插法建表：读入序列 $$，得到链表次序为 $$（逆序）——选择题直接考；头插法也是"就地逆置"的原理。
5. 尾插法建表：需维护尾指针，结果保持原序。

#双链表

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

在 p 之后插入 s（四条语句，顺序必须保证不断链）：

s->next = p->next;        // 1
p->next->prior = s;       // 2  （若 p->next 为空则跳过）
s->prior = p;             // 3
p->next = s;              // 4

坑：p 是尾结点时 p->next 为 NULL，语句 2 不可执行——代码题里要么判空，要么题目保证非尾部。

#循环链表

经典选择题："在循环单链表中，设 rear 指针比设 head 指针的优势是？"——尾插/两表合并 $$：p = r->next; r->next = q->next->next; ... 合并两表不需遍历找尾。

#静态链表

用数组 + 游标（cur）模拟指针，适合不支持指针的语言。考点：插入删除不需移动元素，仍需修改游标，且没有改善按位查找的效率（仍 $$）；存储密度低于顺序表。

#408 算法题的类 C 伪代码规范（如何拿结构分）

408 算法大题（约 13-15 分）按步骤给分：思路（文字/流程说明）→ 类 C 伪代码 → 时间/空间复杂度分析。规范要点：

1. 语言：类 C 代码即可，不要求编译通过，但语法不能面目全非。变量先声明后使用；结点类型定义可直接引用题面已给结构。
2. 注释：关键行加简短注释，阅卷按"功能块"给分，注释帮助阅卷人定位你的意图。
3. 边界：空表、单元素、i 非法等边界判断写出来就是分。判空 if (L == NULL || L->next == NULL) return; 一行值 1-2 分。
4. 返回值：按题面要求返回（如找到返回 1 找不到返回 0），题目没要求时选一个并在说明里讲清楚。
5. 复杂度分析必写：最后一问通常明确"分析本算法的时间和空间复杂度"，不写直接丢分。
6. 禁止：直接调库函数假装完成（如直接 qsort）；引用未定义的魔法函数。所有辅助函数要么给出定义，要么用自然语言注明"其功能为 XX"。

#真题风格算法设计题

#题 1（2010 年 408 真题改编，结构同源）

题目：设将 $$ 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将 R 中保存的序列循环左移 $$ 个位置，即将 R 中的数据由 $$ 变换为 $$。要求：

1. 给出算法的基本设计思想；
2. 根据设计思想，采用类 C 语言描述；
3. 说明算法的时间复杂度和空间复杂度。

完整解答

思路：整体逆置三次。将数组视为两段 $$、$$，目标为 $$。利用 $$（$$ 表示逆置）：

1. 逆置前 $$ 个元素；
2. 逆置后 $$ 个元素；
3. 整体逆置。

分步演示（$$，$$，R = a b c d e，待动画化）：

伪代码：

// 将 R[left..right] 逆置（闭区间）
void Reverse(int R[], int left, int right) {
    int i = left, j = right, tmp;
    while (i < j) {              // 首尾对称交换
        tmp = R[i];
        R[i] = R[j];
        R[j] = tmp;
        i++;  j--;
    }
}

void LeftShift(int R[], int n, int p) {
    if (p <= 0 || p >= n) return;   // 边界：非法 p 直接返回
    Reverse(R, 0, p - 1);           // 逆置 A
    Reverse(R, p, n - 1);           // 逆置 B
    Reverse(R, 0, n - 1);           // 整体逆置
}

复杂度分析：三段逆置的交换次数分别为 $$、$$、$$，合计约 $$ 次交换，总时间 $$；只用 tmp 常数辅助单元，空间 $$。

评分要点对照：思路中写出"数学恒等式 $$"是满分思路分的关键；若用辅助数组 $$ 空间或逐个左移 $$ 时间，会因"未尽可能高效"扣思路分。

#题 2（2009 年 408 真题，链表经典）

题目：已知一个带有头结点的单链表，结点结构为 (data, next)，假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 $$ 个位置上的结点（$$ 为正整数）。若查找成功，输出该结点的 data 值并返回 1；否则返回 0。要求给出基本设计思想、类 C 描述、时间空间复杂度。

完整解答

思路：双指针（间隔指针）一次遍历。设 $$、$$ 均从头出发，先让 $$ 沿 next 走 $$ 步（到达正数第 $$ 个结点），随后 $$、$$ 同步后移；$$ 到达尾结点时，$$ 恰指向倒数第 $$ 个结点（$$ 与 $$ 相距恒为 $$）。

分步演示（链表 a→b→c→d→e，$$，待动画化）：

伪代码：

typedef struct LNode {          // 结点定义
    int data;
    struct LNode *next;
} LNode, *LinkList;

int FindKthFromEnd(LinkList list, int k) {
    LNode *p = list->next, *q = list->next;   // 均指向首元结点
    if (k <= 0) return 0;                     // 边界：k 非法
    while (k > 1 && q != NULL) {              // q 先走 k-1 步
        q = q->next;
        k--;
    }
    if (q == NULL) return 0;                  // 表长不足 k，查找失败
    while (q->next != NULL) {                 // 同步后移直到 q 为尾结点
        p = p->next;
        q = q->next;
    }
    printf("%d", p->data);
    return 1;
}

复杂度分析：时间 $$（一遍扫描）；空间 $$（两个指针）。

命题陷阱：若先遍历求表长 $$ 再走 $$ 步，同样是 $$，但需要两遍扫描，题面"尽可能高效"下双指针版是最优答法（一遍）。k > 表长 的失败分支必须显式处理，否则扣边界分。

#常见坑

1. 位序 vs 下标：题面"第 i 个元素"是 1 起位序，数组下标是 $$；自己设的游标变量在伪代码里要交代清楚从 0 还是从 1 开始。
2. 带头结点与否：题干画图带头结点但你的代码没写 L->next 取首元，属审题失误；反之亦然。
3. "链表插入删除 O(1)"的隐含前提：是在已定位的结点处操作；若包含查找定位过程，仍是 $$。选择题最爱挖这一点。
4. 存储密度：$$，链表因指针域小于 1；顺序表为 1。问"空间利用率"指同一概念。
5. 顺序表按值查找：无序表需 $$ 全表扫描，有序表提前终止也不能改进最坏 $$（二分要"可随机存取"前提，顺序表满足，但题面问"顺序表按值查找"默认线性扫描）。

#自测

1. 表长 $$ 的顺序表，等概率删除一个元素平均移动多少次？在末尾插入移动多少次？
2. 不带头结点的单链表 H，删除首元结点的语句序列是什么？与带头结点时的差别？
3. 双链表中在 p 之前插入 s 的语句（利用 prior 指针，4 条）？
4. 判断：循环单链表任何结点出发都能遍历全表，因此按位查找的平均时间比普通单链表低。（对/错）
5. 设计思路一句话：如何用单链表实现"时间上尽可能高效"的就地逆置（不申请新结点）？

答案与简析

1. 删除平均 $$ 次；末尾插入（第 $$ 位）移动 0 次。
2. 不带头结点：q = H; H = H->next; free(q);。带头结点：首元结点与中间结点统一为 q = L->next; L->next = q->next; free(q);。
3. s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s;（对称于"之后插入"）。
4. 错。遍历可达性不等于查找效率，仍需 $$，平均比较次数不降。
5. 头插法：依次取原表结点插到头结点之后，p=L->next; L->next=NULL; 后逐个头插，$$ 时间、$$ 空间。

下一步：学完本章 → 做 测验/01-线性表与栈队列-章节测 校验掌握度。