文档介绍：C语言程序设计
1
链表的相关概念
链表是由一个个结点顺序连接起来构成的表，称为链表。其中，结点用来存放元素信息和下一个元素的地址。链表中的元素在逻辑上相邻，在物理上不一定相邻。而数组中的元素逻辑上相邻，在物理上也一定相邻。本节主要讲解链表的根本概念和动态内存分配。
2
链表的相关概念
链表
1．链表
链表是由结点连接而成，结点就表示一个元素的信息。链表就是通过地址〔指针〕将每个结点〔元素〕连接起来的表。例如，链表中的元素包括A、B、C、D，。
3
链表的相关概念
，链表由4个结点构成，每个结点包括两个域：数据域和指针域。数据域用来存放数据信息，指针域表示地址信息，指向下一个结点的地址。数据域存放的是’A’、’B’、’C’、’D’。在C语言中，通常用箭头表示结点之间的先后关系，一个结点的指针指向下一个相邻的元素。这样利用指针将结点连接起来的表就构成了链表。
4
链表的相关概念
假如要访问链表中的元素，需要先找到第一个结点，为了找到链表的第一个结点，还需要一个指针指向第一个结点，我们称这样的指针为头指针，记作。另外，最后一个元素’D’的结点没有其它结点，将最后一个结点的指针域置为。。
5
链表的相关概念
2．定义链表的结点
链表是由结点构成，结点包括数据域和指针域。一个结点可以包括一个或多个数据域，因此，需要将结点定义为构造体类型。因为指针域是指向自身一样的构造体类型数据，’A’所在结点的指针域指向元素’B’所在的结点，而’A’和’B’都是同一个类型。
6
链表的相关概念
/*定义结点类型*/
{
; /*数据域*/
*; /*是指针域，指向构造体类型 */
};
其中，指针域是一个指向 的构造体指针类型。我们将这种存在指针指向自己的构造体类型称为自引用类型。
7
链表的相关概念
假如有如下的构造体类型定义：
{
; /*学号*/
[20]; /*姓名*/
[30]; /*地址*/
*; /*是指向 的指针*/
};
8
链表的相关概念
。
9
链表的相关概念
动态存储分配
链表中的结点是动态存储分配的，而不是由系统自动分配的。动态存储分配是在使用前才进展分配内存空间，使用完毕就可以释放内存空间。内存空间的分配和释放由用户自己决定。
1。函数──动态内存分配函数
函数的主要作用是分配一块长度为的内存空间。函数原型如下：
*( );
10