C语言 链表的概念

链表是一种重要的数据结构，链表中的元素在物理空间上并不连续，链表的逻辑顺序是通过链表中的指针链接次序实现的。

下图所示为一个单向链表的形式：

所谓链表是指若干个数据项按一定的原则连接起来，物理上不连续的序列。每个数据项称为结点，每个结点都是由两部分组成：

    ©数据域：用来存储用户实际的数据。

    ©地址域（指向下一个结点的指针）：依靠这些指针将所有的数据项连接成一个链表。

从上图可以看出：

    链表中第一个结点称为头指针head，头指针中不存放具体数据，只存放链表的第一个结点的地址。

    head指向第一个结点，第一个结点又指向第二个结点……一直到最后一个结点。最后一个结点不再指向其他结点，称为表尾，表尾的地址域中放一个NULL，表示链表到此结束。

    链表中各结点在内存中存放的位置并不像数组那样是连续的，而是任意的。如果想查找链表中的某—个结点，必须从链表的头指针所指向的第一个结点开始顺序查找。

链表与数组的区别是：

    ©数组的元素个数在定义时就固定下来了，而链表的结点个数可根据需要进行增减。

    ©数组中元素在内存中的存储位置是连续存放的，而链表的各个结点的存储位置则是不连续的。

    ©数组元素的存储单元在数组定义时分配，链表结点的存储单元在程序执行时根据需要动态向系统申请或释放。

    ©数组中的元素顺序关系由元素在内存中存储位置确定，链表中的结点顺序关系由结点所包含的指针来体现。

从结构上看，链表是一个结构体类型，该结构体类型中至少包含两个成员：

    ©具体数据（可以是整型、浮点型、字符型、字符串）。

    ©指向下一个结点的地址：该成员是一个本结构体类型的指针。

所以，可以设计一个简单的结构体类型如下：

struct: node 

{

    long num;

    sturct student *next

};

数据域也可以是比较复杂的类型，如图所示的链表：

    链表的头指针指向的地址为2044，按照头指针的指向可找到内存地址为2044的链表的第一个结 点。要想查找第二个结点，按照第一个结点的地址域存放的地址找到内存地址为0676的第二个结点。依次顺序查找，可以找到链表中的每一个结点，直到最后一个结点的地址域为“NULL”，表示这是链表尾。

    图中的结构可以定义如下：

struct student

{

    int no;

    char name [10]; 

    char sex;

    int age;

    struct student *next;

);