线性表(Linear List)是最简单和最常用的一种数据结构,它是由n个数据元素(节点)a1,a2,a3,...an
组成的有限序列,数据元素的个数n
为表的长度。
线性表的逻辑特征(非空的线性表)
a1
, 他没有前趋,仅有一个直接后继a2
an
,他没有后继,仅有一个直接前趋an-1
ai
(2 <= i <= n-1 )称为内部元素,它们都有一个直接前趋ai-1
和后继ai+1
initList(L)
,构造一个空的表i
个元素GetnNode(L, i)
LocateNode(L, x)
, 在表L中查找一个值为i的元素InsertList(L, i, x)
, 在表L的第i个元素插入一个值为x的元素,表的长度加1DeleteList(L, i)
, 删除表L的第i个元素,表长减一线性表的顺序存储指的是将线性表的数据元素按照逻辑顺序依次存入一组地址连续的存储单元里,用这种方法存贮的线性表称为顺序表。
线性表的第i个元素的存储位置:
// d为每个元素占用的存储单元个数
LOC(ai) = LOC(a1) + (i - 1) * d
线性表的这种机内表示称为线性表的顺秀存储结构,它的特点是,元素在表中的相邻关系,在计算机内也存在着相邻的关系。每个元素a1
的存储地址是该元素
在表中的位置i的线性函数,只要知道基地址和每个元素占用的单元数(元素的大小),就可以求出表中的任意元素的存储地址。
只要确定了线性表存储的起始位置,线性表中的任意一个元素都可以随机存取,所以顺序表也是一种随机存取结构。
优点
线性表顺序存储结构的特点是,在逻辑关系上相邻的两个元素在存储位置上也是相邻的,因此可以随机存取表中的任一元素。
但是,当经常需要做插入和删除运算时,需要移动大量的元素,而采用链式存储结构时就可以避免这些移动。
由于链式存储结构存储线性表的数据元素的存储位置可能是连续的也可能是不连续的,因此链表的节点是不可以随机存取的。
在使用链式存储结构表示每个数据元素ai
是,除了存储ai
本身的信息之外,还需要一个存储指示其后继元素ai+1
存储位置的指针,由这两个部分组成元素ai
的存储映像通常称为节点。
利用这种存储方式表示的线性表称为链表:
+-----------+------------+
| data | next |
+-----------+------------+
链表指的是有n个节点链成一个链表,即为线性表的链式存储结构
单链表的每个节点只包含一个指针域,因此称为单链表。
head
|
| +----+---+ +----+----+ +----+----+
\----> | a1 | |----->| a2 | |----> ... ---->| an | |
+----+---+ +----+----+ +----+----+
线性表(Linear List)是最简单和最常用的一种数据结构,它是由n个数据元素(节点)a1,a2,a3,...an
组成的有限序列,数据元素的个数n
为表的长度。
线性表的逻辑特征(非空的线性表)
a1
, 他没有前趋,仅有一个直接后继a2
an
,他没有后继,仅有一个直接前趋an-1
ai
(2 <= i <= n-1 )称为内部元素,它们都有一个直接前趋ai-1
和后继ai+1
initList(L)
,构造一个空的表i
个元素GetnNode(L, i)
LocateNode(L, x)
, 在表L中查找一个值为i的元素InsertList(L, i, x)
, 在表L的第i个元素插入一个值为x的元素,表的长度加1DeleteList(L, i)
, 删除表L的第i个元素,表长减一线性表的顺序存储指的是将线性表的数据元素按照逻辑顺序依次存入一组地址连续的存储单元里,用这种方法存贮的线性表称为顺序表。
线性表的第i个元素的存储位置:
// d为每个元素占用的存储单元个数
LOC(ai) = LOC(a1) + (i - 1) * d
线性表的这种机内表示称为线性表的顺秀存储结构,它的特点是,元素在表中的相邻关系,在计算机内也存在着相邻的关系。每个元素a1
的存储地址是该元素
在表中的位置i的线性函数,只要知道基地址和每个元素占用的单元数(元素的大小),就可以求出表中的任意元素的存储地址。
只要确定了线性表存储的起始位置,线性表中的任意一个元素都可以随机存取,所以顺序表也是一种随机存取结构。
优点
线性表顺序存储结构的特点是,在逻辑关系上相邻的两个元素在存储位置上也是相邻的,因此可以随机存取表中的任一元素。
但是,当经常需要做插入和删除运算时,需要移动大量的元素,而采用链式存储结构时就可以避免这些移动。
由于链式存储结构存储线性表的数据元素的存储位置可能是连续的也可能是不连续的,因此链表的节点是不可以随机存取的。
在使用链式存储结构表示每个数据元素ai
是,除了存储ai
本身的信息之外,还需要一个存储指示其后继元素ai+1
存储位置的指针,由这两个部分组成元素ai
的存储映像通常称为节点。
利用这种存储方式表示的线性表称为链表:
+-----------+------------+
| data | next |
+-----------+------------+
链表指的是有n个节点链成一个链表,即为线性表的链式存储结构
单链表的每个节点只包含一个指针域,因此称为单链表。
head
|
| +----+---+ +----+----+ +----+----+
\----> | a1 | |----->| a2 | |----> ... ---->| an | |
+----+---+ +----+----+ +----+----+
单链表中的每个节点的存储结构是存放在其直接前趋节点的指针域(next)中,而开始节点无直接前趋,因此设立头指着鞥heead只向开始节点。又由于终端节点无后继节点,所以终端节点的指针域为空
如果链表中一个节点都没有,则为空链表,此时head=NULL
。
O(n)
O(n)
i-1
个节点的存储地址是存储在第i-1个节点的指针域next中,因此要先使p指向第i-1个节点,然后使得p->next指向第i+1个节点,在将第i个节点释放掉。时间复杂度也是O(n)
循环链表是链式存储结构的另一种形式,其特点是单链表中最后一个节点的指针域不为空,而是指向链表的头结点,使整个链表构成一个环。
任意一节点开始都可以访问表中的其他元素。这种结构形式的链表称为单循环链表。
循环链表的节点类型与单链表完全相同,在操作上也与单链表基本一致,差别仅在与算法中循环的结束判断条件不在是p或p->next是否为空,而是它们是否等于头结点。
在单链表和单循环链表中的节点只设有一个纸箱器直接后继的指针域,因此从某个节点出发只能顺指针向后访问其他节点。若需要查找节点的直接前趋,则需要从头指针开始查找某节点的直接前趋节点。
双向链表可以从表中快速确定一个节点的直接前趋,双向链表中的节点类型中增加了一个指向其直接前趋的指针域prior
,形成了两条不同方向的链,因此称为双向链表。
与单链表不同的是在双向链表中插入和删除必须同时修改两个方向上的指针
线性表有两种存储结构:顺序存储和线性存储,这两种存储表示各有其特点:顺序表结构可以随机存取表中的任一元素,元素的存储位置可用一个简单的公式来表示,然而在做插入和删除操作时,需要移动大量的元素。
链式存储则可以克服在做插入和删除运算时大量移动元素的问题,但却失去了随机存取的特点。
性能比较:
时间性能
线性表节点的存储密度,也是选择存储结构的一个重要依据,所谓存储密度就是节点空间的利用率。它的计算公式为:
存储密度 = (节点数据域所占空间)/ (整个节点所占空间)
一般来说存储密度越大,存储空间的利用率就越高。顺序表的存储密度为1,而链表的节点的存储密度小于1,若不考虑顺序表的空闲区,则顺序表的存储空间利用率为100%,远高于链表的节点存储密度。
原文:https://blog.51cto.com/jlnetc/2445796