2.3单链表

一、单链表的定义

1. 结点结构定义

typedef struct LNode {
    ElemType data;      // 数据域：存放数据元素
    struct LNode *next; // 指针域：指向下一个结点
} LNode, *LinkList;

• ​​LNode*​​：强调这是一个指向​​结点​​的指针。
• ​​LinkList​​：强调这是一个​​单链表​​（通常指向头结点或第一个结点）。

2. 两种类型

• ​​不带头结点​​：L指针直接指向第一个数据结点。

  // 初始化
  bool InitList(LinkList &L) {
      L = NULL; // 初始化为空表
      return true;
  }
  // 判空
  bool Empty(LinkList L) {
      return (L == NULL);
  }

• ​​带头结点​​：L指针指向一个不存数据的头结点，头结点的next指向第一个数据结点。

  // 初始化（带头结点）
  bool InitList(LinkList &L) {
      L = (LNode *)malloc(sizeof(LNode)); // 分配头结点
      if (L == NULL) return false;        // 内存不足，分配失败
      L->next = NULL;                     // 头结点之后暂时无结点
      return true;
  }
  // 判空
  bool Empty(LinkList L) {
      return (L->next == NULL);
  }

3. 选择带头结点的原因

• ​​代码统一性​​：无论是第一个结点还是其他结点，无论是空表还是非空表，操作逻辑一致，无需特殊处理。
• ​​简化操作​​：避免了对头指针L的直接修改，只需要修改头结点的next域。

​​📌 考试注意​​：一定要审清题目要求是​​带头结点​​还是​​不带头结点​​，两种情况的代码实现不同。

二、单链表的建立

1. 初始化操作

这是所有操作的第一步，必须先执行。

// 养成好习惯，初始化后立刻将头指针的next域置为NULL
L->next = NULL; // 带头结点
L = NULL;       // 不带头结点

2. 尾插法建立单链表

• ​​思路​​：始终保持一个尾指针r指向链表的最后一个结点，将新结点插入到r之后，并更新r。
• ​​优点​​：建立链表的元素顺序与输入顺序一致。
• ​​时间复杂度​​：O(n)

// 尾插法（带头结点）
LinkList List_TailInsert(LinkList &L) {
    InitList(L); // 初始化空表
    LNode *s, *r = L; // r为表尾指针，初始指向头结点
    ElemType x;
    scanf("%d", &x);
    while (x != 9999) { // 9999为结束标志
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; // 核心操作：尾指针的next指向新结点
        r = s;       // 核心操作：r指向新的表尾
        scanf("%d", &x);
    }
    r->next = NULL; // 尾结点next置空
    return L;
}

3. 头插法建立单链表

• ​​思路​​：每次将新结点插入到头结点​​之后​​。
• ​​优点​​：逻辑简单。​​重要应用：链表的逆置​​。
• ​​时间复杂度​​：O(n)

// 头插法（带头结点）
LinkList List_HeadInsert(LinkList &L) {
    InitList(L); // 初始化空表
    LNode *s;
    ElemType x;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next; // 新结点指向原第一个结点
        L->next = s;       // 头结点指向新结点
        scanf("%d", &x);
    }
    return L;
}

​​💡 链表的逆置​​：给定一个链表L，遍历其每个结点，用头插法依次插入到一个新链表中，即可完成逆置。

三、单链表的插入

1. 按位序插入（带头结点）

• ​​核心思想​​：找到第i-1个结点，对其执行​​后插操作​​。
• ​​时间复杂度​​：
  • 最好情况（插在表头）：O(1)
  • 最坏/平均情况：O(n)

// 在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) return false; // 位序i从1开始，小于1则非法

    LNode *p = GetElem(L, i-1); // 封装好的按位查找函数，找到第i-1个结点
    // 也可以用循环实现查找：
    // LNode *p = L; // p指向头结点（第0个）
    // int j = 0;
    // while (p != NULL && j < i-1) { // 循环找到第i-1个结点
    //     p = p->next;
    //     j++;
    // }

    if (p == NULL) return false; // i值非法，i-1超出链表长度

    return InsertNextNode(p, e); // 对p结点执行后插操作
}

2. 指定结点的后插操作

• ​​核心思想​​：申请新结点s，调整s和p的指针指向。
• ​​时间复杂度​​：O(1)
• ​​⚠️ 注意​​：s->next = p->next 和 p->next = s 的顺序​​不能颠倒​​！

// 后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e) {
    if (p == NULL) return false;

    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false; // 内存分配失败（如内存不足）
    s->data = e;    // 新结点保存数据e

    // 以下顺序不能颠倒！
    s->next = p->next; // 绿：新结点s指向p的后继
    p->next = s;      // 黄：p指向新结点s
    return true;
}

3. 指定结点的前插操作

• ​​问题​​：单链表无法直接获取前驱结点。
• ​​方法一（O(n)）​​：传入头指针，循环找到p的前驱结点q，再对q执行后插。
• ​​方法二（偷天换日，O(1)）​​：在p后插一个新结点s，交换p和s的数据域。

// 前插操作：在p结点之前插入元素e（O(1)版本）
bool InsertPriorNode(LNode *p, ElemType e) {
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;

    // 第一步：在p后插入s
    s->next = p->next;
    p->next = s;
    // 第二步：交换数据
    s->data = p->data; // 将p的元素复制到s
    p->data = e;       // 将新元素e覆盖p的元素
    return true;
}

4. 按位序插入（不带头结点）

• ​​特殊点​​：插入位置为​​第1个​​时，需要修改头指针L，操作与其他位置不同。

bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) return false;
    if (i == 1) { // 插入第一个结点，需特殊处理
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L; // 新结点指向原第一个结点
        L = s;       // 头指针指向新结点
        return true;
    }
    // i>1的情况，逻辑与带头结点相同...
    LNode *p;
    int j = 1; // 注意！此时p已指向第1个结点，j从1开始
    p = L;
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    // ... 后续操作相同
}

​​📌 考试注意​​：不带头结点的链表，插入/删除第1个元素时​​一定会修改头指针L​​。

四、单链表的删除

1. 按位序删除（带头结点）

• ​​核心思想​​：找到第i-1个结点p，令q = p->next（即要删除的结点），将p->next指向q->next，最后释放q。
• ​​时间复杂度​​：
  • 最好情况（删除表头）：O(1)
  • 最坏/平均情况：O(n)

bool ListDelete(LinkList &L, int i, ElemType &e) {
    if (i < 1) return false;
    LNode *p = GetElem(L, i-1); // 找到第i-1个结点p

    if (p == NULL || p->next == NULL) return false; // i值非法

    LNode *q = p->next; // q指向被删除结点
    e = q->data;        // 用e返回被删除元素的值
    p->next = q->next;  // 将*q结点从链中“断开”
    free(q);            // 释放结点的存储空间
    return true;
}

2. 指定结点的删除

• ​​问题​​：需要修改被删除结点p的​​前驱结点​​的next指针。
• ​​方法一（O(n)）​​：传入头指针，循环找到p的前驱结点。
• ​​方法二（偷天换日，O(1)）​​：将p的后继结点q的值赋给p，然后删除q。​​⚠️此方法有坑！​​

// 删除指定结点p（O(1)版本）
bool DeleteNode(LNode *p) {
    if (p == NULL) return false;
    LNode *q = p->next;      // 令q指向*p的后继结点

    if (q == NULL) {
        // ⚠️ 坑：如果p是最后一个结点，此法失效！
        // 只能从头开始遍历找到p的前驱，时间复杂度O(n)
        return false;
    }

    p->data = p->next->data; // 和后继结点交换数据域
    p->next = q->next;       // 将*q结点从链中“断开”
    free(q);
    return true;
}

​​📌 重要考点​​：​​删除指定结点（要求O(1)时间）时，如果结点是最后一个，无法用偷天换日法处理，必须特殊说明或改用O(n)的方法。​​

五、单链表的查找

1. 按位查找

• ​​功能​​：获取表L中第i个位置的结点的指针。
• ​​时间复杂度​​：O(n)

// 按位查找，返回第i个结点（带头结点）
LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;  // i=0返回头结点
    if (i == 0) return L;     // i=0返回头结点

    LNode *p = L; // p指向头结点
    int j = 0;    // 当前p指向的是第j个结点
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p; // 找到返回指针，否则返回NULL
}

2. 按值查找

• ​​功能​​：查找数据域等于e的结点。
• ​​时间复杂度​​：O(n)

// 按值查找，找到数据域==e的结点
LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next; // 从第1个数据结点开始查找
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p; // 找到后返回该结点指针，否则返回NULL
}

​​💡 注意​​：如果ElemType是结构类型（如struct），则不能直接用!=比较，需要逐个比较成员变量或重写比较函数。

3. 求表长

• ​​时间复杂度​​：O(n)

int Length(LinkList L) {
    int len = 0;
    LNode *p = L;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

六、总结与重要考点

📌 核心技巧与易错点

1. ​​封装思想​​：将后插操作(InsertNextNode)、按位查找(GetElem)等封装为基本操作，供其他函数（如ListInsert）调用，可以使代码更简洁、易维护、健壮性更强。
2. ​​边界处理​​：时刻注意处理i值非法、链表为空、内存分配失败、操作首尾结点等边界条件。
3. ​​带头结点的优势​​：​​强烈推荐使用带头结点的单链表​​，它能极大简化对第一个数据结点的操作逻辑，避免对头指针L的修改。
4. ​​指针操作顺序​​：在插入、删除时，调整指针指向的顺序至关重要，写代码和做题时务必留心。
5. ​​审题​​：做题时第一要务是判断题目要求的是​​带头结点​​还是​​不带头结点​​的单链表。

​