关于Python的高级数据结构与算法
作者:SYBH. 发布时间:2023-12-22 00:29:40
一、简介
在这篇文章中,我们将学习Python中的高级数据结构,如堆、栈、队列、链表等,并使用Python实现常见的算法,如排序、查找等。我们将从以下几个方面来展开本文的内容:
栈(Stack)
队列(Queue)
链表(Linked List)
堆(Heap)
排序算法(Sorting Algorithms)
查找算法(Searching Algorithms)
二、栈(Stack)
栈是一种后进先出(LIFO)的数据结构,只允许在栈顶进行插入和删除操作。在Python中,我们可以使用列表(list)实现栈。
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
三、队列(Queue)
队列是一种先进先出(FIFO)的数据结构,只允许在队尾进行插入操作,而在队头进行删除操作。在Python中,我们可以使用collections
模块中的deque
类实现队列。
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
previous.next = current.next
else:
raise ValueError("Data not found in the list")
四、堆(Heap)
堆是一种特殊的完全二叉树,它的每个节点都大于等于(最大堆)或小于等于(最小堆)其子节点。在Python中,我们可以使用heapq
库实现堆。
import heapq
class MaxHeap:
def __init__(self):
self.items = []
def push(self, item):
heapq.heappush(self.items, -item)
def pop(self):
return -heapq.heappop(self.items)
def peek(self):
return -self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
五、排序算法(Sorting Algorithms)
1. 冒泡排序(Bubble Sort)
冒泡排序是一种简单的排序算法,通过重复遍历列表,比较相邻元素并交换不正确的顺序。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
2. 选择排序(Selection Sort)
选择排序是一种简单的排序算法,每次遍历列表找到最小(或最大)的元素,将其放到正确的位置。
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
3. 插入排序(Insertion Sort)
插入排序是一种简单的排序算法,将未排序的元素逐个插入已排序的序列中。
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
六、查找算法(Searching Algorithms)
1. 顺序查找(Sequential Search)
顺序查找是一种简单的查找算法,通过遍历列表,逐个比较元素来查找目标值。
def sequential_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
2. 二分查找(Binary Search)
二分查找是一种高效的查找算法,要求列表已排序。每次查找都将范围缩小一半,直到找到目标值。
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
小结
在本文中,我们学习了Python中的高级数据结构,如栈、队列、链表、堆,并实现了常见的排序和查找算法。掌握这些数据结构和算法将帮助我们在实际编程中解决各种问题,提高我们的编程技巧和水平。
在后续的文章中,我们将继续探讨更多的Python实战案例,如网络编程、数据分析、爬虫、机器学习等。希望这些文章能够对你的学习和实践带来帮助。
来源:https://blog.csdn.net/m0_68036862/article/details/129905352
猜你喜欢
- ----------记录一下这两天做的一个小demo功能是要实现一个从前端传给后端一张图片,在后端完成目标检测后,传给前端,前端接收后并展示
- 提高SQL执行效率的几点建议:◆尽量不要在where中包含子查询;关于时间的查询,尽量不要写成:where to_char(dif_date
- 一、模板图像处理(1)灰度图、二值图转化template = cv2.imread('C:/Users/bwy/Desktop/nu
- 本文实例讲述了Go语言通过Luhn算法验证信用卡卡号是否有效的方法。分享给大家供大家参考。具体实现方法如下:package mainimpo
- 从有道词典网页获取某单词的中文解释。import reimport urllibword=raw_input('input a wo
- 一、程序运行1.效果展示 - 轮廓描绘看轮廓描绘效果:2.效果展示 - 颜色填充衣服和裤子颜色填充效果:二、实现过程1.绘图数据下载获取地址
- 采用双重循环。把图片进行“.”分割后名字问前面部分,那其余数据库中的 图片路径记录进行对比 采用vb的InStr函数 如果存在的话返回值&g
- 一、Views文件夹 -> Shared文件夹下的 _Layout.cshtml 母版页@RenderBody当创建基于_Layout
- python中函数定义参数有四种形式:def fun1(a,b,c): passdef fun2(a=1,b=2,c=3): &
- 首先,你得下载SocksiPy这个.解压出来之后里面会有一个socks.py文件.然后你可以把这个文件复制到python安装目录里面的Lib
- 假设需要打包的模块文件名为my.py,打包模块需要新建的一个脚本setip.py,然后在脚本下输入如下的内容:from disut
- 一、查询操作可以使用Dataframe的index属性和columns属性获取行、列索引。import pandas as pddata =
- 如果使用Python做大型海量数据批量任务时,并且backend用mongodb做数据储存时,常常面临大量读写数据库的情况。尤其是大量更新任
- 将Excel与Word集成,无缝生成自动报告毫无疑问,微软的Excel和Word是公司和非公司领域使用最广泛的两款软件。它们实际上是“工作”
- 启动sql server Net Start MSSqlServer 暂停sql server Net Pause MSSqlServer
- 一、持久化 --shelve持久化工具(1)作用:类似字典,用kv对保存数据,存取方式类似于字典(2)例子:通过一下案例创建了一个数据库,第
- python3的多行输入问题因为在OJ上做编程,要求标准输入,特别是多行输入。特意查了资料,自己验证了可行性。if __name__ ==
- 登录、注销和登录限制:登录在使用authenticate进行验证后,如果验证通过了。那么会返回一个user对象,拿到user对象后,可以使用
- js实现千分符转化function fmoney(s, n){ n = n > 0 && n <= 20 ? n
- 昨天第一次用python画圆,当时并没有安装numpy库(导入数据包)和matplotlib库(导入图形包),于是尝试用pip安装库首先,我