重学数据结构之行列

一、行列的观点

1.基本观点

  行列(queue)又被称为队,也是一种保留数据元素的容器。行列时一种特殊的线性表,只允许在表的前端(front)举行删除操作,只允许在表的后端(rear)举行插入操作,举行删除操作的一端叫做对头,举行插入操作的一端称为队尾。

  行列根据先进先出的原则(FIFO,First In First Out)存储数据,先存入的元素会先被取出来使用。在行列中插入一个行列元素称为入队,从行列中删除一个行列元素称为出队。

2.抽象数据形貌

  行列的基本操作和栈是类似的,只不过操作名称有些许不一样,下面是一个基本行列的抽象数据形貌:

ADT Queue:

  Queue(self)  # 建立一个空行列

  is_empty(self)  # 判断行列是否为空

  enqueue(self, elem)  # 入队,向行列中插入一个元素

  dequeue(self)  # 出队,从行列中删除一个元素

  peek(self)  # 查看对头位置的元素

3.用 Python 实现

 1 # 自界说行列
 2 class MyQueue:
 3     def __init__(self): 4 self.data = [] 5 6 def is_empty(self): 7 return len(self.data) == 0 8 9 def enqueue(self, elem): 10  self.data.append(elem) 11 12 def dequeue(self): 13 if self.data: 14 ret, self.data = self.data[0], self.data[1:] 15 return ret 16 return None 17 18 def peek(self): 19 return self.data[0] if self.data else None

 

二、行列

1.顺序行列

  顺序行列是行列的顺序存储结构,顺序行列实际上是运算受限的顺序表。和顺序表一样,顺序行列使用一个向量空间来存放当前行列中的元素。由于行列的队头和队尾的位置是转变的,设置两个指针front和rear划分指示队头元素和队尾元素的位置,它们的初值在初始化时都置为0。

2.循环行列

  循环行列将向量空间想象为一个首尾相接的回环,在循环行列中,由于入队时队尾指针向前追赶队头指针,出队时队头指针追赶队尾指针,因而队空和队满时头尾指针均相等。

3.双端行列

  双端行列是一种具有行列和栈的性子的数据结构。双端行列中的元素可以从两头弹出,其限制插入和删除操作在表的两头举行。双端行列是限制插入和删除操作在表的两头举行的线性表。

4.优先级行列

  在优先级行列中,会给每一个元素都分配一个数字用来符号其优先级,例如给其中最小的数字以最高的优先级,这样就可以在一个聚集中接见优先级最高的元素并对其举行查找和删除操作了。

  使用 Python 实现一个优先级行列,可以借助 Python 中的 heapq 模块来实现,heapq 是一个二叉堆的实现,其内部使用内置的 list 工具,对于列表中的每一个元素都知足 a[k] <= a[2 * k + 1] and a[k] <= a[2 * k + 2],因此其默认是一个最小堆,a[0] 是行列中最小的元素。下面是行使 heapq 模块实现的一个优先级行列代码示例:

 1 # 自界说优先级行列
 2 class PriorityQueue:
 3     def __init__(self): 4 self.data = [] 5 self.index = 0 6 7 def push(self, elem, priority): 8 """ 9 入队,将元素插入到行列中 10 :param elem: 待插入元素 11 :param priority: 该元素的优先级 12 :return: 13 """ 14 # priority 加上负号是因为 heapq 默认是最小堆 15 heapq.heappush(self.data, (-priority, self.index, elem)) 16 self.index += 1 17 18 def pop(self): 19 """ 20 出队,从行列中取出优先级最高的元素 21 :return: 22 """ 23 return heapq.heappop(self.data)[-1] 24 25 def size(self): 26 """ 27 获取行列中元素数目 28 :return: 29 """ 30 return len(self.data) 31 32 def is_empty(self): 33 """ 34 判断行列是否为空 35 :return: 36 """ 37 return len(self.data) == 0

 

三、行列的应用

1.迷宫问题

1)问题形貌

中小型管理系统脚手架

  将一个迷宫映射成一个由0和1组成的二维矩阵,迷宫里的空位置用0来示意,障碍和界限用1来示意,最左上角为入口,最右下角为出口,求是否能从迷宫中走出来?

2)问题剖析

  首先在算法初始时,可行的位置用0标识,不可行的位置用1标识,但在搜索路径的历程中需要将已经走过的位置给符号上,这里可以用数字2来符号,在后面的搜索历程中碰着2也就不会重复搜索了。

  当到达一个位置时,需要确定该位置的可行偏向,而除了界限点,每个位置都有四个可行的偏向需要探索,例如对于坐标点(i,j),其四个相邻位置如下图:

  重学数据结构之行列

  为了能够利便的盘算相邻位置,可以用一个列表来纪录:

DIR = [(0, 1), (1, 0), (0, -1), (-1, 0)]

  对于任何一个位置(i,j),都可以划分加上 DIR[0]、DIR[1]、DIR[2]、DIR[3],就能获得相邻位置了。

  为了使算法变得简朴,这里可以先界说两个辅助用的函数,一个用于符号走过的点,一个用于判断输入的位置是否可以通行,详细代码如下:

 1 def mark(maze, pos):
 2     """
 3     将迷宫中已经走过的位置举行符号,设置为2
 4     :param maze: 迷宫
 5     :param pos: 位置
 6     :return:
 7     """
 8     maze[pos[0]][pos[1]] = 2
 9 
10 
11 def passable(maze, pos):
12     """
13     检车迷宫中指定位置是否能走
14     :param maze: 迷宫
15     :param pos: 位置
16     :return:
17     """
18     if pos[0] < len(maze) and pos[1] < len(maze[0]):
19         return maze[pos[0]][pos[1]] == 0
20     return False

3)递归算法求解

  在使用递归算法求解的历程中,对于每一个位置,都有如下的算法历程:

  • 符号当前位置;
  • 检查当前位置是否为出口,若是则解释找到路径,算法竣事,不是则举行下一步;
  • 遍历该位置的相邻位置,使用递归挪用自身;
  • 若是相邻位置都不可行,解释无法从迷宫中走出来,算法竣事。

  递归算法的焦点函数代码如下:

 1 def solution(maze, pos, end):
 2     """
 3     递归算法的焦点函数
 4     :param maze: 迷宫,二维矩阵
 5     :param pos: 当前位置
 6     :param end: 出口
 7     :return:
 8     """
 9     mark(maze, pos)
10     if pos == end:
11         print(pos)
12         return True
13     for i in range(4):
14         next_pos = pos[0] + DIR[i][0], pos[1] + DIR[i][1]
15         if passable(maze, next_pos):
16             if solution(maze, next_pos, end):
17                 print(pos)
18                 return True
19     return False

4)使用行列求解

  基于行列的求解算法照样使用之前的示意方式和辅助函数,但算法历程有转变。

  首先将入口符号为已经到过并入队,然后当行列里另有未探索的位置时,取出一个位置并检查该位置的相邻位置,当相邻位置可行时,若是这个位置就是出口则竣事算法,否则加入到行列中,当整个行列中的元素都被取出来后,行列为空,示意未找到从迷宫中走出来的路径,竣事算法。使用行列求解迷宫问题的算法代码如下:

 1 def queue_solution(maze):
 2     """
 3     使用行列求解迷宫问题
 4     :param maze: 迷宫,二维矩阵
 5     :return: 
 6     """
 7     start, end = (0, 0), (len(maze) - 1, len(maze[0]) - 1)
 8     q = MyQueue()
 9     mark(maze, start)
10     q.enqueue(start)
11     while not q.is_empty():
12         pos = q.dequeue()
13         for i in range(4):
14             next_pos = pos[0] + DIR[i][0], pos[1] + DIR[i][1]
15             if passable(maze, next_pos):
16                 if next_pos == end:
17                     print("Find Path!")
18                     return True
19                 mark(maze, next_pos)
20                 q.enqueue(next_pos)
21     print("No Path!")
22     return False

2.生产者消费者模式

  所谓生产者消费者模式,简而言之就是两个线程,一个饰演生产者,卖力发生数据,另一个饰演消费者,不停获取这些数据并举行处置。而只有生产者和消费者,还算不上生产者消费者模式,还需要有一个缓冲区位于两者之间,生产者把数据放入缓冲区,消费者从缓冲区中取出数据。使用生产者消费者模式有几个利益:解耦,支持并发等。

  在编写爬虫爬取数据时,就可以使用该模式,一个模块不停获取 URL,另一个模块就卖力发送请求和剖析数据,而在其中就可以使用行列作为缓冲区,将待爬取的 URL 都存放在这个行列中,然后爬取模块再从中取出 URL 举行爬取,直至行列为空。这里可以参考我以前写过的一篇博客:https://www.cnblogs.com/TM0831/p/10510319.html

 

原创文章,作者:28qn新闻网,如若转载,请注明出处:https://www.28qn.com/archives/8733.html