广义表头尾链表存储结构_每日一课——「链表」链式存储结构和基础操作

链表，别名链式存储结构或单链表，用于存储逻辑关系为 "一对一" 的数据。

与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
例如，使用链表存储 {1,2,3}，数据的物理存储状态如图 1 所示：

我们看到，图 1 根本无法体现出各数据之间的逻辑关系。对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。如图 2 所示：

像图 2 这样，数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

链表的节点

从图 2 可以看到，链表中每个数据的存储都由以下两部分组成：

1. 数据元素本身，其所在的区域称为数据域；
2. 指向直接后继元素的指针，所在的区域称为指针域；

即链表中存储各数据元素的结构如图 3 所示：

图 3 所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，如图 4 所示：

因此，链表中每个节点的具体实现，需要使用 C 语言中的结构体，具体实现代码为：

link * initLink() {    int i;    link * p = NULL;//创建头指针    link * temp = (link*)malloc(sizeof(link));//创建首元节点    //首元节点先初始化    temp->elem = 1;    temp->next = NULL;    p = temp;//头指针指向首元节点    //从第二个节点开始创建    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=a也对        temp = temp->next;    }    //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表    return p;}

提示，由于指针域中的指针要指向的也是一个节点，因此要声明为 Link 类型(这里要写成 struct Link* 的形式)。

头节点，头指针和首元节点

其实，图 4 所示的链表结构并不完整。一个完整的链表需要由以下几部分构成：

1. 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
2. 节点：链表中的节点又细分为头节点、首元节点和其他节点：头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；首元节点：由于头节点(也就是空节点)的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；其他节点：链表中其他的节点；

因此，一个存储 {1,2,3} 的完整链表结构如图 5 所示：

注意：链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。

明白了链表的基本结构，下面我们来学习如何创建一个链表。

链表的创建(初始化)

创建一个链表需要做如下工作：

1. 声明一个头指针(如果有必要，可以声明一个头节点)；
2. 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；

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

link * initLink() {    int i;    link * p = NULL;//创建头指针    link * temp = (link*)malloc(sizeof(link));//创建首元节点    //首元节点先初始化    temp->elem = 1;    temp->next = NULL;    p = temp;//头指针指向首元节点    //从第二个节点开始创建    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=a也对        temp = temp->next;    }    //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表    return p;}

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

link * initLink(){    int i;    link * p=(link*)malloc(sizeof(link));//创建一个头结点    link * temp=p;//声明一个指针指向头结点，    //生成链表    for (i=1; i<5; i++) {        link *a=(link*)malloc(sizeof(link));        a->elem=i;        a->next=NULL;        temp->next=a;        temp=temp->next;    }    return p;}

我们只需在主函数中调用 initLink 函数，即可轻松创建一个存储 {1,2,3,4} 的链表，C 语言完整代码如下：

#include #include //链表中节点的结构typedef struct Link {    int  elem;    struct Link *next;}link;//初始化链表的函数link * initLink();//用于输出链表的函数void display(link *p);int main() {    link*p = NULL;    //初始化链表(1，2，3，4)    printf("初始化链表为：");    p = initLink();    display(p);    return 0;}link * initLink() {    int i;    link * p = NULL;//创建头指针    link * temp = (link*)malloc(sizeof(link));//创建首元节点    //首元节点先初始化    temp->elem = 1;    temp->next = NULL;    p = temp;//头指针指向首元节点    for (i = 2; i < 5; i++) {        link *a = (link*)malloc(sizeof(link));        a->elem = i;        a->next = NULL;        temp->next = a;        temp = temp->next;    }    return p;}void display(link *p) {    link* temp = p;//将temp指针重新指向头结点    //只要temp指针指向的结点的next不是Null，就执行输出语句。    while (temp) {        printf("%d ", temp->elem);        temp = temp->next;    }    printf("");}

程序运行结果为：

初始化链表为：1 2 3 4

注意，如果使用带有头节点创建链表的方式，则输出链表的 display 函数需要做适当地修改：

void display(link *p){    link* temp=p;//将temp指针重新指向头结点    //只要temp指针指向的结点的next不是Null，就执行输出语句。    while (temp->next) {        temp=temp->next;        printf("%d",temp->elem);    }    printf("");}

链表的一些基本操作

包括对链表中数据的添加、删除、查找(遍历)和更改。
注意，以下对链表的操作实现均建立在已创建好链表的基础上，创建链表的代码如下所示：

//声明节点结构typedef struct Link {    int  elem;//存储整形元素    struct Link *next;//指向直接后继元素的指针}link;//创建链表的函数link * initLink() {    link * p = (link*)malloc(sizeof(link));//创建一个头结点    link * temp = p;//声明一个指针指向头结点，用于遍历链表    int i = 0;    //生成链表    for (i = 1; i < 5; i++) {        //创建节点并初始化        link *a = (link*)malloc(sizeof(link));        a->elem = i;        a->next = NULL;        //建立新节点与直接前驱节点的逻辑关系        temp->next = a;        temp = temp->next;    }    return p;}

从实现代码中可以看到，该链表是一个具有头节点的链表。由于头节点本身不用于存储数据，因此在实现对链表中数据的"增删查改"时要引起注意。

链表插入元素

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

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

虽然新元素的插入位置不固定，但是链表插入元素的思想是固定的，只需做以下两步操作，即可将新元素插入到指定的位置：

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

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

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

注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，会导致插入位置后续的部分链表丢失，无法再实现步骤 1。

通过以上的讲解，我们可以尝试编写 C 语言代码来实现链表插入元素的操作：

//p为原链表，elem表示新数据元素，add表示新元素要插入的位置link * insertElem(link * p, int elem, int add) {    link * temp = p;//创建临时结点temp    link * c = NULL;    int i = 0;    //首先找到要插入位置的上一个结点    for (i = 1; i < add; i++) {        if (temp == NULL) {            printf("插入位置无效");            return p;        }        temp = temp->next;    }    //创建插入结点c    c = (link*)malloc(sizeof(link));    c->elem = elem;    //向链表中插入结点    c->next = temp->next;    temp->next = c;    return  p;}

提示，insertElem 函数中加入一个 if 语句，用于判断用户输入的插入位置是否有效。例如，在已存储 {1,2,3} 的链表中，用户要求在链表中第 100 个数据元素所在的位置插入新元素，显然用户操作无效，此时就会触发 if 语句。

链表删除元素

从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再利用的存储空间要及时释放。因此，从链表中删除数据元素需要进行以下 2 步操作：

1. 将结点从链表中摘下来;
2. 手动释放掉结点，回收被结点占用的存储空间;

其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点 temp，执行一行程序：

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

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

因此，链表删除元素的 C 语言实现如下所示：

//p为原链表，add为要删除元素的值link * delElem(link * p, int add) {    link * temp = p;    link * del = NULL;    int i = 0;    //temp指向被删除结点的上一个结点    for (i = 1; i < add; i++) {        temp = temp->next;    }    del = temp->next;//单独设置一个指针指向被删除结点，以防丢失    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域    free(del);//手动释放该结点，防止内存泄漏    return p;}

我们可以看到，从链表上摘下的节点 del 最终通过 free 函数进行了手动释放。

链表查找元素

在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL(比对失败的标志)。
因此，链表中查找特定数据元素的 C 语言实现代码为：

//p为原链表，elem表示被查找元素、int selectElem(link * p, int elem) {    //新建一个指针t，初始化为头指针 p    link * t = p;    int i = 1;    //由于头节点的存在，因此while中的判断为t->next    while (t->next) {        t = t->next;        if (t->elem == elem) {            return i;        }        i++;    }    //程序执行至此处，表示查找失败    return -1;}

注意，遍历有头节点的链表时，需避免头节点对测试数据的影响，因此在遍历链表时，建立使用上面代码中的遍历方法，直接越过头节点对链表进行有效遍历。

链表更新元素

更新链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。
直接给出链表中更新数据元素的 C 语言实现代码：

//更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值link *amendElem(link * p, int add, int newElem) {    int i = 0;    link * temp = p;    temp = temp->next;//在遍历之前，temp指向首元结点    //遍历到被删除结点    for (i = 1; i < add; i++) {        temp = temp->next;    }    temp->elem = newElem;    return p;}

总结

以上内容详细介绍了对链表中数据元素做"增删查改"的实现过程及 C 语言代码，在此给出本节的完整可运行代码：

#include #include typedef struct Link {    int  elem;    struct Link *next;}link;link * initLink();//链表插入的函数，p是链表，elem是插入的结点的数据域，add是插入的位置link * insertElem(link * p, int elem, int add);//删除结点的函数，p代表操作链表，add代表删除节点的位置link * delElem(link * p, int add);//查找结点的函数，elem为目标结点的数据域的值int selectElem(link * p, int elem);//更新结点的函数，newElem为新的数据域的值link *amendElem(link * p, int add, int newElem);void display(link *p);int main() {    link *p = NULL;    int address;    //初始化链表(1，2，3，4)    printf("初始化链表为：");    p = initLink();    display(p);    printf("在第4的位置插入元素5：");    p = insertElem(p, 5, 4);    display(p);    printf("删除元素3:");    p = delElem(p, 3);    display(p);    printf("查找元素2的位置为：");    address = selectElem(p, 2);    if (address == -1) {        printf("没有该元素");    }    else {        printf("元素2的位置为：%d", address);    }    printf("更改第3的位置上的数据为7:");    p = amendElem(p, 3, 7);    display(p);    return 0;}link * initLink() {    link * p = (link*)malloc(sizeof(link));//创建一个头结点    link * temp = p;//声明一个指针指向头结点，用于遍历链表    int i = 0;    //生成链表    for (i = 1; i < 5; i++) {        link *a = (link*)malloc(sizeof(link));        a->elem = i;        a->next = NULL;        temp->next = a;        temp = temp->next;    }    return p;}link * insertElem(link * p, int elem, int add) {    link * temp = p;//创建临时结点temp    link * c = NULL;    int i = 0;    //首先找到要插入位置的上一个结点    for (i = 1; i < add; i++) {        if (temp == NULL) {            printf("插入位置无效");            return p;        }        temp = temp->next;    }    //创建插入结点c    c = (link*)malloc(sizeof(link));    c->elem = elem;    //向链表中插入结点    c->next = temp->next;    temp->next = c;    return  p;}link * delElem(link * p, int add) {    link * temp = p;    link * del = NULL;    int i = 0;    //遍历到被删除结点的上一个结点    for (i = 1; i < add; i++) {        temp = temp->next;    }    del = temp->next;//单独设置一个指针指向被删除结点，以防丢失    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域    free(del);//手动释放该结点，防止内存泄漏    return p;}int selectElem(link * p, int elem) {    link * t = p;    int i = 1;    while (t->next) {        t = t->next;        if (t->elem == elem) {            return i;        }        i++;    }    return -1;}link *amendElem(link * p, int add, int newElem) {    int i = 0;    link * temp = p;    temp = temp->next;//tamp指向首元结点    //temp指向被删除结点    for (i = 1; i < add; i++) {        temp = temp->next;    }    temp->elem = newElem;    return p;}void display(link *p) {    link* temp = p;//将temp指针重新指向头结点    //只要temp指针指向的结点的next不是Null，就执行输出语句。    while (temp->next) {        temp = temp->next;        printf("%d ", temp->elem);    }    printf("");}

代码运行结果：

初始化链表为：1 2 3 4在第4的位置插入元素5：1 2 3 5 4删除元素3:1 2 5 4查找元素2的位置为：元素2的位置为：2更改第3的位置上的数据为7:1 2 7 4

想学习C/C++的朋友，如果你没有思绪，不知道如何着手学习，欢迎点击下方了解更多，我会给你最使用的建议，免费的哦~