欢迎来到我的主页!
0%

数据结构及实现：数组和链表

发表于 更新于 分类于
本文字数： 8.8k 阅读时长 ≈ 8 分钟

引言：线性表是一种线性结构，它是具有相同类型的n(n≥0)个数据元素组成的有限序列。本章先介绍线性表的几个基本组成部分：数组、单向链表、双向链表；随后给出双向链表C++的实现。

数组

数组有上界和下界，数组的元素在上下界内是连续的。

存储10,20,30,40,50的数组的示意图如下：

231243264043298.jpg

数组的特点是：数据是连续的；随机访问速度快。

数组中稍微复杂一点的是多维数组和动态数组。对于C语言而言，多维数组本质上也是通过一维数组实现的。至于动态数组，是指数组的容量能动态增长的数组；对于C语言而言，若要提供动态数组，需要手动实现；而对于C++而言，STL提供了Vector；

单向链表

单向链表(单链表)是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。

单链表的示意图如下：

单链表.jpg

表头为空，表头的后继节点是"节点10"(数据为10的节点)，“节点10"的后继节点是"节点20”(数据为10的节点)，…

单链表删除节点

删除节点.jpg

删除"节点30"
删除之前：“节点20” 的后继节点为"节点30"，而"节点30" 的后继节点为"节点40"。
删除之后：“节点20” 的后继节点为"节点40"。

单链表添加节点

添加节点.jpg

在"节点10"与"节点20"之间添加"节点15"
添加之前：“节点10” 的后继节点为"节点20"。
添加之后：“节点10” 的后继节点为"节点15"，而"节点15" 的后继节点为"节点20"。

单链表的特点是：节点的链接方向是单向的；相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很高。

双向链表

双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

双链表的示意图如下：

双链表.jpg

表头为空，表头的后继节点为"节点10"(数据为10的节点)；“节点10"的后继节点是"节点20”(数据为10的节点)，“节点20"的前继节点是"节点10”；“节点20"的后继节点是"节点30”，“节点30"的前继节点是"节点20”；…；末尾节点的后继节点是表头。

双链表删除节点

双链表删除.jpg

删除"节点30"
删除之前：“节点20"的后继节点为"节点30”，“节点30” 的前继节点为"节点20"。“节点30"的后继节点为"节点40”，“节点40” 的前继节点为"节点30"。
删除之后：“节点20"的后继节点为"节点40”，“节点40” 的前继节点为"节点20"。

双链表添加节点

双链表添加节点.jpg

在"节点10"与"节点20"之间添加"节点15"
添加之前：“节点10"的后继节点为"节点20”，“节点20” 的前继节点为"节点10"。
添加之后：“节点10"的后继节点为"节点15”，“节点15” 的前继节点为"节点10"。“节点15"的后继节点为"节点20”，“节点20” 的前继节点为"节点15"。

C++实现双链表

双向链表文件(DoubleLink.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
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
#ifndef DOUBLE_LINK_HXX
#define DOUBLE_LINK_HXX

#include <iostream>
using namespace std;

template<class T>
struct DNode
{
    public:
        T value;
        DNode *prev;
        DNode *next;
    public:
        DNode() { }
        DNode(T t, DNode *prev, DNode *next) {
            this->value = t;
            this->prev  = prev;
            this->next  = next;
           }
};

template<class T>
class DoubleLink
{
    public:
        DoubleLink();
        ~DoubleLink();

        int size();
        int is_empty();

        T get(int index);
        T get_first();
        T get_last();

        int insert(int index, T t);
        int insert_first(T t);
        int append_last(T t);

        int del(int index);
        int delete_first();
        int delete_last();

    private:
        int count;
        DNode<T> *phead;
    private:
        DNode<T> *get_node(int index);
};

template<class T>
DoubleLink<T>::DoubleLink() : count(0)
{
    // 创建“表头”。注意：表头没有存储数据！
    phead = new DNode<T>();
    phead->prev = phead->next = phead;
    // 设置链表计数为0
    //count = 0;
}

// 析构函数
template<class T>
DoubleLink<T>::~DoubleLink()
{
    // 删除所有的节点
    DNode<T>* ptmp;
    DNode<T>* pnode = phead->next;
    while (pnode != phead)
    {
        ptmp = pnode;
        pnode=pnode->next;
        delete ptmp;
    }

    // 删除"表头"
    delete phead;
    phead = NULL;
}

// 返回节点数目
template<class T>
int DoubleLink<T>::size()
{
    return count;
}

// 返回链表是否为空
template<class T>
int DoubleLink<T>::is_empty()
{
    return count==0;
}

// 获取第index位置的节点
template<class T>
DNode<T>* DoubleLink<T>::get_node(int index)
{
    // 判断参数有效性
    if (index<0 || index>=count)
    {
        cout << "get node failed! the index in out of bound!" << endl;
        return NULL;
    }

    // 正向查找
    if (index <= count/2)
    {
        int i=0;
        DNode<T>* pindex = phead->next;
        while (i++ < index) {
            pindex = pindex->next;
        }

        return pindex;
    }

    // 反向查找
    int j=0;
    int rindex = count - index -1;
    DNode<T>* prindex = phead->prev;
    while (j++ < rindex) {
        prindex = prindex->prev;
    }

    return prindex;
}

// 获取第index位置的节点的值
template<class T>
T DoubleLink<T>::get(int index)
{
    return get_node(index)->value;
}

// 获取第1个节点的值
template<class T>
T DoubleLink<T>::get_first()
{
    return get_node(0)->value;
}

// 获取最后一个节点的值
template<class T>
T DoubleLink<T>::get_last()
{
    return get_node(count-1)->value;
}

// 将节点插入到第index位置之前
template<class T>
int DoubleLink<T>::insert(int index, T t)
{
    if (index == 0)
        return insert_first(t);

    DNode<T>* pindex = get_node(index);
    DNode<T>* pnode  = new DNode<T>(t, pindex->prev, pindex);
    pindex->prev->next = pnode;
    pindex->prev = pnode;
    count++;

    return 0;
}

// 将节点插入第一个节点处。
template<class T>
int DoubleLink<T>::insert_first(T t)
{
    DNode<T>* pnode  = new DNode<T>(t, phead, phead->next);
    phead->next->prev = pnode;
    phead->next = pnode;
    count++;

    return 0;
}

// 将节点追加到链表的末尾
template<class T>
int DoubleLink<T>::append_last(T t)
{
    DNode<T>* pnode = new DNode<T>(t, phead->prev, phead);
    phead->prev->next = pnode;
    phead->prev = pnode;
    count++;

    return 0;
}

// 删除index位置的节点
template<class T>
int DoubleLink<T>::del(int index)
{
    DNode<T>* pindex = get_node(index);
    pindex->next->prev = pindex->prev;
    pindex->prev->next = pindex->next;
    delete pindex;
    count--;

    return 0;
}

// 删除第一个节点
template<class T>
int DoubleLink<T>::delete_first()
{
    return del(0);
}

// 删除最后一个节点
template<class T>
int DoubleLink<T>::delete_last()
{
    return del(count-1);
}

#endif

双向链表测试文件(DlinkTest.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
#include <iostream>
#include "DoubleLink.h"
using namespace std;

// 双向链表操作int数据
void int_test()
{
    int iarr[4] = {10, 20, 30, 40};

    cout << "\n----int_test----" << endl;
    // 创建双向链表
    DoubleLink<int>* pdlink = new DoubleLink<int>();

    pdlink->insert(0, 20);        // 将 20 插入到第一个位置
    pdlink->append_last(10);    // 将 10 追加到链表末尾
    pdlink->insert_first(30);    // 将 30 插入到第一个位置

    // 双向链表是否为空
    cout << "is_empty()=" << pdlink->is_empty() <<endl;
    // 双向链表的大小
    cout << "size()=" << pdlink->size() <<endl;

    // 打印双向链表中的全部数据
    int sz = pdlink->size();
    for (int i=0; i<sz; i++)
        cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;
}

void string_test()
{
    string sarr[4] = {"ten", "twenty", "thirty", "forty"};

    cout << "\n----string_test----" << endl;
    // 创建双向链表
    DoubleLink<string>* pdlink = new DoubleLink<string>();

    pdlink->insert(0, sarr[1]);        // 将 sarr中第2个元素 插入到第一个位置
    pdlink->append_last(sarr[0]);    // 将 sarr中第1个元素  追加到链表末尾
    pdlink->insert_first(sarr[2]);    // 将 sarr中第3个元素  插入到第一个位置

    // 双向链表是否为空
    cout << "is_empty()=" << pdlink->is_empty() <<endl;
    // 双向链表的大小
    cout << "size()=" << pdlink->size() <<endl;

    // 打印双向链表中的全部数据
    int sz = pdlink->size();
    for (int i=0; i<sz; i++)
        cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;
}

struct stu
{
    int id;
    char name[20];
};

static stu arr_stu[] =
{
    {10, "sky"},
    {20, "jody"},
    {30, "vic"},
    {40, "dan"},
};
#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )

void object_test()
{
    cout << "\n----object_test----" << endl;
    // 创建双向链表
    DoubleLink<stu>* pdlink = new DoubleLink<stu>();

    pdlink->insert(0, arr_stu[1]);        // 将 arr_stu中第2个元素 插入到第一个位置
    pdlink->append_last(arr_stu[0]);    // 将 arr_stu中第1个元素  追加到链表末尾
    pdlink->insert_first(arr_stu[2]);    // 将 arr_stu中第3个元素  插入到第一个位置

    // 双向链表是否为空
    cout << "is_empty()=" << pdlink->is_empty() <<endl;
    // 双向链表的大小
    cout << "size()=" << pdlink->size() <<endl;

    // 打印双向链表中的全部数据
    int sz = pdlink->size();
    struct stu p;
    for (int i=0; i<sz; i++)
    {
        p = pdlink->get(i);
        cout << "pdlink("<<i<<")=[" << p.id << ", " << p.name <<"]" <<endl;
    }
}


int main()
{
    int_test();        // 演示向双向链表操作“int数据”。
    string_test();    // 演示向双向链表操作“字符串数据”。
    object_test();    // 演示向双向链表操作“对象”。

    return 0;
}

示例说明

在上面的示例中，我将双向链表的"声明"和"实现"都放在头文件中。而编程规范告诫我们：将类的声明和实现分离，在头文件(.h文件或.hpp)中尽量只包含声明，而在实现文件(.cpp文件)中负责实现！
那么为什么要这么做呢？这是因为，在双向链表的实现中，采用了模板；而C++编译器不支持对模板的分离式编译！简单点说，如果在DoubleLink.h中声明，而在DoubleLink.cpp中进行实现的话；当我们在其他类中创建DoubleLink的对象时，会编译出错。

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
----int_test----
is_empty()=0
size()=3
pdlink(0)=30
pdlink(1)=20
pdlink(2)=10

----string_test----
is_empty()=0
size()=3
pdlink(0)=thirty
pdlink(1)=twenty
pdlink(2)=ten

----object_test----
is_empty()=0
size()=3
pdlink(0)=[30, vic]
pdlink(1)=[20, jody]
pdlink(2)=[10, sky]

总结

对链表的理论知识进行简单介绍，给出C++实现，并对实现代码进行了测试。

本文转载自：https://www.cnblogs.com/skywang12345/p/3561803.html