一、数据结构基础
a、什么是数据结构
b、数据结构的分类
c、列表
import random
from timewrap import * def list_to_buckets(li, iteration):
"""
:param li: 列表
:param iteration: 装桶是第几次迭代
:return:
"""
buckets = [[] for _ in range(10)]
for num in li:
digit = (num // (10 ** iteration)) % 10
buckets[digit].append(num)
return buckets def buckets_to_list(buckets):
return [num for bucket in buckets for num in bucket]
# li = []
# for bucket in buckets:
# for num in bucket:
# li.append(num) @cal_time
def radix_sort(li):
maxval = max(li) #
it = 0
while 10 ** it <= maxval:
li = buckets_to_list(list_to_buckets(li, it))
it += 1
return li li = [random.randint(0,1000) for _ in range(100000)]
radix_sort(li)
列表
d、栈
二、栈的Python实现
a、栈的应用——括号匹配为题
def brace_match(s):
stack = []
match = {')':'(', ']':'[', '}':'{'}
match2 = {'(':')', '[':']', '{':'}'}
for ch in s:
if ch in {'(', '[', '{'}:
stack.append(ch)
elif len(stack) == 0:
print("缺少%s" % match[ch])
return False
elif stack[-1] == match[ch]:
stack.pop()
else:
print("括号不匹配")
return False
if len(stack) > 0:
print("缺少%s" % (match2[stack[-1]]))
return False
return True brace_match("[{()[]}{}{}")
括号匹配实现
b、队列
c、队列的实现
d、队列的实现原理——环形队列
e、队列的实现原理——环形队列
f、队列的内置模块
三、栈的应用——迷宫为题
解决思路
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,y+1), #右
lambda x,y:(x+1,y), #下
lambda x,y:(x,y-1), #左
] def solve_maze(x1, y1, x2, y2):
stack = []
stack.append((x1,y1))
maze[x1][y1] = 2
while len(stack) > 0: # 当栈不空循环
cur_node = stack[-1]
if cur_node == (x2,y2): #到达终点
for p in stack:
print(p)
return True
for dir in dirs:
next_node = dir(*cur_node)
if maze[next_node[0]][next_node[1]] == 0: #找到一个能走的方向
stack.append(next_node)
maze[next_node[0]][next_node[1]] = 2 # 2表示已经走过的点
break
else: #如果一个方向也找不到
stack.pop()
else:
print("无路可走")
return False def solve_maze2(x1,y1,x2,y2):
queue = deque()
path = [] # 记录出队之后的节点
queue.append((x1,y1,-1))
maze[x1][y1] = 2
while len(queue) > 0:
cur_node = queue.popleft()
path.append(cur_node)
if cur_node[0] == x2 and cur_node[1] == y2: #到终点
real_path = []
x,y,i = path[-1]
real_path.append((x,y))
while i >= 0:
node = path[i]
real_path.append(node[0:2])
i = node[2]
real_path.reverse()
for p in real_path:
print(p)
return True
for dir in dirs:
next_node = dir(cur_node[0], cur_node[1])
if maze[next_node[0]][next_node[1]] == 0:
queue.append((next_node[0], next_node[1], len(path)-1))
maze[next_node[0]][next_node[1]] = 2 # 标记为已经走过
else:
print("无路可走")
return False solve_maze2(1,1,8,8)
迷宫问题
a、队列的应用
def solve_maze2(x1,y1,x2,y2):
queue = deque()
path = [] # 记录出队之后的节点
queue.append((x1,y1,-1))
maze[x1][y1] = 2
while len(queue) > 0:
cur_node = queue.popleft()
path.append(cur_node)
if cur_node[0] == x2 and cur_node[1] == y2: #到终点
real_path = []
x,y,i = path[-1]
real_path.append((x,y))
while i >= 0:
node = path[i]
real_path.append(node[0:2])
i = node[2]
real_path.reverse()
for p in real_path:
print(p)
return True
for dir in dirs:
next_node = dir(cur_node[0], cur_node[1])
if maze[next_node[0]][next_node[1]] == 0:
queue.append((next_node[0], next_node[1], len(path)-1))
maze[next_node[0]][next_node[1]] = 2 # 标记为已经走过
else:
print("无路可走")
return False solve_maze2(1,1,8,8)
迷宫问题——队列实现
四、链表
import random
from timewrap import * def list_to_buckets(li, iteration):
"""
:param li: 列表
:param iteration: 装桶是第几次迭代
:return:
"""
buckets = [[] for _ in range(10)]
for num in li:
digit = (num // (10 ** iteration)) % 10
buckets[digit].append(num)
return buckets def buckets_to_list(buckets):
return [num for bucket in buckets for num in bucket]
# li = []
# for bucket in buckets:
# for num in bucket:
# li.append(num) @cal_time
def radix_sort(li):
maxval = max(li) #
it = 0
while 10 ** it <= maxval:
li = buckets_to_list(list_to_buckets(li, it))
it += 1
return li li = [random.randint(0,1000) for _ in range(100000)]
radix_sort(li)
列表
def insert_sort(li):
for i in range(1, len(li)):
# i 表示无序区第一个数
tmp = li[i] # 摸到的牌
j = i - 1 # j 指向有序区最后位置
while li[j] > tmp and j >= 0:
#循环终止条件： 1. li[j] <= tmp; 2. j == -1
li[j+1] = li[j]
j -= 1
li[j+1] = tmp def shell_sort(li):
d = len(li) // 2
while d > 0:
for i in range(d, len(li)):
tmp = li[i]
j = i - d
while li[j] > tmp and j >= 0:
li[j+d] = li[j]
j -= d
li[j+d] = tmp
d = d >> 1
练习i——插入
from timewrap import * @cal_time
def binary_search(li, val):
low = 0
high = len(li) - 1
while low <= high:
mid = (low + high) // 2
if li[mid] > val:
high = mid - 1
elif li[mid] < val:
low = mid + 1
else:
return mid
else:
return -1 def find_a(nums, target):
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) // 2
if target <= nums[mid]:
high = mid - 1
else:
low = mid + 1
#[1, 2, 2, 2, 4, 8, 10] if low < len(nums):
return low
else:
return -1 def find_b(nums, target):
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) // 2
if target < nums[mid]:
high = mid - 1
else:
low = mid + 1
if low < len(nums):
return low
else:
return -1 @cal_time
def linear_search(li, val):
try:
return li.index(val)
except ValueError:
return -1 li = [1,2,2,2,4,8,10]
print(find_a(li, 10))
def insert_sort(li):
for i in range(1, len(li)):
# i 表示无序区第一个数
tmp = li[i] # 摸到的牌
j = i - 1 # j 指向有序区最后位置
while li[j] > tmp and j >= 0:
#循环终止条件： 1. li[j] <= tmp; 2. j == -1
li[j+1] = li[j]
j -= 1
li[j+1] = tmp def shell_sort(li):
d = len(li) // 2
while d > 0:
for i in range(d, len(li)):
tmp = li[i]
j = i - d
while li[j] > tmp and j >= 0:
li[j+d] = li[j]
j -= d
li[j+d] = tmp
d = d >> 1