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)

# 使用內(nèi)置函數(shù)操作
# start_2 = time.perf_counter()
# list_1.insert(position-1, value)
# print(time.perf_counter()-start_2) ?# 8*10^-7
# 顯然使用內(nèi)置函數(shù)時插入時使用的時間大大減少

# 海盜問題
# 64個人被海盜劫持 圍成一個圈1-64 依次報數(shù) 每個報數(shù)11的就會被槍決 有32個倒霉蛋會被槍決 哪些位置的倒霉蛋會被槍斃


def pirates(total, out, end):
? ?# 初始化數(shù)據(jù)
? ?result = [] ?# 結(jié)果數(shù)組
? ?index = 0 ?# 索引
? ?number = 0 ?# 報數(shù)計數(shù)
? ?inside_count = total ?# 剩余圈內(nèi)元素
? ?circle = [1]*total ?# 初始化數(shù)組 在圈內(nèi)的狀態(tài)為1
? ?while inside_count > end: ?# 只要圈內(nèi)人數(shù)大于end人數(shù)就執(zhí)行
? ? ? ?number += circle[index] ?# 報數(shù)等于圈內(nèi)的索引
? ? ? ?if number == out: ?# 如果報數(shù)等于出去的數(shù)字
? ? ? ? ? ?result.append(index+1) ?# 在結(jié)果中添加索引+1
? ? ? ? ? ?inside_count -= 1 ?# 圈內(nèi)的人數(shù)-1
? ? ? ? ? ?number = 0 ?# 重新初始化數(shù)字
? ? ? ?index = (index+1) % total
? ? ? ?# 當(dāng)索引index加1后，通過對總數(shù)total取模，可以得到在循環(huán)數(shù)組中的下一個位置。
? ? ? ?# 例如，如果index是2，total是3，那么(2 + 1) % 3的結(jié)果是0，就回到了數(shù)組的起始位置
? ?return result


print(pirates(64, 11, 32))

# 數(shù)組是順序存儲結(jié)構(gòu)的線性表 鏈表數(shù)據(jù)結(jié)構(gòu)同樣是一種線性表 是鏈?zhǔn)絻Υ娼Y(jié)構(gòu) 以連續(xù)和不連續(xù)的儲存單元儲存數(shù)據(jù)
# 鏈表
# 1.單向鏈表 每個數(shù)據(jù)節(jié)點 包括一個數(shù)據(jù)和一個指針 指針指向下一個數(shù)據(jù)列表
# 2.循環(huán)鏈表 循環(huán)列表就是在單向鏈表的基礎(chǔ)上 ?最后一個數(shù)據(jù)節(jié)點指向第一個數(shù)據(jù)節(jié)點
# 3.雙向鏈表 雙向列表就是在單向鏈表的基礎(chǔ)上 ?每個數(shù)據(jù)節(jié)點增加了一個指向前一個數(shù)據(jù)節(jié)點的指針

# 例子
# 創(chuàng)建數(shù)據(jù)節(jié)點對象
class Node:
? ?def __init__(self, data=None):
? ? ? ?self.data = data ?# 數(shù)據(jù)
? ? ? ?# self.next表示指向鏈表中下一個節(jié)點的指針。在鏈表中，每個節(jié)點都有一個指向下一個節(jié)點的指針，
? ? ? ?# 這就是使得鏈表能夠在其中添加、刪除節(jié)點和遍歷節(jié)點的關(guān)鍵所在。當(dāng)我們向鏈表中添加新節(jié)點時，
? ? ? ?# 將當(dāng)前節(jié)點的next指針指向新節(jié)點，從而將其添加到鏈表中。
? ? ? ?# 同樣地，當(dāng)我們遍歷鏈表時，我們可以使用next指針來移動到鏈表中的下一個節(jié)點，并執(zhí)行我們需要的操作
? ? ? ?self.next = None


class LinkedList:
? ?# 初始化鏈表 鏈表頭 鏈長度
? ?def __init__(self):
? ? ? ?self.head = None

? ?# 給鏈表添加數(shù)據(jù) 在尾部添加數(shù)據(jù)
? ?def append(self, data):
? ? ? ?new_node = Node(data)
? ? ? ?# 如果鏈表沒有表頭 則把添加的數(shù)據(jù)作為表頭
? ? ? ?if self.head is None:
? ? ? ? ? ?self.head = new_node
? ? ? ? ? ?return
? ? ? ?curr_node = self.head
? ? ? ?# 鏈表中添加新節(jié)點的功能。它首先將curr_node設(shè)置為鏈表的頭節(jié)點，
? ? ? ?# 然后在鏈表中找到最后一個節(jié)點，最后將新節(jié)點添加到鏈表的末尾。
? ? ? ?while curr_node.next is not None:
? ? ? ? ? ?# 當(dāng)前節(jié)點的指針移動到鏈表中的下一個節(jié)點
? ? ? ? ? ?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()