Python数据结构与算法笔记（七）：数据结构——队列，链表和哈希表

队列

看成人在排队。


在出队到最后一个元素时，再想入队，使用列表可以在后面append，但是前面仍然占据着一部分内存，无法处理。想个办法让其收尾连成一个圈。
队列的实现方式：环形队列
判定一个队列是否为空，rear=front。最后一个图，rear和front之间空一位，是为了更好地判别这个队列是空的还是满的。
规定空的一块空间为队满。

对最大数取余，为0时，进入从0开始的索引。

class Queue:
    def __init__(self,size=100):
        self.queue = [0 for _ in range(size)]
        self.rear = 0 # 队尾指针
        self.front = 0 # 队首指针
        self.size = size
        
    def push(self,element):
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = element
        else:
            raise IndexError('Queue is filled.')
        
    def pop(self):
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError('Queue is empty.')
            
    # 判断队空
    def is_empty(self):
        return self.rear == self.front
    # 判断队满
    def is_filled(self):
        return (self.rear +1) % self.size == self.front

q = Queue(5)
for i in range(4):
    q.push(i)
    
print(q.is_filled())
True

print(q.pop())
0

python队列内置模块

from collections import deque# 双向队列

# 单向队列
q = deque()
q.append(1)# 队尾进队
q.popleft()# 队首出队
1
# 双向队列
q.appendleft(1) # 队首进队
q.pop() # 队尾出队
1

q = deque([1,2,3])
q.append(4)
q.popleft()
1

#队满之后，前面的自动出队
q = deque([1,2,3,4,5],5)
q.append(6)
q.popleft()
2

栈和队列的应用：迷宫问题

使用栈解决迷宫问题

深度优先搜索需要借助栈；
广度优先搜索需要借助队列。

深度优先搜索：
找不到路就往回走。路径不一定是最短的。

按照上右下左的顺序，不走回头路。把走过的路径放在栈里，然后从后往前看，看哪个路能走。没有路就一直出栈。

找到一个出口，然后还是遵循上右下左的原则。

最后走出迷宫。用栈来存储走过的路径。

使用队列解决迷宫问题

广度优先搜索：
考虑多条路。

找到最近的路径。队列用来存储同时考虑的几条路径。

路径进队情况。队列存储的是路径分叉的终端。

找到终点前一个点，逐渐回溯，顺藤摸瓜。
需要存储上一个点的路径。
下面的数字是记录的索引。

这里代码有一些问题：

1. print_r()函数中的’==‘应该是’!=’；
2. maze_path_queue()中的pop()，改成popleft()。代码所使用的内置队列模块的pop()是右出队，应该使用leftpop()才对。
   感谢聪头的评论说明。

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)
]

from collections import deque

def print_r(path):
    curNode = path[-1]

    realpath = []

    while curNode[2] != -1:
        realpath.append(curNode[0:2])
        curNode = path[curNode[2]]

    realpath.append(curNode[0:2])  # 起点
    realpath.reverse()
    for node in realpath:
        print(node)

def maze_path_queue(x1, y1, x2, y2):
    queue = deque()
    queue.append((x1, y1, -1))# 第一个元素起点-1
    # x,y索引
    path = []# 存储路径索引
    while len(queue) > 0:
        curNode = queue.popleft()# 队首出队
        path.append(curNode)
        if curNode[0] == x2 and curNode[1] == y2:
            # 终点
            print_r(path)# 输出所有路径
            return True
        for dir in dirs:# 搜索四个方向
            nextNode = dir(curNode[0], curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                queue.append((nextNode[0], nextNode[1], len(path) - 1))  # 后续节点进队，记录哪个节点带他来的
                maze[nextNode[0]][nextNode[1]] = 2  # 标记为已经走过
    else:
        print("没有路")
        return False

maze_path_queue(1, 1, 8, 8)
(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)

True

链表

链表简介

链表不是固定顺序组成的。节点和节点之间通过箭头链接。

class Node:
    def __init__(self,item):
        self.item = item
        self.next = None

a = Node(1)
b = Node(2)
c = Node(3)

a.next = b
b.next = c

print(a.next.item)
2
print(a.next.next.item)
3
# c之后没有节点
print(a.next.next.next.item)
AttributeError: 'NoneType' object has no attribute 'item'

链表创建和遍历

创建链表：

最左边是头结点。
**头插法：从头部节点插入。**数值倒序。

3连上2，然后头结点指向3。

def create_linklist_head(li):
    head = Node(li[0]) # 头结点
    for element in li[1:]:
        node = Node(element)
        node.next = head# 链接新的数据
        head = node# 转移头部节点位置
    return head

lk = create_linklist_head([1,2,3,6,8])
lk.item
8

lk.next.item
6

print_linklist(lk)
8,6,3,2,1,

**尾插法：从尾巴插入。**需要知道头部和尾部。数值正序。

def create_linklist_tail(li):
    head = Node(li[0])# 根据第一个元素创建头结点
    tail = head # 此时头尾都指向一个
    for element in li[1:]:
        node = Node(element) # 创建新的节点
        tail.next = node # 先链接数据
        tail = node # 让新的node成为尾节点
    return head # 返回head，从head开始往后找

lk = create_linklist_tail([1,2,3,6,8])
print_linklist(lk)
1,2,3,6,8,

链表遍历：

# 依次从头部打印
def print_linklist(lk):
    while lk:
        print(lk.item, end=',')
        lk = lk.next

链表的插入和删除

链表插入：
列表的insert()插入，时间复杂度是O(n)。
由于链表不是顺序存储数据，因此插入时的时间复杂度要小。把两个链解开，然后next插入即可。


第一步，先将4跟2链接起来。如果1跟4链接起来，那么1和2之间就没有链表了。

第二步，再把1跟4链接起来。

链表删除：

第一步，将1跟2链接起来。

第二步，将p删除。

由于没有任何元素的移动，因此执行速度很快。

双链表

之前的链表只能从前向后。双链表，双指向。

双链表插入：

将2跟3链接。




双链表删除：

链表总结

时间复杂度分析：

• 按元素值查找：从头到尾，都是O(n)。
• 按下标查找：列表是O(1)，链表是O(n)，需要从头开始数数。
• 在某元素后插入/删除：列表是O(n)，链表是O(1)。

链表与顺序表：

哈希表

高效的查找的数据结构。

直接寻址表：
所有数的集合：U
T是U的列表。
K是关键字，在T对应的位置上存储数据。想找到K对应的数据，只需要对应的下标即可。


直接寻址表+哈希函数=哈希表

哈希：
之前T是根据U创建的，这次T自己选择大小。
h(k)是做映射，将原来k元素映射到T中，返回的是值是从[0,m-1]。h(k)是哈希函数。

哈希表定义：

哈希冲突：
h(k)得到一样的值，跟原有位置上的数冲突。

解决哈希冲突——开放寻址法：
有值的话，往后找新的位置。逐个往后找位置，然后插入。
在查找的时候也是，第一个位置满足条件，但不是想要的，则往后找符合条件的值。

解决哈希冲突——拉链法：
在冲突的位置，加一个链表来进行存储。
查找的时候先定位，然后遍历链表。

**哈希函数最好是将数据平均分到列表的各个位置上。**共n个数，表长为m。每个表内n/m个元素。需要查找n/m次。

常见的哈希函数：

class LinkList:
    class Node:
        def __init__(self, item=None):
            self.item = item
            self.next = None

    class LinkListIterator:
        def __init__(self, node):
            self.node = node

        def __next__(self):
            if self.node:
                cur_node = self.node
                self.node = cur_node.next
                return cur_node.item
            else:
                raise StopIteration

        def __iter__(self):
            return self

    def __init__(self, iterable=None):# 传一个列表进来
        self.head = None
        self.tail = None
        if iterable:
            self.extend(iterable)

    def append(self, obj):# 插入对象
        s = LinkList.Node(obj)
        if not self.head:
            self.head = s
            self.tail = s
        else:
            self.tail.next = s
            self.tail = s

    def extend(self, iterable):# 往后接列表
        for obj in iterable:
            self.append(obj)

    def find(self, obj):
        for n in self:
            if n == obj:
                return True
        else:
            return False

    def __iter__(self):# 列表支持for循环
        return self.LinkListIterator(self.head)

    def __repr__(self):# 转换字符串
        return "<<"+", ".join(map(str, self))+">>"

lk = LinkList([1,2,3,4,5])
for element in lk:
    print(element)
1
2
3
4
5

# 类似于集合的结构
class HashTable:
    def __init__(self, size=101):
        self.size = size
        self.T = [LinkList() for i in range(self.size)]

    def h(self, k):
        return k % self.size

    def insert(self, k):
        i = self.h(k)
        if self.find(k):
            print("Duplicated Insert.")
        else:
            self.T[i].append(k)

    def find(self, k):
        i = self.h(k)
        return self.T[i].find(k)

哈希表：

# 类似于集合的结构
class HashTable:
    def __init__(self, size=101):
        self.size = size
        self.T = [LinkList() for i in range(self.size)]# 创建T列表

    def h(self, k): # 哈希函数
        return k % self.size

    def insert(self, k):# 插入
        i = self.h(k)
        if self.find(k):
            print("Duplicated Insert.")
        else:
            self.T[i].append(k)

    def find(self, k):# 查找
        i = self.h(k)
        return self.T[i].find(k)

ht = HashTable()

ht.insert(0)
ht.insert(1)
ht.insert(3)
ht.insert(102)
ht.insert(508)

print(",".join(map(str, ht.T)))
<<0>>,<<1, 102>>,<<>>,<<3, 508>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>,<<>>

print(ht.find(3))
True
print(ht.find(203))
False

哈希表的应用：python的集合与字典
把值放在键哈希映射对应的位置上。

哈希表的应用：md5算法


哈希表的应用：SHA2算法