1、什么是数据结构
2、栈：后进先出
1、什么是栈
栈(Stack)是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。
2、栈的Python实现
stack = [] stack.append(1) # 进栈 stack.append(2) print(stack.pop()) # 最后一个，出去 print(stack[-1]) # 最后一个元素，栈顶
3、栈的应用——括号匹配问题
def check_kuohao(s): stack = [] for char in s: print(stack) if char in {'(', '{', '['}: stack.append(char) # 判断下一个是: ) } ] elif char == ")": if stack[-1] == '(' and len(stack) > 0: stack.pop() else: return False elif char == "}": if stack[-1] == '{' and len(stack) > 0: stack.pop() else: return False elif char == "]": if stack[-1] == '[' and len(stack) > 0: stack.pop() else: return False if len(stack) == 0: return True else: return False strings = "([{()}])" if check_kuohao(strings): print('匹配') else: print('不匹配')
4、栈的应用——迷宫问题：深度优先
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] ]
1、解决思路：逆向游走算法
在一个迷宫节点(x,y)上，可以进行四个方向的探查：maze[x-1][y], maze[x+1][y], maze[x][y-1], maze[x][y+1]
2、栈实现
# -*- coding: utf-8 -*- # @Time : 2018/08/01 0001 14:17 # @Author : Venicid 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 mpath(x1, y1, x2, y2): stack = [] stack.append((x1, y1)) while len(stack) > 0: curNode = stack[-1] if (curNode[0], curNode[-1]) == (x2, 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]] = -1 #标记为已经走过，防止死循环 break else: # 四个方向都没找到 maze[curNode[0]][curNode[1]] = -1 stack.pop() print("没有路") return False mpath(2,2,8,8)
5、队列：先进先出
队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
1、队列能否用list实现？
费时间，费内存
2、队列的使用：from collections import deque
from collections import deque queue = deque() # q = "" queue.append(1) # q = "1" queue.append(2) # q = "1 2" print(queue.popleft()) # q = "2"
3、队列的实现原理——环形队列：求余
环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0。 实现方式：求余数运算 队首指针前进1：front = (front + 1) % MaxSize 队尾指针前进1：rear = (rear + 1) % MaxSize 队空条件：rear == front 队满条件：(rear + 1) % MaxSize == front
6、队列的应用——迷宫问题：广度优先
（1）思路
（2）队列实现
# -*- coding: utf-8 -*- # @Time : 2018/08/01 0001 14:46 # @Author : Venicid mg = [ [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) ] from collections import deque def print_p(path): curNode = path[-1] realpath = [] print('迷宫路径为：') while curNode[2] != -1: realpath.append(curNode[0:2]) curNode = path[curNode[2]] realpath.append(curNode[0:2]) realpath.reverse() print(realpath) def mgpath(x1, y1, x2, y2): queue = deque() path = [] queue.append((x1,y1,-1)) while len(queue) > 0: curNode = queue.popleft() path.append(curNode) if (curNode[0], curNode[1]) == (x2, y2): # 到达终点 print_p(path) return True for dir in dirs: nextNode = dir(curNode[0], curNode[1]) if mg[nextNode[0]][nextNode[1]] == 0: # 找到下一个方块 queue.append((*nextNode, len(path)-1)) mg[nextNode[0]][nextNode[1]] = -1 # 标记我已经走过 else: return False mgpath(2,2,8,8)
7、链表
1、节点
class Node(object): def __init__(self, item=None): self.item = item self.next = None head = Node() a = Node(86) b = Node(19) c = Node(4) a.next = b b.next = c print(a.next.next.item)
2、链表的遍历
class Node(object): def __init__(self, item=None): self.item = item self.next = None # 定义一个链表 head = Node() head.next = Node(20) head.next.next = Node(30) # 遍历列表 def traversal(head): curNode = head # 临时用指针 while curNode is not None: print(curNode.item) curNode = curNode.next traversal(head)
3、链表节点的插入与删除
插入： O(1) p.next = curNode.next curNode.next = p
删除：O(1) p = curNode.next curNode.next = curNode.next.next del p
4、建立链表
（1）头插法
（2）尾插法
5、双链表
双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点
6、链表与列表的对比分析
列表 链表 按元素值查找 O(n) 按下标查找 O(1) O(n) 在某元素后插入 O(n) O(1) 删除某元素 O(n) O(1)
8、Python中的集合与字典（了解）
（1）哈希表查找
哈希表（Hash Table，又称为散列表），是一种线性表的存储结构。通过把每个对象的关键字k作为自变量，通过一个哈希函数h(k)，将k映射到下标h(k)处，并将该对象存储在这个位置。
例如：数据集合{1,6,7,9}，假设存在哈希函数h(x)使得h(1) = 0, h(6) = 2, h(7) = 4, h(9) = 5，那么这个哈希表被存储为[1,None, 6, None, 7, 9]。
当我们查找元素6所在的位置时，通过哈希函数h(x)获得该元素所在的下标（h(6) = 2），因此在2位置即可找到该元素。
（2）哈希冲突
哈希函数种类有很多，这里不做深入研究。
哈希冲突：由于哈希表的下标范围是有限的，而元素关键字的值是接近无限的，因此可能会出现h(102) = 56， h(2003) = 56这种情况。此时，两个元素映射到同一个下标处，造成哈希冲突。
（3）字典 O(1)
使用哈希表存储字典，通过哈希函数将字典的键映射为下标。假设h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4，则哈希表存储为[None, 18, None, ’Alex’, ‘Man’]
（4）列表
