数据结构 - Lesson 2.1


本节课的内容较多,又牵扯到实际代码,因此分为基本内容和实践代码两部分

#基本内容

#实践代码

#顺序表

#简单的C++(zao)实(lun)现(zi)

一个省略部分实现的C++实现的框架如下所示:

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
// 第一次写纯C++程序,如有不当,欢迎指出
#ifndef seqlist_hpp
#define seqlist_hpp
#include <iostream>
#include <stdlib.h>
template <class T>
class SeqList {
public:
int max_length;
T *data;
int real_lengh;
SeqList(int);
~SeqList();
bool AddElement(T);
void PrintList() const;
bool FindInSortedList(T, int &) const;
bool FindElement(T, int &) const;
void SortList();
bool InsertElement(int);
bool DelElement(int);
bool PartList(int);
bool ValidIndex(int) const;
bool SwapElement(int, int);
};
template <class T>
bool SeqList<T>::SwapElement(int x, int y) { // swap two elements by given index
if (!(ValidIndex(x) && ValidIndex(y))) {
return false;
}
T tmp;
tmp = data[x];
data[x] = data[y];
data[y] = tmp;
return true;
}
template <class T>
bool SeqList<T>::ValidIndex(int index) const { // check if a given index is valid
if (index < 0 index >= real_lengh) {
return false;
}
return true;
}
// allocate memory for seq list
template <class T>
SeqList<T>::SeqList(int length) : max_length(length) {
data = (T *) malloc(sizeof(T) * length);
real_lengh = 0;
}
// destroy the list object
template <class T>
SeqList<T>::~SeqList() {
free(data);
}
template <class T>
bool SeqList<T>::AddElement(T element) { // add an element at the tail
if (real_lengh >= max_length) {
return false;
}
data[real_lengh] = element;
real_lengh++;
return true;
}
template <class T>
void SeqList<T>::PrintList() const {
for (int i = 0; i < real_lengh; ++i) {
std::cout << data[i] << ' ';
}
std::cout << std::endl;
}
#endif /* seqlist_hpp */

这里我们使用模版来实现顺序表可以存储不同类型的数据对象。使用构造函数和析构函数来实现顺序表的存储和初始化和销毁。

#排序

由于技艺不精,这里暂且实现一个简单的冒泡排序,为下面有序表的二分查找做准备:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T>
void SeqList<T>::SortList() {
int tmp = 0;
for (int i = 0; i < real_lengh; ++i) {
for (int j = i; j < real_lengh; ++j) {
if (data[i] > data[j]) {
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
}

时间复杂度O(n^2),空间复杂度为O(1).

#有序表二分查找

既然已经搭起了框架,就要开始实现一些方法了,首先尝试实现有序表的二分查找算法。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T>
bool SeqList<T>::FindInSortedList(T element, int &index) const {
int part_begin = 0; // 搜索区域头
int part_end = real_lengh;
int part_middle = part_end / 2;
while (part_begin != part_middle) {
if (data[part_middle] > element) {
part_end = part_middle;
part_middle = (part_middle + part_begin) / 2; // 注意向下取整
} else if (data[part_middle] < element) {
part_begin = part_middle;
part_middle = (part_end + part_begin) / 2;
} else {
index = part_middle;
return true;
}
}
index = -1;
return false;
}

这里注意两点:

  • 初始时将搜索区域尾设置为表的实际长度+1的目的是中和整型除以2带来的向下取整的影响,保证变量part_middle能刚好取到所有有效值
  • 循环终止的条件一个是找到需要的数据,一个是查找完毕也没有找到需要的值,后者的条件是part_begin == part_middle,同样是向下取整的影响。

本算法的时间复杂度O(logn),空间复杂度为O(1).

#根据基准元素分割(快排基础)

这个算法所实现的是预定一个基准元素,将表中与该元素大小关系相同的元素放在该元素的同一侧,是快速排序的第一步。算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class T>
bool SeqList<T>::PartList(int pivot) { // 基准元素的索引
if (!ValidIndex(pivot)) {
return false;
}
T tmp = 0;
tmp = data[pivot]; // 将基准元素与表首的元素互换,保证所有元素被遍历
data[pivot] = data[0]; // 暂存基准元素
int part_head = 0;
int part_tail = real_lengh - 1;
while (part_tail != part_head) {
while (data[part_tail] > tmp && part_tail != part_head) {
part_tail--;
}
SwapElement(part_tail, part_head);
while (data[part_head] <= tmp && part_tail != part_head) {
part_head++;
}
SwapElement(part_tail, part_head);
}
data[part_tail] = tmp;
return true;
}

这里的part_tail和part_head相当于两把相向而行的梳子,同时两者每次均前进1,因此两者必然会相遇。相遇的位置即放置基准元素的位置。

#测试

最后测试一下上面的几个算法,结果如图:


← Prev 《程序员的自我修养》- 重定位 | 《程序员的自我修养》- ELF文件预备知识 Next →