什么是单个链表，链存储结构的详细说明

序列表已在前面详细介绍. 在本节中，我们介绍另一种线性存储结构链接列表.

链表，别名链存储结构或单个链表用于存储逻辑关系为“”的数据. 与序列列表不同，链接列表不限制数据的物理存储状态. 换句话说，使用链表存储的数据元素的物理存储位置是随机的.

例如，使用链接列表存储{1,2,3}，数据的物理存储状态如图1所示:

图1链表随机存储数据

我们看到图1根本不能反映各种数据之间的逻辑关系. 在这方面，链表的解决方案是每个数据元素在存储期间都配备有一个指针，该指针用于指向其自己的直接后继元素. 如图2所示:

图2每个数据元素都配备了一个指针

如图2所示单链表，其中数据元素随机存储并且数据之间的逻辑关系由指针表示的存储结构是链存储结构.

从图2可以看到链表的节点. 链表中每个数据的存储由以下两部分组成: 数据元素本身，其所在区域称为数据字段；指向直接后继元素的指针，称为指针字段的区域；

也就是说，将每个数据元素存储在链表中的结构如图3所示:

图3节点结构

图3中所示的结构在链接列表中称为节点. 换句话说，链表实际上一个接一个地存储节点，并且实际的数据元素包含在这些节点中，如图4所示:

图4链接列表中的节点

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

typedef struct Link{
    char elem; //代表数据域
    struct Link * next; //代表指针域，指向直接后继元素
}link; //link为节点名，每个节点都是一个 link 结构体

提示，由于指针字段中的指针也指向节点，因此必须将其声明为链接类型（此处必须以struct Link *形式编写）.

头节点，头指针和头节点. 实际上，图4中所示的链表结构是不完整的. 完整的链表需要由以下部分组成: 头指针: 普通指针，其特征在于始终指向链表的第一个节点的位置. 显然，头指针是用来指示链表的位置的，方便以后查找链表和使用链表中的数据. 节点: 将链表中的节点分为头节点，领导者节点和其他节点:

因此，图5中显示了存储{1,2,3}的完整链表结构:

图5完整链表的

注: 当链表中有头节点时，头指针指向头节点；否则，如果链接列表中没有头节点，则头指针指向头节点.

了解链表的基本结构，让我们学习如何创建链表.

创建链表（初始化）要创建链表，您需要执行以下操作: 声明头指针（如果需要，可以声明头节点）；创建多个存储数据的节点. 前体节点建立逻辑关系；

例如，要创建具有{1,2,3,4}和无头节点的链表，C语言实现代码如下:

link * initLink(){
    link * p=NULL;//创建头指针
    link * temp = (link*)malloc(sizeof(link));//创建首元节点
    //首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;
    p = temp;//头指针指向首元节点
    //从第二个节点开始创建
    for (int 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(){
    link * p=(link*)malloc(sizeof(link));//创建一个头结点
    link * temp=p;//声明一个指针指向头结点，
    //生成链表
    for (int 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 <stdio.h>
#include <stdlib.h>
//链表中节点的结构
typedef struct Link{
    int  elem;
    struct Link *next;
}link;
//初始化链表的函数
link * initLink();
//用于输出链表的函数
void display(link *p);
int main() {
    //初始化链表（1，2，3，4）
    printf("初始化链表为：\n");
    link *p=initLink();
    display(p);
    return 0;
}
link * initLink(){
    link * p=NULL;//创建头指针
    link * temp = (link*)malloc(sizeof(link));//创建首元节点
    //首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;
    p = temp;//头指针指向首元节点
    for (int 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("\n");
}

程序的运行结果为:

初始链接列表为:

1 2 3 4

请注意，如果使用头节点创建链接列表单链表，则需要适当修改输出链接列表的显示功能:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-279049-1.html