顺序存储结构的不足的解决办法
从上一节我们对顺序表的讨论中可见,线性表的顺序存储结构的特点是:
逻辑关系上相邻的两个元素在物理位置(内存)上也相邻,因此可以随机存取表中任一位置元素,它的存储位置可用一个简单...线性表链式存储结构的定义
线性表的链式存储结构的特点是:
用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的....结构图示如下:
n个结点(
的存储映像)链结成一个链表,即为线性表(
)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表.单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起...,如下图:
对于线性表来说,总得有个头有个尾,链表也不例外.我们把链表中第一个结点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了.之后的每一个结点,其实就是上一个的后继指针指向的位置...头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针,如下图所示:
头指针与头结点的异同
头指针
头指针是指链表指向第一个结点的指针,若链表有头结点