Python7-数据结构

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

---

常见的数据结构有哪些？

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

线性数据结构有哪些？

数组(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添加元素1，2 [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等

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