线性表 (Linear List) 是最简单和最常用的一种数据结构, 它是由 n 个数据元素(节点)a1,a2,a3,...an 组成的有限序列, 数据元素的个数 n 为表的长度.
线性表的逻辑特征(非空的线性表)
有且只有一个称谓开始元素的 a1, 他没有前趋, 仅有一个直接后继 a2
有且只有一个称为终端元素的 an, 他没有后继, 仅有一个直接前趋 an-1
其余元素 ai (2 <= i <= n-1 )称为内部元素, 它们都有一个直接前趋 ai-1 和后继 ai+1
线性表的基本运算
置空表 initList(L), 构造一个空的表
求表长 ```ListLength(L)
取表中的第 i 个元素 GetnNode(L, i)
按值查找 LocateNode(L, x), 在表 L 中查找一个值为 i 的元素
插入 InsertList(L, i, x), 在表 L 的第 i 个元素插入一个值为 x 的元素, 表的长度加 1
删除 DeleteList(L, i), 删除表 L 的第 i 个元素, 表长减一
顺序表
线性表的顺序存储指的是将线性表的数据元素按照逻辑顺序依次存入一组地址连续的存储单元里, 用这种方法存贮的线性表称为顺序表.
线性表的第 i 个元素的存储位置:
- // d 为每个元素占用的存储单元个数
- LOC(ai) = LOC(a1) + (i - 1) * d
线性表的这种机内表示称为线性表的顺秀存储结构, 它的特点是, 元素在表中的相邻关系, 在计算机内也存在着相邻的关系. 每个元素 a1 的存储地址是该元素
在表中的位置 i 的线性函数, 只要知道基地址和每个元素占用的单元数(元素的大小), 就可以求出表中的任意元素的存储地址.
只要确定了线性表存储的起始位置, 线性表中的任意一个元素都可以随机存取, 所以顺序表也是一种随机存取结构.
优点
通过下标获取元素, 时间复杂度为 O(1)
缺点
插入, 删除操作需要移动大量元素, 时间复杂度为 O(n)
链表
线性表顺序存储结构的特点是, 在逻辑关系上相邻的两个元素在存储位置上也是相邻的, 因此可以随机存取表中的任一元素.
但是, 当经常需要做插入和删除运算时, 需要移动大量的元素, 而采用链式存储结构时就可以避免这些移动.
由于链式存储结构存储线性表的数据元素的存储位置可能是连续的也可能是不连续的, 因此链表的节点是不可以随机存取的.
在使用链式存储结构表示每个数据元素 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), 构造一个空的表
求表长 ```ListLength(L)
取表中的第 i 个元素 GetnNode(L, i)
按值查找 LocateNode(L, x), 在表 L 中查找一个值为 i 的元素
插入 InsertList(L, i, x), 在表 L 的第 i 个元素插入一个值为 x 的元素, 表的长度加 1
删除 DeleteList(L, i), 删除表 L 的第 i 个元素, 表长减一
顺序表
线性表的顺序存储指的是将线性表的数据元素按照逻辑顺序依次存入一组地址连续的存储单元里, 用这种方法存贮的线性表称为顺序表.
线性表的第 i 个元素的存储位置:
- // d 为每个元素占用的存储单元个数
- LOC(ai) = LOC(a1) + (i - 1) * d
线性表的这种机内表示称为线性表的顺秀存储结构, 它的特点是, 元素在表中的相邻关系, 在计算机内也存在着相邻的关系. 每个元素 a1 的存储地址是该元素
在表中的位置 i 的线性函数, 只要知道基地址和每个元素占用的单元数(元素的大小), 就可以求出表中的任意元素的存储地址.
只要确定了线性表存储的起始位置, 线性表中的任意一个元素都可以随机存取, 所以顺序表也是一种随机存取结构.
优点
通过下标获取元素, 时间复杂度为 O(1)
缺点
插入, 删除操作需要移动大量元素, 时间复杂度为 O(n)
链表
线性表顺序存储结构的特点是, 在逻辑关系上相邻的两个元素在存储位置上也是相邻的, 因此可以随机存取表中的任一元素.
但是, 当经常需要做插入和删除运算时, 需要移动大量的元素, 而采用链式存储结构时就可以避免这些移动.
由于链式存储结构存储线性表的数据元素的存储位置可能是连续的也可能是不连续的, 因此链表的节点是不可以随机存取的.
在使用链式存储结构表示每个数据元素 ai 是, 除了存储 ai 本身的信息之外, 还需要一个存储指示其后继元素 ai+1 存储位置的指针, 由这两个部分组成元素 ai 的存储映像通常称为节点.
节点包括两个域:
存储数据元素的域, 称为数据域
存储直接后继指针的域, 称为指针域
利用这种存储方式表示的线性表称为链表:
- +-----------+------------+
- | data | next |
- +-----------+------------+
链表指的是有 n 个节点链成一个链表, 即为线性表的链式存储结构
单链表
单链表的每个节点只包含一个指针域, 因此称为单链表.
- head
- |
- | +----+---+ +----+----+ +----+----+
- \----> | a1 | |----->| a2 | |----> ... ---->| an | |
- +----+---+ +----+----+ +----+----+
单链表中的每个节点的存储结构是存放在其直接前趋节点的指针域 (next) 中, 而开始节点无直接前趋, 因此设立头指着鞥 heead 只向开始节点. 又由于终端节点无后继节点, 所以终端节点的指针域为空
来源: http://www.bubuko.com/infodetail-3260912.html