线性表
python的list是可变线性表。
-
len()是 O（1）操作
-
元素访问和赋值，尾端加入和尾端删除（包括尾端切片删除）都是O（1）操作。
-
一般位置的元素加入，切片替换，切片删除，表拼接（extend）都是O（n）操作。
-
pop操作默认为删除表尾元素并将其返回O（1），指定非尾端位置为O（n）时间复杂度。
-
lst.clear()清除表lst所有元素O（1）操作。两种实现方式：
a. 元素记数值（表长度）设置为0。实现简单，操作效率高，但不能真正释放占用的存储。若表很长，执行操作后表内没有元素，但仍会占用原有大块内存。
b. 另分配一个空表用的存储区，原存储区直接丢弃。若表又一次增大，会频繁更换存储区。
-
lst.reverse()修改表lst自身，元素顺序倒置O（n）
1
2
3
4
5
6
|
def reverse(self):
elems = self.elements
i, j = 0, len(elems) - 1
while i < j：
elems[i], elems[j] = elems[j], elems[i]
i, j = i+1, j-1
|
-
sort排序， 最好的排序算法的平均和最坏情况时间复杂度都是O（nlogn）
- 最重要特点（优势）是O（1）时间定位元素访问，许多简单操作效率较高。
- 缺陷是加入/删除操作的效率问题，插入删除可能要移动很多元素，操作代价高。
- 只有特殊的尾端插入/删除操作具有O(1)时间复杂度。但插入操作受元素存储区固定大小限制。通过加倍存储区扩充策略（初始分配为空，第一次增长到4个单元，增长率为1.125倍。1.保证O（1）的append,2.防止过多的空闲单元。），尾端插入可达到O（1）。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
## 链接表
### 条件
1. 能够找到表中的首元素。
2. 从任一元素出发，可以找到下一个元素。
### 单链表
- 定义
```python
class LNode:
def __init__(self, elem, next_= None):
self.elem = elem
self.next = next_
|
栈
栈（stack）又名堆栈，是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。
允许进行插入和删除操作的一段称为栈顶（top）,另一端称为栈底（bottom）
栈底固定，栈顶浮动。
栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH）， 删除则称为退栈（POP）。
后进先出（LIFO，Last In First Out）, 后进先出表。
进栈和退栈时间复杂度都为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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Stack(Object):
def __init__(self, limit=10):
""" 创建空栈
"""
self.stack = [] # 存放元素
self.limit = limit # 栈容量限制
def push(self, data):
""" 将元素data加入栈，也常称为压入或推入
"""
# 判断栈是否溢出
if len(self.stack) >= self.limit:
raise IndexError('超出栈的最大容量！')
self.stack.append(data)
def pop(self):
""" 删除栈里最后压入的元素并将其返回，常称为弹出。
"""
if self.stack:
return self.stack.pop()
else:
rasie IndexError('pop from an empty stack')
def top(self):
""" 取得栈里最后压入的（最上面的）元素，不删除。
"""
if self.stack:
return self.stack[-1]
def is_empty(self):
""" 判断栈是否为空， 空时返回True, 否则返回 False
"""
return not bool(self.stack)
def size(self):
""" 取得栈中的元素个数
"""
return len(self.stack)
|
应用：括号匹配
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
|
"""
使用一个堆栈检查括号字符串是否平衡
有效括号字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
举例：
((())): True
((()): False
(())): False
"""
import stack
st = stack.Stack()
input_str = "(()"
for s in input_str:
if st.top() == s:
st.pop()
else:
st.push(s)
result = True if st.is_empty() else False
print(result)
|