首页 > 编程笔记 > C++笔记 阅读：102

C++单链表的基本操作（图文并茂，附带实例）

链表是采用了链式存储方式的线性表，即逻辑上相邻的数据在计算机内的存储位置不一定相邻，则怎么表示逻辑上的相邻关系呢？

可以给每个元素都附加一个指针域，存储下一个节点的地址，即该指针指向下一个节点，如下图所示：


每个节点都包含两个域，分别是数据域和指针域：
若链表中的每个指针都指向下一个节点，都朝向一个方向，则这样的链表被称为“单向链表”或“单链表”。

单链表的节点结构体定义如下图所示：


在定义了节点结构体之后，就可以把若干节点连接在一起，形成一个单链表。


不管这个单链表有多长，只要找到它的头，就可以拉起整个单链表。因此若给这个单链表设置一个头指针，则这个单链表的每个节点就都可被找到了。


有时为了操作方便，还会给单链表增加一个不存储数据的头节点（也可以存储单链表的长度等信息）。给单链表加上头节点，就像给铁链子加上钥匙扣。


若想在顺序表中找到第 i 个元素，则可以立即通过 L.elem[i-1] 找到，想找哪个就找哪个，这叫作“随机存取”。但若想在单链表中找到第 i 个元素，则该怎么办？答案是必须从头开始，按顺序一个一个地找，一直找到第 i 个元素，这叫作“顺序存取”。

链表中插入新节点

在节点 i 之前插入元素 e，相当于在节点 i-1 之后插入元素 e。假设 p 指针指向节点 i-1，s 指针指向待插入的新节点，则插入操作如下图所示：



算法代码： 
bool ListInsert_L(LinkList &L, int i, int e) { // 在带头节点的单链表 L 中的第 i 个位置插入 e
    LinkList p = L, s;
    int j = 0;
    while (p && j < i - 1) { // 查找第 i-1 个节点，p 指向该节点
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) // i > n+1 或者 i < 1
        return false;
    s = new LNode;       // 生成新节点
    s->data = e;         // 将新节点的数据域置为 e
    s->next = p->next;    // 将新节点的指针域指向 a_i
    p->next = s;         // 将 p 的指针域指向 s
    return true;
}

链表中删除节点

删除一个节点，实际上就是跳过这个节点。根据单链表向后操作的特性，要想跳过节点 i，就必须先找到节点 i-1，否则是无法跳过的，如下图所示：


其中，“p->next=q->next”表示将 q 的下一个节点的地址赋值给 p 的指针域。

在有关指针的赋值语句中，等号右侧是节点的地址，等号左侧是节点的指针域，如下图所示：


在上图中，假设 q 下一个节点的地址为 1013，该地址被存储在 q->next 里面，因此等号右侧 q->next 的值为 1013。把该地址赋值给 p 的 next 指针域，把原来的值 2046 覆盖，这样，p->next 的值也为 1013，相当于跳过了 q。赋值之后如下图所示：


之后用 delete q 释放被删除节点占用的内存空间。

算法代码： 
bool ListDelete_L(LinkList &L, int i) { // 在带头节点的单链表 L 中删除节点 i
    LinkList p = L, q;
    int j = 0;
    while (p->next && j < i - 1) { // 查找节点 i-1，p 指向该节点
        p = p->next;
        j++;
    }
    if (!(p->next) || (j > i - 1)) // 当 i > n 或 i < 1 时，删除位置不合理
        return false;
    q = p->next;      // q 指向被删除节点
    p->next = q->next; // 改变被删除节点的前驱 p 的指针域
    delete q;         // 释放被删除节点 q 占用的内存空间
    return true;
}
在单链表中，每个节点除了存储自身数据，还存储下一个节点的地址，因此可以轻松访问下一个节点及其所有后继，但是不能再访问前面的节点了，因为在单链表中只能向后操作，不能向前操作。例如在删除 q 时，要先找到它的上一个节点 p，然后才能删掉 q。若需要向前操作，则该怎么办呢？可以借助另一种链表，叫做双向链表。

相关文章