【数据结构1】数据结构的分类、数组和列表的区别、栈(括号匹配问题)、队列(双向对列、环形队列、队列内置模块)、从队列读取文件、栈和队列的应用(迷宫问题-[栈-深度优先搜索]、[队列-广度优先搜索])

本文主要是介绍【数据结构1】数据结构的分类、数组和列表的区别、栈(括号匹配问题)、队列(双向对列、环形队列、队列内置模块)、从队列读取文件、栈和队列的应用(迷宫问题-[栈-深度优先搜索]、[队列-广度优先搜索]),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1 数据结构的分类
2 数组和列表的区别
3 栈
3.1 栈的基本实现
3.2 栈的应用:括号匹配问题
4 队列
4.1 环形队列的实现
4.2 双向对列
4.3 python队列内置模块
4.4 从队列读取文件
5 栈和队列的应用:迷宫问题
6 栈和队列的应用(迷宫问题[队列-广度优先搜索])

1 数据结构的分类

数据结构按照其逻辑结构可分为线性结构、树结构、图结构
线性结构:数据结构中的元素存在一对一的相互关系
树结构:数据结构中的元素存在一对多的相互关系
图结构:数据结构中的元素存在多对多的相互关系

2 数组和列表的区别

数组与列表有两点不同:1.数组元素类型要相同2.数组长度固定

3 栈

栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除操作的列表。
栈的特点:后进先出 LIFO(last-in,frst-out)
栈的概念:栈顶、栈底-栈的基本操作:进栈(压栈):push出栈:pop取栈顶:gettop-栈的实现:使用一般的列表结构即可实现栈进栈:li.append出栈:li.pop取栈顶:li[-1]

在这里插入图片描述

3.1 栈的基本实现

class Stack:def __init__(self):self.stack = []def push(self, element):self.stack.append(element)def pop(self):return self.stack.pop()def get_top(self):if len(self.stack) > 0:return self.stack[-1]return Nonestack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())

3.2 栈的应用:括号匹配问题

def brace_match(s):stack = Stack()match = {'}': '{', ']': '[', ')': '('}for ch in s:if ch in {'(', '[', '{'}:stack.push(ch)else:  # ch in {'}', ']', ')'}if stack.is_empty():return Falseelif stack.get_top() == match[ch]:stack.pop()else:  # stack.get_top() != mathc[ch]return Falseif stack.is_empty():return Truereturn Falseprint(brace_match('[{()}(){()}[]({}){}]'))  # True
print(brace_match('[]}'))  # False

4 队列

队列(Queue)是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除。
进行插入的一端称为队尾(rear),插入动作称为进队或入队
进行删除的一端称为队头(front),删除动作称为出队
队列的性质:先进先出(First-in,First-out)

在这里插入图片描述

4.1 环形队列的实现

环形队列:当队尾指针front ==Maxsize+1时,再前进一个位置就自动到0
队首指针前进1:front=(front+1)% MaxSize
队尾指针前进1:rear=(rear+1)%MaxSize
队空条件:rear ==front
队满条件:(rear+1)% MaxSize == front
class Queue:def __init__(self, size=100):"""初始化一个循环队列。:param size: 队列的最大容量(默认值为100)"""# 创建一个固定大小的列表来存储队列元素self.queue = [0 for _ in range(size)]self.size = size  # 队列的最大容量self.rear = 0     # 队尾指针,指向下一个插入位置self.front = 0    # 队首指针,指向下一个删除位置def push(self, element):"""将元素插入队列。:param element: 要插入的元素:raises IndexError: 如果队列已满,则抛出异常"""if not self.is_filled():  # 检查队列是否已满self.queue[self.rear] = element  # 在队尾位置插入元素self.rear = (self.rear + 1) % self.size  # 更新队尾指针,使用模运算实现循环else:raise IndexError('Queue is filled!')  # 如果队列已满,抛出异常def pop(self):"""从队列中删除并返回队首元素。:return: 从队列中删除的元素:raises IndexError: 如果队列为空,则抛出异常"""if not self.is_empty():  # 检查队列是否为空element = self.queue[self.front]  # 获取队首元素self.front = (self.front + 1) % self.size  # 更新队首指针,使用模运算实现循环return elementelse:raise IndexError('Queue is empty!')  # 如果队列为空,抛出异常def is_empty(self):"""检查队列是否为空。:return: 如果队列为空,返回True;否则,返回False"""# 队列为空的条件是队尾指针和队首指针相同return self.rear == self.frontdef is_filled(self):"""检查队列是否已满。:return: 如果队列已满,返回True;否则,返回False"""# 队列满的条件是队尾指针的下一个位置与队首指针相同return (self.rear + 1) % self.size == self.frontq = Queue(5)
for i in range(4):q.push(i)
print(q.is_filled())  # True

在这里插入图片描述

4.2 双向对列

双向队列的两端都支持进队和出队操作
双向队列的基本操作:队首进队队首出队队尾进队队尾出队

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

4.3 python队列内置模块

使用方法:from collections import deque
创建队列:queue = deque()
p进队:append()
出队:popleft()
双向队列队首进队:appendleft()
双向队列队尾出队:pop()
from collections import deque# 创建一个双向队列(deque)对象 q
# q = deque()# 使用指定的初始元素和最大长度来创建双向队列
q = deque([1, 2, 3], 5)  # 初始化队列 q,包含元素 1, 2, 3,最大长度为 5# 操作单向队列# 队尾进队:将元素 6 添加到队列的末尾
q.append(6)# 队首出队:移除并返回队列的第一个元素
# q.popleft()
print(q.popleft())  # 输出: 1# 操作双向队列# 队首进队:将元素 1 添加到队列的开头
q.appendleft(1)# 队尾出队:移除并返回队列的最后一个元素
q.pop()

4.4 从队列读取文件

from collections import dequedef tail(n):with open('test.txt', 'r') as f:q = deque(f, n)return q# print(tail(5))
for line in tail(5):print(line, end='')

5 栈和队列的应用:迷宫问题

栈:深度优先搜索
回溯法
思路:从一个节点开始,任意找下一个能走的点,当找不到能走的点时,退回上一个点寻找是否有其他方向的点。
使用栈存储当前路径
# 1代表墙  0代表通道
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)   # 右
]def maze_path(x1: int, y1: int, x2: int, y2: int) -> bool:"""在迷宫中寻找从 (x1, y1) 到 (x2, y2) 的路径:param x1: 起点的x坐标:param y1: 起点的y坐标:param x2: 终点的x坐标:param y2: 终点的y坐标:return: 如果找到路径返回 True,并打印路径;否则返回 False"""stack = []  # 用栈来存储路径stack.append((x1, y1))  # 将起点坐标入栈while len(stack) > 0:  # 当栈不为空时,循环寻找路径cur_node = stack[-1]  # 取当前路径的最后一个节点作为当前节点if cur_node[0] == x2 and cur_node[1] == y2:  # 如果当前节点是终点for p in stack:  # 打印路径print(p)return True  # 找到路径,返回 True# 尝试从当前节点向四个方向移动for dir in dirs:next_node = dir(cur_node[0], cur_node[1])  # 计算下一个节点的位置# 如果下一个节点是通道(未访问过)if maze[next_node[0]][next_node[1]] == 0:stack.append(next_node)  # 将下一个节点入栈maze[next_node[0]][next_node[1]] = 2  # 标记该节点已访问过break  # 成功移动到新节点,退出当前循环else:maze[next_node[0]][next_node[1]] = 2stack.pop()  # 如果四个方向都无法移动else:  # 如果栈为空且未找到路径print('无路可走')return False  # 返回 False,表示没有找到路径# 调用迷宫路径寻找函数,从 (1, 1) 到 (8, 8)
print(maze_path(1, 1, 8, 8))

6 栈和队列的应用(迷宫问题[队列-广度优先搜索])

思路:从一个节点开始,寻找所有接下来能继续走的点,继续不断寻找,直到找到出口。
使用队列存储当前正在考虑的节点

图形演示
在这里插入图片描述

from collections import deque# 1代表墙  0代表通道
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)  # 右
]def print_node(path):"""还原并打印从起点到终点的实际路径:param path: 保存路径的列表,每个元素是一个三元组,表示当前节点的坐标和其父节点的索引"""real_path = list()  # 存储实际路径i = len(path) - 1  # 从路径的最后一个节点开始回溯while i >= 0:real_path.append(path[i][0:2])  # 将当前节点的坐标添加到实际路径中i = path[i][2]  # 继续回溯到父节点real_path.reverse()  # 由于是从终点回溯到起点,所以需要反转路径for node in real_path:print(node)  # 打印实际路径中的每个节点坐标def maze_path_queue(x1: int, y1: int, x2: int, y2: int) -> bool:"""使用广度优先搜索(BFS)在迷宫中寻找从 (x1, y1) 到 (x2, y2) 的路径:param x1: 起点的x坐标:param y1: 起点的y坐标:param x2: 终点的x坐标:param y2: 终点的y坐标:return: 如果找到路径返回 True,否则返回 False"""queue = deque()  # 初始化队列用于BFSpath = list()  # 保存已访问节点的路径,每个元素包含节点坐标和其父节点的索引queue.append((x1, y1, -1))  # 将起点节点入队,初始节点没有父节点,因此索引为 -1while len(queue) > 0:  # 当队列不空时,继续寻找路径cur_node = queue.popleft()  # 从队列中取出当前节点path.append(cur_node)  # 将当前节点加入到路径中if cur_node[0] == x2 and cur_node[1] == y2:  # 检查当前节点是否为终点print_node(path)  # 如果到达终点,则打印实际路径return True  # 返回 True 表示成功找到路径# 遍历当前节点的四个可能的移动方向for dir in dirs:next_node = dir(cur_node[0], cur_node[1])  # 计算下一个节点的坐标# 如果下一个节点是通道(未访问过)if maze[next_node[0]][next_node[1]] == 0:queue.append((next_node[0], next_node[1], len(path) - 1))  # 将下一个节点入队,并记录其父节点的索引maze[next_node[0]][next_node[1]] = 2  # 标记该节点已访问过,避免重复访问else:  # 如果队列为空,且未找到路径return False  # 返回 False 表示没有找到路径# 调用迷宫路径寻找函数,从 (1, 1) 到 (8, 8)
print(maze_path_queue(1, 1, 8, 8))

这篇关于【数据结构1】数据结构的分类、数组和列表的区别、栈(括号匹配问题)、队列(双向对列、环形队列、队列内置模块)、从队列读取文件、栈和队列的应用(迷宫问题-[栈-深度优先搜索]、[队列-广度优先搜索])的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1100665

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

GORM中Model和Table的区别及使用

《GORM中Model和Table的区别及使用》Model和Table是两种与数据库表交互的核心方法,但它们的用途和行为存在著差异,本文主要介绍了GORM中Model和Table的区别及使用,具有一... 目录1. Model 的作用与特点1.1 核心用途1.2 行为特点1.3 示例China编程代码2. Tab

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py