Python中的数据结构
#巧用Python列表特性实现特定数据结构
#栈实现
stack = []
stack.push(x)
stack.pop()
stack[-1]
#队列实现
from collections import deque
queue = deque()
#单向队列
queue.append(x)
queue.popleft()
#双向队列
queue.append(x)
queue.popleft()
queue.appendleft(x)
queue.pop()
#环形队列
#初始
dqueue = []
rear = 0
front = 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 = None
def main():
head = Node(1)
b = Node(2)
head.next = b
head -> 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 False mpath(1,1,8,8)
#利用队列解决迷宫问题
from collections import deque 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,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 False mgpath(1,1,8,8)