Python7-数据结构

ops/2024/12/22 18:26:26/

记录python学习,直到学会基本的爬虫,使用python搭建接口自动化测试就算学会了,在进阶webui自动化,app自动化

python基础7-数据结构的那些事儿

    • 常见的数据结构有哪些?
      • 线性数据结构有哪些?
      • 非线性数据结构有哪些?
      • 生活中有哪些常见的线性结构示例呢?
      • 生活中有哪些常见的非线性结构示例呢?
      • 时间复杂度优先级(从低到高(从优到劣))
    • 列表(数组)的crud有哪些方法呢?时间复杂度如何?
      • 创建(Create)
      • 读取(Read)
      • 更新(Update)
      • 删除(Delete)
    • 链表的crud有哪些方法呢?时间复杂度如何?
      • 创建(Create)
      • 读取(Read)
      • 更新(Update)
      • 删除(Delete)
    • 实践是检验真理的唯一标准


常见的数据结构有哪些?

线性数据结构和非线性数据结构

线性数据结构有哪些?

数组(Array):也叫列表存储固定大小的相同类型元素的集合,其元素可以通过索引进行随机访问。
链表(Linked List):由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针。链表分为单链表、双向链表和循环链表。
栈(Stack):遵循后进先出(LIFO)原则的线性表,主要操作有入栈(push)和出栈(pop)。
队列(Queue):遵循先进先出(FIFO)原则的线性表,主要操作有入队(enqueue)和出队(dequeue)。队列的变种包括双端队列(Deque)和优先队列(Priority Queue)。
字符串(String):字符的序列,可以看作是数组的一种特例,用于存储文本数据。

非线性数据结构有哪些?

树(Tree):由节点和边组成,具有层次结构。常见的树结构包括:
二叉树(Binary Tree):每个节点最多有两个子节点的树。
平衡树(Balanced Tree):如AVL树,通过自平衡操作来保持树的高度平衡。
二叉搜索树(Binary Search Tree, BST):每个节点的值大于或等于其左子树中的所有节点的值,小于或等于其右子树中的所有节点的值。
堆(Heap):一种特殊的完全二叉树,分为最大堆和最小堆,常用于实现优先队列。
B树(B-Tree)和B+树(B+Tree):用于数据库和文件系统的索引结构。
图(Graph):由顶点和边组成,顶点之间通过边相互连接。图可以分为无向图和有向图,还可以是加权图或非加权图。
哈希表(Hash Table):通过哈希函数将键映射到表中的一个位置来访问记录,实现快速的数据查找、插入和删除操作。

生活中有哪些常见的线性结构示例呢?

数组:数组是线性数据结构的一个例子。它存储元素的序列,每个元素都有一个索引,索引是元素在数组中的位置。例如,一个学生的成绩单可以看作是一个数组,其中每个索引对应一门课程的成绩。
链表:链表中的每个元素称为节点,每个节点包含数据和一个指向下一个节点的指针。例如,一个排队系统可以看作是一个链表,其中每个节点代表一个排队的人,指针指向下一个排队的人。
栈:栈是一种后进先出(LIFO)的数据结构。例如,一叠盘子可以看作是一个,最后一个放上去的盘子是第一个被拿下来的。
队列:队列是一种先进先出(FIFO)的数据结构。例如,银行的排队系统可以看作是一个队列,先来的顾客先得到服务。

生活中有哪些常见的非线性结构示例呢?

树:树是一种非线性数据结构,其中每个元素(称为节点)可以有多个子节点。例如,公司的组织结构可以看作是一棵,其中每个部门是一个节点,部门下的员工是子节点。
图:图是由节点(顶点)和边组成的非线性数据结构。例如,社交网络可以看作是一个,其中每个人是一个节点,朋友关系是边。
堆:堆是一种特殊的树形数据结构,其中每个节点的值都大于或等于其子节点的值(最大堆)或小于或等于其子节点的值(最小堆)。例如,一个任务调度系统可以使用来确定下一个要执行的任务。
散列表(哈希表):散列表通过哈希函数将键映射到表中的位置来存储数据。例如,一个电话簿可以看作是一个散列表,其中人名是键电话号码是值

时间复杂度优先级(从低到高(从优到劣))

常数时间复杂度O(1)
无论输入规模如何,算法的运行时间都是常数,不随输入规模变化。例如,访问数组的某个元素。
对数时间复杂度O(logn)
算法的运行时间与输入规模的对数成正比。例如,二分查找算法。
线性时间复杂度O(n)
算法的运行时间与输入规模成正比。例如,遍历数组中的每个元素。
线性对数时间复杂度O(n*logn)
算法的运行时间与输入规模的线性对数成正比。例如,快速排序、归并排序等高效的排序算法。
平方时间复杂度O(n^2)
算法的运行时间与输入规模的平方成正比。例如,冒泡排序、选择排序等简单排序算法。
立方时间复杂度O(n^3)
算法的运行时间与输入规模的立方成正比。例如,某些矩阵乘法算法。
指数时间复杂度O(2^n)
算法的运行时间随着输入规模的增加而指数增长。例如,解决某些组合问题的暴力搜索算法。
阶乘时间复杂度O(n!)
法的运行时间随着输入规模的增加而阶乘增长。例如,解决旅行商问题的暴力搜索算法。

列表(数组)的crud有哪些方法呢?时间复杂度如何?

创建(Create)

append(x):在列表的末尾添加一个元素x。
时间复杂度:O(1)(平均情况,因为可能需要扩容)
insert(i, x):在指定位置i插入一个元素x。
时间复杂度:O(n),因为可能需要移动插入点之后的所有元素。

读取(Read)

索引访问:使用索引访问列表中的元素,例如 list[i]
时间复杂度:O(1)
index(x, start=None, end=None):找出元素x在列表中第一次出现的索引位置。
时间复杂度:O(n),因为可能需要遍历列表直到找到元素x。
count(x):返回x在列表中出现的次数。
时间复杂度:O(n),因为需要遍历整个列表来计数。

更新(Update)

索引赋值:使用索引直接更新列表中的元素,例如 list[i] = x
时间复杂度:O(1)
切片赋值:使用切片语法更新列表中的一段元素,例如 list[i:j] = [x, y, z]
时间复杂度:O(k),其中k是被赋值的元素数量。

删除(Delete)

pop():移除列表中的最后一个元素,并返回该元素。
时间复杂度:O(1)
pop(i):移除列表中指定位置i的元素,并返回该元素。
时间复杂度:O(n),因为可能需要移动删除点之后的所有元素。
remove(x):移除列表中第一次出现的元素x。
时间复杂度:O(n),因为可能需要遍历列表直到找到元素x。
clear():清空列表中的所有元素。
时间复杂度:O(1)
其他操作
sort():对列表中的元素进行排序。
时间复杂度:O(n log n),使用的是Timsort算法。
reverse():反转列表中的元素顺序。
时间复杂度:O(n)
python实战示例,咱就是这些都是一些基础东西,但是再离谱的业务逻辑也是由这些基础函数和方法构成的,所以需要代码加深下理解

# 创建(Create)
from astropy.io.fits import appendmy_list = []  # 创建一个空列表
print("初始列表:", my_list)# append(x):在列表的末尾添加一个元素x
my_list.append(10)
my_list.append(20)
print("使用append添加元素后:", my_list)# insert(i, x):在指定位置i插入一个元素x
my_list.insert(1, 15)  # 在索引1的位置插入15
print("使用insert插入元素后:", my_list)# 读取(Read)
# 索引访问:使用索引访问列表中的元素
print("索引为2的元素:", my_list[2])# index(x, start=None, end=None):找出元素x在列表中第一次出现的索引位置
index_of_10 = my_list.index(10)
print("元素10的索引:", index_of_10)# count(x):返回x在列表中出现的次数
count_of_15 = my_list.count(15)
print("元素15出现的次数:", count_of_15)# 更新(Update)
# 索引赋值:使用索引直接更新列表中的元素
my_list[0] = 5
print("更新索引为0的元素后:", my_list)# 切片赋值:使用切片语法更新列表中的一段元素
# 这里需要注意是左开右比较的
my_list[1:3] = [12, 18]
print("使用切片赋值更新元素后:", my_list)# 删除(Delete)
# pop():移除列表中的最后一个元素,并返回该元素
last_element = my_list.pop()
print("使用pop移除最后一个元素后:", my_list)
print("移除的元素:", last_element)# pop(i):移除列表中指定位置i的元素,并返回该元素
element_at_index_1 = my_list.pop(1)
print("使用pop(1)移除索引为1的元素后:", my_list)
print("移除的元素:", element_at_index_1)# remove(x):移除列表中第一次出现的元素x
my_list.remove(5)
print("使用remove移除元素5后:", my_list)
my_list.append(1)
my_list.append(2)
print("append添加元素1,2",my_list)
# clear():清空列表中的所有元素
my_list.clear()
print("使用clear清空列表后:", my_list)# 其他操作
# sort():对列表中的元素进行排序
another_list = [3, 1, 4, 1, 5, 9, 2, 6]
another_list.sort()
print("排序后的列表:", another_list)# reverse():反转列表中的元素顺序
another_list.reverse()
print("反转后的列表:", another_list)

终端回显:

初始列表: []
使用append添加元素后: [10, 20]
使用insert插入元素后: [10, 15, 20]
索引为2的元素: 20
元素10的索引: 0
元素15出现的次数: 1
更新索引为0的元素后: [5, 15, 20]
使用切片赋值更新元素后: [5, 12, 18]
使用pop移除最后一个元素后: [5, 12]
移除的元素: 18
使用pop(1)移除索引为1的元素后: [5]
移除的元素: 12
使用remove移除元素5: []
append添加元素12 [1, 2]
使用clear清空列表后: []
排序后的列表: [1, 1, 2, 3, 4, 5, 6, 9]
反转后的列表: [9, 6, 5, 4, 3, 2, 1, 1]

在这里插入图片描述

链表的crud有哪些方法呢?时间复杂度如何?

链表是一种线性数据结构,其中的元素通过指针连接在一起。与数组不同,链表中的元素不必存储在连续的内存空间中。

创建(Create)

插入节点
在链表头部插入:创建一个新节点,并将其指针指向当前的头节点,然后更新头节点为新节点。
时间复杂度:O(1)
在链表尾部插入:遍历整个链表找到尾节点,然后在尾节点之后插入新节点。
时间复杂度:O(n),因为需要遍历整个链表。
在链表中间插入:找到插入位置的前一个节点,然后调整指针以插入新节点。
时间复杂度:O(n),因为需要遍历链表直到找到插入位置。

读取(Read)

访问特定节点
需要从头节点开始遍历链表,直到找到目标节点。
时间复杂度:O(n),因为最坏情况下需要遍历整个链表。

更新(Update)

更新节点的值
需要找到目标节点,然后更新其值。
时间复杂度:O(n),因为需要遍历链表直到找到目标节点。

删除(Delete)

删除节点
删除头节点:更新头节点为当前头节点的下一个节点。
时间复杂度:O(1)
删除尾节点或中间节点:需要找到目标节点的前一个节点,然后调整指针以绕过目标节点。
时间复杂度:O(n),因为需要遍历链表直到找到目标节点的前一个节点
其他操作
查找节点
遍历链表,直到找到具有特定值的节点。
时间复杂度:O(n),因为需要遍历整个链表。
反转链表
遍历链表,同时反转每个节点的指针方向。
时间复杂度:O(n)

class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None# 创建(Create)# 在链表头部插入节点def insert_at_head(self, data):new_node = Node(data)new_node.next = self.headself.head = new_node# 在链表尾部插入节点def insert_at_tail(self, data):new_node = Node(data)if not self.head:self.head = new_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_node# 在链表中间插入节点def insert_after_node(self, prev_node_data, data):new_node = Node(data)current = self.headwhile current:if current.data == prev_node_data:new_node.next = current.nextcurrent.next = new_nodereturncurrent = current.nextprint(f"Node with data {prev_node_data} not found.")# 读取(Read)# 访问特定节点def get_node(self, index):current = self.headcount = 0while current:if count == index:return current.datacount += 1current = current.nextreturn "Index out of range."# 更新(Update)# 更新节点的值def update_node(self, old_data, new_data):current = self.headwhile current:if current.data == old_data:current.data = new_datareturncurrent = current.nextprint(f"Node with data {old_data} not found.")# 删除(Delete)# 删除头节点def delete_head(self):if self.head:self.head = self.head.nextelse:print("List is empty.")# 删除尾节点或中间节点def delete_node(self, data):if not self.head:print("List is empty.")returnif self.head.data == data:self.head = self.head.nextreturncurrent = self.headwhile current.next:if current.next.data == data:current.next = current.next.nextreturncurrent = current.nextprint(f"Node with data {data} not found.")# 其他操作# 查找节点def find_node(self, data):current = self.headwhile current:if current.data == data:return Truecurrent = current.nextreturn False# 反转链表def reverse(self):prev = Nonecurrent = self.headwhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodeself.head = prev# 打印链表def display(self):current = self.headwhile current:print(current.data, end=" -> ")current = current.nextprint("None")# 示例用法
ll = LinkedList()# 创建链表
ll.insert_at_head(1)
ll.insert_at_tail(2)
ll.insert_at_tail(3)
ll.insert_after_node(2, 4)
ll.display()  # 输出: 1 -> 2 -> 4 -> 3 -> None# 读取链表
print(ll.get_node(2))  # 输出: 4# 更新链表
ll.update_node(4, 5)
ll.display()  # 输出: 1 -> 2 -> 5 -> 3 -> None# 删除链表
ll.delete_head()
ll.display()  # 输出: 2 -> 5 -> 3 -> None
ll.delete_node(5)
ll.display()  # 输出: 2 -> 3 -> None# 查找节点
print(ll.find_node(3))  # 输出: True
print(ll.find_node(4))  # 输出: False# 反转链表
ll.reverse()
ll.display()  # 输出: 3 -> 2 -> None

终端回显:

1 -> 2 -> 4 -> 3 -> None
4
1 -> 2 -> 5 -> 3 -> None
2 -> 5 -> 3 -> None
2 -> 3 -> None
True
False
3 -> 2 -> None

列表很好理解,链表其实也挺好理解的,就是手拉手的小朋友关系。实际中这种数据结构用的也挺多,虽然后端返回的字段对于前端来说都只是数据类型不一样,可能是对象,可能是大json等
在这里插入图片描述

实践是检验真理的唯一标准


http://www.ppmy.cn/ops/144090.html

相关文章

进网许可认证、交换路由设备检测项目更新25年1月起

实施时间 2025年1月1日起实施 涉及设备范围 核心路由器、边缘路由器、以太网交换机、三层交换机、宽带网络接入服务器(BNAS) 新增检测依据 GBT41266-2022网络关键设备安全检测方法交换机设备 GBT41267-2022网络关键设备安全技术要求交换机设备 GB/…

[oeasy]python054_python有哪些关键字_keyword_list_列表_reserved_words

python有哪些关键字_keyword_list_列表_reserved_words 回忆上次内容 hello world 不是 从来就有的 来自于 c语言 print、小括号 和 双引号 也来自于 c语言 添加图片注释,不超过 140 字(可选) python 标识符 的 命名规则 依然 完全 学习…

[手机Linux] 六,ubuntu18.04私有网盘(NextCloud)安装

一,LNMP介绍 LNMP一键安装包是一个用Linux Shell编写的可以为CentOS/RHEL/Fedora/Debian/Ubuntu/Raspbian/Deepin/Alibaba/Amazon/Mint/Oracle/Rocky/Alma/Kali/UOS/银河麒麟/openEuler/Anolis OS Linux VPS或独立主机安装LNMP(Nginx/MySQL/PHP)、LNMPA(Nginx/MySQ…

基于 SSM 和 Vue 架构的新锐台球厅管理系统:创新设计引领高效实现

1系统概述 1.1 研究背景 如今互联网高速发展,网络遍布全球,通过互联网发布的消息能快而方便的传播到世界每个角落,并且互联网上能传播的信息也很广,比如文字、图片、声音、视频等。从而,这种种好处使得互联网成了信息传…

SQL进阶技巧:如何计算商品需求与到货队列表进出计划?

目录 0 需求描述 1 数据准备 2 问题分析 3 小结 累计到货数量计算 出货数量计算 剩余数量计算 0 需求描述 假设现有多种商品的订单需求表 DEMO_REQUIREMENT,以及商品的到货队列表 DEMO_ARR_QUEUE,要求按照业务需要,设计一个报表&#…

MFC/C++学习系列之简单记录6

MFC/C学习系列之简单记录6 前言CAboutDlg和CMFCtest1Dlg的区别MSFlexGrid的限制输入其他方式 CWndCDC总结 前言 简单的记录一下! CAboutDlg和CMFCtest1Dlg的区别 在使用添加事件后,出现两者,并且在CAboutDlg中无法使用已经定义的控件&#x…

算法 计算大的长方形容器中,存放一排小长形容器,计算出小长形容器中最后一个元素的x坐标的位置的实现方法

1、先上个图: 2、说明 1)中间的蓝色长方形是里面的橙色长方形的容器,比如第一个图中width2width3,因为只有一个,第二个图中有二个小的长方形,也就是说width22width3,第三个图中有3个小长方形&a…

DA-CLIP:Controlling Vision-Language Models for Universal Image Restoration

conference:2024 ICLR paper:https://arxiv.org/pdf/2310.01018 code:https://github.com/Algolzw/daclip-uir 文章目录 作者动机核心思想常见解决方案挑战本文解决方法 贡献方法基本框架Controller的优化与Loss函数数据对的生成基本框架数据…