数据结构与算法python描述_数据结构与算法 Python语言描述 笔记

数据结构

线性表包括顺序表和链表，python的list是顺序表，链表一般在动态语言中不会使用。不过链表还是会出现在各种算法题中。

链表 link list

双链表

循环单链表

字符串 string

有一个重要的点就是字符串的匹配问题，其中比较重要的是无回溯匹配算法(KMP算法)，算法比较复杂，重要的思想在于匹配过程中不回溯。实际复杂度是O(m+n), m和n分别是匹配模式串和目标串，一般m<

通配符 *和?

* 匹配任意一个字符串

？匹配任意一个字符

正则表达式：内容很多，这里就不讲了

原始字符串：在字符串前面加r前缀,\不作为转义符

栈 stack

队列 queue

python3有内置的实现模块

二叉树

基本概念：路径，长度，层数。都比较好理解。

root的层数为0。

二叉树的性质：

性质6.1：在非空二叉树第i层中最多有2^i个节点

性质6.2：高度为h的二叉树最多有2^(h+1)-1个节点

性质6.2：对于任何非空二叉树，如果其叶节点的个数为n0,度数为2的节点个数为n2,那么n0=n2+1

满二叉树：所有分支节点的度数都是2

性质6.4: 满二叉树的叶节点比分支节点多一个

扩充二叉树：把一个二叉树的所有节点变成度数为2的节点（就是这棵树长了一圈叶子），旧节点叫内部节点，新节点叫外部节点。

性质6.5：扩充二叉树的外部路径长度叫E, 内部路径长度叫I, n是内部节点数量， E=I+2*n

完全二叉树：0-(h-1)层的节点都满，并且最后一层的节点都在左边。

性质6.6：完全二叉树节点数为n，则高度h=floor(log2n)

性质6.7：完全二叉树节点数为n, 并从0开始编号（按层次按左右）

root的编号是0

i的父节点是floor((i-1)/2)

if 2i+1

if 2i+2

完全二叉树到线性结构有自然的双向映射

深度优先遍历 depth first traversal, depth first search, DFS

先根序遍历DLR

中根序遍历LDR

后根序遍历LRD

宽度(广度)优先遍历, Breadth First Search, BFS：实现BFS一般要用到一个队列

先根序DFT

def preorder(t, proc):

if not t:

return None

proc(t.val)

preorder(t.left)

preorder(t.right)

广度优先遍历 BFS

def levelorder(t, proc_):

q = Queue()

q.put(t)

while not q.empty():

n = q.get()

if not n:

continue

q.put(n.left)

q.put(n.right)

proc_(n.val)

堆：一个完全二叉树，并且，任意一个节点存放的数据先于其子节点的数据

小顶堆 大顶堆

堆和完全二叉树

堆+一个元素 ->完全二叉树

堆 去掉root 生成两个堆

上面得到的两个堆+新的root -> 完全二叉树

堆去掉最后一个节点，还是堆

堆可以用来构建优先队列(py3已经实现了)

由堆实现的优先队列，创建的时间复杂度是O(n)，插入和弹出是O(logn)

堆还可以用来排序

heap sort python实现

def heap_sort(nums_):

def siftdown(nums_i, e, begin, end):

i = begin

j = begin*2+1

while j < end:

if j + 1 < end and nums_i[j+1] < nums_i[j]:

j += 1

if e < nums_i[j]:

break

nums_i[i] = nums_i[j]

i = j

j = 2*j+1

nums_i[i] = e

end = len(nums_)

for k in range(end//2, -1, -1):

siftdown(nums_, nums_[k], k, end)

for k in range((end-1), 0, -1):

e = nums_[k]

nums_[k] = nums_[0]

siftdown(nums_, e, 0, k)

return nums_[::-1]

heap sort c++实现 序列是数组

c++堆排序

排序算法 sort algorithm

内排序：在内存上排序

外排序

归并是外排序的基础

原地排序算法：空间复杂度为O(1)

稳定性

就是原序列里有一些Key一样的元素，排序之后能否保持不改变这部分序列的相对顺序。

比如key-value pair，按照key 排序：

(0, 100), (1, 50), (1, 60), (1, 45), (-2, 80)

希望排序之后(1, 50), (1, 60), (1, 45)这三个元素的相对位置不变。

适应性

如果一个排序算法对接近有序的序列工作的更快，就称这种算法具有适应性。

也就是说，如果本来已经快排序完了，还差一点，那么算法是能够利用这种优势迅速完成剩下的工作，还是推倒重来，按照原本既定的方法重新排序。

9.2 简单排序算法

插入排序：已经有一个排序完的序列，从剩余序列中顺序拿出一个跟前面的序列挨个比较，寻找合适的位置插入。用于链表不错

选择排序：

简单选择排序：每次找到最小的元素放在最前面

直接选择排序算法：把找到的最小元素和已排序序列后面的元素交换位置。是一个非常烂的算法。别用。

堆排序：堆排序的问题是不稳定

交换排序

冒泡排序

交错排序：从左向右扫描一遍，从右向左再扫描一遍

9.3快速排序