线性表

2.1 线性表的定义

线性表是具有相同数据类型的 n（n ≥ 0）个数据元素的有限序列。记为 L = (a₁, a₂, ..., aₙ)，其中 a₁ 是第一个元素（表头），aₙ 是最后一个元素（表尾）。

特点：

元素个数有限。
元素具有相同数据类型。
元素具有逻辑上的顺序性，除首尾元素外每个元素有且仅有一个直接前驱和一个直接后继。

基本操作：

InitList(&L)：初始化线性表
ListInsert(&L, i, e)：在第 i 个位置插入元素 e
ListDelete(&L, i, &e)：删除第 i 个元素，返回被删元素
LocateElem(L, e)：查找元素 e，返回位置
GetElem(L, i)：获取第 i 个位置的元素
Length(L)：返回线性表长度
PrintList(L)：输出线性表
DestroyList(&L)：销毁线性表

💡 记忆技巧：线性表就像"排成一队的人"，每个人的位置是固定的，可以报数、插入、离队。

2.2 顺序表

顺序表是用顺序存储方式实现的线性表，即用连续的存储单元依次存储元素。

静态分配

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

长度固定，不可改变。如果数组满了，无法插入新元素。

动态分配

#define InitSize 100
typedef struct {
    ElemType *data;
    int maxSize;  // 最大容量
    int length;   // 当前长度
} SqList;

通过 malloc 和 realloc 动态分配空间，可在运行时扩充容量。

顺序表的基本操作

插入操作

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= MaxSize) return false;
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length++;
    return true;
}

时间复杂度：最好 O(1)（表尾插入），最坏 O(n)（表头插入），平均 O(n)。

删除操作

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i-1];
    for (int j = i; j < L.length; j++)
        L.data[j-1] = L.data[j];
    L.length--;
    return true;
}

时间复杂度：最好 O(1)（删除表尾），最坏 O(n)（删除表头），平均 O(n)。

按值查找

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e) return i + 1;
    return 0;
}

时间复杂度：最好 O(1)，最坏 O(n)，平均 O(n)。

📌 408考点提示：顺序表插入、删除时元素移动次数的计算是常考题型。平均移动次数 = n/2（插入）或 (n-1)/2（删除）。

2.3 链表

链表是用链式存储方式实现的线性表，通过指针将各结点连接。

单链表

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

头插法建立单链表

LinkList List_HeadInsert(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

头插法得到的链表顺序与输入顺序相反，常用于链表逆置。

尾插法建立单链表

LinkList List_TailInsert(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    LNode *r = L;  // 尾指针
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

尾插法得到的链表顺序与输入顺序一致，需要维护一个尾指针。

按序号查找

LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    LNode *p = L;
    int j = 0;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

插入操作（在第 i 个位置插入 e）

bool Insert(LinkList &L, int i, ElemType e) {
    LNode *p = GetElem(L, i-1);
    if (!p) return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

时间复杂度 O(n)（主要耗在查找上）。

删除操作（删除第 i 个结点）

bool Delete(LinkList &L, int i, ElemType &e) {
    LNode *p = GetElem(L, i-1);
    if (!p || !p->next) return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

时间复杂度 O(n)。

双链表

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

双链表既有前驱指针又有后继指针，可以双向遍历。

双链表的插入（在 p 之后插入 s）

s->next = p->next;
s->prior = p;
if (p->next) p->next->prior = s;
p->next = s;

双链表的删除（删除 p 的后继结点 q）

p->next = q->next;
if (q->next) q->next->prior = p;
free(q);

循环链表

循环单链表：最后一个结点的 next 指向头结点（或第一个结点）。判空条件：L->next == L。
循环双链表：头结点的 prior 指向尾结点，尾结点的 next 指向头结点。判空条件：L->next == L && L->prior == L。

静态链表

用数组实现的链表结构，通过"游标"（数组下标）代替指针：

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;  // 游标
} SLinkList[MaxSize];

静态链表适用于不支持指针的高级语言，如早期的 BASIC。

2.4 顺序表与链表的比较

比较维度	顺序表	链表
存取方式	随机存取（O(1)）	顺序存取（O(n)）
插入/删除	需移动大量元素，O(n)	只需修改指针，O(1)
存储密度	高（=1，无额外空间）	低（<1，需要存指针）
空间分配	静态分配或动态分配，可能造成浪费	动态分配，灵活
适用场景	频繁按位查找、对存储密度要求高	频繁插入删除、长度变化大

💡 记忆技巧："顺序表找得快，链表改得快"——这是选择时的根本原则。

2.5 408高频考点

链表逆置

将单链表就地逆置（头插法思路）：

LinkList Reverse(LinkList L) {
    LNode *p = L->next;
    LNode *q;
    L->next = NULL;
    while (p) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
    return L;
}

时间复杂度 O(n)，空间复杂度 O(1)。

链表合并

合并两个递增有序单链表为一个递减有序链表（头插法）：

LinkList Merge(LinkList &A, LinkList &B) {
    LNode *p = A->next, *q = B->next;
    LinkList C = A;
    C->next = NULL;
    free(B);
    while (p && q) {
        if (p->data <= q->data) {
            LNode *r = p->next;
            p->next = C->next;
            C->next = p;
            p = r;
        } else {
            LNode *r = q->next;
            q->next = C->next;
            C->next = q;
            q = r;
        }
    }
    while (p) {
        LNode *r = p->next;
        p->next = C->next;
        C->next = p;
        p = r;
    }
    while (q) {
        LNode *r = q->next;
        q->next = C->next;
        C->next = q;
        q = r;
    }
    return C;
}

找链表中间节点

使用快慢指针法（慢指针每次走一步，快指针每次走两步）：

LNode *FindMiddle(LinkList L) {
    LNode *slow = L->next, *fast = L->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  // slow 即为中间结点
}

⚠️ 易错点：

链表操作中容易丢失指针，修改指针时务必先保存后继结点地址。
头结点和头指针的区别：头结点是第一个结点之前的辅助结点，头指针指向链表的第一个结点（可以是头结点）。
顺序表插入删除时注意边界条件，i 的合法范围是 [1, length+1]（插入）和 [1, length]（删除）。

2.6 题型示例

例题1：已知长度为 n 的顺序表 L，编写算法删除所有值为 x 的元素。解：用 k 记录不等于 x 的元素个数（同时也是新表的下标位置），遍历一次即可。

void DeleteX(SqList &L, ElemType x) {
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}