k@M0me’s Humble Abode      博  客   时 间 线   归  档 



数据结构1:表、栈和队列
Published on Mon Feb 17 2020 16:13:00 GMT+0000

前导知识

时间复杂度

增长率的大O记法:

O(N^2):以二次方级别增长

一般计算法则:

for循环:循环内语句时间*迭代次数

嵌套循环:N^(循环嵌套数)

顺序语句:单纯的将各段的时间相加

if/else:取时间较长者计算

时间复杂度中的对数:

程序每次用O(1)时间将问题大小削减为一部分(通常为1/2,二分搜索)

此时时间复杂度为O(logN)

运用分治算法也可以实现一些复杂度为对数的时间复杂度算法.

数据结构实现

数据结构的表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ADT structureName;
{
Data
{
var a;
var b;
//......
}
Operation
{
Ope1{
initial condition;
Operation results;
}
Ope2;
//......
}
}

数组(Array):最简单的表ADT(抽象数据结构)实现

数组是最基本的数据结构,虽然我们在学C++和C时已经了解过,但深入探讨一下数组仍旧很有必要.

数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始

C++实现:

1
2
3
4
int arr[5];//建立数组
int arr[5]={0};//建立数组时顺便全部初始化为0
int *p = new int[5];//运行时创建数组
delete[] p;//释放内存

优点:
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点:
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加,删除的操作慢,因为要移动其他的元素。

4.需要一整块连续的存储空间,这个要求就很苛刻,这意味着你没法开很大的数组.

适用场景:
频繁查询,对存储空间要求不大,很少增加和删除的情况。

栈(stack)

接下来讨论栈ADT:

栈可以通过表来实现,任何一种实现表的方法都可以实现栈.

栈只能读取并操作栈顶元素,因此其可以使用一个简单链表来轻松实现:

在链表的最后一个元素的右边直接插入数据.

接下来使用链表式结构实现一个栈,并能做到在其中查找最小值

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
#include <bits/stdc++.h>

using namespace std;
class Node
{

public:
int value = 0;
Node *next;
};

class MinStack
{

public:
Node *topNode;
int min;
bool isFirst = true;
/** initialize your data structure here. */
MinStack()
{
topNode = NULL;
}

void push(int x)
{
Node *currentNode = new Node;
currentNode->value = x;
currentNode->next = topNode;
topNode = currentNode;
if (isFirst)
{
min = x;
isFirst = false;
}
if (x < min)
{
min = x;
}
}

void pop()
{

if (topNode->value == min)//如果栈顶数为最小值的处理方式
{
Node *search = topNode;
if (search->next != NULL)//注意这里的坑:如果是取最后一个结点,则清空栈
{
min = search->next->value;
}
else
{
isFirst = true;
}
while (search->next != NULL)
{
search = search->next;
if (search->value < min)
{
min = search->value;
}
}
}
topNode = topNode->next;
}

int top()
{
return topNode->value;
}

int getMin()
{
return min;
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/

使用一个动态数组也可以简单的实现栈,c++中的模板类vector提供了

1
2
vector.push_back();
vector.pop_back();

功能.

栈是最适合实现递归的一种数据结构,我们可以使用栈的思想实现一个逆波兰计算器.

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
//逆波兰计算器(从一个string数组提取输入)
class Solution {
public:
int evalRPN(std::vector<std::string>& tokens) {
std::stack<int> cacuList;
std::vector<std::string>::iterator cacuValue = tokens.begin();
while(cacuValue != tokens.end())
{
if(cacuValue->length() == 1) { //在位数为1时确认为符号或数字,将负号与减号分开
if ((*cacuValue)[0] == '+') {
int top, res;
top = cacuList.top();
cacuList.pop();
res = cacuList.top() + top;
cacuList.pop();
cacuList.push(res);
}
else if ((*cacuValue)[0] == '-') {
int top, res;
top = cacuList.top();
cacuList.pop();
res = cacuList.top() - top;
cacuList.pop();
cacuList.push(res);
}
else if ((*cacuValue)[0] == '*') {
int top, res;
top = cacuList.top();
cacuList.pop();
res = cacuList.top() * top;
cacuList.pop();
cacuList.push(res);
}
else if ((*cacuValue)[0] == '/') {
int top, res;
top = cacuList.top();
cacuList.pop();
res = cacuList.top() / top;
cacuList.pop();
cacuList.push(res);
} else {
cacuList.push((*cacuValue)[0]-'0');
}
}
else{
int inputNumber=0;
int i=0;
bool rev = false;
int digit = cacuValue->length() - 1;
if((*cacuValue)[0] == '-')
{
i++;
rev = true;
digit--;
}
for (; i < cacuValue->length(); ++i) {
inputNumber += pow(10,digit) * ((*cacuValue)[i]-'0');
digit--;
}
if(rev)
{
inputNumber*= -1;
}
cacuList.push(inputNumber);
}
cacuValue++;
}
return cacuList.top();
}
};

队列

队列的实现:使用链表或是循环数组

链表的实现方式非常简单,只需加上几个方法,出队就是移除初数据,入队就是在队列尾部上一个新数据.由是我们不关心如何用链表实现,我们关心如何用循环数组实现.

首先使用一个数组来模拟一个短队列:

1 2 3 4
front back

当队列塞满数组之后,就绕回到开头:

7 1 2 3 4 5 6
back front

而在队首取数也很容易,只需将队首对应的下标改变:

7 1 2 3 4 5 6
back 删除front front

实现队列数组的长度取决于队列长度.

循环数组实现的队列:

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
class MyCircularQueue
{

public:
vector<int> queue_data;
int queueLength = 0;
int queueSize = 0;
int qFront = 0;
int qEnd = 0;
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k)
{
queue_data.resize(k);
queueSize = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value)
{
if (queueLength >= queueSize)
{
return false;
}
if (queueLength == 0)
{
queue_data[0] = value;
qFront = 0; //这里是一个坑,如果队列初始化时为空队列,首位的位置要重新设置
qEnd = 0;
}
else
{
qEnd++;
if (qEnd == queueSize)
{
qEnd = 0;
}
queue_data[qEnd] = value;
}
queueLength++;
return true;
}

/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue()
{
if (queueLength == 0)
return false;
else
{
qFront++;
if (qFront == queueSize)
qFront = 0;
}
queueLength--;
return true;
}

/** Get the front item from the queue. */
int Front()
{
if (queueLength == 0)
return -1;
return queue_data[qFront];
}

/** Get the last item from the queue. */
int Rear()
{
if (queueLength == 0)
return -1;
return queue_data[qEnd];
}

/** Checks whether the circular queue is empty or not. */
bool isEmpty()
{
if (queueLength == 0)
return true;
return false;
}

/** Checks whether the circular queue is full or not. */
bool isFull()
{
if (queueLength == queueSize)
return true;
return false;
}
};

链表

链表是一种非连续非顺序的数据结构,每一个元素只汇报下一个元素(或前一个元素)的位置(或指针).

链表的插入删除数据十分方便,但是要想读出某个位置的值就很困难,因为你要遍历链表才能知道那个位置的数据.

链表的设计代码(单向链表):

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
class Node
{

public:
int value = 0;
Node *next;
};

class MyLinkedList
{

public:
Node *head, *next, *tail;
int length;

/** Initialize your data structure here. */
MyLinkedList()
{
head = NULL;
next = NULL;
tail = NULL;
length = 0;
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index)
{
if (index < 0 || index >= length)
return -1;
else
{
Node *current = head;
int returnVal = head->value;
while (index-- >= 0)
{
returnVal = current->value;
current = current->next;
}
return returnVal;
}
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val)
{
if (head == NULL)
{
Node *currentNode = new Node;
head = currentNode;
head->value = val;
head->next = NULL;
tail = head;
length = 1;
}
else
{
Node *currentNode = new Node;
(*currentNode).next = head;
(*currentNode).value = val;
head = currentNode;
length++;
}
}

/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val)
{
if (head == NULL)
{
Node *currentNode = new Node;
head = currentNode;
head->value = val;
head->next = NULL;
tail = head;
length = 1;
}
else
{
Node *currentNode = new Node;
(*currentNode).next = NULL;
(*currentNode).value = val;
(*tail).next = currentNode;
tail = currentNode;
length++;
}
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val)
{
Node *current = new Node;
Node *insert = head;
if (index < 0 || index > length)
{
return;
}
if (index == 0)
{
(*this).addAtHead(val);
}
else
{
if (index > length)
return;
if (index == length)
{
(*this).addAtTail(val);
}
else
{
while (index-- > 1)
{
insert = insert->next;
}
current->next = insert->next;
current->value = val;
insert->next = current;
length++;
}
}
}

/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index)
{
if (index < 0 || index >= length)
return;
if (index == 0)
{
head = head->next;
length--;
}
else
{
Node *deleteNode = head;
while (index-- > 1)
{
deleteNode = deleteNode->next;
}
deleteNode->next = deleteNode->next->next;
if(deleteNode->next == NULL)
{
tail = deleteNode;
}
length--;
}
}
};

/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/

STL中的链表

C++的STL包含了一个模板类:list.

这个模板类提供了一套完整的链表系统,这样你就不需要动手造轮子.

c++的list是由一个双向链表实现的.

下面是一些用法及实例:

1
2
3
4
5
6
7
8
9
10
11
12
list<int> my_list;  //构造list(空的)
//将数组赋值到list的示例:
int myints[] = {75,23,65,42,13};
list<int> my_list (myints, myints+5);
//给予list一个初始大小,但全部赋初值:
std::list<int> sayings {20}; // A list of 20 empty int
std::list<double> values(50, 3.14159265);//A List of 50 same elements
//使用迭代器
my_list.begin();//返回首迭代器
my_list.end();//返回尾迭代器
my_list.rbegin();//返回反向的首迭代器,记住,c++的list是一个双向链表,所以你可以这么做.
my_list.rend();//返回反向的尾迭代器

元素访问:

迭代器访问:我觉得你应该很懂,参见前面的迭代器使用那一章节

函数名 作用
front 访问第一个元素
back 访问最后一个元素

元素插入删除:

可以在迭代器指定的位置插入一个新的元素:

1
2
std::list<int> data(10, 55); // 构建一个全为55的链表
data.insert(++begin(data), 66); // 将66作为第二个元素插入

有关list,我们后面会根据 C++ Prime数据结构与算法分析 中的内容进行详细说明.