线性表之静态链表

1. 静态链表的设计

1.1 定义静态链表

链表是由多个相同类型的节点组成的线性表,它的每个节点都包含一个数据项和一个指向下一个节点的指针,链表中各个节点的地址是不连续的。

下面是一个用于存储整形数据的链表节点结构:

1
2
3
4
5
struct Node
{
int data;
struct Node* next;
};
  • data:用于存储实际数据
  • next:用于连接当前节点的后继节点,存储的是下一个节点的地址(很多资料中将其称之为游标

静态链表是一种使用数组实现的链表,通常用于环境中无法使用指针的情况。这种结构在内存中是连续存储的,但节点的位置可以变化,因此称为静态链表。

静态链表的节点结构和链表类似,但是不完全相同,当前节点连接后继节点使用的是索引而不是指针。

下面是一个用于存储整形数据的链表节点结构:

1
2
3
4
5
struct Node
{
int data;
int next;
};
  • data:用于存储实际数据
  • next:使用索引的方式记录后继节点的位置

由于静态链表是一个数组,也就是说在存储数据之前元素对应的存储空间就已经存在了,此时我们就需要考虑以下几个问题:

  1. 如何判断当前节点是一个空闲节点?
  2. 如何判断当前节点是一个有效的数据节点?
  3. 如何判断当前节点是链表的尾节点?

由于链表的数据域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 遍历和搜索

关于静态链表中数据搜索,搜索的是节点的值,而不是它的位置。在搜索的时候需要分两步走:

  1. 根据链表节点的next域,从前往后依次访问各个节点
  2. 取出当前节点的data值,和要搜索的值进行比较
    • 相等:节点找到了,使用break或者return终止循环
    • 不相等:没找到需要的节点,继续向下遍历

下图描述的就是遍历静态数组的整个过程:

  • 通过头结点的next域记录的值找到第一个数据节点的位置
  • 通过第1个数据节点的next域记录的值找到第2个数据节点的位置
  • 通过第2个数据节点的next域记录的值找到第3个数据节点的位置
  • ……
  • 如果节点的next域值为-1,表示当前节点是最后一个数据节点,静态链表遍历结束。

上面的这个图乍一看乱糟糟,其实一点不乱,根据箭头的方向就能完成整个静态链表的遍历了。

掌握了静态链表的遍历,关于节点的搜索就非常简单了,只需要在遍历过程中再进行一次判断即可,在此就不再过多赘述了。

2.2 数据的插入

因为链表是线性表,在链表中插入数据的时候一般都是根据位置进行操作,添加节点有三种方式:

  1. 在链表的头部添加新节点
  2. 在链表的尾部添加新节点
  3. 在链表的中间位置添加新节点

在链表头部和尾部添加节点的操作都相对比较简单,因为我们可以将它们和插入合并到一起,也就是此处讲的插入节点的操作是在链表的任意位置插入新的节点

下面带大家一起分析一下在静态链表中插入数据的具体流程:

  1. 判断要插入的数据的位置,有效范围应该是:0 <= pos <= length
    • pos==0 新节点作为链表的第一个数据节点
    • pos==length 新节点添加到链表的尾部
    • 0 < pos < length 新节点插入到pos位置之前
  2. 遍历数组,找到一个没有存储数据的空闲节点,记作freeNode
    • 条件为:next == -2
  3. 判断静态链表是否满了,如果满了可以选择扩容或者拒绝插入数据
  4. 根据静态链表节点的next域遍历链表,找到pos-1位置的节点, 记作curNode
  5. 节点赋值并调整位置
    • freeNode 节点赋值
    • freeNode的后继节点设置为pos节点,该节点的索引值是存储在curNode.next里边的
    • curNode节点的后继节点设置为freeNode

下图是是一个静态链表,链表中的元素依次是:a->d->f->b->c

现在要求在静态链表的第三个节点位置插入新的元素 g,也就是说插入成功之后g就变成了第三个数据节点,原来的第三个数据节点变成了第四个数据节点。

  1. 首先需要根据链表节点的next域遍历链表,找到第三个节点的上一个节点,即第二个数据节点。

    • 根据头结点的next域找到的第一个数据节点为1号位置的节点

    • 根据1号位置节点的next域找到的第二个数据节点为5号位置的节点

  2. 给6号位置节点初始化为g,将它的后继设置为5号节点的后继(该节点为原来的第三个数据节点)

  3. 更新第二个数据节点的后继,让6号位置节点作为链表的第三个数据节点,也就是让五号位置节点的 next = 6

再次遍历这个静态链表,节点值依次为:a->d->g->f->b->c

到此为止新节点的插入操作就完成了。

2.3 数据的删除

删除静态链表中的元素,通常情况下还是根据位置来进行操作,操作步骤如下:

  1. 判断要删除的数据的位置,有效范围应该是:0 <= pos < length
    • pos==0 删除的是第一个数据节点
    • pos==length-1 删除的是尾部最后一个数据节点
    • 0 < pos < length-1 删除的是pos位置的数据节点
  2. 遍历静态链表,找到pos-1位置的节点,记作curNode
  3. 根据curNode找到要是删除的节点delNode ,它的位置 = curNode.next
  4. 链表节点重新连接curNode.next = delNode.next
  5. 将已删除节点delNodenext域标记为未使用,即delNode.next=2

接下来再通过图表的方式为大家举例说明,看下图,要求删除静态链表中的第二个数据节点,第二个数据节点也就是数组5号位置的节点,因为遍历链表节点的顺序为:a->d->f->b->c

遍历这个静态链表,找到第一个数据节点(要删除位置的节点的前驱)

重新进行链表节点的连接:第一个数据节点的后继 = 要删除的节点的后继,通过这个操作就从静态链表中删除了原来的第二个数据节点。

再次遍历这个静态链表,得到的节点顺序应该是:a->f->b->c。为了能够复用数组5号位置的元素,根据规则需要将它的next域修改为-2

3. 示例代码

3.1 头文件

StaticLinkList.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma once
#include <iostream>
using namespace std;


struct Node
{
int data;
int next;
};

// 静态链表列
class SLinkList
{
public:
SLinkList(int size);
~SLinkList();
// 插入元素, 把数据放到某个元素之前
bool insert(int pos, int data);
// 删除元素
void remove(int pos);
// 查找元素, 返回位置
int find(int data);
// 遍历元素
void display();
private:
Node* m_list = nullptr;
int m_size; // 链表的容量
int m_length; // 元素数量
};

3.2 源文件

StaticLinkList.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include "StaticLinkList.h"

SLinkList::SLinkList(int size) :
m_size(size),
m_length(0),
m_list(new Node[size])
{
m_list[0].next = -1;
for (int i = 1; i < size; ++i)
{
m_list[i].next = -2;
}
}

SLinkList::~SLinkList()
{
if (m_list)
{
delete[]m_list;
m_list = nullptr;
}
}

bool SLinkList::insert(int pos, int data)
{
if (pos < 0 || pos > m_size)
{
cout << "插入的位置不合法!" << endl;
return false;
}

int index = -1;
for (int i = 1; i < m_size; ++i)
{
if (m_list[i].next == -2)
{
index = i;
break;
}
}
if (index == -1)
{
cout << "链表已满, 无法插入新数据" << endl;
return false;
}

int current = 0;
int count = 0;
while (m_list[current].next != -1 && count < pos)
{
current = m_list[current].next;
count++;
}

m_list[index].data = data;
m_list[index].next = m_list[current].next;
m_list[current].next = index;
m_length++;
return true;
}

void SLinkList::remove(int pos)
{
if (pos < 0 || pos >= m_length)
{
cout << "删除的位置的不合法" << endl;
return;
}
int current = 0;
int count = 0;
while (m_list[current].next != -1 && count < pos)
{
current = m_list[current].next;
count++;
}

int delPos = m_list[current].next;
m_list[current].next = m_list[delPos].next;
m_list[delPos].data = 0;
m_list[delPos].next = -2;
m_length--;
}

int SLinkList::find(int data)
{
int current = m_list[0].next;
int pos = 0;
while (current != -1)
{
if (data == m_list[current].data)
{
return pos;
}
current = m_list[current].next;
pos++;
}
return -1;
}

void SLinkList::display()
{
if (m_list[0].next == -1)
{
cout << "当前链表是一个空链表" << endl;
return;
}
int current = m_list[0].next;
while (current != -1)
{
cout << m_list[current].data << " ";
current = m_list[current].next;
}
cout << endl;
}

int main()
{
SLinkList ls(30);
ls.insert(0, 10);
ls.insert(0, 100);
ls.insert(1, 30);
ls.insert(1, 33);
ls.insert(2, 66);
ls.insert(5, 88);
ls.insert(6, 99);
ls.display();

ls.remove(0);
ls.display();
ls.remove(5);
ls.remove(1);
ls.display();

int pos = ls.find(88);
cout << "pos = " << pos << endl;

return 0;
}

程序输出的结果为:

1
2
3
4
100 33 66 30 10 88 99
33 66 30 10 88 99
33 30 10 88
pos = 3

在上面的示例程序中,使用的是一个静态数组,当可用空间用完之后就拒绝再次往静态链表中添加数据了。当然,也可以将这个数组修改为动态数组,这样这样静态链表也就没有了最大存储上限。关于如何实现一个动态数组在上一节中已经做了详细讲解,大家可以自行考古。

4. 静态链表和数组

静态链表和数组的本质是相同的,但是在使用方式上又有所不同,下面就给大家总结一下二者的优缺点:

  1. 插入删除操作,静态链表效率高
    • 静态链表只需要修改对应节点的next域的值,需不要移动元素
    • 数组在插入新节点需要大量元素后移,删除节点需要大量元素前移
  2. 访问指定位置的元素,数组效率高
    • 静态链表需要遍历才能找到这个节点
    • 数组通过下标就可以找到该节点了
  3. 默认情况下内存大小是固定的
    • 申请的内存空间大,但是数据量少,浪费存储空间
    • 申请的内存空间小,但是数据量大,内存不够用

静态链表和数组是对同一块连续内存的两种不同使用方式,二者没有孰优孰劣之分,作为一名合格的程序猿要做的就是具体问题具体分析,从众多解决方案中找出一个最优解。