链表的概念
使用数组存放大量数据时,需要事先定义固定长度的数组,当数组元素个数不确定时,需要定义足够长的数组,这样会造成内存空间的浪费。而且根据数组的存储方式,数组的所有元素必须占用连续的内存空间。
链表是一种常见的重要的数据结构,可以存储多个同类型的数据,它是动态地进行存储分配的一种数据结构。因此链表没有使用数组时的限制,它可以根据实际需要动态地申请内存空间,并且所申请的内存空间也不要求是连续的
结点是链表的基本存储单位,一个结点对应链表中的一个数据元素,所有的结点具有相同的数据结构。每个结点占用一段连续内存空间,而结点之间可以占用不连续的内存空间。结点和结点之间使用指针链接在一起,所以称为链表。
链表中的每个结点包括数据域和指针域两个部分,其中数据域存放结点的数据,指针域存放下一个结点的地址。C语言使用结构体来定义结点,其一般形式为:
struct node
{
int data； //数据域
struct node *next；//指针域
}；
使用上面的结构体类型可以建立基本的单向链表,下图显示了单向链表的结构。下图所示的单向链表中,有以下几个需要注意的问题：
(1)需要定义一个指针变量指向第1个结点(即存放第1个结点的地址),称为头指针。
(2)除最后一个结点外,其他结点的指针域指向下一个结点。
(3)最后一个结点的指针域存放NULL,表示链表结束。图中用“∧”表示。
(4)结点的数据域可以根据程序实际需要定义多个数据成员。
单向链表是链式存储结构中最简单的一种方式,链式存储结构最基本的特点是每个结点都存储它的后续结点的地址,不需要占用连续的内存空间。链式存储结构的优点包括:插入删除结点的操作灵活简洁,方便进行内存扩展和回收等。缺点是查询操作只能顺序进行,效率较低。
