Mark'sBLOG
CARD
jinyaoMa
issue, func, flow, std, solve
15 | 8 | 24
SKIN
SETTINGS
Night Shift
Disable Canvas
简体中文
中文
|
English
|
日本語
PAGE CONTENT
数据结构之线性表 List
2020-04-20
2020-04-23
1.9k
13 min.

线性表(List),了解线性表的基础知识,认识一下线性表的种类。

# 线性表List

线性表(List):由另个或多个元素组成的有限序列。元素是有序的,可以被排列的。在有序结构中,某个元素ai前面的元素ai-1称为前驱元素,后面的元素ai+1称为后继元素。在Java语言中,数组(ArrayList)和链表(Linked List)都属于线性表。其中数组使用了顺序结构,而链表使用了链式结构。

线性表的数据对象集合为{a1,a2,...,an-1,an},每个元素的类型均为DataType。**数据元素之间的关系是一对一的关系。**其中,除第一个元素a1外,每个元素有且只有一个直接前驱元素,除最后一个元素an外,每个元素有且只有一个直接后继元素。

# 线性表伪代码

ADT 线性表(List)
Data
  数据对象集合 {a1,a2,...,an-1,an}
Operation
  init(*L):初始化空线性表L
  isEmpty(L):判断线性表是否为空
  clear(*L):清空线性表
  getElement(L,i,*e):将线性表L中第i个元素返回给e
  elementAt(L,e):线性表L中查找与e相等的元素,返回元素的位置
  insert(*L,i,e):线性表L中第i个位置插入新元素e
  delete(*L,i,*e):删除线性表L中第i个位置元素,并返回该元素给e
  length(L):返回线性表L的元数个数
endADT

# 线性表的顺序存储结构

线性表的顺序存储结构封装需要3个属性:

  • 存储空间初始位置,数组指针
  • 线性表的最大长度,指存储空间总长度,初始化后不变
  • 线性表的当前长度,指表中元素数量,大于等于0,小于表的最大长度

# 顺序存储结构的地址计算方法

注:i从“1”开始

假设每个元素类型的DataType都需要占用c个储存单位(字节),那么线性表中第i+1个元素和第i个元素的存储位置的关系是(LOC为获得存储位置的函数):

LOC(ai+1) = LOC(ai) + c

所以找第i个元素ai的储存位置可以又线性表初始指针指向的a1推算出:

LOC(ai) = LOC(a1) + (i-1) * c

通过这个公式,计算出线性表中任意位置的地址,所用的时间都是相同的,那么他的存储时间性能就是O(1)这种结构通常被称为随机存储结构。

# 线性表的链式存储结构

顺序存储结构最大的缺点,插入和删除需要移动大量元素,从而保持表中元素邻居的关系;链式存储结构通过携带后继元素的存储地址就解决了这个缺点。

链式存储结构的线性表中元素称为“存储映像”,也称为“节点(Node)”。每个节点都是由两部分组成:

  • 数据域:储存数据元素信息的域
  • 指针域:存储直接后继元素地址的域

# 单链表

n个节点链接成一个链表,即为线性表(a1,a2,...,an-1,an)的链式存储结构。因为此链表的每个节点中只包含一个指针域,所以叫做单链表。

单链表图示

单链表必须有一个头部加上0到多个节点。头指针是链表指向第一个节点的指针,如果链表有头结点,则头指针指向头结点。头结点携带第一个元素的节点指针,放在第一个节点之前,其数据域一般无意义,但也可以存放链表的长度。头结点不是必须的,但是头结点可以放一些对列表有用的变量。

尾指针是指向单链表的最后一个节点的指针,这个指针不是必须的,但是尾指针有好处,比如需要在尾部插入新节点。

若线性表需要频繁查找,很少进行插入和删除操作是,宜采用顺序存储结构。

若需要频繁插入和删除时,宜采用单链表结构。

# 静态链表

在内存中建立一个数组,在数组最大长度内的空间中再建立一个链表,这种链表就是静态链表。静态链表通过“游标(Cursor)”指向后继元素所处数组中的“下标(Index)”。下图为静态链表转普通链表,最大长度为100,第一个元素游标指向备用链表的头节点(既当前链表尾节点的游标,也是尾指针),最后一个元素游标指向当前链表头节点。

静态链表转普通链表

  • 数组中第一个和最后一个元素不存放数据
  • 未使用的数组元素被称为备用链表
  • 数组第一个元素,即Index = 0的元素的游标(Cursor)存放备用链表的第一个节点的下标
  • 数组最后一个元素,即Index = MAX_SIZE-1的元素的游标(Cursor)存放当前链表的第一个节点的下标
  • 静态链表初始化时,Index = 0的元素的游标应从1开始,而Index = MAX_SIZE-1的元素的游标则是0,表示空链表

# 循环链表

在单链表中,如果不从头结点出发,就无法访问到全部节点。循环链表就解决了这个问题。只要有链表中某一节点的指针,就能跑完全部节点。当表为空时,头部后继指针指向头部本身。

循环链表所用的方法就是把尾节点的空指针指向头节点,使单链表形成一个环,这种头尾相接的单链表被称为单循环链表,简称循环链表。

原单链表判断尾节点用node.next === null ?,现在则是用node.next === head ?

# 双向链表

对比单链表,双向链表的节点有两个指针:前驱指针和后继指针。双向列表允许从尾部往回跑。当表为空时,头部前驱指针和后继指针都指向头部本身。

# 找单链表中间的节点的方法

利用快慢指针原理:设置两个指针*search*middle都指向单链表的头结点。其中*search的移动速度是*middle的2倍。当*search指向尾节点时,*middle正好就在中间。

在一个长度为100的单链表中,当*search指向第100个节点时,*middle指向第50个节点。

在一个长度为101的单链表中,当*search指向102(即超出长度)时,*middle指向第51个节点,正好在中间。

# 判断一个链表是否有环

方法一:设置两个指针*q*b*q一直在走的情况下,每遇到一个节点,*b就从新从头结点开始走。如果*q所在当前步数等于*b从头开始数的步数,则*q继续往前走一步,而*b从新走。如果*q所在当前步数不等于*b的从头开始数的步数,则存在环。这种方法可以找到环所在节点。

方法二:设置两个指针*q*b都指向单链表的头结点。其中*q的移动速度是*b的2倍,若在某个时候*q == *b,则存在环。一般偶数量节点的单循环链表跑两次后*q == *b

本文参考: 【C语言描述】《数据结构和算法》(小甲鱼) (opens new window)

The post above ended Thanks for your reading
Come on! Write some comments, and your suggestions will improve the quality of my creative!
FRIEND ME
QQ
WeChat
Post Author: jinyaoMa
Post Link: /
Copyright Notice: All articles/posts in this website are licensed under BY-NC-SA unless stating additionally.
Enable Read Mode
COMMENTS
DEFAULT