博客

顺序表（顺序存储结构）与 链表（单链表）

  • Post author:
  • Post category:其他


顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。


顺序表的建立：

使用顺序表存储数据，除了存储数据本身的值以外，通常还会记录以下两样数据：

  • 顺序表的最大存储容量：顺序表最多可以存储的数据个数；
  • 顺序表的长度：当前顺序表中存储的数据个数。

用C语言，定义一个结构体表示顺序表： 

typedef struct{
    int * head; //定义一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表的存储容量
}Table;

建立顺序表，如： 

#define Size 5 //对Size进行宏定义，表示顺序表的最大容量
void initTable(Table * t) {
    //构造一个空的顺序表，动态申请存储空间
    t->head = (int*)malloc(Size * sizeof(int));
    //如果申请失败，作出提示并直接退出程序
    if (!t->head)
    {
        printf("初始化失败");
        exit(0);
    }
    //空表的长度初始化为0
    t->length = 0;
    //空表的初始存储空间为Size
    t->size = Size;
}

如上所示，整个建立顺序表的过程都封装在一个函数中，建好的顺序表可以存储 5 个逻辑关系为“一对一”的整数。

通常情况下，malloc() 函数都可以成功申请内存空间，当申请失败时，示例程序中进行了“输出失败信息和强制程序退出”的操作，您可以根据实际需要修改代码。


顺序表的使用：

通过调用 initTable() 函数，就可以成功地创建一个顺序表，还可以往顺序表中存储一些元素。

例如，将 {1,2,3,4,5} 存储到顺序表中，实现代码如下： 

#include <stdio.h>
#include <stdlib.h>
#define Size 5 //对Size进行宏定义，表示顺序表的最大容量
typedef struct{
    int* head;
    int length;
    int size;
}Table;
void initTable(Table * t) {
    //构造一个空的顺序表，动态申请存储空间
    t->head = (int*)malloc(Size * sizeof(int));
    //如果申请失败，作出提示并直接退出程序
    if (!t->head)
    {
        printf("初始化失败");
        exit(0);
    }
    //空表的长度初始化为0
    t->length = 0;
    //空表的初始存储空间为Size
    t->size = Size;
}
//输出顺序表中元素的函数
void displayTable(Table t) {
    int i;
    for (i = 0; i < t.length; i++) {
        printf("%d ", t.head[i]);
    }
    printf("\n");
}
int main() {
    int i;
    Table t = { NULL,0,0 };
    initTable(&t);
    //向顺序表中添加{1,2,3,4,5}
    for (i = 1; i <= Size; i++) {
        t.head[i - 1] = i;
        t.length++;
    }
    printf("顺序表中存储的元素分别是：\n");
    displayTable(t);
    free(t.head);//释放申请的堆内存
    return 0;
}


顺序表元素的插入：

向已有顺序表中插入数据元素，根据插入位置的不同，可分为以下 3 种情况：

  1. 插入到顺序表的表头；
  2. 在表的中间位置插入元素；
  3. 尾随顺序表中已有元素，作为顺序表中的最后一个元素；

虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：

  • 将要插入位置元素以及后续的元素整体向后移动一个位置；
  • 将元素放到腾出来的位置上；

例如，在

{1,2,3,4,5}

的第 3 个位置上插入元素 6，实现过程如下：

  • 遍历至顺序表存储第 3 个数据元素的位置，如下图所示：

  • 将元素 3、4 和 5 整体向后移动一个位置，如图 所示

  • 将新元素 6 放入腾出的位置，如图所示：

因此，顺序表插入数据元素的 C 语言实现代码如下： 

//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
void insertTable(Table* t, int elem, int add)
{
    int i;
    //如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出
    if (add > t->length + 1 || add < 1) {
        printf("插入位置有问题\n");
        return;
    }
    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
    if (t->length == t->size) {
        t->head = (int*)realloc(t->head, (t->size + 1) * sizeof(int));
        if (!t->head) {
            printf("存储分配失败\n");
            return;
        }
        t->size += 1;
    }
    //插入操作，需要将自插入位置之后的所有元素全部后移一位
    for (i = t->length - 1; i >= add - 1; i--) {
        t->head[i + 1] = t->head[i];
    }
    //后移完成后，直接插入元素
    t->head[add - 1] = elem;
    t->length++;
}

注意，动态


数组


额外申请更多物理空间使用的是 realloc 函数。此外在实现元素整体后移的过程中，目标位置其实是有数据的，还是 3，只是下一步新插入元素时会把旧元素直接覆盖。


顺序表的删除元素：

从顺序表中删除指定元素，实现起来非常简单，只需找到目标元素，并将其后续所有元素整体前移 1 个位置即可。

后续元素整体前移一个位置，会直接将目标元素删除，可间接实现删除元素的目的。

例如，从

{1,2,3,4,5}

中删除元素 3 的过程如图所示：

因此，顺序表删除元素的 C 语言实现代码为： 

void delTable(Table* t, int add) {
    int i;
    if (add > t->length || add < 1) {
        printf("被删除元素的位置有误\n");
        return;
    }
    //删除操作
    for (i = add; i < t->length; i++) {
        t->head[i - 1] = t->head[i];
    }
    t->length--;
}


顺序表查找元素：

顺序表中查找目标元素，可以使用多种查找算法实现，比如说


二分查找


算法、插值查找算法等。

这里，我们选择


顺序查找


算法，具体实现代码为： 

//查找函数，其中，elem表示要查找的数据元素的值
int selectTable(table t,int elem){
    for (int i=0; i<t.length; i++) {
        if (t.head[i]==elem) {
            return i+1;
        }
    }
    return -1;//如果查找失败，返回-1
}

顺序表更改元素：

顺序表更改元素的实现过程是：

  1. 找到目标元素；
  2. 直接修改该元素的值；


顺序表更改元素的 C 语言实现代码为： 

void amendTable(Table* t, int elem, int newElem) {
    int add = selectTable(*t, elem);
    if (add == -1) {
        printf("顺序表中没有找到目标元素\n");
        return;
    }
    t->head[add - 1] = newElem;
}


li
 

#include <stdio.h>
#include <stdlib.h>
#define Size 5
typedef struct {
    int* head; //定义一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表的存储容量
}Table;
//创建顺序表
void initTable(Table* t) {
    //构造一个空的顺序表，动态申请存储空间
    t->head = (int*)malloc(Size * sizeof(int));
    //如果申请失败，作出提示并直接退出程序
    if (!t->head)
    {
        printf("初始化失败");
        exit(0);
    }
    //空表的长度初始化为0
    t->length = 0;
    //空表的初始存储空间为Size
    t->size = Size;
}
//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
void insertTable(Table* t, int elem, int add)
{
    int i;
    //如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出
    if (add > t->length + 1 || add < 1) {
        printf("插入位置有问题\n");
        return;
    }
    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
    if (t->length == t->size) {
        t->head = (int*)realloc(t->head, (t->size + 1) * sizeof(int));
        if (!t->head) {
            printf("存储分配失败\n");
            return;
        }
        t->size += 1;
    }
    //插入操作，需要将自插入位置之后的所有元素全部后移一位
    for (i = t->length - 1; i >= add - 1; i--) {
        t->head[i + 1] = t->head[i];
    }
    //后移完成后，直接插入元素
    t->head[add - 1] = elem;
    t->length++;
}
//删除函数
void delTable(Table* t, int add) {
    int i;
    if (add > t->length || add < 1) {
        printf("被删除元素的位置有误\n");
        return;
    }
    //删除操作
    for (i = add; i < t->length; i++) {
        t->head[i - 1] = t->head[i];
    }
    t->length--;
}
//查找函数
int selectTable(Table t, int elem) {
    int i;
    for (i = 0; i < t.length; i++) {
        if (t.head[i] == elem) {
            return i + 1;
        }
    }
    return -1;
}
//更改函数
void amendTable(Table* t, int elem, int newElem) {
    int add = selectTable(*t, elem);
    if (add == -1) {
        printf("顺序表中没有找到目标元素\n");
        return;
    }
    t->head[add - 1] = newElem;
}
//输出顺序表中的元素
void displayTable(Table t) {
    int i;
    for (i = 0; i < t.length; i++) {
        printf("%d ", t.head[i]);
    }
    printf("\n");
}
int main() {
    int i,add;
    Table t = { NULL,0,0 };
    initTable(&t);
    for (i = 1; i <= Size; i++) {
        t.head[i - 1] = i;
        t.length++;
    }
    printf("原顺序表：\n");
    displayTable(t);
    printf("删除元素1:\n");
    delTable(&t, 1);
    displayTable(t);
    printf("在第2的位置插入元素5:\n");
    insertTable(&t, 5, 2);
    displayTable(t);
    printf("查找元素3的位置:\n");
    add = selectTable(t, 3);
    printf("%d\n", add);
    printf("将元素3改为6:\n");
    amendTable(&t, 3, 6);
    displayTable(t);
    return 0;
}

链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。

与顺序表不同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。例如，使用链表存储 {1,2,3}，各个元素在内存中的存储状态可能是：

可以看到，数据不仅没有集中存放，在内存中的存储次序也是混乱的。那么，链表是如何存储数据间逻辑关系的呢？

链表存储数据间逻辑关系的实现方案是：为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素，如下图所示：

显然，我们只需要记住元素 1 的存储位置，通过它的指针就可以找到元素 2，通过元素 2 的指针就可以找到元素 3，以此类推，各个元素的先后次序一目了然。

像这样，数据元素随机存储在内存中，通过指针维系数据之间“一对一”的逻辑关系，这样的存储结构就是链表。


节点（结点）：

在链表中，每个数据元素都配有一个指针，这意味着，链表上的每个“元素”都长下图这个样子：

数据域用来存储元素的值，指针域用来存放指针。数据结构中，通常将图 3 这样的整体称为结点。

也就是说，链表中实际存放的是一个一个的结点，数据元素存放在各个结点的数据域中。举个简单的例子，图 2 中 {1,2,3} 的存储状态用链表表示，如下图所示：

在 C 语言中，可以用结构体表示链表中的结点，例如： 

typedef struct link{
    char elem; //代表数据域
    struct link * next; //代表指针域，指向直接后继元素
}Link;

我们习惯将结点中的指针命名为 next，因此指针域又常称为“Next 域”。


头结点、头指针和首元结点：

上图 所示的链表并不完整，一个完整的链表应该由以下几部分构成：

  1. 头指针：一个和结点类型相同的指针，它的特点是：永远指向链表中的第一个结点。上文提到过，我们需要记录链表中第一个元素的存储位置，就是用头指针实现。
  2. 结点：链表中的节点又细分为头结点、首元结点和其它结点：

    • 头结点：某些场景中，为了方便解决问题，会故意在链表的开头放置一个空结点，这样的结点就称为头结点。也就是说，头结点是位于链表开头、数据域为空（不利用）的结点。
    • 首元结点：指的是链表开头第一个存有数据的结点。
    • 其他节点：链表中其他的节点。


也就是说，一个完整的链表是由头指针和诸多个结点构成的。每个链表都必须有头指针，但头结点不是必须的。

例如，创建一个包含头结点的链表存储 {1,2,3}，如下图所示：

再次强调，头指针永远指向链表中的第一个结点。换句话说，如果链表中包含头结点，那么头指针指向的是头结点，反之头指针指向首元结点。


链表的创建：

创建一个链表，实现步骤如下：

  1. 定义一个头指针；
  2. 创建一个头结点或者首元结点，让头指针指向它；
  3. 每创建一个结点，都令其直接前驱结点的指针指向它。


例如，创建一个存储 {1,2,3,4} 且无头节点的链表，C 语言实现代码为： 

Link* initLink() {
    int i;
    //1、创建头指针
    Link* p = NULL;
    //2、创建首元结点
    Link* temp = (Link*)malloc(sizeof(Link));
    temp->elem = 1;
    temp->next = NULL;
    //头指针指向首元结点
    p = temp;
    //3、每创建一个结点，都令其直接前驱结点的指针指向它
    for (i = 2; 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;
}

再比如，创建一个存储 {1,2,3,4} 且含头节点的链表，则 C 语言实现代码为： 

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;
}


链表的使用
 

#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;
}
void display(Link* p) {
    Link* temp = p;//temp指针用来遍历链表
    //只要temp指向结点的next值不是NULL，就执行输出语句。
    while (temp) {
        Link* f = temp;//准备释放链表中的结点
        printf("%d ", temp->elem);
        temp = temp->next;
        free(f);
    }
    printf("\n");
}
int main() {
    Link* p = NULL;
    printf("初始化链表为：\n");
    //创建链表{1,2,3,4}
    p = initLink();
    //输出链表中的数据
    display(p);
    return 0;
}

程序中创建的是带头结点的链表，头结点的数据域存储的是元素 0，因此最终的输出结果为：

0 1 2 3 4

如果不想输出头结点的值，可以将 p->next 作为实参传递给 display() 函数。


如果程序中创建的是不带头结点的链表，最终的输出结果应该是：

1 2 3 4

首先，创建一个带头结点的链表，链表中存储着 {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 的结点，则此代码的执行效果如图 所示：

实现代码如下： 

//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 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