6
Python数据结构和算法入门
source link: https://blog.51cto.com/u_16200598/6865754
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一、算法入门
1、时间复杂度
用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度
常见的时间复杂度（按效率排序）为：
复杂问题的时间复杂度：
快速判断算法时间复杂度：
- 确定问题规模n
- 有循环减半过程：logn
- k层关于 n 的循环：n^k
# 时间复杂度
# O(1)
print('Hello World')
n = 10
# O(n)
for i in range(n):
print('Hello World')
# O(n^2)
for i in range(n):
for j in range(n):
print('Hello World')
# O(n^3)
for i in range(n):
for j in range(n):
for k in range(n):
print('Hello World')
# O(logn)
# 当算法过程出现循环折半的时候，复杂度会出现logn
while n > 1:
print(n)
n //= 22、空间复杂度
用于评估执行程序所占用的内存空间,可以估算出程序对计算机内存的使用程度
算法使用了几个变量：O(1) 算法使用了长度为 n 的一维列表：O(n) 算法使用了 m 行 n 列的二维列表：O(mn)
（1）两个特点
（2）举例
x = 3
# 没有结束条件，死递归
def func1(x):
print(x)
func1(x - 1)
# 递归式为 x+1，没有调用自身
def func2(x):
if x > 0:
print(x)
func2(x + 1)
# 先打印，后递归：3 2 1
def func3(x):
if x > 0:
print(x)
func3(x - 1)
# 先递归，后打印:1 2 3
def func4(x):
if x > 0:
func4(x - 1)
print(x)（3）汉诺塔问题
该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上
def hanoi(n, a, b, c):
if n > 0:
hanoi(n - 1, a, c, b)
print('moving from %s to %s' % (a, c))
hanoi(n - 1, b, a, c)
hanoi(64, 'A', 'B', 'C')在一些数据元素中，通过一定得方法找出与给定关键字相同的数据元素的过程
1、列表查找
从列表中查找指定元素（线性表查找），内置列表查找函数index()
li = [3,2,4,5,6,1,7,9,8]
print(li.index(3)) # 0 查找的元素不在列表中会报错2、顺序查找
顺序查找也叫线性查找，从第一个元素开始顺序进行搜索，直到找到元素或者搜索到最后一个元素为止
def linear_search(li,val):
for ind,v in enumerate(li):
if v == val:
return ind
else:
return None
li = [3,2,4,5,6,1,7,9,8]
print(linear_search(li,4)) # 2
# 时间复杂度O(n)3、二分查找(折半查找)
对有序列表进行折半，对比待查找的值和中间值的大小关系进行定位查找
def binary_search(li,val):
left = 0
right = len(li) - 1
while left <= right: # 候选区有值
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val: # 待查找的值在mid左侧
right = mid - 1
else: # 待查找的值在mid右侧
left = mid + 1
else:
return None
li = [1,2,3,4,5,6,7,8,9]
print(binary_search(li,3)) # 2
# 时间复杂度O(logn)
'''
列表升序，大于右，小于左，左加右减
'''二分查找的时间复杂度低，但是它只针对于有序列表；如果查找次数少，二者差距不大； 习题：力扣28、34、162、153、33
# 三种二分查找的模板
def lower_bound(nums, target):
left, right = 0, len(nums) - 1 # 闭区间 [left, right]
while left <= right: # 区间不为空
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # [mid + 1, right]
else:
right = mid - 1 # [left, mid - 1]
return left
def lower_bound2(nums, target):
left, right = 0, len(nums) # 左闭右开区间 [left, right)
while left < right: # 区间不为空
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # [mid + 1, right)
else:
right = mid # [left, mid)
return left # right
def lower_bound3(nums, target):
left, right = -1, len(nums) # 开区间 (left, right)
while left + 1 < right: # 区间不为空
mid = (left + right) // 2
if nums[mid] < target:
left = mid # [mid + 1, right)
else:
right = mid # [left, mid)
return right # right返回有序数组中第一个 >= X 的数的位置，如果所有数都 < X，返回数组长度
\>= X ：正常二分查找 \> X ：转换为 \>= X + 1 < X ：转换为 \>= X - 1（大于等于X左边那个数） \<= X ： 转换为 > X - 1（大于X左边那个数）
三、列表排序
将一组“无序”的记录序列调整为“有序”的记录序列，分为升序和降序，内置排序函数sort()
1、排序LowB三人组
（1）冒泡排序
- 列表每两个相邻的数，如果前面比后面大，则交换这两个数；
- 一趟排序完成后，则无序区减少一个数，有序区增加一个数；
- 代码关键：趟、无序区范围
def bubble_sort(lst):
n = len(lst)
for i in range(n - 1):
for j in range(n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
lst = [3, 2, 4, 5, 6, 1, 7, 9, 8]
print(bubble_sort(lst))# 优化排序次数
def bubble_sort_up(lst):
n = len(lst)
for i in range(n - 1):
exchange = False
for j in range(n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
exchange = True
if not exchange:
return lst
li = [3, 2, 4, 5, 6, 1, 7, 9, 8]
print(bubble_sort_up(lst))（2）选择排序
- 一趟排序记录最小的数，放到第一个位置；再一趟排序记录列表无序区最下的数，放到第二个位置；
- 算法关键：有序区和无序区、无序区最小数位置
def select_sort_simple(lst):
n = len(lst)
new_lst = []
for i in range(n):
# 找到最小值放在new_lst，再从原列表删除最小值
min_val = min(lst)
new_lst.append(min_val)
lst.remove(min_val)
return new_lst
lst = [3, 2, 4, 5, 6, 1, 7, 9, 8]
print(select_sort_simple(lst)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 生成两个列表，占内存；复杂度为O(n^2)def select_sort(lst):
n = len(lst)
for i in range(n):
min_local = i # 最小值出现的位置
for j in range(i + 1, n): # 遍历无序区
if lst[j] < lst[min_local]:
min_local = j
lst[i], lst[min_local] = lst[min_local], lst[i]
return lst
lst = [3, 2, 4, 5, 6, 1, 7, 9, 8]
print(select_sort(lst))
# 时间复杂度为O(n^2)（3）插入排序
类似于打牌接到牌后按顺序插入排序
def insert_sort(lst):
n = len(lst)
for i in range(1, n): # i表示摸到的牌的下标
temp = lst[i] # 表示摸到的牌
j = i - 1 # j指的是手里的牌的下标
while j >= 0 and lst[j] > temp: # j >= 0 表示还有牌摸
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = temp
return lst
lst = [3, 2, 4, 5, 6, 1, 7, 9, 8]
print(insert_sort(lst))
# 时间复杂度为O(n^2)2、排序NB三人组
（1）快速排序
- 取一个元素p(第一个元素)，使元素p归位；
- 列表被p分成两部分，左边都比p小，右边都比p大；
- 递归完成排序
def partition():
pass
def quick_sort(data,left,right):
if left < right:
mid = partition(data,left,right)
quick_sort(data,left,mid-1)
quick_sort(data,mid+1,right)def partition(li,left,right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: # 从右边找到比tmp小的数
right -= 1 # 往左走一个
# 若右边的数都比tmp大，无法退出循环，用left < right控制循环
li[left] = li[right] # 把右边的值写到左边空位上
while left < right and li[left] <=tmp:
left += 1
li[right] = li[left] # 把左边的值写到右边空位上
li[left] = tmp # 把tmp归位
return left
def quick_sort(li,left,right):
if left < right: # 至少两个元素
mid = partition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)
# 时间复杂度为O(nlogn)（2）堆排序
a、树的概念
- 树是一种数据结构；
- 树是一种可以递归定义的数据结构；
- 数是由n个节点组成的的 集合：
- 如果n=0，那这是一棵空树；
- 如果n>0，那存在1个节点作为树的根节点，其他节点可以分别为m个集合，每个集合本身又是一棵树
b、树的相关名称
- 根节点：A就是根节点
- 叶子节点：树的末端，不能再分叉的节点(B、C、H、J、P、Q等)
- 树的深度：树的深度
- 节点的度：每个节点的分叉个数叫做度；F节点的度为3
- 树的度：整个树最大的节点的度；A是最大的节点，所以这个树的度为6
- 孩子节点、父节点：E是I的父节点，I是E的子节点
- 子树：EIJPQ是一个子树
ii、二叉树
- 度不超过2的树；
- 每个节点最多有两个孩子节点；
- 两个孩子节点被区分为左孩子节点和右孩子节点
一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树被称为满二叉树
完全二叉树
叶子节点只能出现在最下层和次次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树
非完全二叉树
c、二叉树的顺序存储方式
- 链式存储方式（链表）
- 顺序存储方式（列表）
记住父节点和孩子节点的下标关系
父节点和左孩子节点的编号关系：
0-1 1-3 2-5 3-7 4-9
父节点和右孩子节点的编号关系：
0-2 1-4 2-6 3-8 4-10
iii、堆
堆是一种特殊的完全二叉树
一棵完全二叉树，满足任意一节点都比其孩子节点大
一棵完全二叉树，满足任意一节点都比其孩子节点小
性质：向下调整性
假设根节点的左右子树都是堆，但根节点不满足堆的性质；可以通过一次向下调整来将其变成一个堆
c、堆排序的过程
- 得到堆顶元素，为最大元素
- 去掉堆顶，将堆最后一个元素放到堆顶，此时可以通过一次调整重新使堆有序
- 堆顶元素为第二大元素
- 重复步骤3，直至堆变空
# 堆调整：大根堆
def sift(lst, low, high):
"""
lst: 列表
low: 堆得根节点位置
high: 堆得最后一个元素的位置
"""
i = low # i 最开始指向根节点
j = 2 * i + 1 # j 开始是左孩子
tmp = lst[low]
while j <= high: # 只要j位置有数
if j + 1 <= high and lst[j + 1] > lst[j]: # 如果右孩子存在并且比左孩子大
j = j + 1 # j指向右孩子
if lst[j] > tmp:
lst[i] = lst[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
lst[i] = tmp
break
else:
lst[i] = tmp # 把tmp放到叶子节点上
def heap_sort(lst):
n = len(lst)
for i in range((n - 2) // 2, -1, -1):
# i表示建堆的时候调整的部分的根的下标
sift(lst, i, n - 1)
# 建堆完成
for i in range(n - 1, -1, -1):
# i指向当前堆得最后一个元素
lst[0], lst[i] = lst[i], lst[0]
sift(lst, 0, i - 1) # i-1是新的high
return lst
lst = [3, 2, 4, 5, 6, 1, 7, 9, 8]
print(heap_sort(lst))
# 时间复杂度为O(nlogn)d、堆排序的内置模块
lst = list(range(10))
random.shuffle(lst)
print(lst)
# 建堆
heapq.heapify(lst)
n = len(lst)
res = []
for i in range(n):
res.append(heapq.heappop(lst))
print(res)（3）归并排序
假设一个列表由两段有序列表组成
3、其他排序
四、数据结构
1、概念：
- 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成
- 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中
- 程序=数据结构+算法
线性结构、树结构、图结构
- 线性结构：数据结构中元素存在一对一的相互关系
- 树结构：数据结构中的元素存在一对多的相互关系
- 图结构：数据结构的元素存在多对多的相互关系
（1）列表
'''
1、概念：栈（Stack）是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表
2、特点：后进先出
3、基本操作：
进栈push、出栈pop、取栈顶gettop
'''
stack = []
# 方法
stack.append() # 压栈
stack.pop() # 出栈
stack[-1] # 查看栈顶元素
if stack: # 判断栈是否为空i、构建栈的类
class Stack:
def __init__(self):
self.stack = []
def push(self,element):
self.stack.append(element)
def pop(self):
return self.stack.pop()
def get_top(self):
if len(self.stack) > 0:
return self.stack[-1]
else:
return None
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())ii、栈的应用
LeetCode20：有效的括号
# 构建栈的类
class Stack:
def __init__(self):
self.stack = []
def push(self,element):
self.stack.append(element)
def pop(self):
return self.stack.pop()
def get_top(self):
if len(self.stack) > 0:
return self.stack[-1]
else:
return None
def brace_match(s):
match = {'}':'{',']':'[',')':'('}
stack = Stack()
for ch in s:
if ch in {'(','[','{'}:
stack.push(ch)
else: # ch in {')',']','}'}
if stack.is_empty():
return False
elif stack.get_top() == match[ch]:
stack.pop()
else: # stack.get_top() != match[ch]:
return True
if stack.is_empty():
return True
else:
return False
s = "{[]}"
print(brace_match(s))
# 利用列表方式
class Solution:
def isValid(self, s: str) -> bool:
data = {'}':'{',']':'[',')':'('}
stack = []
for ch in s:
if ch in {'(','[','{'}:
stack.append(ch)
else:
if stack and stack[-1] == data[ch]:
stack.pop()
else:
return False
if stack:
return False
else:
return True（3）队列
- 队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除
- 进行插入的一端称队尾(rear)，插入动作称为进队或入队
- 进行删除的一端称为队头(front)，删除动作称为出队
- 队列性质：先进先出
i、队列的构建
ii、队列的实现
# Python下的deque模块
import collections
d = collections.deque() # 创建队列
d = collections.deque([1,2,3],4) # 4表示队列长度
d.append() # 往右边添加一个元素
d.appendleft() # 往左边添加一个元素
d.clear() # 清空队列
d.count() # 返回指定元素出现的次数
d.extend() # 从队列右边扩展一个列表的元素
d.extendleft() # 从队列左边扩展一个列表的元素
d.index() # 查找某个元素的索引值
d.insert() # 在队列指定位置插入元素
d.pop() # 获取最右边的一个元素，并在队列中删除
d.popleft() # 获取最左边的一个元素，并在队列中删除
d.remove() # 删除指定元素
d.reverse() # 队列反转
d.rotate() # 把右边元素放到左边iii、队和队列的应用
迷宫问题：给一个二维列表，表示迷宫（0表示通道，1表示围墙）；设计一个算法，求一条走出迷宫的路径
栈：深度优先搜索
# 迷宫问题
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
lambda x, y: (x + 1, y),
lambda x, y: (x - 1, y),
lambda x, y: (x, y - 1),
lambda x, y: (x, y + 1),
]
def maze_path(x1, y1, x2, y2):
stack = []
stack.append((x1, y1))
while len(stack) > 0:
# 记录栈顶元素，指当前节点
curNode = stack[-1]
# x,y表示现在方向,x,y表示行和列；四个方向：x-1,y;x+1,y;x,y-1;x,y+1 上下左右
# 判断是否到达终点，即当前节点是不是等于终点
if curNode[0] == x2 and curNode[1] == y2:
# 走到终点
for p in stack:
print(p)
return True
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
# 如果下一个节点能走，把节点加入栈中
if maze[nextNode[0]][nextNode[1]] == 0:
stack.append(nextNode)
maze[nextNode[0]][nextNode[1]] = 2 # 2表示已经走过，不走回头路
break # 能找到一个能走的点就走，不找了
else:
# 如果一个都找不到，进行出栈回退到上一次的位置
maze[nextNode[0]][nextNode[1]] = 2
stack.pop()
else:
# 栈空表示没有路
print("没有路")
return False
maze_path(1, 1, 8, 8)队列：广度优先搜索
# 队列解决
from collections import deque
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
lambda x, y: (x + 1, y),
lambda x, y: (x - 1, y),
lambda x, y: (x, y - 1),
lambda x, y: (x, y + 1),
]
def print_r(path):
curNode = path[-1]
realpath = []
while curNode[2] != -1:
realpath.append(curNode[0:2])
curNode = path[curNode[2]]
realpath.append(curNode[0:2]) # 起点
realpath.reverse()
for node in realpath:
print(node)
def maze_path_queue(x1, y1, x2, y2):
queue = deque()
queue.append((x1, y1, -1))
path = []
while len(queue) > 0:
curNode = queue.pop()
path.append(curNode)
if curNode[0] == x2 and curNode[1] == y2:
# 终点
print_r(path)
return True
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
if maze[nextNode[0]][nextNode[1]]== 0:
queue.append((nextNode[0], nextNode[1], len(path) - 1))
maze[nextNode[0]][nextNode[1]] = 2 # 标记已经走过的
else:
print("没有路")
return False
maze_path_queue(1,1,8,8)（5）链表
i、链表的定义
链表是由一系列节点组成的元素集合；每个节点包含两个部分，数据域item和指向下一个节点的指针next，节点之间互相连接形成链表
# 链表创建
class Node:
def __init__(self, item):
self.item = item
self.next = None
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
print(a.next.item) # 1
print(a.next.next.item) # 3
print(a.next.next.next.item) # 报错，未定义节点ii、链表的创建和遍历
a、头插法
b、尾插法
class Node:
def __init__(self, item):
self.item = item
self.next = None
# 头插法创建
def creat_linklist_head(li):
head = Node(li[0])
for element in li[1:]:
node = Node(element)
node.next = head
head = node
return head
# 尾插法创建
def creat_linklist_tail(li):
head = Node(li[0])
tail = head
for element in li[1:]:
node = Node(element)
tail.next = node
tail = node
return head
# 读取链表
def print_linklist(lk):
while lk:
print(lk.item, end=' ')
lk = lk.next
lk_head = creat_linklist_head([1, 2, 3])
print(lk_head.item) # 3
print(lk_head.next.item) # 2
print_linklist(lk_head)
lk_tail = creat_linklist_tail([1, 2, 3, 6, 8])
print_linklist(lk_tail)iii、链表的插入和删除
a、链表插入
# 链表删除
p.next = curNode.next # 确定插入位置
curNode.next = p # 更新当前节点
b、链表删除
p = curNode.next # 确定删除节点
curNode.next = curNode.next.next # 链接节点防止丢失
del p
线性数据结构
（6）哈希表
（7）二叉树
i、用树模拟一个文件系统
class Node:
def __init__(self, name, type='dir'):
self.name = name
self.type = type
self.children = []
self.parent = None
def __repr__(self):
return self.name
class FileSystemTree:
def __init__(self):
self.root = Node("/")
self.now = self.root
def mkdir(self, name):
# 以/结尾的
if name[-1] != '/':
name += "/"
node = Node(name)
self.now.children.append(node)
node.parent = self.now
def ls(self):
return self.now.children
def cd(self, name):
# 相对路径
if name[-1] == "/":
name += "/"
if name == "../":
self.now = self.now.parent
return
for child in self.now.children:
if child.name == name:
self.now = child
return
return ValueError("invalid dir")
tree = FileSystemTree()
tree.mkdir("var/")
tree.mkdir("bin/")
tree.mkdir("usr/")
tree.cd("bin/")
tree.mkdir("python/")
print(tree.ls())ii、创建一个树
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
root = e
print(root.lchild.rchild.data) # Ciii、二叉树的遍历
前序遍历：EACBDGF
中序遍历：ABCDEGF
后序遍历：BDCAFGE
层次遍历：EAGCFBD
b、代码实现
# 构造二叉树
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
root = e
# 前序遍历：先遍历根，再遍历左子树，后遍历右子树
def pre_order(root):
if root:
print(root.data, end=',')
pre_order(root.lchild)
pre_order(root.rchild)
# pre_order(root)
# 中序遍历：先遍历左子树，后遍历根，再右子树（把树上下拍扁）
def in_order(root):
if root:
in_order(root.lchild)
print(root.data, end=',')
in_order(root.rchild)
# in_order(root)
# 后序遍历：先遍历左子树，再遍历右子树，后遍历根
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data, end=',')
# post_order(root)
# 层次遍历：按树的深度一层层遍历
from collections import deque
def level_order(root):
queue = deque()
queue.append(root)
while len(queue)>0:
node = queue.popleft()
print(node.data,end=',')
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
level_order(root)（8）二叉搜索树
五、算法入门
1、贪心算法
2、滑动窗口
3、回溯算法
3、动态规划
KMP算法
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK