线性表

线性表(List):零个或多个数据元素的有限序列。线性表中元素的个数即线性表的长度,元素个数为 0 的线程表为空表。

抽象数据类型定义

ADT :线性表(List)

Data :线性表的数据对象集合为 {a1, a2, a3 … an} ,每个元素的类型均为 DataType。除第一个元素外,每个元素有且只有一个直接前驱元素;除最后一个元素外,每个元素有且只有一个直接后继元素。数据元素之间为一对一的关系。

Operation

  • init(创建一个空表)
  • isEmpty(判断线性表是否为空)
  • clear(清空线性表)
  • get(获取第 i 个位置的元素)
  • indexOf(获取指定元素在线性表中的位置)
  • insert(插入元素)
  • delete(删除元素)
  • length(获取线性表长度)

endADT

线性表的存储结构

线性表的存储结构分为 顺序存储结构链式存储结构 两种。

顺序存储结构

线性表的顺序存储结构,指用一段地址连续的存储单元依次存储线性表的数据元素,可以用一维数组来实现。线性表的顺序存储结构实现称为顺序表。

链式存储结构

线性表的链式存储结构中,每个存储单元除了存储元素数据外,额外存储一个指示其后继元素位置的信息。线性表的链式存储结构实现称为链表。

存储数据元素信息的域称为数据域,存储后继元素位置信息的域称为指针域,两部分信息合在一起称为结点 Node。链表中每个结点包含一个指针域,所以称为单链表。

两种存储结构的对比

顺序存储结构无需为元素之间的逻辑关系增加额外的存储空间,并且可以快速存储表中任一位置的元素;而链式存储结构插入和删除操作不需要移动大量元素,也不必提前分配存储空间。

如需要频繁查找,而很少进行插入和删除操作,宜使用顺序存储结构;如元素个数变化较大不好确认范围,或需要频繁插入和删除,宜使用链式存储结构。

其他链表结构

  • 静态链表

静态链表即用数组描述的链表,每个元素有数据域和指针域。

第一个元素的指针域用于存放第一个未使用的结点位置,最后一个元素的指针域用于存放第一个使用中的结点位置,不使用指针。

  • 循环链表

单链表中终端结点的指针域由空改为指向头结点。

  • 双向链表

跟单链表相比,每个节点再设置一个指向其前驱结点的指针域。

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2016-2020 姜越

谢谢老板

支付宝
微信