标签搜索

数据结构-线性表

海绵
2022-04-14 / 0 评论 / 8 阅读 / 正在检测是否收录...

线性表

线性表和线性结构的区别

线性结构的基本特点 是除第一个元素无直接前驱,最后一个元素无直接后继之外,其他每个数据元素都有一个前驱和 后继。线性表是最基本且最常用的一种线性结构。看底下的图片可知线性结构和线性表的关系。

image-20220307155650647

线性表的定义和特点

线性表的定义

线性表是具有相同特性的数据元素的一个有限序列

线性表的特点

对千非空的线性表或线性结构, 其特点是:

(1) 存在唯一的一个被称作 “第一个 " 的数据元素;

(2) 存在唯一的一个被称作 “最后一个" 的数据元素;

(3) 除第一个之外, 结构中的每个数据元素均只有一个前驱;

(4) 除最后一个之外,结构中的每个数据元素均只有一个后继。

线性表的存储方式

线性表中数据存储的方式可以是顺序存储,也可以是链式存储,根据存储的方式不同,可以把线性表分为顺序表和链表

线性表的顺序存储—顺序表

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素, 这种表示 也称作线性表的顺序存储结构或顺序映像。通常, 称这种存储结构的线性表为顺序表(Sequential List)。其特点是,逻辑上相邻的数据元素, 其物理次序也是相邻的。

线性表的顺序存储结构是一种随机存取的存储结构。通常使用数组来描述数据结构中的顺序的存储结构。

顺序表的基本操作

初始化

初始化的操作就是构造一个空的顺序表,同时为它分配空间大小。

取值

上面提到顺序表其实就类似数组,也就是线性表的随机存储的实现方式。取值直接使用下标就可以了。其中查找的复杂度是 O(1)。

查找

从第一个元素开始,依次与 e 做比较,若找到与 e 相等的元素,则查找成功,返回元素的下标。其中查找的复杂度是 O(N)。

插入

线性表的插入操作是指在表的第i个位置插入一个新的数据元素,是长度为 n 的线性表变成长度为 n + 1 的线性表。其中查找的复杂度是 O(N)。

删除

线性表的删除操作是指将表的第i个元素删去,将长度为 n 的线性表变成长度为 n - 1 的线性表。其中查找的复杂度是 O(N)。

线性表的总结

顺序表可以随机存取表中的任一元素,但是在插入或者删除的时候,需要移动大量的元素。当表中的数据元素个数较多且变化较大时,操作过程相对复杂,必然导致存储空间的浪费。但是这些问题都可以使用链表去解决。链表是线性表的另外一种存储方式的表现。

线性表的链序存储—单链表

线性表的链式存储结构的特点:用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个元素与其直接后继数据元素之间的逻辑关系,除了存储本身的信息之外,还要存储一个指示其直接后继的信息(即直接后继的存储位置)。其中这样的一个数据元素也称为结点。其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域。

线性表的单链表存储结构,整个链表的存取必须从头指针开始进行,头指针指示链表中第一个结点,也被称为首元结点。同时,由于最后一个数据元素没有直接后继,则单链表中的最后一个结点的指针为空。

数据元素之间的逻辑关系是由结点中的指针指示的,也就是说明逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻。链表只关系数据元素之间的逻辑关系。

单链表首元结点

首元结点是指链表中存储第一个数据元素的结点。

单链表头结点

头结点是首元结点之前附设的一个结点。其指针域指向首元结点。其数据域可以不存储任何信息。

单链表头指针

头指针是指向链表中第一个结点的指针。若链表设有头结点,则头指针所指结点为线性表的头结点。若链表不设头结点,则头指针所指向的首元结点。

为什么增加头结点

  1. 便于首元结点的处理
  2. 便于空表和非空表的统一处理

单链表的实现

初始化

单链表的初始化操作就是构造一个空表。使得头指针指向头结点。

取值

和顺序表不同,链表中的逻辑相邻的结点并没有存储在物理相邻的单元中。这样就不能像数组那样通过下标去寻找值了。只能从链表中的首元结点出发。顺着链域 NEXT 逐个结点向下访问。

查找

0

打赏

海报

正在生成.....

评论 (0)

取消