| title | categories | tags | date | updated | |||
|---|---|---|---|---|---|---|---|
数据结构之线性表List |
|
|
2020-04-20 09:20:49 -0700 |
2020-04-23 09:20:49 -0700 |
线性表（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语言描述】《数据结构和算法》（小甲鱼）