数据结构 - 链表 (单链表, 循环链表)

Akari2024-02-282024-03-01

懒猫老师-C语言-链表(PPT文稿) - 知乎
 懒猫老师-C语言-链表（单链表，循环链表）_哔哩哔哩_bilibili
单链表——之二 | Akari的小站
 单链表 | Akari的小站

1 链表的概念

引例1 建立学生信息表

假设需要建立一个学生信息表, 学生人数无法估计, 而且学生人数经常变化应该如何实现?

顺序表 → 静态存储分配 → 事先确定容量

链表 → 动态存储分配 → 运行时分配空间

单链表: 线性表的链接存储结构.
存储思想: 用一组任意的存储单元存放线性表的元素.

任意: 1. 不连续; 2. 零散分布

单链表的节点结构:

typedef struct node{
    DataType data;      // 数据域
    struct node *next;  // 指针域
}Node, *Link;

申请一个结点:

p = (Link)malloc(sizeof(Node));

头指针: 指向第一个结点的地址.
尾标志: 终端结点的指针域为空.
头结点: 在单链表的第一个元素结点之前附设一个类型相同的结点, 以便空表和非空表的处理统一. 如图:

2 单链表的实现

2.1 单链表的遍历操作

操作接口: void displayNode(Link head);

void displayNode(Link head){
    p = head->next;
    while (p != Null){
        printf("%d", p->data);
        p = p->next;
    }
}

2.2 求单链表的元素个数

操作接口: int length(Link head);

int length(Link head){
    p = head->next;
    count = 0;
    while (p != NULL){
        p = p->next;
        count++;
    }
    return count;   // 注意 count 的初始化和返回值之间的关系
}

2.3 单链表的查找操作

操作接口: int queryNode(Link head, DataType x);

int queryNode(Link head, DataType x){
    p = head->next;
    while (p != NULL){
        if (p->data = x){
            printf(data);   // 找到则调用输出函数, 并提前返回 true
            return true;
        }
        p = p->next;
    }

    return false;   // 如果循环结束了, 说明没有找到
}

2.4 单链表的插入操作

操作接口: bool insertNode(Link head, int i, DataType x);

bool insertNode(Link head, int i, DataType x){
    p = head;       // 工作指针 p 指向头结点
    count = 0;
    while (p != NULL && count < i - 1){     // 查找第 i - 1 个结点
        p = p->next;
        count++;
    }

    if (p == NULL)
        return false;   // 没有找到第 i - 1 个结点
    else {
        node = (Link)malloc(sizeof(Node));  // 申请一个结点 node
        node-data = x;
        node->next = p->next;   // 结点 node 插入结点 p 之后
        p->next = node;

        return true;
    }
}

2.5 创建一个单链表 - 头插法

操作接口: Link newList(Datatype a[], int n);
头插法: 将待插入结点插在头结点的后面.

数组 a = {35, 12, 24, 33, 42}

template <class DataType>
Link newList(DataType a[], int n){
    head = (Link)malloc(sizeof(Node));      // 创建头结点
    head->next = NULL;

    for (int i = 0; i < n; i ++ ){          // 创建后续结点
        node = (Link)malloc(sizeof(Node));
        node->data = a[i];
        node->next = head->next;
        head->next = node;
    }

    return head;
}

2.6 创建一个单链表 - 尾插法

操作接口: Link newList(Datatype a[], int n);
尾插法: 将待插入结点插在终端结点的后面.

数组 a = {35, 12, 24, 33, 42};

Link newList(DataType a[], int n){
    head = (Link)malloc(sizeof(Node));
    head->next = NULL;      // 保持良好习惯: 新生成结点指针域赋空
    read = head;

    for (int i = 0; i < n; i ++ ){
        node = (Link)malloc(sizeof(Node));
        node->data = a[i];
        rear->next = node;
        rear = node;
    }

    rear->next = NULL;
    return head;
}

2.7 单链表结点的删除

操作接口: bool deleteNode(Link head, DataType x);
如何删除 p 所指向的结点?
查找结点过程中, 如何保证 p, q 指针一前一后?
空表的状态是怎样的?
伪代码:

bool deleteNode(Link head, DataType x){
    if (head == NULL && head->next == NULL)     // 若链表没有数据
        return false;
    
    p = head->next;     // 初始化. p, q, 两个指针一前一后
    q = head;
    while (p != NULL){
        if (p->data == x){
            q->next = p->next;      // 找到  x 结点, 删除这个结点, 并提前返回
            free(p);
            return true;
        } else {        // p 的 data 域不等于 x , 则继续向后找
            q = p;
            p = p->next;
        }
    }

    return false;      // 如果循环结束了, 说明没有找到和 x 相等的结点
}

2.8 单链表的释放

操作接口: void clearLink(Link head);
将单链表中所有结点的存储空间释放.

3 循环链表的实现

从单链表中某结点 p 出发如何找到其前驱?
将单链表的首尾相接, 将终端结点的指针域由空指针改为指向头结点, 构成单循环链表, 简称循环链表.
空表和非空表的处理?
循环链表的插入
循环链表的特点
循环链表中没有明显的尾端 → 如何避免死循环?
循环条件:

p != NULL → p != head
p->next != NULL → p->next != head

4 双向链表

如何求结点 p 的直接前驱, 时间性能?
如何快速求得结点 p 的前驱?
双向链表: 在单链表的每个结点中再设置一个指向其前驱节点的指针域.
结点结构: