作者：解学武

学会创建链表之后，本节继续讲解链表的一些基本操作，包括向链表中添加数据、删除链表中的数据、查找和更改链表中的数据。

首先，创建一个带头结点的链表，链表中存储着 {1,2,3,4}：

//链表中节点的结构
typedef struct link {
    int  elem;
    struct link* next;
}Link;
Link* initLink() {
    int i;
    //1、创建头指针
    Link* p = NULL;
    //2、创建头结点
    Link* temp = (Link*)malloc(sizeof(Link));
    temp->elem = 0;
    temp->next = NULL;
    //头指针指向头结点
    p = temp;
    //3、每创建一个结点，都令其直接前驱结点的指针指向它
    for (i = 1; i < 5; i++) {
        //创建一个结点
        Link* a = (Link*)malloc(sizeof(Link));
        a->elem = i;
        a->next = NULL;
        //每次 temp 指向的结点就是 a 的直接前驱结点
        temp->next = a;
        //temp指向下一个结点（也就是a),为下次添加结点做准备
        temp = temp->next;
    }
    return p;
}

链表插入元素

同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：

• 插入到链表的头部，作为首元节点；
• 插入到链表中间的某个位置；
• 插入到链表的最末端，作为链表中最后一个结点；

对于有头结点的链表，3 种插入元素的实现思想是相同的，具体步骤是：

1. 将新结点的 next 指针指向插入位置后的结点；
2. 将插入位置前结点的 next 指针指向插入结点；

例如，在链表 {1,2,3,4} 的基础上分别实现在头部、中间、尾部插入新元素 5，其实现过程如图 1 所示：


从图中可以看出，虽然新元素的插入位置不同，但实现插入操作的方法是一致的，都是先执行步骤 1 ，再执行步骤 2。实现代码如下：

void insertElem(Link* p, int elem, int add) {
    int i;
    Link* c = NULL;
    Link* temp = p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (i = 1; i < add; i++) {
        temp = temp->next;
        if (temp == NULL) {
            printf("插入位置无效\n");
            return;
        }
    }
    //创建插入结点c
    c = (Link*)malloc(sizeof(Link));
    c->elem = elem;
    //① 将新结点的 next 指针指向插入位置后的结点
    c->next = temp->next;
    //② 将插入位置前结点的 next 指针指向插入结点；
    temp->next = c;
}

注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤 1。

对于没有头结点的链表，在头部插入结点比较特殊，需要单独实现。


和 2)、3) 种情况相比，由于链表没有头结点，在头部插入新结点，此结点之前没有任何结点，实现的步骤如下：

1. 将新结点的指针指向首元结点；
2. 将头指针指向新结点。

实现代码如下：

Link* insertElem(Link* p, int elem, int add) {
    if (add == 1) {
        //创建插入结点c
        Link* c = (Link*)malloc(sizeof(Link));
        c->elem = elem;
        c->next = p;
        p = c;
        return p;
    }
    else {
        int i;
        Link* c = NULL;
        Link* temp = p;//创建临时结点temp
        //首先找到要插入位置的上一个结点
        for (i = 1; i < add-1; i++) {
            temp = temp->next;
            if (temp == NULL) {
                printf("插入位置无效\n");
                return p;
            }
        }
        //创建插入结点c
        c = (Link*)malloc(sizeof(Link));
        c->elem = elem;
        //向链表中插入结点
        c->next = temp->next;
        temp->next = c;
        return p;
    }
}

注意当 add==1 成立时，形参指针 p 的值会发生变化，因此需要它的新值作为函数的返回值返回。

链表删除元素

从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除。

对于有头结点的链表来说，无论删除头部（首元结点）、中部、尾部的结点，实现方式都一样，执行以下三步操作：

1. 找到目标元素所在结点的直接前驱结点；
2. 将目标结点从链表中摘下来;
3. 手动释放结点占用的内存空间；

从链表上摘除目标节点，只需找到该节点的直接前驱节点 temp，执行如下操作：

temp->next=temp->next->next;

例如，从存有 {1,2,3,4} 的链表中删除存储元素 3 的结点，则此代码的执行效果如图 3 所示：


实现代码如下：

//p为原链表，elem 为要删除的目标元素
int delElem(Link* p, int elem) {
    Link* del = NULL, *temp = p;
    int find = 0;
    //1、找到目标元素的直接前驱结点
    while (temp->next) {
        if (temp->next->elem == elem) {
            find = 1;
            break;
        }
        temp = temp->next;
    }
    if (find == 0) {
        return -1;//删除失败
    }
    else
    {
        //标记要删除的结点
        del = temp->next;
        //2、将目标结点从链表上摘除
        temp->next = temp->next->next;
        //3、释放目标结点
        free(del);
        return 1;
    }
}

对于不带头结点的链表，需要单独考虑删除首元结点的情况，删除其它结点的方式和图 3 完全相同，如下图所示：


实现代码如下：

//p为原链表，elem 为要删除的目标元素
int delElem(Link** p, int elem) {
    Link* del = NULL, *temp = *p;
    //删除首元结点需要单独考虑
    if (temp->elem == elem) {
        (*p) = (*p)->next;
        free(temp);
        return 1;
    }
    else
    {
        int find = 0;
        //1、找到目标元素的直接前驱结点
        while (temp->next) {
            if (temp->next->elem == elem) {
                find = 1;
                break;
            }
            temp = temp->next;
        }
        if (find == 0) {
            return -1;//删除失败
        }
        else
        {
            //标记要删除的结点
            del = temp->next;
            //2、将目标结点从链表上摘除
            temp->next = temp->next->next;
            //3、释放目标结点
            free(del);
            return 1;
        }
    }
}

函数返回 1 时，表示删除成功；返回 -1，表示删除失败。注意，该函数的形参 p 为二级指针，调用时需要传递链表头指针的地址。

链表查找元素

在链表中查找指定数据元素，最常用的方法是：从首元结点开始依次遍历所有节点，直至找到存储目标元素的结点。如果遍历至最后一个结点仍未找到，表明链表中没有存储该元素。

因此，链表中查找特定数据元素的 C 语言实现代码为：

//p为原链表，elem表示被查找元素
int selectElem(Link* p, int elem) {
    int i = 1;
    //带头结点，p 指向首元结点
    p = p->next;
    while (p) {
        if (p->elem == elem) {
            return i;
        }
        p = p->next;
        i++;
    }
    return -1;//返回-1，表示未找到
}

注意第 5 行代码，对于有结点的链表，需要先将 p 指针指向首元结点；反之，对于不带头结点的链表，注释掉第 5 行代码即可。

链表更新元素

更新链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。

直接给出链表中更新数据元素的 C 语言实现代码：

//p 为有头结点的链表，oldElem 为旧元素，newElem 为新元素
int amendElem(Link* p, int oldElem, int newElem) {
    p = p->next;
    while (p) {
        if (p->elem == oldElem) {
            p->elem = newElem;
            return 1;
        }
        p = p->next;
    }
    return -1;
}

函数返回 1，表示更改成功；返回数字 -1，表示更改失败。如果是没有头结点的链表，直接删除第 3 行代码即可。

总结

以上内容详细介绍了对链表中数据元素做"增删查改"的实现过程及 C 语言代码，最后给大家一段完整的代码，实现对有头结点链表的“增删查改”：

#include <stdio.h>
#include <stdlib.h>
//链表中节点的结构
typedef struct link {
    int  elem;
    struct link* next;
}Link;
Link* initLink() {
    int i;
    //1、创建头指针
    Link* p = NULL;
    //2、创建头结点
    Link* temp = (Link*)malloc(sizeof(Link));
    temp->elem = 0;
    temp->next = NULL;
    //头指针指向头结点
    p = temp;
    //3、每创建一个结点，都令其直接前驱结点的指针指向它
    for (i = 1; i < 5; i++) {
        //创建一个结点
        Link* a = (Link*)malloc(sizeof(Link));
        a->elem = i;
        a->next = NULL;
        //每次 temp 指向的结点就是 a 的直接前驱结点
        temp->next = a;
        //temp指向下一个结点（也就是a),为下次添加结点做准备
        temp = temp->next;
    }
    return p;
}
//p为链表，elem为目标元素，add为要插入的位置
void insertElem(Link* p, int elem, int add) {
    int i;
    Link* c = NULL;
    Link* temp = p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (i = 1; i < add; i++) {
        temp = temp->next;
        if (temp == NULL) {
            printf("插入位置无效\n");
            return;
        }
    }
    //创建插入结点c
    c = (Link*)malloc(sizeof(Link));
    c->elem = elem;
    //① 将新结点的 next 指针指向插入位置后的结点
    c->next = temp->next;
    //② 将插入位置前结点的 next 指针指向插入结点；
    temp->next = c;
}
//p为原链表，elem 为要删除的目标元素
int delElem(Link* p, int elem) {
    Link* del = NULL, *temp = p;
    int find = 0;
    //1、找到目标元素的直接前驱结点
    while (temp->next) {
        if (temp->next->elem == elem) {
            find = 1;
            break;
        }
        temp = temp->next;
    }
    if (find == 0) {
        return -1;//删除失败
    }
    else
    {
        //标记要删除的结点
        del = temp->next;
        //2、将目标结点从链表上摘除
        temp->next = temp->next->next;
        //3、释放目标结点
        free(del);
        return 1;
    }
}
//p为原链表，elem表示被查找元素
int selectElem(Link* p, int elem) {
    int i = 1;
    //带头结点，p 指向首元结点
    p = p->next;
    while (p) {
        if (p->elem == elem) {
            return i;
        }
        p = p->next;
        i++;
    }
    return -1;//返回-1，表示未找到
}
//p 为有头结点的链表，oldElem 为旧元素，newElem 为新元素
int amendElem(Link* p, int oldElem, int newElem) {
    p = p->next;
    while (p) {
        if (p->elem == oldElem) {
            p->elem = newElem;
            return 1;
        }
        p = p->next;
    }
    return -1;
}
//输出链表中各个结点的元素
void display(Link* p) {
    p = p->next;
    while (p) {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
//释放链表
void Link_free(Link* p) {
    Link* fr = NULL;
    while (p->next)
    {
        fr = p->next;
        p->next = p->next->next;
        free(fr);
    }
    free(p);
}
int main() {
    Link* p = initLink();
    printf("初始化链表为：\n");
    display(p);
    printf("在第 3 的位置上添加元素 6：\n");
    insertElem(p, 6, 3);
    display(p);
    printf("删除元素4：\n");
    delElem(p, 4);
    display(p);
    printf("查找元素 2：\n");
    printf("元素 2 的位置为：%d\n", selectElem(p, 2));
    printf("更改元素 1 的值为 6：\n");
    amendElem(p, 1, 6);
    display(p);
    Link_free(p);
    return 0;
}

执行结果为：

初始化链表为：
1 2 3 4
在第 3 的位置上添加元素 6：
1 2 6 3 4
删除元素4：
1 2 6 3
查找元素 2：
元素 2 的位置为：2
更改元素 1 的值为 6：
6 2 6 3