线性表之静态链表
线性表之静态链表
苏丙榅1. 静态链表的设计
1.1 定义静态链表
链表是由多个相同类型的节点组成的线性表,它的每个节点都包含一个数据项和一个指向下一个节点的指针,链表中各个节点的地址是不连续的。
下面是一个用于存储整形数据的链表节点结构:
1 | struct Node |
data
:用于存储实际数据next
:用于连接当前节点的后继节点,存储的是下一个节点的地址(很多资料中将其称之为游标
)
静态链表是一种使用数组实现的链表
,通常用于环境中无法使用指针的情况。这种结构在内存中是连续存储的,但节点的位置可以变化,因此称为静态链表。
静态链表的节点结构和链表类似,但是不完全相同,当前节点连接后继节点使用的是索引而不是指针。
下面是一个用于存储整形数据的链表节点结构:
1 | struct Node |
data
:用于存储实际数据next
:使用索引的方式记录后继节点的位置
由于静态链表是一个数组,也就是说在存储数据之前元素对应的存储空间就已经存在了,此时我们就需要考虑以下几个问题:
- 如何判断当前节点是一个空闲节点?
- 如何判断当前节点是一个有效的数据节点?
- 如何判断当前节点是链表的尾节点?
由于链表的数据域data
的值是千变万化的,所以我们只能在它的next
域上下功夫,在使用静态链表之前可以对它的值做如下规定(不考虑头结点):
next == -1
:当前节点为静态链表的尾节点next == -2
:当前节点为静态链表的空闲节点next >= 0
:当前节点为静态链表的有效的数据节点
1.2 链表头结点
不论是链表(动态)还是静态链表根据处理方式的不同,都可以分为两大类:带头结点
的链表和不带头结点
的链表。
带头结点
:链表的第一个节点(头结点)的data
域不存储
数据,next
域记录的是第一个数据节点的位置(索引或者地址)不带头结点
:链表的第一个节点的data
域存储
数据,next
域记录的是第二个数据节点的位置(索引或者地址)
一般情况下建议大家使用带头结点的链表,带头结点的链表避免了链表中没有节点的这种情况(空链表指的是链表中没有数据节点),减少了bug的产生,并且更容易处理和维护。
下图描述的是一个静态链表,请大家动脑分析,完成对这个链表的遍历。
虽然数组中存储的数据的按照下边遍历顺序为:null、a、b、c、f、d、g
,但实际上在静态链表中存储的数据顺序并非如此。其中的关键点就是:先看各个节点中的 next 域记录的位置,然后再把这个位置作为数组的下标,去访问对应的数组元素。
- 数组0号元素为静态链表的头结点,
next=6
,所以第1个数据为g
- 数组6号元素为静态链表的数据节点,
next=1
,所以第2个数据节点为a
- 数组1号元素为静态链表的数据节点,
next=5
,所以第3个数据节点为d
- 数组5号元素为静态链表的数据节点,
next=4
,所以第4个数据节点为f
- 数组4号元素为静态链表的数据节点,
next=2
,所以第5个数据节点为b
- 数组2号元素为静态链表的数据节点,
next=3
,所以第6个数据节点为c
- 数组3号元素为静态链表的尾节点,没有后继节点
因此遍历静态链表,得到的序列应该是:g、a、d、f、b、c
2. 静态链表的操作
以下操作的都是带头结点的静态链表,它的第一个数据节点记作 pos=0
2.1 遍历和搜索
关于静态链表中数据搜索,搜索的是节点的值,而不是它的位置。在搜索的时候需要分两步走:
- 根据链表节点的
next
域,从前往后依次访问各个节点 - 取出当前节点的
data
值,和要搜索的值进行比较- 相等:节点找到了,使用
break
或者return
终止循环 - 不相等:没找到需要的节点,继续向下遍历
- 相等:节点找到了,使用
下图描述的就是遍历静态数组的整个过程:
- 通过头结点的
next
域记录的值找到第一个数据节点的位置- 通过第1个数据节点的
next
域记录的值找到第2个数据节点的位置- 通过第2个数据节点的
next
域记录的值找到第3个数据节点的位置- ……
- 如果节点的
next
域值为-1
,表示当前节点是最后一个数据节点,静态链表遍历结束。
上面的这个图乍一看乱糟糟,其实一点不乱,根据箭头的方向就能完成整个静态链表的遍历了。
掌握了静态链表的遍历,关于节点的搜索就非常简单了,只需要在遍历过程中再进行一次判断即可,在此就不再过多赘述了。
2.2 数据的插入
因为链表是线性表,在链表中插入数据的时候一般都是根据位置进行操作,添加节点有三种方式:
- 在链表的头部添加新节点
- 在链表的尾部添加新节点
- 在链表的中间位置添加新节点
在链表头部和尾部添加节点的操作都相对比较简单,因为我们可以将它们和插入合并到一起,也就是此处讲的插入节点的操作是在链表的任意位置插入新的节点
。
下面带大家一起分析一下在静态链表中插入数据的具体流程:
- 判断要插入的数据的位置,有效范围应该是:
0 <= pos <= length
pos==0
新节点作为链表的第一个数据节点pos==length
新节点添加到链表的尾部0 < pos < length
新节点插入到pos
位置之前
- 遍历数组,找到一个没有存储数据的空闲节点,记作
freeNode
- 条件为:
next == -2
- 条件为:
- 判断静态链表是否满了,如果满了可以选择扩容或者拒绝插入数据
- 根据静态链表节点的
next
域遍历链表,找到pos-1
位置的节点, 记作curNode
- 节点赋值并调整位置
- 给
freeNode
节点赋值 - 将
freeNode
的后继节点设置为pos
节点,该节点的索引值是存储在curNode.next
里边的 - 将
curNode
节点的后继节点设置为freeNode
- 给
下图是是一个静态链表,链表中的元素依次是:
a->d->f->b->c
现在要求在静态链表的
第三个节点
位置插入新的元素g
,也就是说插入成功之后g
就变成了第三个数据节点,原来的第三个数据节点变成了第四个数据节点。
首先需要根据链表节点的
next
域遍历链表,找到第三个节点的上一个节点,即第二个数据节点。根据头结点的
next
域找到的第一个数据节点为1号位置的节点
根据1号位置节点的
next
域找到的第二个数据节点为5号位置的节点
给6号位置节点初始化为
g
,将它的后继设置为5号节点的后继(该节点为原来的第三个数据节点)
更新第二个数据节点的后继,让6号位置节点作为链表的第三个数据节点,也就是让
五号位置节点的 next = 6
再次遍历这个静态链表,节点值依次为:
a->d->g->f->b->c
到此为止新节点的插入操作就完成了。
2.3 数据的删除
删除静态链表中的元素,通常情况下还是根据位置来进行操作,操作步骤如下:
- 判断要删除的数据的位置,有效范围应该是:
0 <= pos < length
pos==0
删除的是第一个数据节点pos==length-1
删除的是尾部最后一个数据节点0 < pos < length-1
删除的是pos
位置的数据节点
- 遍历静态链表,找到
pos-1
位置的节点,记作curNode
- 根据
curNode
找到要是删除的节点delNode
,它的位置 =curNode.next
- 链表节点重新连接
curNode.next = delNode.next
- 将已删除节点
delNode
的next
域标记为未使用,即delNode.next=2
接下来再通过图表的方式为大家举例说明,看下图,要求
删除静态链表中的第二个数据节点
,第二个数据节点也就是数组5号位置的节点,因为遍历链表节点的顺序为:a->d->f->b->c
遍历这个静态链表,找到第一个数据节点(要删除位置的节点的前驱)
重新进行链表节点的连接:
第一个数据节点的后继 = 要删除的节点的后继
,通过这个操作就从静态链表中删除了原来的第二个数据节点。
再次遍历这个静态链表,得到的节点顺序应该是:
a->f->b->c
。为了能够复用数组5号位置的元素,根据规则需要将它的next
域修改为-2
3. 示例代码
3.1 头文件
StaticLinkList.h
1 |
|
3.2 源文件
StaticLinkList.cpp
1 |
|
程序输出的结果为:
1 | 100 33 66 30 10 88 99 |
在上面的示例程序中,使用的是一个静态数组,当可用空间用完之后就拒绝再次往静态链表中添加数据了。当然,也可以将这个数组修改为动态数组,这样这样静态链表也就没有了最大存储上限。关于如何实现一个动态数组在上一节中已经做了详细讲解,大家可以自行考古。
4. 静态链表和数组
静态链表和数组的本质是相同的,但是在使用方式上又有所不同,下面就给大家总结一下二者的优缺点:
- 插入删除操作,静态链表效率高
- 静态链表只需要修改对应节点的
next
域的值,需不要移动元素 - 数组在插入新节点需要大量元素后移,删除节点需要大量元素前移
- 静态链表只需要修改对应节点的
- 访问指定位置的元素,数组效率高
- 静态链表需要遍历才能找到这个节点
- 数组通过下标就可以找到该节点了
- 默认情况下内存大小是固定的
- 申请的内存空间大,但是数据量少,浪费存储空间
- 申请的内存空间小,但是数据量大,内存不够用
静态链表和数组是对同一块连续内存的两种不同使用方式,二者没有孰优孰劣之分,作为一名合格的程序猿要做的就是具体问题具体分析,从众多解决方案中找出一个最优解。