邓公数据结构与算法3-列表

事实上 2017 年的这个时候我看了一遍浙大陈越老师的《数据结构》,并且有详细的做笔记。但现在回过头来看,这些好像基本上又都忘了。。问题应该是在于学过之后不怎么使用,当时也只是看了视频,而没有去刷题。

所以这次总结下经验,只看视频并做笔记是远远不够的。视频的缺陷在于不像书本那样,能够随意的翻到你不懂或者模糊的知识点。所以,这次我应该做的是,把视频快速过一遍,记下老师说的知识点,然后对照书本去敲代码。更更更重要的是,不断的练习。

列表(链表)

这部分内容的结构跟 向量 那一章是一样的。先介绍操作接口,然后逐个介绍它们的实现。

列表,也就是链表,与向量对称且互补。

向量: 循秩访问 call-by-rank
列表: 循位置访问 call-by-position

双向链表和单向链表。

邓老师讲的是双向链表,所以含有 头节点 header 和 尾节点 trailer。

header 和 trailer 是与生俱来的,也是不可见的。所以初始化的链表节点中含有两个空节点。

双向链表的实现

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
# ifndef DOUBLE_LINK_HPP
# define DOUBLE_LINK_HPP
/*
双向链表的节点结构
*/
template <typename T>
struct Node
{
public:
Node()= default;
Node(T value, Node<T>* preptr, Node<T>* nextptr)
:_value(value), pre_ptr(preptr), next_ptr(nextptr){}

public:
T _value;
Node<T>* pre_ptr;
Node<T>* next_ptr;
};

/*
* 双向链表类
*/
template<typename T>
class DoubleLink
{
public:
typedef Node<T>* pointer;
public:
DoubleLink();
~DoubleLink(){};
public:
Node<T>* insert(int index, T value);
Node<T>* insert_front(T value);
Node<T>* insert_last(T value);

Node<T>* del(int index);
Node<T>* delete_front();
Node<T>* delete_last();

bool isEmpty();
int size();

T get(int index);
T get_front();
T get_last();
Node<T>* getHead();

private:
Node<T>* phead;
int count;
private :
Node<T>* getNode(int index);
};
/*
* 构造函数
*
*/
template <typename T>
DoubleLink<T>::DoubleLink()
{
phead = new Node<T>(0, NULL, NULL);
phead->next_ptr = phead;
phead->pre_ptr = phead;
count = 0;
};
template<typename T>
Node<T>* DoubleLink<T>::getHead()
{
return phead;
}

/*
*返回链表长度
*/
template <typename T>
int DoubleLink<T>::size()
{
return count;
}
/*
获取指定下标的元素
*/
template <typename T>
Node<T>* DoubleLink<T>::getNode(int index)
{
if (index >= count || index < 0)
return NULL;

if (index<=count / 2) //如果在前半部分
{
Node<T>* pnode = phead->next_ptr;
while (index)
{
pnode = pnode->next_ptr;
index--;
}
return pnode;
} //在后半部分

index = count - index-1;
Node<T>* pnode = phead->pre_ptr;
while (index)
{
pnode = pnode->pre_ptr;
index--;
}
return pnode;
};
/*
*将新节点插到第一个位置
*/
template <typename T>
Node<T>* DoubleLink<T>::insert_front(T value)
{
Node<T>* newNode = new Node<int>(value, phead, phead->next_ptr);
phead->next_ptr ->pre_ptr= newNode;
phead->next_ptr = newNode;
count++;
return newNode;
};
/*
*将新节点插到链表尾部
*/
template <typename T>
Node<T>* DoubleLink<T>::insert_last(T value)
{
Node<T> * newNode = new Node<int>(value, phead->pre_ptr, phead);
phead->pre_ptr->next_ptr = newNode;
phead->pre_ptr = newNode;
count++;
return newNode;
};
/*
*将节点位置插到index位置之前
*/

template <typename T>
Node<T>* DoubleLink<T>::insert(int index, T value)
{
if (index == 0)
return insert_front(value);

Node<T>* pNode = getNode(index);
if (pNode == NULL)
return NULL;
Node<T>* newNode = new Node<T>(value, pNode->pre_ptr, pNode);
pNode->pre_ptr->next_ptr = newNode;
pNode->pre_ptr = newNode;
count++;

return newNode;
};
/*
*删除链表第一个节点
*返回删除后链表第一个节点
*/
template<typename T>
Node<T>* DoubleLink<T>::delete_front()
{
if (count == 0) //空树,返回NULL
{
return NULL;
}
Node<T>* pnode = phead->next_ptr;
phead->next_ptr = pnode->next_ptr;
pnode->next_ptr->pre_ptr = phead;
delete pnode;
count--;
return phead->next_ptr;
};
/*
*删除链表的末尾节点
*返回删除后链表尾部元素
*/
template<typename T>
Node<T>* DoubleLink<T>::delete_last()
{
if (count == 0)
{
return NULL;
}
Node<T>*pnode = phead->pre_ptr;
pnode->pre_ptr->next_ptr = phead;
phead->pre_ptr = pnode->pre_ptr;
delete pnode;
count--;
return phead->pre_ptr;
}
/*
*删除指定位置的元素
*
*/
template <typename T>
Node<T>* DoubleLink<T>::del(int index)
{
if (index == 0)
return delete_front();
if (index == count - 1)
return delete_last();
if (index >= count)
return NULL;
Node<T>* pnode = getNode(index);
pnode->pre_ptr->next_ptr = pnode->next_ptr;
pnode->next_ptr->pre_ptr = pnode->pre_ptr;

Node<T>* ptemp = pnode->pre_ptr;
delete pnode;
count--;
return ptemp;
};

template <typename T>
bool DoubleLink<T>::isEmpty()
{
return count == 0;
};
/*
*获取第一个节点的值
*/
template<typename T>
T DoubleLink<T>::get_front()
{
return phead->next_ptr->_value;
};
/*
*获取最后一个节点的值
*/
template <typename T>
T DoubleLink<T>::get_last()
{
return phead->pre_ptr->_value;
};
/*
*获取指定位置节点的值
*/
template <typename T>
T DoubleLink<T>::get(int index)
{
Node<T> pnode = getNode(index);
return pnode->_value;
};
# endif

排序

leetcode 148: https://leetcode.com/problems/sort-list/submissions/

选择排序

实际上 冒泡排序 也可以看做是选择排序,不同的是,在选择最大元素的时候,冒泡排序每比较一次都会进行一次交换,这样亦步亦趋的方式增加了消耗。而选择排序,只是进行比较,每一趟遍历只交换一次。

邓老师这里的代码会比较复杂,是基于双向链表实现的。这里我们只需要理解算法思想。

列表的排序算法, 对于起始于位置 p 的 n 个元素的排序。

1
2
3
4
5
6
7
8
9
10
11
#define ListNodePosi(T) ListNode<T>* //列表节点位置
template <typename T> //列表的选择排序算法:对起始于位置p的n个元素排序
void List<T>::selectionSort ( ListNodePosi(T) p, int n ) { //valid(p) && rank(p) + n <= size
ListNodePosi(T) head = p->pred; ListNodePosi(T) tail = p;
for ( int i = 0; i < n; i++ ) tail = tail->succ; //待排序区间为(head, tail)
while ( 1 < n ) { //在至少还剩两个节点之前,在待排序区间内
ListNodePosi(T) max = selectMax ( head->succ, n ); //找出最大者(歧义时后者优先)
insertB ( tail, remove ( max ) ); //将其移至无序区间末尾(作为有序区间新的首元素)
tail = tail->pred; n--;
}
}
1
2
3
4
5
6
7
8
template <typename T> //从起始于位置p的n个元素中选出最大者
ListNodePosi(T) List<T>::selectMax ( ListNodePosi(T) p, int n ) {
ListNodePosi(T) max = p; //最大者暂定为首节点p
for ( ListNodePosi(T) cur = p; 1 < n; n-- ) //从首节点p出发,将后续节点逐一与max比较
if ( !lt ( ( cur = cur->succ )->data, max->data ) ) //若当前元素不小于max,则
max = cur; //更新最大元素位置记录
return max; //返回最大节点位置
}

插入排序

归并排序

对列表的归并排序,相比向量要更复杂些,主要在怎么找到中间点
- 归并排序的整体思想
- 找到一个链表的中间节点的方法
- 合并两个已排好序的链表为一个新的有序链表

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getMid(ListNode* head)
{
if (!head) return NULL;
if (!head->next) return head;
ListNode* slow = head;
ListNode* fast = head->next;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

ListNode* mergeLists(ListNode* l1, ListNode* l2)
{
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
ListNode dummy(-1);
ListNode *tail = &dummy;

while(l1 && l2)
{
if (l1->val < l2->val)
{
tail->next = l1;
tail = tail->next;
l1 = l1->next;
}
else
{
tail->next = l2;
tail = tail->next;
l2 = l2->next;
}
}
if (l1) tail->next = l1;
if (l2) tail->next = l2;
return dummy.next;
}


ListNode* sortList(ListNode* head)
{
if (!head) return NULL;
if (head->next==NULL) return head;
// 找到中间点
ListNode *mid = getMid(head);
// 将链表分成两个子链表
ListNode *nextPart = NULL;
if (mid)
{
nextPart = mid->next;
mid->next = NULL;
}
return mergeLists(sortList(head), sortList(nextPart));
}
};