Python中的数据结构
#巧用Python列表特性实现特定数据结构
#栈实现
stack = []stack.push(x)stack.pop()stack[-1]
#队列实现
from collections import dequequeue = deque()#单向队列queue.append(x)queue.popleft()#双向队列queue.append(x)queue.popleft()queue.appendleft(x)queue.pop()
#环形队列
#初始dqueue = []rear = 0front = 0#添加一个数据front = (front + 1 ) % MaxSize#一个数据出队rear = (rear + 1 ) % MaxSize#空队条件rear == front #满队条件(rear + 1 ) % MaxSize == front
#巧用Python类特性实现特定数据结构
#链表实现
class Node(object): def __init__(self,item=None): self.item = item self.next = Nonedef main():
head = Node(1) b = Node(2) head.next = bhead -> b -> None
#head为链表首部,有无数据都可以
#遍历链表def traversal(head): currNode = head while currNode is not None: print(currNode.item) currNode = currNode.next#链表的插入、删除#插入#p.next = currNode.next#currNode.next = p#删除#currNode.next = p#currNode.next = currNode.next.next#del p
#双向链表
class Node(object): def __init__(self,item=None): self.item = itme self.next = None self.prev = None#插入#p.next = currNode.next#currNode.next.prev = p #p.prev = currNode#currNode.next = p#删除#p = currNode.next#currNode.next = p.next#p.next.prev = currNode#del p
#链表和列表的效率分析
#按元素查找时间复杂度都为O(n)#按下标查找链表时间复杂度为O(n),列表为O(1)#在某元素后插入数据链表时间复杂度为O(1),列表的时间复杂度为O(n)#删除某元素链表时间复杂度为O(n),列表时间复杂度为O(1)#散列表（Hash表）实现#它是一种线性存储的表结构#首先根据关键字k，进过某Hash函数，获得一个索引值#然后将该关键字存储到索引值所在的位置
#这也是集合的存储原理
#对于字典也是类似的
#字典是对每一个key求索引值，索引值对应的位置存放相应的value#问题一：
#索引值重复#解决一：线性表每个位置采用链表存储，相同索引值得关键字，依次链接起来（拉链法#解决二：通过哈希冲突函数得到新的地址（开放地址法）#利用栈解决迷宫问题
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,1,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] == 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]] = -1 # 标记为已经走过，防止死循环 break else:#四个方向都没找到 maze[curNode[0]][curNode[1]] = -1 # 死路一条,下次别走了 stack.pop() #回溯 print("没有路") return Falsempath(1,1,8,8) from collections import dequemg = [ [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,1,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_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] == x2 and curNode[1] == 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 # 标记为已经走过 return Falsemgpath(1,1,8,8)