数据结构之线性表（链表实现）_1. 基于链表的线性表实现

数据结构之线性表（链表实现）

引言

在数据结构的世界里，链表是一种重要的非连续存储线性数据结构，其特点是动态分配空间并利用指针链接各个元素。链表是一种动态数据结构，它通过节点之间的指针链接来实现元素之间的关联。与数组不同，链表不需要预先分配连续的内存空间，因此在插入和删除操作上具有较高的灵活性。本文将详细介绍一个基于 C++ 模板编程技术实现的链表类—— Chain<T>，它扩展自抽象基类 LinearListForLinkedList<T>，以提供一种高效、灵活的链式数据结构解决方案。线性表是一种基本的数据结构，它是由n（n>=0）个相同类型元素组成的有序集合。在 C++ 中，我们可以使用链表来实现线性表，以提供更灵活的数据存储和操作方式。

注意⚠️：
运行环境：“intelliSenseMode”: “macos-clang-x64”
C++ 版本： “cppStandard”: “c++17”
编译器：clang-x64

线性表的链表实现

要使用链表实现线性表，我们需要定义一个链表节点结构，用于存储线性表中的元素。通常，我们可以使用一个指向元素类型的数据成员和一个指向下一个节点的指针来实现链表节点。其实可以使用 struct 来实现，但是我觉得为了统一就使用了 class 来实现，实际上区别就是访问权限的差异。

1. 链表节点定义

首先，我们需要定义链表中的节点结构。每个节点包含两个部分：存储的数据（类型为T）和指向下一个节点的指针。

#pragma once
// 链表节点

template <class T>
class ChainNode
{
public:
    // 存储的数据
    T data;

    // 指向下一个节点
    ChainNode<T> *next;

public:
    // 默认构造函数
    ChainNode() : next(nullptr) {}

    // 拷贝构造函数
    ChainNode(T const &data) : data(data), next(nullptr) {}

    // 带参数构造函数
    ChainNode(T const &data, ChainNode<T> *next) : data(data), next(next) {}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2. 基于链表的线性表类设计

接下来创建名为 Chain 的类，继承自抽象的线性表接口或实现一些基本的操作方法，如插入、删除和访问等。和上一篇博客一样，也需要定义抽象数据结构，里面包含的抽象方法一样，如下所示：

#pragma once

template <class T>
class LinearListForLinkedList
{
public:
    // 析构函数
    virtual ~LinearListForLinkedList() = default;

    // ADT 方法
public:
    // 返回 true，表示列表为空
    virtual bool empty() const = 0;

    // 返回列表中元素的个数
    virtual int size() const = 0;

    // 返回第 index 个元素
    virtual T &get(int theIndex) const = 0;

    // 返回元素 elem 列表中第一次出现的下标
    virtual int indexOf(T const &elem) const = 0;

    // 在列表中插入元素 elem
    virtual void insert(int index, T const &elem) = 0;

    // 在列表中删除第 index 个元素
    virtual void erase(int index) = 0;

    // 清空列表
    virtual void clear() = 0;

    // 打印列表
    virtual void print() = 0;
};

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

接下来，我们可以定义一个线性表类，它包含一个指向头节点的指针和一个计数器来记录线性表中元素的数量。

#pragma once

#include "chainNode.h"
#include "linearListForLinkedList.h"

template <class T>
class Chain : public LinearListForLinkedList<T>
{
protected:
    // 指向线性表的第一个节点的指针
    ChainNode<T> *firstNode;

    // 链表的长度
    int listSize;

protected:
    // 检查索引是否合法
    void checkIndex(int theIndex) const;

public:
    // 构造函数
    Chain();

    // 拷贝构造函数
    Chain(Chain const &other);

    // 析构函数
    virtual ~Chain();

    // ADT 方法
public:
    // 返回 true，表示列表为空
    virtual bool empty() const;

    // 返回列表中元素的个数
    virtual int size() const;

    // 返回第 index 个元素
    virtual T &get(int theIndex) const;

    // 返回元素 elem 列表中第一次出现的下标
    virtual int indexOf(T const &elem) const;

    // 在列表中插入元素 elem
    virtual void insert(int theIndex, T const &elem);

    // 在列表中删除第 index 个元素
    virtual void erase(int theIndex);

    // 清空列表
    virtual void clear();

    // 打印列表
    virtual void print();
};

// 检查索引是否合法
template <class T>
void Chain<T>::checkIndex(int theIndex) const
{
    if (theIndex < 0 || theIndex >= listSize)
    {
        throw std::out_of_range("Index out of range");
    }
}

// 构造函数
template <class T>
Chain<T>::Chain()
{
    firstNode = nullptr;
    listSize = 0;
}

// 拷贝构造函数
template <class T>
Chain<T>::Chain(Chain const &other)
{
    listSize = other.listSize;

    if (listSize == 0)
    {
        firstNode = nullptr;
    }
    else
    {
        // 链表有数据

        // 构造一个指针指向被拷贝的链表的第一个节点
        ChainNode<T> *p = other.firstNode;

        // 生成第一个节点
        firstNode = new ChainNode<T>(p->data);

        // 第一个节点指向下一个，因为 firstNode 已经被生成了。
        // 所以不需要重新构造一个 chainNode
        p = p->next;

        // 构造剩余的节点
        // 之所以不直接使用 firstNode 而是用 lastNode，是因为 firstNode
        // 在这里保持不变，它始终指向原链表的头节点。而 lastNode 则随着循环
        // 不断更新，用于维护新链表的构造进度。通过这种方式，我们可以确保每次
        // 循环都在正确的位置添加新的节点，最终构建出与原链表具有相同元素顺序的新链表。
        ChainNode<T> *lastNode = firstNode;
        while (p != nullptr)
        {
            // 生成剩余的元素
            lastNode->next = new ChainNode<T>(p->data);
            lastNode = lastNode->next;
            p = p->next;
        }

        // 最后一个元素是 nullptr
        lastNode->next = nullptr;
    }
}

// 析构函数
template <class T>
Chain<T>::~Chain()
{
    clear();
}

// 返回 true，表示列表为空
template <class T>
bool Chain<T>::empty() const
{
    return firstNode == nullptr;
}

// 返回列表中元素的个数
template <class T>
int Chain<T>::size() const
{
    return listSize;
}

// 返回第 index 个元素
template <class T>
T &Chain<T>::get(int theIndex) const
{
    // 检查索引是否合法 0 <= theIndex < listSize
    checkIndex(theIndex);

    // 找到 theIndex 位置的元素。
    int cnt = 0;

    // 用一个临时节点保存第一个节点
    auto tempNode = firstNode;

    // 循环找 theIndex 元素
    while (tempNode != nullptr)
    {
        if (cnt == theIndex)
        {
            break;
        }
        tempNode = tempNode->next;

        // 如果是第 0 个应该也要正确处理
        ++cnt;
    }

    return tempNode->data;
}

// 返回元素 elem 列表中第一次出现的下标
template <class T>
int Chain<T>::indexOf(T const &elem) const
{
    // 用一个临时节点保存第一个节点
    auto tempNode = firstNode;
    int cnt = 0;

    // 循环查找
    while (tempNode != nullptr)
    {
        if (tempNode->data == elem)
        {
            return cnt;
        }

        // 保存一下下一个节点的地址
        tempNode = tempNode->next;

        // 如果是第 0 个应该也要正确处理
        ++cnt;
    }

    // 没找到
    return -1;
}

// 在列表中插入元素 elem
template <class T>
void Chain<T>::insert(int theIndex, T const &elem)
{
    // 检查索引是否合法
    if (theIndex < 0 || theIndex > listSize)
    {
        throw std::out_of_range("Index out of range");
    }

    // 1.0 如果在第一个位置插入。
    // 2.0 中间位置插入
    // 3.0 如果在最后一个位置插入。

    if (theIndex == 0)
    {
        // 在第一个位置插入
        firstNode = new ChainNode<T>(elem, firstNode);
    }
    else
    {
        // 在中间位置插入
        // 用一个临时节点保存第一个节点
        auto tempNode = firstNode;

        // 循环找到插入位置
        for (int i = 0; i < theIndex - 1; ++i)
        {
            tempNode = tempNode->next;
        }

        // 找到 index 位置，插入节点
        tempNode->next = new ChainNode<T>(elem, tempNode->next);
    }

    // 增加元素个数
    ++listSize;
}

// 在列表中删除第 index 个元素
template <class T>
void Chain<T>::erase(int theIndex)
{
    // 检查索引是否合法
    checkIndex(theIndex);

    // 1.0 如果删除第一个元素
    // 2.0 如果删除中间元素
    // 3.0 如果删除最后一个元素

    if (theIndex == 0)
    {
        // 删除第一个元素
        auto tempNode = firstNode;
        firstNode = firstNode->next;

        // 删除元素
        delete tempNode;
    }
    else
    {
        // 删除中间元素
        // 用一个临时节点保存第一个节点
        auto tempNode = firstNode;

        // 循环找到插入位置
        for (int i = 0; i < theIndex - 1; ++i)
        {
            tempNode = tempNode->next;
        }

        // 找到index 位置，删除节点
        auto node = tempNode->next;
        tempNode->next = tempNode->next->next;

        // 删除节点
        delete node;
    }

    // 减少元素个数
    --listSize;
}

// 清空列表
template <class T>
void Chain<T>::clear()
{
    // 清空链表
    while (firstNode != nullptr)
    {
        // 保存下一个链表节点，避免删除
        // 一个节点时候丢失整个链表信息
        auto nextNode = firstNode->next;

        // 删除一个节点
        delete firstNode;

        // 记录下一个链表指向的信息
        firstNode = nextNode;
    }

    // 重置链表大小
    listSize = 0;
}

// 打印列表
template <class T>
void Chain<T>::print()
{
    auto tempNode = firstNode;

    while (tempNode != nullptr)
    {
        std::cout << tempNode->data << " ";
        tempNode = tempNode->next;
    }

    // 换行
    std::cout << std::endl;
}
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314

3. 重要方法的实现

erase 方法用于在线性表中删除指定位置的元素。该方法首先检查索引是否合法，然后定位到要删除的节点，并通过更新前驱节点的 next 指针完成删除操作。除了 erase 方法外，还需要实现 insert 方法（已在问题描述中给出）、构造函数、析构函数以及下标运算符重载等功能以支持完整的线性表操作。

在使用链表实现线性表时，erase 方法和 insert 方法是非常重要的操作，但需要注意以下几点：

1. 内存管理：在链表中，节点是动态分配的，因此在 erase 方法中删除节点时，需要释放该节点的内存。同样，在 insert 方法中插入节点时，需要分配新的节点内存。在操作过程中，需要确保不会出现内存泄漏或野指针问题。
2. 异常安全性：在 erase 方法和 insert 方法中，如果在操作过程中发生异常（如内存分配失败），需要确保程序能够安全地恢复到操作前的状态。这需要使用异常安全编程技巧，如使用 RAII（Resource Acquisition Is Initialization） 技术管理资源。
3. 效率考虑：在链表中，erase 方法和 insert 方法的时间复杂度都是 O(1)，但是需要找到要操作的节点的前一个节点。因此，如果频繁地在链表中间插入或删除节点，会导致效率问题。如果需要频繁进行这种操作，可能需要考虑使用其他数据结构，如双向链表或循环链表。
4. 边界情况处理：在 erase 方法和 insert 方法中，需要处理一些边界情况，如删除头节点或尾节点，或者在空链表中插入或删除节点。在这些情况下，需要特别注意对链表指针的处理，以确保链表的正确性。

总结

使用链表实现的线性表是一种常见的数据结构，它通过链式存储方式来存储元素，每个元素都包含一个指向下一个元素的指针。相比于使用数组实现的线性表，链表在插入和删除操作上更加灵活，因为它们只需要更改相邻元素的指针即可，而不需要移动元素。但是，链表的随机访问性能较差，因为它们需要遍历链表来访问特定位置的元素。 在使用链表实现的线性表中，需要注意一些关键点。首先，在插入和删除操作中，需要特别注意处理好指针的更改，以避免出现内存泄漏或访问非法内存的问题。其次，在实现线性表的其他操作时，需要注意链表的遍历和访问方式，以确保代码的正确性和高效性。 总的来说，使用链表实现的线性表是一种灵活且有用的数据结构，但需要仔细处理好相关操作的实现细节。

后记

在分享技术时，虽力求详尽与精确，但也深知技术之深广与个人认知有限。我持谦逊态度，欢迎所有程序员朋友的指正与交流，共同在技术探索的道路上携手前行。对于任何疏漏之处，请大家不吝赐教。