|
|
在数据结构中,线性结构通常称为线性表,它是最简单、最常见的一种数据结构。通常线性表是由n个相同数据类型的节点组成的有限序列。其特点是在数据元素的非空有限集合中,存在唯一的一个被称为"第一个"的数据元素;存在唯一的一个被称为"最后一个"的数据元素;除第一个之外,集合中的每个数据元素均有且仅有一个前驱;除最后一个之外,集合中的每个数据元素均有且仅有一个后继。
|
|
|
一个由n个节点e0, e1,…, en-1组成的线性表记为(e0, e1, …, en-1)。线性表的节点个数称为线性表的长度,长度为0的线性表称为空的线性表,简称空表。对于非空线性表,e0是线性表的第一节点,en-1是线性表的最后一个节点。线性表的节点构成了一个序列,对序列中两个相邻节点ei和ei+1,称前者为后者的前驱节点,后者是前者的后继节点。
|
|
|
|
线性表最重要的性质是线性表中节点的相对位置是确定的。线性表的节点也称为表元,
或称为记录,要求线性表的节点一定是同一类型的数据。线性表的节点可由若干个成分组成,其中唯一标识表元的成分称为关键字,简称键。
|
|
|
|
|
.Initiate(L):初始化操作,对线性表中的各个元素的初始值进行初始化。
|
|
|
.Length(L):求长度函数,线性表的长度就是线性表中元素的个数。
|
|
|
.Get(L, i):取元素函数,取线性表中的一个元素。
|
|
|
.Prior(L, elm):求前驱函数,给定一个线性表元素,求出其前一个元素。
|
|
|
.Next(L, elm):求后继函数,给定一个线性表元素,求出其后一个元素。
|
|
|
.Locate(L, x):定位函数,根据给定的值,在线性表中找到并返回其位置。
|
|
|
.Insert(L, i, b):插入操作,给定一个元素后,将其插在线性表的某个位置。
|
|
|
.Delete(L, i):删除操作,删除给定位置或值的元素。
|
|
|
|
有多种存储方式能将线性表存储在计算机内,其中最常用的是顺序存储和链式存储。根据存储方式的不同,其上述基本操作的实现也不一样。
|
|
|
(1)顺序存储:顺序存储是最简单的存储方式,其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。通常使用一个足够大的数组,从数组的第一个元素开始,将线性表的节点依次存储在数组中。顺序存储方式的优点是能直接访问线性表中的任意节点。线性表的第i个元素a[i]的存储位置可以使用以下公式求得:Loc(ai)=Loc(aI)+(i-1)×1。式中Loc(ai)是线性表的第一个元素a1的存储位置,通常称作线性表的起始位置或基地址。顺序存储的缺点是:线性表的大小固定,浪费大量的存储空间,不利于节点的增加和减少;执行线性表的插入和删除操作要移动其他元素,不够方便。
|
|
|
(2)链式存储:链式存储是用链表来存储线性表。其特点是:每个链表都有一个头指针,整个链表的存取必须从头指针开始,头指针指向第一个数据元素的位置,最后的节点指针为空。当链表为空时,头指针为空值。当链表非空时,头指针指向第一个节点。链式存储的缺点是:由于要存储地址指针,所以浪费空间;直接访问节点不方便。
|
|
|
链式存储有单链表(线性链表)、循环链表、双向链表。
|
|
|
.单链表从链表的第一个表元开始,将线性表的节点依次存储在链表的各表元中。链表的每个表元除要存储线性表节点信息外,还要存储其后继节点的指针。
|
|
|
.循环链表是单链表的变形,其特点是表中最后一个节点的指针域指向头节点,整个链表形成一个环。因此,从表中的任意一个节点出发都可以找到表中的其他节点。循环链表中,从头指针开始遍历的结束条件不是节点的指针是否为空,而是是否等于头指针。为简化操作,循环链表中往往加入表头节点。
|
|
|
.双向链表的节点中有两个指针域,一个指向直接后继,另一个指向直接前驱,克服了单链表的单向性缺点。
|
|
|