线性链表

Hh0203 · 发表于 2016-7-13 15:24

EDA365欢迎您！

您需要登录才可以下载或查看，没有帐号？注册

x

线性表的链式表示和实现
线性表的顺序存储结构的特点是逻辑关系上相邻的两个匀速在物理位置上也相邻，因此可以随机存取表中任一元素，它的存取位置可用一个简单、直观的公式来表示。然而，从另一方面来看这个特点也铸成了这种存储结构的弱点；在作插入和删除操作时，需移动大量元素。现在我们来讨论线性表的另一种表示方法——链式存储结构，由于它不要求逻辑相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。

线性链表
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，成为结点。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储信息称作指针或链。n个结点链结成一个链表，即为线性表（a1,…,ai-1,ai,…,an）的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。
整个链表的存取必须从头指针开始，头指针指示链表中第一个结点的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”。
用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。