Python实现常用的数据结构

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)

View Code

#利用队列解决迷宫问题

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)

View Code