记录python学习，直到学会基本的爬虫，使用python搭建接口自动化测试就算学会了，在进阶webui自动化，app自动化
python基础7-数据结构的那些事儿
常见的数据结构有哪些？
线性数据结构和非线性数据结构
线性数据结构有哪些？
数组(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 append
my_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 = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# 创建（Create）
# 在链表头部插入节点
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
# 在链表尾部插入节点
def insert_at_tail(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
# 在链表中间插入节点
def insert_after_node(self, prev_node_data, data):
new_node = Node(data)
current = self.head
while current:
if current.data == prev_node_data:
new_node.next = current.next
current.next = new_node
return
current = current.next
print(f"Node with data {prev_node_data} not found.")
# 读取（Read）
# 访问特定节点
def get_node(self, index):
current = self.head
count = 0
while current:
if count == index:
return current.data
count += 1
current = current.next
return "Index out of range."
# 更新（Update）
# 更新节点的值
def update_node(self, old_data, new_data):
current = self.head
while current:
if current.data == old_data:
current.data = new_data
return
current = current.next
print(f"Node with data {old_data} not found.")
# 删除（Delete）
# 删除头节点
def delete_head(self):
if self.head:
self.head = self.head.next
else:
print("List is empty.")
# 删除尾节点或中间节点
def delete_node(self, data):
if not self.head:
print("List is empty.")
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
print(f"Node with data {data} not found.")
# 其他操作
# 查找节点
def find_node(self, data):
current = self.head
while current:
if current.data == data:
return True
current = current.next
return False
# 反转链表
def reverse(self):
prev = None
current = self.head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev
# 打印链表
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("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等
