时间复杂度

什么是时间复杂度?

  在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

  算法复杂度分为时间复杂度空间复杂度。其作用:时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。(算法的复杂性体运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度。)计算机发展到今天,空间相对于时间来说已经没那么重要,因此现在许多程序员在设计程序或者算法时,会选择使用更高的空间复杂度来换取更低的时间复杂度。
时间复杂度

算法时间复杂度比较的前提

  • 1.数据样本量相同(n)
  • 2.每一条指令执行的时间相同(t)

常见的时间复杂度

O(1) 常量阶

1
2
3
4
5
6
7
8
int add(int m,int n)
{
m++; //1*t
n++; //1*t
m+=1; //1*t
n+=1; //1*t
return m+n;//1*t
}

每一行代码执行需要1t的时间,加起来就是5t,因为无论给多少个样本这个函数执行时间都是5t,所以这个函数的时间复杂度为O(1)。

O(n) 线性阶

1
2
3
4
5
6
7
8
9
int add(int a[],int n)
{
int s=0,i; //2t
for(i=0;i<n;i++)//t + n*t + n*t = (2n+1)*t
{
s=s+a[i];//n*t
}
printf("%d",s); //1t
}

执行语句的时间:(3n+4)*t

O(n^2) 平方阶

  • demo1单个样本 (n) :
1
2
3
4
5
6
7
8
9
10
11
12
int add(int n)
{
int s=0,t,i,j; //4t
for(i=0;i<n;i++) //t + n*t + n*t = (2n+1)*t
{
t = 1; //n*t
for(j=1;j<=i;j++) //n*t + (1+n)*n*1.5
t*=j;
s+=t; //n*t
}
return s; //1*t
}

4t + 2nt + t + nt + nt + 1.5n^2t + 1.5nt + nt + 1t
执行语句的时间:(1.5n^2 + 6.5n + 6)*t

  • demo2两个样本 (m) (n) :
1
2
3
4
5
6
7
8
9
10
11
12
int add(int m,int n)
{
int i,j,s=0; //3t
for(i=0;i<m;i++) //1t+2m
{
for(j=1;j<=n;j++) //m + m*n + m*n
{
s++; //m*n
printf("%d",s); //m*n
}
}
}

4m*n + 3m + 4t
在这种情况下 要假定m=n
执行语句的时间:4n^2 + 3n + 4t

O(n^3) 立方阶 (待更新。。)

O(2^n) 指数阶 (待更新。。)

O(long) 对数阶

1
2
3
4
5
6
7
void fun(int n)
{
for(int i=0;i<n;)
{
i = i * 2;
}
}

O(nlong) 线性对数阶(待更新。。)

O(n!) 阶乘(待更新。。)

动态数组

为什么需要动态数组?

在使用普通数组的时候,我们是这样声明的char ary[10]或者new char[10],这时候就会存在一个问题,如果数组里的元素存满了,还想继续存入元素或者调整数组长度的话,都是无法做到的。为了解决这个问题,我们就需要自己封装一个数组,实现普通数组无法做到的功能,这就是动态数组

实现一个动态数组

  • Carray.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
#pragma once
class CArrary
{
public:
CArrary();
CArrary(const CArrary& ary);
virtual ~CArrary();

public:
//增加
bool AddHead(char chVal);
bool AddTail(char chVal);
bool Insert(int nIdx, char chVal);

//删除
bool RemoveHead();
bool RemoveTail();
bool Remove(int nIdx);

//修改
bool SetVal(int nIdx, char chVal);
char& operator[](int nIdx);
CArrary& operator+=(const CArrary& ary);
CArrary& operator=(const CArrary& ary);

//查询
int Find(char chVal);

//获取数组元素个数
int size()const;

//清空
void Clear();

private:
char* m_pBuff;//存放数组元素的缓冲区
int m_nBuffSize;//缓冲区的大小
int m_nElemenSize; //数组中元素的个数

};
  • Carray.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
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
#include "CArrary.h"
#include <cstring>
#include <stdexcept>

CArrary::CArrary()
{
m_pBuff = nullptr;
m_nElemenSize = 0;
m_nBuffSize = 0;
}

CArrary::CArrary(const CArrary& ary)
{
*this = ary;
}

CArrary::~CArrary()
{
Clear();
}

bool CArrary::AddHead(char chVal)
{
return Insert(0, chVal);
}

bool CArrary::AddTail(char chVal)
{
return Insert(m_nElemenSize, chVal);
}

bool CArrary::Insert(int nIdx, char chVal)
{
//判断是否为空
if (m_pBuff==nullptr)
{
const int nInitBuffSize = 16;
m_nBuffSize = nInitBuffSize;
m_pBuff = new char[m_nBuffSize];
m_nElemenSize = 0;
}

//判断索引值是否合理
if (nIdx < 0 || nIdx > m_nElemenSize)
{
return false;
}

//判断缓冲区是否足够
if (m_nElemenSize>=m_nBuffSize)
{
//申请新的缓冲区
m_nBuffSize = m_nBuffSize*2; //原缓冲区扩大两倍
char* pNewBuff = new char[m_nBuffSize];
memcpy(pNewBuff, m_pBuff, m_nElemenSize);//拷贝原来的数据
delete[]m_pBuff; //删除原来的缓冲区
m_pBuff = pNewBuff;

}

//添加新的元素
//从nIdx开始的元素都向后移动
memcpy(&m_pBuff[nIdx + 1], &m_pBuff[nIdx], m_nElemenSize - nIdx);
m_pBuff[nIdx] = chVal;
m_nElemenSize++;

return true;
}

bool CArrary::RemoveHead()
{
return Remove(0);
}

bool CArrary::RemoveTail()
{
return Remove(m_nElemenSize-1);
}

bool CArrary::Remove(int nIdx)
{
//判断数组是否为空
if (m_pBuff==nullptr)
{
return false;
}

//判断索引是否合理
if (nIdx < 0 || nIdx > m_nElemenSize)
{
return false;
}

//删除元素
memcpy(&m_pBuff[nIdx], &m_pBuff[nIdx + 1], m_nElemenSize - nIdx - 1);
m_nElemenSize--;

return true;
}

bool CArrary::SetVal(int nIdx, char chVal)
{
//判断索引是否合理
if (nIdx < 0 || nIdx > m_nElemenSize)
{
return false;
}

m_pBuff[nIdx] = chVal;
return true;
}



int CArrary::Find(char chVal)
{
//判断数组是否为空
if (m_pBuff == nullptr)
{
return false;
}


for (int i=0;i<=m_nElemenSize;i++)
{
if (m_pBuff[i]==chVal)
{
return i;
}

}

return -1;
}

int CArrary::size() const
{
return m_nElemenSize;
}

void CArrary::Clear()
{
if (m_pBuff != nullptr)
{
delete[]m_pBuff;
m_pBuff = nullptr;
m_nElemenSize = 0;
m_nBuffSize = 0;
}
}

char& CArrary::operator[](int nIdx)
{
//判断索引是否合理
if (nIdx < 0 || nIdx > m_nElemenSize || m_pBuff == nullptr)
{
throw std::out_of_range("访问越界");
}
return m_pBuff[nIdx];
}

CArrary& CArrary::operator=(const CArrary& ary)
{
//判断是否自己赋值自己,不做任何操作
if(this == &ary)
{
return *this;
}
//清除原来的数据
Clear();

//拷贝目标对象的数据到自己
m_pBuff = new char[ary.m_nElemenSize];
memcpy(m_pBuff, ary.m_pBuff, ary.m_nElemenSize);
m_nElemenSize = ary.m_nElemenSize;
m_nBuffSize = ary.m_nElemenSize;

return *this;
}

CArrary& CArrary::operator+=(const CArrary& ary)
{
//如果对方为空则不拷贝
if (ary.m_pBuff == nullptr)
{
return *this;
}
//如果自己为空,直接拷贝
if (m_pBuff == nullptr)
{
*this = ary;
return *this;
}

char* pNewBuff = new char[m_nElemenSize + ary.m_nElemenSize];
memcpy(pNewBuff, m_pBuff, m_nElemenSize);
memcpy(pNewBuff + m_nElemenSize, ary.m_pBuff, ary.m_nElemenSize);
delete[]m_pBuff;
m_nElemenSize = m_nElemenSize + ary.m_nElemenSize;
m_nBuffSize = m_nElemenSize + ary.m_nElemenSize;

return *this;
}

动态数组模板

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
#pragma once
#include <cstring>
#include <stdexcept>

template<typename T>
class CArrary
{
public:
CArrary();
CArrary(const CArrary& ary);
virtual ~CArrary();

public:
//增加
bool AddHead(T val);
bool AddTail(T val);
bool Insert(int nIdx, T val);

//删除
bool RemoveHead();
bool RemoveTail();
bool Remove(int nIdx);

//修改
bool SetVal(int nIdx, T val);
T& operator[](int nIdx);
CArrary& operator+=(const CArrary& ary);
CArrary& operator=(const CArrary& ary);

//查询
int Find(T val);

//获取数组元素个数
int size()const;

//清空
void Clear();

private:
T* m_pBuff;//存放数组元素的缓冲区
int m_nBuffSize;//缓冲区的大小
int m_nElemenSize; //数组中元素的个数

};

template<typename T>
CArrary<T>::CArrary()
{
m_pBuff = nullptr;
m_nElemenSize = 0;
m_nBuffSize = 0;
}

template<typename T>
CArrary<T>::CArrary(const CArrary& ary)
{
*this = ary;
}

template<typename T>
CArrary<T>::~CArrary()
{
Clear();
}

template<typename T>
bool CArrary<T>::AddHead(T val)
{
return Insert(0, val);
}

template<typename T>
bool CArrary<T>::AddTail(T val)
{
return Insert(m_nElemenSize, val);
}

template<typename T>
bool CArrary<T>::Insert(int nIdx, T val)
{
//判断是否为空
if (m_pBuff == nullptr)
{
const int nInitBuffSize = 16;
m_nBuffSize = nInitBuffSize;
m_pBuff = new T[m_nBuffSize];
m_nElemenSize = 0;
}

//判断索引值是否合理
if (nIdx < 0 || nIdx > m_nElemenSize)
{
return false;
}

//判断缓冲区是否足够
if (m_nElemenSize >= m_nBuffSize)
{
//申请新的缓冲区
m_nBuffSize = m_nBuffSize * 2; //原缓冲区扩大两倍
T* pNewBuff = new T[m_nBuffSize];
memcpy(pNewBuff, m_pBuff, m_nElemenSize * sizeof(T));//拷贝原来的数据
delete[]m_pBuff; //删除原来的缓冲区
m_pBuff = pNewBuff;

}

//添加新的元素
//从nIdx开始的元素都向后移动
memcpy(&m_pBuff[nIdx + 1], &m_pBuff[nIdx], (m_nElemenSize - nIdx) * sizeof(T));
m_pBuff[nIdx] = val;
m_nElemenSize++;

return true;
}

template<typename T>
bool CArrary<T>::RemoveHead()
{
return Remove(0);
}

template<typename T>
bool CArrary<T>::RemoveTail()
{
return Remove(m_nElemenSize - 1);
}

template<typename T>
bool CArrary<T>::Remove(int nIdx)
{
//判断数组是否为空
if (m_pBuff == nullptr)
{
return false;
}

//判断索引是否合理
if (nIdx < 0 || nIdx > m_nElemenSize)
{
return false;
}

//删除元素
memcpy(&m_pBuff[nIdx], &m_pBuff[nIdx + 1], (m_nElemenSize - nIdx - 1)*sizeof(T));
m_nElemenSize--;

return true;
}

template<typename T>
bool CArrary<T>::SetVal(int nIdx, T val)
{
//判断索引是否合理
if (nIdx < 0 || nIdx > m_nElemenSize)
{
return false;
}

m_pBuff[nIdx] = val;
return true;
}

template<typename T>
int CArrary<T>::Find(T val)
{
//判断数组是否为空
if (m_pBuff == nullptr)
{
return false;
}


for (int i = 0; i <= m_nElemenSize; i++)
{
if (m_pBuff[i] == val)
{
return i;
}

}

return -1;
}

template<typename T>
int CArrary<T>::size() const
{
return m_nElemenSize;
}

template<typename T>
void CArrary<T>::Clear()
{
if (m_pBuff != nullptr)
{
delete[]m_pBuff;
m_pBuff = nullptr;
m_nElemenSize = 0;
m_nBuffSize = 0;
}
}

template<typename T>
T& CArrary<T>::operator[](int nIdx)
{
//判断索引是否合理
if (nIdx < 0 || nIdx > m_nElemenSize || m_pBuff == nullptr)
{
throw std::out_of_range("访问越界");
}
return m_pBuff[nIdx];
}

template<typename T>
CArrary<T>& CArrary<T>::operator=(const CArrary& ary)
{
if(this == &ary)
{
return *this;
}
//清除原来的数据
Clear();

//拷贝目标对象的数据到自己
m_pBuff = new T[ary.m_nBuffSize];
memcpy(m_pBuff, ary.m_pBuff, ary.m_nElemenSize * sizeof(T));
m_nElemenSize = ary.m_nElemenSize;
m_nBuffSize = ary.m_nBuffSize;

return *this;
}

template<typename T>
CArrary<T>& CArrary<T>::operator+=(const CArrary& ary)
{
//如果对方为空则不拷贝
if (ary.m_pBuff == nullptr)
{
return *this;
}
//如果自己为空,直接拷贝
if (m_pBuff == nullptr)
{
*this = ary;
return *this;
}

T* pNewBuff = new T[m_nElemenSize + ary.m_nElemenSize];
memcpy(pNewBuff, m_pBuff, m_nElemenSize * sizeof(T));
memcpy(pNewBuff + m_nElemenSize, ary.m_pBuff, ary.m_nElemenSize * sizeof(T));
delete[]m_pBuff;
m_pBuff = pNewBuff;
m_nBuffSize = m_nElemenSize + ary.m_nElemenSize;
m_nElemenSize = m_nElemenSize + ary.m_nElemenSize;

return *this;
}

动态数组各种操作的时间复杂度

  • 1.增加
    平均:O(n)
    最好:O(1)
    最坏:O(n)
  • 2.修改
    平均:O(1)
    最好:O(1)
    最坏:O(1)
  • 3.删除
    平均:O(n)
    最好:O(1)
    最坏:O(n)
  • 4.查询
    平均:O(n)
    最好:O(1)
    最坏:O(n)
  • 5.随机访问
    平均:O(1)
    最好:O(1)
    最坏:O(1)

链表

什么是链表?为什么需要链表?

  • 数组的缺点
    数组的插入和删除操作,每次都需要移动数据,算法时间复杂度为**O(n)**。
  • 为什么数组插入和删除数据都必须移动数据?
    因为数组的元素和元素之间的地址是连续的(线性地址空间),中间没有可用的内存空间。
  • 如何改进数组的缺点?
    不再把数组元素紧挨着存储,把他们分散开来,每当插入新的元素的时候,为其申请新的内存。
  • 使之成为线性表(链表)
    在插入新元素的时候都申请内存会出现一个问题,就是散落在内存(堆)中的数据元素之间没有联系,而且存入线性表中的数据元素是有序的,所以,需要为每个元素添加一个额外的位置信息,用来记录下一个数据元素的位置。

链表的定义

  • 结点
    链表中每一个元素称为结点,每个结点至少包含两部分内容,一个是数据,一个是指针。
    img

  • 链表
    多个结点链接起来构成链表

    链表中的第一个结点称之为头结点,最后一个结点称之为尾结点

    链表中保存了一个指向第一个结点的指针,称之为头结点指针

img

链表的分类

  • 单向链表
    如果结点只有一个指针,指向此结点的后结点,则这个链表称之为单向链表

img

  • 双向链表
    如果结点有两个指针,一个指向此结点的后继结点,一个指向此结点的前驱结点,则这个链表称之为双向链表

img

  • 循环链表
    如果尾结点的指针指向了头结点,则这个链表称之为循环链表。循环链表分为单向循环链表和双向循环链表。

img

实现一个链表

  • Clist.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
#pragma once
class CList
{
public:
//双向链表的结点
typedef struct tagNode
{
tagNode(int val) :m_val(val), m_pPre(nullptr), m_pNext(nullptr) {}
tagNode() :m_pPre(nullptr), m_pNext(nullptr) {}
int m_val; //保存的数据
tagNode* m_pNext;//指向下一个结点的指针
tagNode* m_pPre; //指向上一个结点的指针
}NODE,*PNODE;

public:
CList();
CList(const CList& lst);
CList& operator=(const CList& lst);
virtual ~CList();

//增加
bool AddHead(int val);
bool AddTail(int val);
bool Insert(PNODE pNode, int val);

//修改
bool SetVal(PNODE pNode, int val);

//删除
bool RemoveHead();
bool RemoveTail();
bool Remove(PNODE pNode);

//查询
PNODE Find(int val);

//判断是否为空
bool IsNull();

int Size();

void clear();

private:
bool IsValidateNodPtr(PNODE pNode);
void InitList();

private:
PNODE m_pHeadGuard; //保存链表的头部哨兵
PNODE m_pTailGuard; //保存链表的尾部哨兵
int m_nSize; //保存链表结点个数
};
  • Clist.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
#include "CList.h"
CList::CList()
{
InitList();
}

CList::CList(const CList& lst)
{
InitList();
*this = lst;
}

CList& CList::operator=(const CList& lst)
{
//如果是自己赋值给自己 不做操作
if (this==&lst)
{
return *this;
}


clear();
PNODE pNode = lst.m_pHeadGuard->m_pNext;
while (pNode!=lst.m_pTailGuard)
{
//将对方的数据添加到自己的链表中
AddHead(pNode->m_val);
//取下一个结点
pNode = pNode->m_pNext;
}
return *this;
}

CList::~CList()
{
//清除链表内容
clear();

//销毁哨兵结点
delete m_pHeadGuard;
delete m_pTailGuard;
m_pHeadGuard = nullptr;
m_pTailGuard = nullptr;
}

bool CList::AddHead(int val)
{
//头部哨兵后面的结点前面
return Insert(m_pHeadGuard->m_pNext,val);
}

bool CList::AddTail(int val)
{
return Insert(m_pTailGuard,val);
}

bool CList::Insert(PNODE pNode, int val)
{
//创建新的结点
PNODE pNewNode = new NODE(val);

//添加新的结点
PNODE pOldPre = pNode->m_pPre;

pNewNode->m_pNext = pNode;
pNewNode->m_pPre = pOldPre;

pNode->m_pPre = pNewNode;
pOldPre->m_pNext = pNewNode;

//元素个数增加
m_nSize++;

return false;
}

bool CList::SetVal(PNODE pNode, int val)
{
//判断是否是个有效结点
if (!IsValidateNodPtr(pNode))
{
return false;
}
pNode->m_val = val;
return true;
}

bool CList::RemoveHead()
{
return Remove(m_pHeadGuard->m_pNext);
}

bool CList::RemoveTail()
{
return Remove(m_pTailGuard->m_pPre);
}

bool CList::Remove(PNODE pNode)
{
if (!IsValidateNodPtr(pNode))
{
return false;
}


//删除前修改前驱后继结点
PNODE pOldPre = pNode->m_pPre;
PNODE pOldNext = pNode->m_pNext;

pOldPre->m_pNext = pOldNext;
pOldNext->m_pPre = pOldPre;

//删除结点
delete pNode;
m_nSize--;
return true;
}

CList::PNODE CList::Find(int val)
{

PNODE pNodeTmp = m_pHeadGuard->m_pNext;
while (pNodeTmp != m_pTailGuard)
{
if (pNodeTmp->m_val == val)
{
return pNodeTmp;
}
pNodeTmp = pNodeTmp->m_pNext;
}

return nullptr;
}

bool CList::IsNull()
{
return m_nSize == 0;
}

int CList::Size()
{
return m_nSize;
}

void CList::clear()
{
while (!IsNull())
{
RemoveHead();
}
}

bool CList::IsValidateNodPtr(PNODE pNode)
{
PNODE pNodeTmp = m_pHeadGuard->m_pNext;
while (pNodeTmp != m_pTailGuard)
{
if (pNodeTmp == pNode)
{
return true;
}
pNodeTmp = pNodeTmp->m_pNext;
}
return false;
}

void CList::InitList()
{
m_pHeadGuard = new NODE;
m_pTailGuard = new NODE;
m_pHeadGuard->m_pNext = m_pTailGuard;
m_pTailGuard->m_pPre = m_pHeadGuard;
m_nSize = 0;
}

  通过以上代码,我们就实现了一个简单的链表,但是这个链表还存在一个问题,就是在使用的过程中,存在返回结点指针的操作,比如如查找的时候就会返回一个结点的指针。
img
另外在增加、修改、删除的操作中同样存在传递结点的指针的操作。
img
在拿到这个结点指针的时候,就可以任意对这个结点进行破坏封装性的操作,比如对任意指针赋值,对任意成员变量赋值。
img

使用迭代器解决破坏封装性问题

  下面使用迭代器的实例代码是从上面链表的头文件中精简而成,为了方便阅读,只保留了会破坏封装性的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class CList
{
private:
typedef struct tagNode{
}NODE,*PNODE;

public:
class CPostision //迭代器
{
private:
NODE m_pNode;
}

public:
bool Insert(CPostision pos, int val);
bool SetVal(CPostision pos, int val);
bool Remove(CPostision pos);
CPostision Find(int val);
};

可以看到,上面的代码中定义了一个叫CPostision的类对象,把PNODE放到这个类里作为私有成员,这样,从外部就不能直接访问PNODE这个类型的指针。这种用一个类将一个指针私有的操作就叫做迭代器(指向数据结构中元素的位置)。

STL中的迭代器

在*C++官方的STL库中就使用了迭代器,下面我使用STL中的链表**进行演示。

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
#include <iostream>
#include <list>
using namespace std;

int main()
{
list<int> lst;

//插入元素到容器起始
lst.push_front(1);

//将元素添加到容器末尾
lst.push_back(2);

//获取头部迭代器 指向头结点
list<int>::iterator itrBegin = lst.begin();

//使用insert在头结点后插入3
lst.insert(itrBegin, 3);

//从头结点开始擦除元素
lst.erase(lst.begin());

//通过begin移动位置 修改结点内容
auto itr = lst.begin();
itr++; //移动到后继结点
*itr = 87;

auto itr1 = lst.end();
itr1--; //移动到尾结点
*itr1 = 66;

//使用begin遍历链表的两种方式
for (auto itr = lst.begin(); itr != lst.end(); itr++)
{
cout << *itr << endl;
}

for (auto val:lst)
{
cout << val << endl;
}
}

更多用法可以查看☛[cppreference]

使用迭代器优化链表

  • Clist.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
#pragma once
#include <cassert>

class CList
{
private:
//双向链表的结点
typedef struct tagNode
{
tagNode(int val) :m_val(val), m_pPre(nullptr), m_pNext(nullptr) {}
tagNode() :m_pPre(nullptr), m_pNext(nullptr) {}
int m_val; //保存的数据
tagNode* m_pNext;//指向下一个结点的指针
tagNode* m_pPre; //指向上一个结点的指针
}NODE,*PNODE;

public:
class iterator
{
public:
iterator& operator++()
{
assert(m_pNode->m_pNext != m_pTailGuard);
m_pNode = m_pNode->m_pNext;
return *this;
}
iterator operator++(int)
{
assert(m_pNode->m_pNext != m_pTailGuard);
m_pNode = m_pNode->m_pNext;
return iterator(m_pNode->m_pPre, m_pHeadGuard,m_pTailGuard);
}
iterator& operator--()
{
assert(m_pNode->m_pPre != m_pHeadGuard);
m_pNode = m_pNode->m_pPre;
return *this;
}
iterator operator--(int)
{
assert(m_pNode->m_pPre != m_pHeadGuard);
m_pNode = m_pNode->m_pPre;
return iterator(m_pNode->m_pNext,m_pHeadGuard,m_pTailGuard);
}
int& operator*()
{
return m_pNode->m_val;
};
bool operator==(const iterator& itr)
{
return m_pNode == itr.m_pNode;
}
bool operator!=(const iterator& itr)
{
return m_pNode != itr.m_pNode;
}
private:
friend class CList;
iterator(PNODE pNode,PNODE pHeadGuard,PNODE pTailGuard) :
m_pNode(pNode),
m_pHeadGuard(pHeadGuard),
m_pTailGuard(m_pTailGuard)
{}
private:
PNODE m_pNode;
PNODE m_pHeadGuard;
PNODE m_pTailGuard;
};

public:
iterator begin();
iterator end();

public:
CList();
CList(const CList& lst);
CList& operator=(const CList& lst);
virtual ~CList();

//增加
bool AddHead(int val);
bool AddTail(int val);
bool Insert(iterator pNode, int val);

//修改
bool SetVal(iterator pNode, int val);

//删除
bool RemoveHead();
bool RemoveTail();
bool Remove(iterator pNode);

//查询
iterator Find(int val);

//判断是否为空
bool IsNull();

int Size();

void clear();

private:
void InitList();

private:
PNODE m_pHeadGuard; //保存链表的头部哨兵
PNODE m_pTailGuard; //保存链表的尾部哨兵
int m_nSize; //保存链表结点个数
};
  • CList.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
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
#include "CList.h"

CList::iterator CList::begin()
{
return iterator(m_pHeadGuard->m_pNext,m_pHeadGuard,m_pTailGuard);
}

CList::iterator CList::end()
{
return iterator(m_pTailGuard, m_pHeadGuard, m_pTailGuard);
}

CList::CList()
{
InitList();
}

CList::CList(const CList& lst)
{
InitList();
*this = lst;
}

CList& CList::operator=(const CList& lst)
{
//如果是自己赋值给自己 不做操作
if (this==&lst)
{
return *this;
}


clear();
PNODE pNode = lst.m_pHeadGuard->m_pNext;
while (pNode!=lst.m_pTailGuard)
{
//将对方的数据添加到自己的链表中
AddHead(pNode->m_val);
//取下一个结点
pNode = pNode->m_pNext;
}
return *this;
}

CList::~CList()
{
//清除链表内容
clear();

//销毁哨兵结点
delete m_pHeadGuard;
delete m_pTailGuard;
m_pHeadGuard = nullptr;
m_pTailGuard = nullptr;
}

bool CList::AddHead(int val)
{
//头部哨兵后面的结点前面
return Insert(begin(),val);
}

bool CList::AddTail(int val)
{
return Insert(end(),val);
}

bool CList::Insert(iterator itr, int val)
{
//创建新的结点
PNODE pNewNode = new NODE(val);

//添加新的结点
PNODE pOldPre = itr.m_pNode->m_pPre;

pNewNode->m_pNext = itr.m_pNode;
pNewNode->m_pPre = pOldPre;

itr.m_pNode->m_pPre = pNewNode;
pOldPre->m_pNext = pNewNode;

//元素个数增加
m_nSize++;

return false;
}

bool CList::SetVal(iterator itr, int val)
{
itr.m_pNode->m_val = val;
return true;
}

bool CList::RemoveHead()
{
return Remove(begin());
}

bool CList::RemoveTail()
{
return Remove(--end());
}

bool CList::Remove(iterator itr)
{
//删除前修改前驱后继结点
PNODE pOldPre = itr.m_pNode->m_pPre;
PNODE pOldNext = itr.m_pNode->m_pNext;

pOldPre->m_pNext = pOldNext;
pOldNext->m_pPre = pOldPre;

//删除结点
delete itr.m_pNode;
m_nSize--;
return true;
}

CList::iterator CList::Find(int val)
{

PNODE pNodeTmp = m_pHeadGuard->m_pNext;
while (pNodeTmp != m_pTailGuard)
{
if (pNodeTmp->m_val == val)
{
return iterator(pNodeTmp,m_pHeadGuard,m_pTailGuard);
}
pNodeTmp = pNodeTmp->m_pNext;
}

return iterator(m_pTailGuard, m_pHeadGuard, m_pTailGuard);
}

bool CList::IsNull()
{
return m_nSize == 0;
}

int CList::Size()
{
return m_nSize;
}

void CList::clear()
{
while (!IsNull())
{
RemoveHead();
}
}

void CList::InitList()
{
m_pHeadGuard = new NODE;
m_pTailGuard = new NODE;
m_pHeadGuard->m_pNext = m_pTailGuard;
m_pTailGuard->m_pPre = m_pHeadGuard;
m_nSize = 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
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
#pragma once
#include <cassert>

template<typename T>
class CList
{
private:
//双向链表的结点
typedef struct tagNode
{
tagNode(T val) :m_val(val), m_pPre(nullptr), m_pNext(nullptr) {}
tagNode() :m_pPre(nullptr), m_pNext(nullptr) {}
T m_val; //保存的数据
tagNode* m_pNext;//指向下一个结点的指针
tagNode* m_pPre; //指向上一个结点的指针
}NODE, * PNODE;

public:
class iterator
{
public:
iterator& operator++()
{
assert(m_pNode->m_pNext != m_pTailGuard);

m_pNode = m_pNode->m_pNext;
return *this;
}
iterator operator++(int)
{
assert(m_pNode->m_pNext != m_pTailGuard);

m_pNode = m_pNode->m_pNext;
return iterator(m_pNode->m_pPre, m_pHeadGuard,m_pTailGuard);
}
iterator& operator--()
{
assert(m_pNode->m_pPre != m_pHeadGuard);
m_pNode = m_pNode->m_pPre;
return *this;
}
iterator operator--(int)
{
assert(m_pNode->m_pPre != m_pHeadGuard);
m_pNode = m_pNode->m_pPre;
return iterator(m_pNode->m_pNext,m_pHeadGuard,m_pTailGuard);
}
T& operator*()
{
return m_pNode->m_val;
};
bool operator==(const iterator& itr)
{
return m_pNode == itr.m_pNode;
}
bool operator!=(const iterator& itr)
{
return m_pNode != itr.m_pNode;
}
private:
friend class CList;
iterator(PNODE pNode, PNODE pHeadGuard, PNODE pTailGuard) :
m_pNode(pNode),
m_pHeadGuard(pHeadGuard),
m_pTailGuard(m_pTailGuard)
{}
private:
PNODE m_pNode;
PNODE m_pHeadGuard;
PNODE m_pTailGuard;
};

public:
iterator begin();
iterator end();


public:
CList();
CList(const CList& lst);
CList& operator=(const CList& lst);
virtual ~CList();

//增加
bool AddHead(T val);
bool AddTail(T val);
bool Insert(iterator pNode, T val);

//修改
bool SetVal(iterator pNode, T val);

//删除
bool RemoveHead();
bool RemoveTail();
bool Remove(iterator pNode);

//查询
iterator Find(T val);

//判断是否为空
bool IsNull();

int Size();

void clear();

private:
void InitList();

private:
PNODE m_pHeadGuard; //保存链表的头部哨兵
PNODE m_pTailGuard; //保存链表的尾部哨兵
int m_nSize; //保存链表结点个数
};


template<typename T>
typename CList<T>::iterator CList<T>::begin()
{
return iterator(m_pHeadGuard->m_pNext, m_pHeadGuard, m_pTailGuard);
}

template<typename T>
typename CList<T>::iterator CList<T>::end()
{
return iterator(m_pTailGuard, m_pHeadGuard, m_pTailGuard);
}

template<typename T>
CList<T>::CList()
{
InitList();
}

template<typename T>
CList<T>::CList(const CList& lst)
{
InitList();
*this = lst;
}

template<typename T>
CList<T>& CList<T>::operator=(const CList& lst)
{
//如果是自己赋值给自己 不做操作
if (this == &lst)
{
return *this;
}


clear();
PNODE pNode = lst.m_pHeadGuard->m_pNext;
while (pNode != lst.m_pTailGuard)
{
//将对方的数据添加到自己的链表中
AddHead(pNode->m_val);
//取下一个结点
pNode = pNode->m_pNext;
}
return *this;
}

template<typename T>
CList<T>::~CList()
{
//清除链表内容
clear();

//销毁哨兵结点
delete m_pHeadGuard;
delete m_pTailGuard;
m_pHeadGuard = nullptr;
m_pTailGuard = nullptr;
}

template<typename T>
bool CList<T>::AddHead(T val)
{
//头部哨兵后面的结点前面
return Insert(begin(), val);
}

template<typename T>
bool CList<T>::AddTail(T val)
{
return Insert(end(), val);
}

template<typename T>
bool CList<T>::Insert(iterator itr, T val)
{
//创建新的结点
PNODE pNewNode = new NODE(val);

//添加新的结点
PNODE pOldPre = itr.m_pNode->m_pPre;

pNewNode->m_pNext = itr.m_pNode;
pNewNode->m_pPre = pOldPre;

itr.m_pNode->m_pPre = pNewNode;
pOldPre->m_pNext = pNewNode;

//元素个数增加
m_nSize++;

return false;
}

template<typename T>
bool CList<T>::SetVal(iterator itr, T val)
{
itr.m_pNode->m_val = val;
return true;
}

template<typename T>
bool CList<T>::RemoveHead()
{
return Remove(begin());
}

template<typename T>
bool CList<T>::RemoveTail()
{
return Remove(--end());
}

template<typename T>
bool CList<T>::Remove(iterator itr)
{
//删除前修改前驱后继结点
PNODE pOldPre = itr.m_pNode->m_pPre;
PNODE pOldNext = itr.m_pNode->m_pNext;

pOldPre->m_pNext = pOldNext;
pOldNext->m_pPre = pOldPre;

//删除结点
delete itr.m_pNode;
m_nSize--;
return true;
}

template<typename T>
typename CList<T>::iterator CList<T>::Find(T val)
{

PNODE pNodeTmp = m_pHeadGuard->m_pNext;
while (pNodeTmp != m_pTailGuard)
{
if (pNodeTmp->m_val == val)
{
return iterator(pNodeTmp, m_pHeadGuard, m_pTailGuard);
}
pNodeTmp = pNodeTmp->m_pNext;
}

return iterator(m_pTailGuard, m_pHeadGuard, m_pTailGuard);
}

template<typename T>
bool CList<T>::IsNull()
{
return m_nSize == 0;
}

template<typename T>
int CList<T>::Size()
{
return m_nSize;
}

template<typename T>
void CList<T>::clear()
{
while (!IsNull())
{
RemoveHead();
}
}

template<typename T>
void CList<T>::InitList()
{
m_pHeadGuard = new NODE;
m_pTailGuard = new NODE;
m_pHeadGuard->m_pNext = m_pTailGuard;
m_pTailGuard->m_pPre = m_pHeadGuard;
m_nSize = 0;
}

链表的时间复杂度

  • 1.增加
    平均:O(1)
    最好:O(1)
    最坏:O(1)
  • 2.修改
    平均:O(1)
    最好:O(1)
    最坏:O(1)
  • 3.删除
    平均:O(1)
    最好:O(1)
    最坏:O(1)
  • 4.查询
    平均:O(n)
    最好:O(1)
    最坏:O(n)
  • 5.随机访问
    平均:O(n)
    最好:O(1)
    最坏:O(n)

链表的占用内存比数组多,但是插入和删除的效率高,这就是空间换时间的思想。

什么是栈

  是仅限定在线性表的一端进行插入和删除的线性结构。允许进行插入和删除的一端称为栈顶,另一端则称为栈底。在栈顶插入数据叫做进栈,也叫做压栈,入栈。从栈顶删除数据叫做出栈,也叫做弹栈。如果栈中没有数据元素,则称为空栈

  • 先进后出(FILO)

  因为最先入栈的数据,最后出栈,所以被称为先进后出结构(FILO – firt in last out),或者后进先出(LIFO – last in first out)。

栈的操作

  • 入栈(push)
  • 出栈(pop)
  • 访问栈顶元素(top)
  • 获得元素个数(size)
  • 清空栈(clear)
  • 判断是否为空(empty)

实现一个栈

这里我直接使用上面封装好的链表模板来实现一个栈

  • CStack.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
#pragma once
#include "MyLib.h"

template<typename T>
class CStack
{
public:
void push(const T& val);
void pop();
T top();
void clear();
bool empty();
int size();

private:
CList<T> m_lst; //链表的头部为栈底,栈的尾部为栈顶
};

template<typename T>
int CStack<T>::size()
{
return m_lst.Size();
}

template<typename T>
inline bool CStack<T>::empty()
{
return m_lst.IsNull();
}

template<typename T>
inline void CStack<T>::clear()
{
m_lst.clear();
}

template<typename T>
inline T CStack<T>::top()
{
return *(--m_lst.end());
}

template<typename T>
inline void CStack<T>::pop()
{
m_lst.RemoveTail();//移除栈顶元素
}

template<typename T>
inline void CStack<T>::push(const T& val)
{
m_lst.AddHead(val); //存入栈顶
}
  • main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include "CStack.h"

using namespace std;

int main()
{
CStack<int> stk;
for (int i = 0; i < 32; i++)
{
stk.push(i);
}
cout << "size:" << stk.size() << endl;

while (!stk.empty())
{
cout << stk.top() << endl;
stk.pop();
}
cout << "size2:" << stk.size() << endl;
return 0;
}

栈的应用

  • 递归
  • 后缀表达式计算
  • 匹配检查

队列

什么是队列?

  队列是限定于仅在一端进行插入,在另一端进行删除的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。队列的插入操作叫入队,删除操作叫出队

  • 先进先出(FIFO)

  因为最先入队的元素最先出队,所以队列被称为先进先出结构(FIFO – firt in firt out),或者后进后出(LILO – last in last out)。
img

队列的操作?

  • 入队(push)
  • 出队(pop)
  • 访问队首数据(front)
  • 获取队中数据个数(size)
  • 清空队列 (clear)

实现一个队列

同样这里我直接使用上面封装好的链表模板来实现一个队列

  • CQueue.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
#pragma once
#include "MyLib.h"

template <typename T>
class CQueue
{
public:
void push(const T& val);
void pop();
T front();
void clear();
int size();
bool empty();

private:
CList<T> m_lst;//链表头为队头,链表尾为队尾
};

template<typename T>
inline void CQueue<T>::push(const T& val)
{
m_lst.AddTail(val);
}

template<typename T>
inline void CQueue<T>::pop()
{
m_lst.RemoveHead();
}

template<typename T>
inline T CQueue<T>::front()
{
return *m_lst.begin();
}

template<typename T>
inline void CQueue<T>::clear()
{
m_lst.clear();
}

template<typename T>
inline int CQueue<T>::size()
{
return m_lst.Size();
}

template<typename T>
inline bool CQueue<T>::empty()
{
return m_lst.IsNull();
}
  • main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include "CQueue.h"

using namespace std;

int main()
{
CQueue<int> queue;
for (int i = 0; i < 32; i++)
{
queue.push(i);
}
cout << "size:" << queue.size() << endl;

while (!queue.empty())
{
cout << queue.front() << endl;
queue.pop();
}
cout << "size2:" << queue.size() << endl;
return 0;
}

什么是树?为什么需要树?

我们知道无论是数组,还是链表,在需要数据查询的时候,通常情况下时间复杂度都是O(n)\,为了解决这个问题,就出现了这个数据结构。

  • 树的定义

树种相连的结点具有父子关系
每个结点只有一个父结点,多个子结点
没有父结点的结点称之为根结点
没有子结点的结点称之为叶子结点
有父结点有子结点的结点称之为分支结点
以某个结点为根结点向下延申出来的树叫做这棵树的子树

  • 结点的高度

结点到叶子的最长路径的边数叶子节点高度0
树的高度为根节点的高度。
img

  • 结点的深度

结点到根节点所经历的边数根节点深度0
树的深度为深度最大的叶子节点深度
img

  • 结点的层

结点的层从根结点开始数,根结点作为第一层,根的子结点作为第二层,以此类推。
img

有序树和无序树

如果规定树中结点的子结点从左向右是有次序的,不能互换的,则该树为有序树,否则为无序树

  • 有序树

img

  • 无序树

img

二叉树

每个结点最多只有两个子结点的树叫做二叉树
img

满二叉树

在一棵二叉树中,如果所有分支节点都存在左子结点右子节点,并且所有的叶子节点都在最底层,这样的树称为满二叉树
img

二叉树的性质

  • 在二叉树的第n层上最多有 2n-1 个结点
  • 深度为n的二叉树上最多有 (2n+1)-1 个结点
  • 含有n个结点的满二叉树最深度为 (logn+1)-1

二叉树的遍历

  • 递归前序遍历
    先自己 再左节点 再右节点
  • 递归中序遍历
    先左节点 再自己 再右节点
  • 递归后序遍历
    先左节点 再右节点 再自己
  • 层序遍历
    从上层到下层,从左向右遍历
  • 非递归前序遍历
    顺序于递归前序遍历相同,使用循环实现
  • 非递归中序遍历
    顺序于递归中序遍历相同,使用循环实现
  • 非递归后续遍历
    顺序于递归后序遍历相同,使用循环实现

二叉搜索树

对于二叉树中的任意结点,左子结点的值小于这个结点的值,右子结点的值大于这个结点的值,这种情况的二叉树叫做二叉查找树,也叫做二叉搜索树二叉排序树
img

二叉搜索树的操作

  • 插入
  • 遍历
  • 删除
  • 修改
  • 查询

实现二叉搜索树

  • CBinarySearchTree.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
#pragma once
class CBinarySearchTree
{
private:
typedef struct tagNode
{
tagNode(int val, tagNode* pParent, tagNode* pLeft, tagNode* pRight) :
m_val(val),
m_pParent(pParent),
m_pLeft(pLeft),
m_pRight(pRight)
{}

int m_val;

tagNode* m_pParent;//指向父结点
tagNode* m_pLeft; //左子结点
tagNode* m_pRight; //右子结点
}NODE,*PNODE;

public:
CBinarySearchTree();
CBinarySearchTree(const CBinarySearchTree& bst);
CBinarySearchTree& operator=(const CBinarySearchTree& bst);
virtual ~CBinarySearchTree();

bool Insert(int val);
bool Remove(int val);
bool Update(int valSrc, int valDst);
bool Find(int val);

//递归
void LMR(); //中序遍历,left middle right
void MLR(); //前序遍历,middle left right
void LRM(); //后序遍历,left right middle

//非递归
void MLRUseLoop(); //前序遍历,middle left right
void LMRUseLoop(); //中序遍历,left middle right
void LRMUseLoop(); //后序遍历,left right middle

//层序遍历
void Level();

private:
PNODE FindNode(int val);
void DelNode(PNODE pNode);
void DelLeaf(PNODE pNode);
void DelSingleChildNode(PNODE pNode);
void DelDoubleChildNode(PNODE pNode);
void LMR(PNODE pNode);
void MLR(PNODE pNode);
void LRM(PNODE pNode);

private:
PNODE m_pRoot;
};
  • CBinarySearchTree.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
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
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
#include "CBinarySearchTree.h"
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

CBinarySearchTree::CBinarySearchTree()
{
m_pRoot = nullptr;
}

CBinarySearchTree::CBinarySearchTree(const CBinarySearchTree& bst)
{
}

CBinarySearchTree& CBinarySearchTree::operator=(const CBinarySearchTree& bst)
{
return *this;
}

CBinarySearchTree::~CBinarySearchTree()
{

}

bool CBinarySearchTree::Insert(int val)
{
//如果树为空,第一个结点作为根节点存在
if (m_pRoot == nullptr)
{
m_pRoot = new NODE(val, nullptr, nullptr, nullptr);
return true;
}

//遍历查找可以插入的位置
PNODE pTmpNode = m_pRoot;
while (true)
{
//如果值小于此节点,取其左子结点判断
if (val < pTmpNode->m_val)
{
//如果子节点没有左子节点,则新插入的值作为节点的左子节点
if (pTmpNode->m_pLeft == nullptr)
{
pTmpNode->m_pLeft = new NODE(val, pTmpNode, nullptr, nullptr);
return true;
}
else
{
pTmpNode = pTmpNode->m_pLeft;
}

}
//如果值大于于此节点,取其右子结点判断
else if(val > pTmpNode->m_val)
{
//如果子节点没有右子节点,则新插入的值作为节点的右子节点
if (pTmpNode->m_pRight == nullptr)
{
pTmpNode->m_pRight = new NODE(val, pTmpNode, nullptr, nullptr);
return true;
}
else
{
pTmpNode = pTmpNode->m_pRight;
}
}
else
{
//不考虑相等的情况
return false;
}
}
return true;
}

bool CBinarySearchTree::Remove(int val)
{
PNODE pNodeToDel = FindNode(val);

if (pNodeToDel == nullptr)//找不到此值
{
return false;
}

DelNode(pNodeToDel);


return true;
}

bool CBinarySearchTree::Update(int valSrc, int valDst)
{
PNODE pNode = FindNode(valSrc);
if (pNode == nullptr)
{
return false;
}

Remove(valSrc);
Insert(valDst);
return true;
}

bool CBinarySearchTree::Find(int val)
{

PNODE pNode = FindNode(val);

if (pNode == nullptr)//找不到此值
{
return false;
}

return true;
}

void CBinarySearchTree::LMR()
{
LMR(m_pRoot);
}

void CBinarySearchTree::MLR()
{
MLR(m_pRoot);
}

void CBinarySearchTree::LRM()
{
LRM(m_pRoot);
}

//前序非递归
void CBinarySearchTree::MLRUseLoop()
{
stack<PNODE> stktmp;

PNODE pNode = m_pRoot;
while (true)
{
//一直向左输出自己,同时右子结点入栈
while (pNode != nullptr)
{
//输出自己
cout << pNode->m_val << " ";
//右子节点入栈
stktmp.push(pNode->m_pRight);
//一路向左
pNode = pNode->m_pLeft;
}

//栈为空,所有右子结点都处理完了,结束遍历
if (stktmp.empty())
{
break;
}

//从栈顶取出右子节点,继续一路向左处理
pNode = stktmp.top();
stktmp.pop();

}
}
//中序非递归
void CBinarySearchTree::LMRUseLoop()
{
//如果为空树,则不遍历
if (m_pRoot == nullptr)
{
return;
}

stack<PNODE> stkTmp;
PNODE pNode = m_pRoot;
while (true)
{
//一路向左,所有节点入栈
while (pNode != nullptr)
{
stkTmp.push(pNode); //入栈
pNode = pNode->m_pLeft;//一路向左
}
//栈空,则所有节点处理完毕
if (stkTmp.empty())
{
break;
}
//从栈顶弹出,并处理
pNode = stkTmp.top();
stkTmp.pop();
cout << pNode->m_val << " ";

//处理右子结点
pNode = pNode->m_pRight;
}
}
//后序非递归
void CBinarySearchTree::LRMUseLoop()
{
//如果是空树 则不遍历
if (m_pRoot == nullptr)
{
return;
}
stack<PNODE> stkTmp;
PNODE pNode = m_pRoot;
PNODE pPreNode = nullptr;
while (true)
{
//一路向左,所有节点入栈
while (pNode!= nullptr)
{
stkTmp.push(pNode); //入栈
pNode = pNode->m_pLeft;//一路向左
}

//栈空,则所有的结点都处理完毕
if (stkTmp.empty())
{
break;
}

//如果上一次处理的是栈顶结点的右子结点,则处理此结点
pNode = stkTmp.top();
if (pNode->m_pRight == pPreNode || pNode->m_pRight == nullptr)
{
cout << pNode->m_val << " ";
pPreNode = pNode;
stkTmp.pop();

//此结点处理完之后,说明右子结点已经处理过了,下次从栈上取结点处理
pNode = nullptr;
continue;
}
//处理又孩子
pNode = pNode->m_pRight;
}
}

void CBinarySearchTree::Level()
{
//如果是空树,则不遍历
if (m_pRoot == nullptr)
{
return;
}
queue<PNODE> quToOut;
quToOut.push(m_pRoot);
while (!quToOut.empty())
{
//取出队首 输出 左右子节点入队
PNODE pNode = quToOut.front();
quToOut.pop();
cout << pNode->m_val << " ";

if (pNode->m_pLeft !=nullptr)
{
quToOut.push(pNode->m_pLeft);
}
if (pNode->m_pRight != nullptr)
{
quToOut.push(pNode->m_pRight);
}

}
}

CBinarySearchTree::PNODE CBinarySearchTree::FindNode(int val)
{
PNODE pNode = m_pRoot;
while (pNode != nullptr)
{
if (pNode->m_val == val)
{
return pNode;
}
else if (val > pNode->m_val)
{
pNode = pNode->m_pRight;
}
else
{
pNode = pNode->m_pLeft;
}
}
return nullptr;
}

void CBinarySearchTree::DelNode(PNODE pNode)
{
//叶子节点
if (pNode->m_pLeft == nullptr && pNode->m_pRight == nullptr)
{
DelLeaf(pNode);
return;
}
//单分支节点
if (pNode->m_pLeft == nullptr || pNode->m_pRight == nullptr)
{
DelSingleChildNode(pNode);
return;
}
//双分支节点
DelDoubleChildNode(pNode);

}

void CBinarySearchTree::DelLeaf(PNODE pNode)
{
PNODE pParent = pNode->m_pParent;

//判断此结点释放为根结点
if (pNode == m_pRoot)
{
delete m_pRoot;
m_pRoot = nullptr;
return;
}

//删除左子节点
if (pParent->m_pLeft == pNode)
{
pParent->m_pLeft = nullptr;
}
//删除右子节点
else
{
pParent->m_pRight = nullptr;
}
//删除节点
delete pNode;
pNode = nullptr;
}

void CBinarySearchTree::DelSingleChildNode(PNODE pNode)
{
PNODE pParent = pNode->m_pParent;



//判断当前节点是含有哪个子节点
PNODE pChild = pNode->m_pLeft;
if (pChild == nullptr)
{
pChild = pNode->m_pRight;
}

//判断是否为根节点
if (pNode == nullptr)
{
m_pRoot = pChild;
pChild->m_pParent = nullptr;
delete m_pRoot;
return;
}


//删除左子节点
if (pParent->m_pLeft == pNode)
{
pParent->m_pLeft = pChild;
}
//删除右子节点
else
{
pParent->m_pRight = pChild;
}

pChild->m_pParent = pParent;

//删除节点
delete pNode;
pNode = nullptr;
}

void CBinarySearchTree::DelDoubleChildNode(PNODE pNode)
{
//查找左子树最大值
PNODE pNodeTmp = pNode->m_pLeft;
while (pNodeTmp->m_pRight != nullptr)
{
pNodeTmp = pNodeTmp->m_pRight;
}

//交换两个值
int nTmp = pNode->m_val;
pNode->m_val = pNodeTmp->m_val;
pNodeTmp->m_val = nTmp;

//删除pNodeTmp
DelNode(pNodeTmp);

}

void CBinarySearchTree::LMR(PNODE pNode)
{
//递归出口
if (pNode == nullptr)
{
return;
}
//中序遍历 先左子结点 再自己 再右子结点
LMR(pNode->m_pLeft);
cout << pNode->m_val << " ";
LMR(pNode->m_pRight);
}

void CBinarySearchTree::MLR(PNODE pNode)
{
//前序
//递归出口
if (pNode == nullptr)
{
return;
}
//中序遍历 再自己 先左子结点 再右子结点
cout << pNode->m_val << " ";
MLR(pNode->m_pLeft);
MLR(pNode->m_pRight);
}

void CBinarySearchTree::LRM(PNODE pNode)
{
//后序
//递归出口
if (pNode == nullptr)
{
return;
}
//中序遍历 先左子结点 再右子结点 再自己
LRM(pNode->m_pLeft);
LRM(pNode->m_pRight);
cout << pNode->m_val << " ";
}

二叉搜索树的时间复杂度

理想状态(满二叉搜索树)

  • 1.插入**Olog(n)**
  • 2.删除**Olog(n)**
  • 3.查询**Olog(n)**
  • 4.修改**Olog(n)**

在非理想状态下(只有左或右结点)时间复杂度将会变为O(n)

二叉平衡树(AVL树)待更新。。

自平衡二叉搜索树(Balanced binary search trees)对树中的任意结点,其左右子树高度差小于等于1。

哈希表

哈希算法

哈希算法也叫信息摘要算法,指的是对算法进行任意长度的输入,得到固定长度的输出,哈希算法也叫散列算法。

常见的哈希算法

  • MD5

  • CRC32

  • SHA1

  • 哈希表

    在数组中挂个链表,链表中的每个结点保存key和数据。

实现一个哈希表

  • CHashTable.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
    #pragma once
    #define MAX_TABLE_SIZE 8
    class CHashTable
    {
    private:
    typedef struct tagNode
    {
    tagNode(int nKey, double dblVal, tagNode* pNext) :
    m_nKey(nKey), m_dblval(dblVal), m_pNext(pNext)
    {}

    int m_nKey;
    double m_dblval;
    tagNode* m_pNext;//指向下一个节点
    }NODE,*PNODE;

    public:
    CHashTable();
    virtual ~CHashTable();

    public:
    bool Insert(int nKey,double dblVAl);
    bool Remove(int nkey);
    double& operator[](int nkey);
    bool Find(int nKey)const;

    private:
    PNODE FindKey(int nKey)const;

    private:
    PNODE m_aryTable[MAX_TABLE_SIZE];
    };
  • CHashTable.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
    101
    102
    103
    #include "CHashTable.h"
    #include <memory.h>
    CHashTable::CHashTable()
    {
    memset(m_aryTable, 0, sizeof(m_aryTable));
    }

    CHashTable::~CHashTable()
    {

    }

    bool CHashTable::Insert(int nKey, double dblVal)
    {
    //判断key是否存在
    PNODE pNode = FindKey(nKey);
    if (pNode != nullptr)
    {
    //key已经存在,则修改其值
    pNode->m_dblval = dblVal;
    return true;
    }

    //获取hash值
    int nIdx = nKey % MAX_TABLE_SIZE;

    //插入新节点
    PNODE pNewNode = new NODE(nKey, dblVal, nullptr);

    //如果为空直接插入
    if (m_aryTable[nIdx] == nullptr)
    {
    m_aryTable[nIdx] = pNewNode;
    return true;
    }

    //如果不为空,将新节点挂到链表头部
    pNewNode->m_pNext = m_aryTable[nIdx];
    m_aryTable[nIdx] = pNewNode;
    return true;
    }

    bool CHashTable::Remove(int nkey)
    {
    PNODE pNode = FindKey(nkey);
    if (pNode == nullptr)
    {
    //没用找到则不删除
    return false;
    }

    //找到了,将此结点的值和头结点做交换,删除头节点
    int nIdx = nkey % MAX_TABLE_SIZE;
    pNode->m_nKey = m_aryTable[nIdx]->m_nKey;
    pNode->m_dblval = m_aryTable[nIdx]->m_dblval;

    //删除头结点
    PNODE pHead = m_aryTable[nIdx];
    m_aryTable[nIdx] = pHead->m_pNext;
    delete pHead;

    return true;

    }

    double& CHashTable::operator[](int nkey)
    {
    PNODE pNode = FindKey(nkey);
    if (pNode != nullptr)
    {
    //找到了
    return pNode->m_dblval;
    }
    //没有找到,则插入新key
    Insert(nkey, 0.0);
    return FindKey(nkey)->m_dblval;
    }

    bool CHashTable::Find(int nKey) const
    {
    return FindKey(nKey) != nullptr;
    }

    CHashTable::PNODE CHashTable::FindKey(int nKey) const
    {
    //获取hash值
    int nIdx = nKey % MAX_TABLE_SIZE;

    //遍历链表
    PNODE pNode = m_aryTable[nIdx];
    while (pNode != nullptr)
    {
    if (pNode->m_nKey == nKey)
    {
    return pNode;
    }

    //取链表的下一个结点
    pNode = pNode->m_pNext;
    }

    return nullptr;
    }