第 2 章　线性表（顺序表与链表）

(1) 错：端点例外——表头无前驱、表尾无后继，须说「除端点外」。(2) 错：表长随插入删除动态变化；顺序表静态分配时固定的是「容量」不是「长度」。

(3) 对：线性表既可顺序存储（顺序表）也可链式存储（链表）。(4) 错：链表每个结点要额外存指针（存储密度小于 1），存同样多元素并不省空间；它省的是「不需要一整块连续空间、容量可按需增长」（见 2.4 对比表）。

(1) 位序 1 即下标 0：\(2000\)；位序 7 即下标 6：\(2000+6\times4=2024\)。

(2) 下标 \(=(2040-2000)/4=10\)，位序 11。注意 2040 对应的是「第 11 个元素」，别答 10。

(3) 下标 5：\(2000+5\times8=2040\)。同一公式换 \(c\) 即可——单位换成 8 后「位序 6」与 (2) 中「位序 11」地址恰相同，说明地址由「下标 × 单元素大小」唯一决定。

(1) L->next == NULL；(2) L->next == L（头结点指向自己）；(3) L->next == L（此时必有 L->prior == L）；(4) L == NULL（头指针本身为空——不带头结点时头指针就是首元指针）。

辨析关键：先问「有没有头结点」，再问「循环到谁」。把 (1) 的答案用到 (2) 上是最高频的错误。

(1) 对：只改前后两个元素的游标（逻辑下一跳），元素物理位置不动。(2) 错：仍要顺游标逐个走，顺序存取。(3) 错：是「常用于 / 适合」不支持指针的语言，不是「必须」——支持指针的语言同样能实现。

对折交换（第 1 章例 7 已分析过同类问题）：

void Reverse(SqList *L) {
    for (int i = 0; i < L->length / 2; i++) {
        int t = L->data[i];
        L->data[i] = L->data[L->length - 1 - i];
        L->data[L->length - 1 - i] = t;
    }
}

\(n=5\) 时交换 \((0,4)\)、\((1,3)\) 两轮，中间 data[2] 不动 \(\lfloor 5/2\rfloor=2\) ✓。时间 \(O(n)\)，空间 \(O(1)\)——它也是自测 10（循环左移）的一个零件。

LNode *FindMid(LinkList L) {
    LNode *slow = L->next, *fast = L->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;          // 慢指针 1 步
        fast = fast->next->next;    // 快指针 2 步
    }
    return slow;
}

验证 \(n=5\)（1…5）：轮次后 (s2,f3)→(s3,f5)，f5 的 next 为 NULL 停 → 第 3 个 = 中点 ✓。\(n=6\)（1…6）：(s2,f3)→(s3,f5)→(s4,f=NULL) 停 → 第 4 个 = \(\lfloor 6/2\rfloor+1\)，即后半段起点 ✓。注意 fast != NULL 与 fast->next != NULL 的先后顺序——写反会在偶数表长时解引用 NULL。

B。\(n-i+1=8-3+1=6\)（\(a_3\cdots a_8\) 依次后移）✓。顺手验极端：位序 1 插入动 8 个、位序 9（表尾后）动 0 个，均与公式吻合。

C。A：链表只能从头顺序存取；B：「顺序表」的「顺序」指存储结构（物理相邻），它恰恰是随机存取的——名字与存取方式正好相反，是本考点的经典陷阱；D：存取方式由存储结构决定（对照 2.4 表：同为线性表，两实现存取方式不同）。

B。带头结点时头指针 t 永远指向头结点，判空看首元：t->next 为 NULL。A 是不带头结点时的判据；C 是带头结点循环单链表的判据；D 表示表中恰剩一个首元结点（非空）。

A（另有多个合法变体，如 ③①②④）。硬约束：①②都读取旧的 p->next（取后继、访问其 prior 域），必须发生在改写它的④之前；B 的错误在于④执行后②访问的是 s->prior 而非「原后继的 prior」，原后继结点的 prior 域没被改，反向遍历在 p→s 处断链；C 首句就毁掉后继地址，非法。口诀：凡「用旧值」的语句一律放在「改旧值」之前。

B。插入删除只改游标（下标），元素物理位置不动。A：仍要顺游标逐个找，不能随机存取；C：游标域占额外空间，存储密度低于顺序表；D：容量由数组大小固定，不能动态增长。

位序 10 ↔ 下标 9：\(1000+9\times6=1054\) ✓（自检：下标 0 存 1000，下标 9 是第 10 个 6 单位格，跨过 \(9\times6=54\) 个单元）。

插入 \(\frac{n}{2}=50.5\) 个；删除 \(\frac{n-1}{2}=50\) 个。代入小 \(n\) 复核：\(n=3\) 时插入按位序 \(1\sim4\) 的移动数为 \(3,2,1,0\)，均值 \(\frac{6}{4}=1.5=\frac{3}{2}\) ✓；删除按位序 \(1\sim3\) 的移动数为 \(2,1,0\)，均值 \(1=\frac{3-1}{2}\) ✓。

循环单链表：L->next == L；循环双链表：L->next == L（等价地 L->prior == L，空表时头结点前后指针都指回自己）。辨析口诀：单链表问「下一个是不是空」，循环链表问「下一个是不是自己」。

// 尾插归并：r 始终指向 C 的表尾，直接摘原结点接上

LinkList MergeList(LinkList A, LinkList B) {
    LinkList C = A;                          // 借用 A 的头结点
    LNode *p = A->next, *q = B->next, *r = C;
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) { r->next = p; r = p; p = p->next; }
        else                   { r->next = q; r = q; q = q->next; }
    }
    r->next = (p != NULL) ? p : q;           // 扫尾：接上剩余段
    free(B);                                 // B 的头结点不再需要
    return C;
}

每结点只接一次，\(O(m+n)\)、\(O(1)\)。与例 6 顺序表版对照：数组用下标 i/j/k，链表用指针 p/q/r，「比较—摘小—挂尾」三步完全同构；扫尾只需改一个指针（剩余段本来就连着）。易错点同样是忘扫尾。

思路（三次逆置，练习 5 是零件）：先把前 \(p\) 个逆置、再把后 \(n-p\) 个逆置、最后整体逆置。

// ab → (a^r b^r)，再整体逆置得 ba，即左移 p 位

void Reverse(int R[], int left, int right) {
    while (left < right) {
        int t = R[left]; R[left] = R[right]; R[right] = t;
        left++; right--;
    }
}

void LeftShift(int R[], int n, int p) {
    Reverse(R, 0, p - 1);      // 前段逆置
    Reverse(R, p, n - 1);      // 后段逆置
    Reverse(R, 0, n - 1);      // 整体逆置
}

数值验证（\(n=5\)，\(p=2\)，R=1 2 3 4 5）：① 逆置前 2 个 → 2 1 3 4 5；② 逆置后 3 个 → 2 1 5 4 3；③ 整体逆置 → 3 4 5 1 2，恰为左移 2 位 ✓（每个元素被交换 \(\le 2\) 次，总交换次数 \(\lfloor p/2\rfloor+\lfloor(n-p)/2\rfloor+\lfloor n/2\rfloor\lt\frac{3n}{2}\)，时间 \(O(n)\)、空间 \(O(1)\)）。

易错：三段逆置的区间端点（0..p−1 / p..n−1 / 0..n−1）；若要右移 \(p\) 位等价于左移 \(n-p\) 位，直接换参数即可。