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