一、数据结构基础
a、什么是数据结构
b、数据结构的分类
c、列表
import randomfrom 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 bucketsdef 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_timedef radix_sort(li): maxval = max(li) # 10000 it = 0 while 10 ** it <= maxval: li = buckets_to_list(list_to_buckets(li, it)) it += 1 return lili = [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 Truebrace_match("[{()[]}{}{}") b、队列
c、队列的实现
d、队列的实现原理——环形队列
e、队列的实现原理——环形队列
f、队列的内置模块
三、栈的应用——迷宫为题
解决思路
from collections import dequemaze = [ [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 Falsedef 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 Falsesolve_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 Falsesolve_maze2(1,1,8,8) 
四、链表
import randomfrom 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 bucketsdef 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_timedef radix_sort(li): maxval = max(li) # 10000 it = 0 while 10 ** it <= maxval: li = buckets_to_list(list_to_buckets(li, it)) it += 1 return lili = [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] = tmpdef 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
from timewrap import *@cal_timedef 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 -1def 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 -1def 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_timedef linear_search(li, val): try: return li.index(val) except ValueError: return -1li = [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] = tmpdef 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