python 数组和链表
import time
n = 500
list_1 = []
for i in range(1, n+1):
list_1.append(i)
position = 200
value = 'x'
# 方法1
start = time.perf_counter()
list_1.append(list_1[n-1])
# [1,2,3,4,5]-->[1,2,3,4,5,5]
for i in range(n, position-1, -1):
# 全部右移动 如果需要在位置[2]插入 [1,2,3,4,5,5]-->[1,2,3,3,4,5]
list_1[i] = list_1[i-1]
list_1[position] = value
print(time.perf_counter()-start) # 2*10^-5
print(list_1)
# 使用内置函数操作
# start_2 = time.perf_counter()
# list_1.insert(position-1, value)
# print(time.perf_counter()-start_2) # 8*10^-7
# 显然使用内置函数时插入时使用的时间大大减少
# 海盗问题
# 64个人被海盗劫持 围成一个圈1-64 依次报数 每个报数11的就会被枪决 有32个倒霉蛋会被枪决 哪些位置的倒霉蛋会被枪毙
def pirates(total, out, end):
# 初始化数据
result = [] # 结果数组
index = 0 # 索引
number = 0 # 报数计数
inside_count = total # 剩余圈内元素
circle = [1]*total # 初始化数组 在圈内的状态为1
while inside_count > end: # 只要圈内人数大于end人数就执行
number += circle[index] # 报数等于圈内的索引
if number == out: # 如果报数等于出去的数字
result.append(index+1) # 在结果中添加索引+1
inside_count -= 1 # 圈内的人数-1
number = 0 # 重新初始化数字
index = (index+1) % total
# 当索引index加1后，通过对总数total取模，可以得到在循环数组中的下一个位置。
# 例如，如果index是2，total是3，那么(2 + 1) % 3的结果是0，就回到了数组的起始位置
return result
print(pirates(64, 11, 32))
# 数组是顺序存储结构的线性表 链表数据结构同样是一种线性表 是链式储存结构 以连续和不连续的储存单元储存数据
# 链表
# 1.单向链表 每个数据节点 包括一个数据和一个指针 指针指向下一个数据列表
# 2.循环链表 循环列表就是在单向链表的基础上 最后一个数据节点指向第一个数据节点
# 3.双向链表 双向列表就是在单向链表的基础上 每个数据节点增加了一个指向前一个数据节点的指针
# 例子
# 创建数据节点对象
class Node:
def __init__(self, data=None):
self.data = data # 数据
# self.next表示指向链表中下一个节点的指针。在链表中，每个节点都有一个指向下一个节点的指针，
# 这就是使得链表能够在其中添加、删除节点和遍历节点的关键所在。当我们向链表中添加新节点时，
# 将当前节点的next指针指向新节点，从而将其添加到链表中。
# 同样地，当我们遍历链表时，我们可以使用next指针来移动到链表中的下一个节点，并执行我们需要的操作
self.next = None
class LinkedList:
# 初始化链表 链表头 链长度
def __init__(self):
self.head = None
# 给链表添加数据 在尾部添加数据
def append(self, data):
new_node = Node(data)
# 如果链表没有表头 则把添加的数据作为表头
if self.head is None:
self.head = new_node
return
curr_node = self.head
# 链表中添加新节点的功能。它首先将curr_node设置为链表的头节点，
# 然后在链表中找到最后一个节点，最后将新节点添加到链表的末尾。
while curr_node.next is not None:
# 当前节点的指针移动到链表中的下一个节点
curr_node = curr_node.next
curr_node.next = new_node
def append_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
curr_node = self.head
while curr_node is not None:
print(curr_node.data)
curr_node = curr_node.next
def delete_at_head(self):
if self.head is not None:
self.head = self.head.next
def delete_at_tail(self):
prev = self.head
curr = self.head.next
while curr.next is not None:
prev = curr
curr = curr.next
prev.next = None
def test_linked_list():
linked_list = LinkedList()
linked_list.append("嘉然")
linked_list.append("星瞳")
linked_list.append("露米")
linked_list.append("向晚")
linked_list.append("贝拉")
linked_list.append_head("龙姬")
linked_list.append_head("永恒")
linked_list.delete_at_tail()
linked_list.delete_at_head()
linked_list.display()
test_linked_list()
