一、數(shù)據(jù)結構
1、數(shù)據(jù)結構定義
數(shù)據(jù)結構是指相互之間存在這一種或者多種關系的數(shù)據(jù)元素的集合和該集合中元素之間的關系組成。
簡單來說，數(shù)據(jù)結構就是設計數(shù)據(jù)以何種方式組織并存儲在計算機中。
比如：列表、集合與字典等都是一種數(shù)據(jù)結構。
N.Wirth:“程序=數(shù)據(jù)結構+算法”
2、數(shù)據(jù)結構的分類
數(shù)據(jù)結構按照其邏輯結構可分為線性結構、樹結構和圖結構。
（1）線性結構：數(shù)據(jù)結構中的元素存在一對一的相互關系。
（2）樹結構：數(shù)據(jù)結構中元素存在一堆多的相互關系。
（3）圖結構：數(shù)據(jù)結構中的元素存在多對多的相互關系。
二、列表（數(shù)組）
1、列表定義
列表（其他語言稱數(shù)組）是一種基本數(shù)據(jù)類型。
2、關于列表的問題：
（1）列表是如何存儲的？
按順序存儲，且存儲的內容為該值的地址而非值。
（2）列表（Python）和數(shù)組（C語言等）的區(qū)別？
a.數(shù)組元素類型要相同。如果數(shù)組的元素類型不同就不能根據(jù)地址查找元素列表。地址=第一個元素的位置+索引*元素字節(jié)數(shù)量。
b.數(shù)組長度固定。創(chuàng)建數(shù)組需要提前給出數(shù)組的長度。
c.C語言數(shù)組按順序存儲的是值，Python的列表是按順序存儲的值的地址。
（3）列表的基本操作：按下標查找、插入元素、刪除元素.......一系列操作，這些操作的時間復雜度是多少？
1）按下標查找操作的時間復雜度：O(1)
查找操作：一個整數(shù)所占字節(jié)數(shù)與一個地址所占字節(jié)數(shù)相同，在32位機器上是4字節(jié)。所以列表查找需要先通過列表第一個元素的位置+ 4 * 索引，得到該元素的地址，再通過地址找到對應的元素值。
2）插入、刪除的時間復雜度：O(n)
插入或刪除操作：找到需要對應位置后，插入一個元素，后續(xù)的元素都需要往后移動，因此操作了n次。在刪除了某個元素后，列表后面的值都需要往前移動，也是進行了n次操作。
三、棧
1、棧的定義
棧（Stack）是一個數(shù)據(jù)集合，可以理解為只能在一端進行插入或刪除操作的列表。
1)棧的特點：先進后出（后進先出）LIFO（last-in,first-out）
2)棧的概念：棧頂、棧底；
示意圖如下：
3)棧的基本操作：
進棧（壓棧）：push
出棧：pop
取棧頂：gettop
2、棧的實現(xiàn)
使用一般的列表結構即可實現(xiàn)棧。
a.進棧：li.append()
b.出棧：li.pop()
c.取棧頂：li[-1]
(1)代碼實現(xiàn)
# 棧的基本操作stack
class Stack():
def __init__(self):
self.stack = [] #初始為空列表
def push(self,element): #壓棧 element：壓入的值
self.stack.append(element) #往空列表中添加值。
# 不需要return是因為append添加后，需要輸出的是現(xiàn)列表，而現(xiàn)列表不需要特意使用return來輸出
def pop(self): # 出棧
return self.stack.pop() # 用列表的刪除函數(shù)pop()，并返回刪除的值，得到出棧的數(shù)
def get_top(self): # 取棧頂
if len(self.stack) > 0: # 判斷列表是否有數(shù)值
return self.stack[-1] # 返回列表的最后一個值
else:
None
stack = Stack() #類實例化
# 1.進棧
stack.push(2)
stack.push(6)
stack.push("hello")
# 2.出棧
print(stack.pop())
# 3.取棧頂
print(stack.get_top())結果輸出：
hello
63、棧的應用：括號匹配問題
（1）括號匹配問題
1）問題
給一個字符串，其中包括小括號、中括號、大括號，求該字符串中的括號是否匹配。
2）工作原理
將左邊的括號存入棧中，當遇到下一個右邊括號與棧頂?shù)淖筮吚ㄌ柶ヅ鋭t出棧，不匹配留下。當最后棧內是空的時候，說明括號都匹配。
（2）代碼實現(xiàn)
class Stack():
def __init__(self):
self.stack = [] #初始為空列表
def push(self,element): #壓棧 element：壓入的值
self.stack.append(element) #往空列表中添加值。
# 不需要return是因為append添加后，需要輸出的是現(xiàn)列表，而現(xiàn)列表不需要特意使用return來輸出
def pop(self): # 出棧
return self.stack.pop() # 用列表的刪除函數(shù)pop()，并返回刪除的值，得到出棧的數(shù)
def get_top(self): # 取棧頂
if len(self.stack) > 0: # 判斷列表是否有數(shù)值
return self.stack[-1] # 返回列表的最后一個值
else:
None
def is_empty(self): # 棧為空
return len(self.stack) == 0 # 列表長度為0，為空棧
? ? ? ? # 等價于：
? ? ? ? # if len(self.stack) == 0:
? ? ? ? # return True
? ? ? ? # else:
? ? ? ? # return False
# 括號匹配問題
def brace_match(str): # str為字符串
stack = Stack() # 創(chuàng)建空棧
match = {')': '(', ']': '[', '}': '{'} # 符號匹配字典
for ch in str: # 遍歷字符串里的每個字符
if ch in {'(','[','{'}: # '(','[','{'的集合
stack.push(ch) # 進棧
else: # 符號不是'(','[','{'
if stack.is_empty(): # 棧是空的，沒有左邊的括號入棧
return False #報錯
elif stack.get_top() == match[ch]: #棧頂值對比
stack.pop() # 出棧
else: #棧頂值與括號不匹配 stack.get_top != match[ch]
return False
if stack.is_empty(): #遍歷結束字符串，棧為空
return True
else: #棧不為空
return False
print(brace_match('{([[]({}[]())])}'))
print(brace_match('[]{}([})'))輸出結果：
True
False四、隊列
1、隊列的定義
隊列(Queue)是一個數(shù)據(jù)集合，僅允許在列表的一端進行插入，另一端進行刪除。
a.進行插入的一端為隊尾(rear)，插入動作稱為進隊或入隊。
b.進行刪除的一端稱為隊頭(front)，刪除動作稱為出隊。
c.隊列的性質：先進先出（First-in，F(xiàn)irst-out）。
2、隊列的實現(xiàn)
（1）隊列的實現(xiàn)方式-環(huán)形隊列
1）使用環(huán)形隊列，如下圖：
其中，rear（隊尾）和front（隊頭）初始位置都是0，隊滿的時候為了區(qū)分與初始隊空的區(qū)別，犧牲一小點點內存，其中一小格無數(shù)據(jù)。每次有數(shù)據(jù)插入，則隊尾rear指針往前移動，每次數(shù)據(jù)出隊時，隊頭front往前移動。
2）實現(xiàn)環(huán)形隊列的內部關系
環(huán)形隊列：當隊尾或隊首的指針佛入front&rear == Maxsize - 1時，再前進一個位置就自動到0。(Maxsize是隊列的大小)
隊首指針前進1：front = （front + 1）%Maxsize
隊尾指針前進1：rear = （rear +1）%Maxsize
隊空條件：rear == front
隊滿條件：（rear +1）%Maxsize == front
（2）隊列代碼實現(xiàn)
# 實現(xiàn)簡單的隊列
class Queue(): # 隊列,類的括號里填的是繼承關系
def __init__(self,size): #初始化屬性設置
self.queue = [0 for i in range(size)] # 創(chuàng)建初始列表，列表長度確定且都為0
self.size = size # 隊列規(guī)模
self.rear = 0 # 隊尾指針初始位置
self.front = 0 # 隊首指針初始位置
def push(self, element): # 入隊
if not self.is_filled(): # 隊列不滿才能入隊
self.rear = (self.rear + 1) % self.size # 找到插入隊列的位置
self.queue[self.rear] = element # 填入元素
else:
# 報錯，raise()函數(shù)，手動設置異常，IndexError異常指列表索引超出范圍
raise IndexError("Queue is filled.")
def pop(self): # 出隊
if not self.is_empty(): # 隊列不空才能出隊
self.front = (self.front + 1) % self.size # 找到隊尾最后一個元素要刪除的位置，最開始front指針指向空位
return self.queue[self.front] # 返回這個值，不需要pop操作，后續(xù)插入的數(shù)值可直接覆蓋，pop的時間復雜度較高
else:
raise IndexError("Queue is empty.")
def is_empty(self): # 隊列是否為空
return self.rear == self.front # 隊尾與隊首的位置相同時，隊列為空，即兩者相同時，返回True
def is_filled(self): # 隊滿
return self.front == (self.rear + 1) % self.size # 隊尾往前一步是隊首的時候，將返回True
queue = Queue(10) #隊列實例化
# 1.入隊
for i in range(9):
queue.push(i)
# 2.出隊
print(queue.pop())
# # 3.隊空或隊滿判斷
print(queue.is_empty())
queue.push(9)
print(queue.is_filled())結果輸出：
0
False
True3、隊列的內置模塊
（1）雙向隊列
雙向隊列的兩端都支持進隊和出隊操作。
雙向隊列的基本操作：
a.隊首進隊
b.隊首出隊
c.隊尾進隊
d.隊尾出隊
（2）python隊列內置模塊的基本函數(shù)
模塊：from collections import deque
創(chuàng)建隊列：queue = deque()，空隊列。
deque(列表，size)：可以傳入兩個參數(shù)，第一個是用于創(chuàng)建非空隊列，傳入列表數(shù)據(jù)；size是指定列表的規(guī)模大小。
其中，deque()隊滿的不會報錯，而是前面的數(shù)據(jù)將自動出隊。
隊尾進隊：append()
隊首出隊：popleft()
隊首進隊：appendleft()
隊尾出隊：pop()
（3）內置模塊實現(xiàn)隊列代碼
from collections import deque # 雙向隊列模塊
# 單向隊列
que = deque() # 創(chuàng)建空隊列
que.append(1) # 隊尾進隊
print(que.popleft()) # 隊首出隊
# 用于雙向隊列
que.appendleft(2) # 隊首進隊
print(que.pop()) # 隊尾出隊
# deque()參數(shù)應用
que2 = deque([0,1,2,3,4], 5) # 創(chuàng)建非空隊列，且定義隊列的規(guī)模為5
que2.append(5) # 隊滿，仍進隊
print(que2.popleft()) # 隊滿進隊后，原隊首數(shù)據(jù)自動出隊，現(xiàn)出隊數(shù)據(jù)為1.輸出結果：
1
2
1（4）讀取文件的最后幾行——隊列模塊的隊滿性質
讀取文件的后幾行的普通操作是先讀取整個文件，再切片后幾行，這樣操作的內存占比大?？梢允褂胐eque()模塊的性質，隊滿后入隊，前面數(shù)據(jù)自動出隊，可以更高效快捷的獲取文件后面的內容。但是讀取文件前面的內容，直接使用readline()函數(shù)即可。
如果需要讀取txt文件的中文進隊列，需要更改中文的編碼為字節(jié)類型，否則無法讀取GBK格式。
代碼實現(xiàn)：
# deque()隊滿性質-另一端自動出隊
# 讀取文件的后幾行，普通操作，讀取整個文件，切片后幾行，內存占比大
def tail(n): # n是需要讀取的數(shù)量
with open('p52_test.txt', 'r') as f: # with語句自動化關閉資源，不需要手動關閉
q = deque(f, n) # 隊列內容為文件f，隊列規(guī)模為n，獲取隊尾的n列
return q
for line in tail(4):
print(line, end = "")結果輸出：
My pillow is my best friend,
it makes me feel comfortable when I sleep.
My bed is also very comfortable,
it's where I spend most of my time.（5）隊列模塊代碼總結
1）with語句的應用
with語句是 Python 中的一種常用語法，用于自動化地管理對象的生命周期。它通常用于打開資源，例如文件、數(shù)據(jù)庫連接等，并在代碼塊結束時自動關閉這些資源。
with的語法結構：
with object [as variable] [try-except-finally]:
code_block # 代碼塊解釋：
object：管理的資源對象，例如，文件、數(shù)據(jù)庫連接等。
Variable：自定義存儲資源對象的變量?？梢岳斫鉃?Variable = object。
try-except-finally：是 with 語句的可選部分，用于處理在代碼塊中發(fā)生錯誤的情況。
with的簡單例子，with語句能支持打開多個文件：
with open('file1.txt', 'w') as f1, open('file2.txt', 'w') as f2:
f1.write('Hello, file1!')
f2.write('Hello, file2!') 五、棧和隊列的應用：迷宮問題
1、迷宮問題
給一個二維列表，表示迷宮（0表示通道，1表示圍墻）。給出算法，求一條走出迷宮的路徑。
如下圖所示：
|
|
2、棧的解題
（1）棧的思路——深度優(yōu)先搜索
深度優(yōu)先搜索，又稱為回溯法。
解題思路：
從一個節(jié)點開始，任意找到下一個能走的點，當找不到能走的點時，退回上一個點尋找是否有其他方向的點。（回退前走過的點將會標記為不能走的點。）
使用棧存儲當前路徑。
優(yōu)劣：
優(yōu)點：代碼簡單；
缺點：不一定得到的是最短路徑。
（2）代碼實現(xiàn)
# 迷宮問題
#迷宮
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
lambda x, y: (x+1, y),
lambda x, y: (x, y+1),
lambda x, y: (x-1, y),
lambda x, y: (x, y-1)
] # lambda函數(shù)，匿名函數(shù)，是簡單函數(shù)的簡寫版本
# 向下，右，向上，左順序尋找
# 迷宮求解
def maze_path(x1,y1,x2,y2): #（x1，y1）表示初始起點，(x2,y2)表示終點坐標
stack = [] # 創(chuàng)建空棧,棧內存儲元組，即各點坐標
stack.append((x1, y1)) #起點位置進棧，(x1,y1)為起點坐標的元組
while len(stack) > 0: #棧不空時，?？諞]有路
curNode = stack[-1] #棧頂位置，當前節(jié)點的坐標（x，y）
if curNode[0] == x2 and curNode[1] == y2: # 當前節(jié)點為終點
for p in stack: #遍歷輸出坐標點
print(p)
return True
# 當前坐標的四個方向，(x+1,y)/(x-1,y)/(x,y+1)/(x,y-1),坐標移動
for dir in dirs: # dir為一個lambda式,輸出為元組
nextNode = dir(curNode[0],curNode[1]) # dir的lambda式需要x，y兩個參數(shù)，curNode[0]=x,curNode[1]=y
# 下一個節(jié)點能走，即值為0
if maze[nextNode[0]][nextNode[1]] == 0: #二維列表取數(shù)用maze[x][y]，x=nextNode[0],y=nextNode[1]
stack.append(nextNode) # 進棧
maze[nextNode[0]][nextNode[1]] = 2 # 表示該點走過了
break # 只要找到一個可以走的位置就結束for循環(huán)
else:
stack.pop() # 出棧
# while循環(huán)中沒有return，則未找到路
print("沒有路")
return False
maze_path(1,1,8,8)輸出結果：
(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)（3）代碼說明
1）與視頻中代碼對比，做了2點修改：
遍歷for循環(huán)后，不需要再運行 maze[nextNode[0]][nextNode[1]] = 2 這一步，因為無法找到出路，說明四周可能都是墻以及走過的路，走過的路已經是2了，墻沒必要改成2。
結束while循環(huán)后，不需要寫else，本身就是不達到while循環(huán)條件才結束的循環(huán)，運行下面的代碼。若在滿足while循環(huán)中就已經得到結果，會直接return輸出，不會在繼續(xù)運行代碼。
2）for....else...語法
for 臨時變量 in 序列：
? ? 重新執(zhí)行代碼塊
? ? return
else:
? ? for循環(huán)正常結束未執(zhí)行return，則執(zhí)行的代碼所謂else指的是循環(huán)正常結束后要執(zhí)行的代碼，即如果是break終止循環(huán)或者return結束循環(huán)的情況，else下方縮進的代碼將不執(zhí)行。
3）lambda表達式的運用
lambda 表達式，又稱匿名函數(shù)，常用來表示內部僅包含 1 行表達式的函數(shù)。如果一個函數(shù)的函數(shù)體僅有 1 行表達式，則該函數(shù)就可以用 lambda 表達式來代替。
lambda表達式：
name = lambda [list]:表達式[list]表示可選參數(shù)，等同于定義函數(shù)的參數(shù)；name為該表達式的名稱。
對比普通寫法與lambda表達式：
# 簡單函數(shù)寫法
def add(x, y):
? ? return x + y
#轉化為lambda表達式
add = lambda x, y: x + y3、用隊列解決迷宮問題
（1）隊列的思路—廣度優(yōu)先搜索
1）基本思路
從一個節(jié)點開始，尋找所有接下來能繼續(xù)走的點，繼續(xù)不斷尋找，直到找到出口。
使用隊列存儲當前正在考慮的節(jié)點。
2）實現(xiàn)思路的操作
轉換為具體的位置示意圖：
找到1，入隊，[1]；
找到2，1出隊，2入隊, [2];
找到3，2出隊，3入隊，[3];
找到4和5,3出隊，4和5入隊，[4,5];
4找到6,4出隊，6入隊，[5,6];
5找到7,5出隊，7入隊，[6,7];
.........依次類推，隊列中存儲正在考慮的節(jié)點。
直到找到終點位置的坐標，再倒回去根據(jù)存儲在另一個列表的索引找到對應之前的值。如下圖，
第一行為隊列中依次出隊的數(shù)字，第二隊為當前數(shù)字的前一個數(shù)字在列表中的索引。
（2）代碼實現(xiàn)
# 用隊列求解迷宮問題
from collections import deque # 調用隊列模塊
#迷宮
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
lambda x, y: (x+1, y),
lambda x, y: (x, y+1),
lambda x, y: (x-1, y),
lambda x, y: (x, y-1)
] # lambda函數(shù)，匿名函數(shù)，是簡單函數(shù)的簡寫版本
# 向下，右，向上，左順序尋找
def print_r(path): # 根據(jù)元組最后一位索引值，找到前一個點元素，依次輸出點的坐標。path為含有三維元組的列表
curNode = path[-1] # 當前的元素為列表的最后一個元素，可以理解為終點為最后一個元素
realpath = [] # 存儲找到的路徑所經過的點坐標
while curNode[2] != -1: # 當前不是起點坐標，則循環(huán)，從終點開始往回倒。
realpath.append(curNode[0:2]) # 循環(huán)最開始的curNode是終點，將其坐標添加到路徑列表中，后續(xù)的元素為根據(jù)終點倒推的點
curNode = path[curNode[2]] #curNode[2]是經過現(xiàn)在點的上一個點在path列表中的下標，根據(jù)下標找到該點的值，并替換curNode
realpath.append(curNode[0:2]) # 結束while循環(huán)，當需要將起點加入到路徑列表中，起點即為curNode[2]==-1的點
realpath.reverse() # 列表中數(shù)據(jù)的反轉
for n in realpath: #遍歷打印路徑的各點
print(n)
def maze_path_queue(x1,y1,x2,y2): # 輸入起點和終點
queue = deque() # 創(chuàng)建空隊列
queue.append((x1,y1,-1)) # 起點坐標進隊，最后一位存儲的是上一個點坐標在列表中的下標，起點前沒有元素，指定為-1
path = [] # 存儲所有出隊的點坐標
while len(queue) > 0: # 隊列不為空，隊列空了就沒路了
curNode = queue.popleft() # 目前的點坐標為隊列的隊首，并出隊
path.append(curNode) # 出隊的點加入到列表中
if curNode[0] == x2 and curNode[1] == y2: # 現(xiàn)坐標點與終點坐標一致，找到終點
print_r(path) # 自定義函數(shù)，輸出path列表中相應的值
return True
for node in dirs: # 遍歷上下左右找下一個可以走的點
nextNode = node(curNode[0],curNode[1]) #下一個點的坐標
if maze[nextNode[0]][nextNode[1]] == 0: # 下一個點坐標對應的值為0，路可以走
queue.append((nextNode[0], nextNode[1], len(path)-1)) # 每次循環(huán)的curNode位于path的最末尾
maze[nextNode[0]][nextNode[1]] = 2 # 標記該點已走
else:
print("no path")
return False
maze_path_queue(1,1,8,8)輸出結果：
(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)（3）代碼說明
1）對視頻中的2處錯誤做了修正：
第44行，隊列是從隊首出隊，所以是popleft()函數(shù)。
第30行，curNode[2] != -1，表示到達起點后不循環(huán)，視頻中用的==是錯誤的。
2）reverse()函數(shù)
python中列表的一個內置方法(在字典、字符串和元組中沒有這個內置方法)，用于列表中數(shù)據(jù)的反轉。
代碼示例：
li = [4, 3, 2, 1]
li.reverse()
print(li)
#輸出結果
[1, 2, 3, 4]六、鏈表
1、定義
（1）概念
鏈表是由一系列節(jié)點組成的元素集合。每個節(jié)點包含兩部分，數(shù)據(jù)域item和指向下一個節(jié)點的指針next。通過節(jié)點之間的相互連接，最終串聯(lián)成一個鏈表。
（2）鏈表節(jié)點基本寫法
class Node(object):
? ? def __init__(self, item):
? ? ? ? self.item = item
? ? ? ? self.next = None（3）手動鏈表簡單實現(xiàn)
# 鏈表實現(xiàn)
class Node():
def __init__(self, item): # 初始化
self.item = item
self.next = None # 最初不存在
# 傳入節(jié)點數(shù)據(jù)
a = Node(1) #類實例化為對象
b = Node(2)
c = Node(3)
# 創(chuàng)建鏈接
a.next = b # a的下一個是b
b.next = c # b的下一個是c
print(a.item) #輸出為1
print(a.next.item) # 輸出為b點，2
print(a.next.next.item) # 輸出為c點，3
print(b.item)
print(b.next.item) #輸出為c點，3輸出結果：
1
2
3
2
32、鏈表的創(chuàng)建和遍歷
創(chuàng)建鏈表的方法有頭插法和尾插法。
（1）創(chuàng)建鏈表-頭插法
首先，如上圖所示，需要有一個head指針，head指向頭節(jié)點，當前面再插入新的元素時，head指針更新，重新指向新的頭節(jié)點，而新插入的節(jié)點與前一個節(jié)點建立鏈接，結果如下圖。
（2）創(chuàng)建列表-尾插法
如上圖所示，尾插法需要有head和tail兩個指針，當有新元素插入是，從鏈表的尾部插入，且tail指針向后移動，結果如下圖。
（3）頭插法-代碼實現(xiàn)
# 鏈表的創(chuàng)建與遍歷
class Node():
def __init__(self, item):
self.item = item
self.next = None
# 頭插法
def creat_linklist_head(li): # 傳入參數(shù)為列表
head = Node(li[0]) # 最開始的head指針，指向列表第一個元素
for element in li[1:]: # 從列表的第2個元素開始插入到列表中
node = Node(element) # 列表元素傳入鏈表節(jié)點
node.next = head # 將該節(jié)點與前一個點鏈接
head = node # 指針head指向新插入的元素
return head # 返回鏈表的第一個元素
# 遍歷鏈表
def print_lk(lk): # 參數(shù)lk：鏈表
while lk: # lk.next不為none
print(lk.item, end = " ") # 打印值
lk = lk.next # 進入下一個點
lk = creat_linklist_head([1,2,3])
print_lk(lk)輸出結果：
3 2 1 （4）尾插法-代碼實現(xiàn)
# 鏈表的創(chuàng)建與遍歷
class Node():
def __init__(self, item):
self.item = item
self.next = None
#尾插法
def creat_linklist_tail(li): # 參數(shù)li：列表
head = Node(li[0]) # head節(jié)點指針，傳入鏈表的第一個元素
tail = head # 起始的tail指針也是第一個元素
# tail = Node(li[0]) 這么寫會創(chuàng)建兩個不同的對象，導致后面的for循環(huán)只在tail上執(zhí)行。
for element in li[1:]: # 從列表的第2位開始加入到鏈表
node = Node(element) # 節(jié)點的值
tail.next = node # 從鏈表尾部節(jié)點鏈接到該點
tail = node # 移動tail指針，指向新加入鏈表的node
return head # 從鏈表的頭到尾輸出，首先仍需返回head
# 遍歷鏈表
def print_lk(lk): # 參數(shù)lk：鏈表
while lk: # lk.next不為none
print(lk.item, end = " ") # 打印值
lk = lk.next # 進入下一個點
lk_tail = creat_linklist_tail([1,4,8,6,3])
print_lk(lk_tail)輸出結果：
1 4 8 6 3 注意：第11行代碼，之所以不用tail = Node(li[0]),而是tail = head，雖然其表達的意義相同，但是由于Node是類，因此tail = Node(li[0])是創(chuàng)建了新的對象，和head不是同一個對象，后續(xù)的操作只會在tail這個對象上進行與head對象無關，導致鏈表鏈接過程中，head指針是脫離了后續(xù)創(chuàng)建的鏈表。
（5）鏈表的遍歷
1）基本思想
先找到鏈表的第一個元素，根據(jù)lk.next往下找到鏈表的下一個元素，知道lk.next= none，即該點為最后一個元素?？梢允褂脀hile循環(huán)實現(xiàn)。
2）代碼實現(xiàn)
# 遍歷鏈表
def print_lk(lk): # 參數(shù)lk：鏈表
while lk: # lk.next不為none
print(lk.item, end = " ") # 打印值
lk = lk.next # 進入下一個點3、鏈表的插入與刪除
（1）鏈表的插入
1）工作思路
|
|
|
如上圖所示，p元素需要插入到鏈表中，需要先將p元素與curNode.next元素連接，否則一旦curNode與后面的連接斷開，那么curNode與后面的一系列鏈表就失去聯(lián)系了，再將curNode與p元素連接?？梢岳斫鉃椋?span id="n5n3t3z" class="kdocs-color" style="color:#C21C13;">插入p，先p尾，后p頭。
2）代碼實現(xiàn)思路
p.next = curNode.next # 先連尾
curNode.next = p #再連頭（2）鏈表的刪除
1）工作思路
|
|
如上圖所示，刪除p點元素，首先將curNode與p.next鏈接上，再刪除p點。因為先刪除p點會導致curNode與后面的鏈表失聯(lián)。
2）代碼實現(xiàn)思路
curNode.next = p.next #或 curNode = curNode.next.next 與curNode與p點后面的值連接
del p #刪除p點（3）鏈表的插入與刪除代碼示例
# 鏈表的創(chuàng)建與遍歷
class Node():
def __init__(self, item):
self.item = item
self.next = None
# 頭插法
def creat_linklist_head(li): # 傳入參數(shù)為列表
head = Node(li[0]) # 最開始的head指針，指向列表第一個元素
for element in li[1:]: # 從列表的第2個元素開始插入到列表中
node = Node(element) # 列表元素傳入鏈表節(jié)點
node.next = head # 將該節(jié)點與前一個點鏈接
head = node # 指針head指向新插入的元素
return head # 返回鏈表的第一個元素
# 尾插法
def creat_linklist_tail(li): # 參數(shù)li：列表
head = Node(li[0]) # head節(jié)點指針，傳入鏈表的第一個元素
tail = head # 起始的tail指針也是第一個元素
# tail = Node(li[0])
for element in li[1:]: # 從列表的第2位開始加入到鏈表
node = Node(element) # 節(jié)點的值
tail.next = node # 從鏈表尾部節(jié)點鏈接到該點
tail = node # 移動tail指針，指向新加入鏈表的node
return head # 從鏈表的頭到尾輸出，首先仍需返回head
# 遍歷鏈表
def print_lk(lk): # 參數(shù)lk：鏈表
while lk: # lk.next不為none
print(lk.item, end = " ") # 打印值
lk = lk.next # 進入下一個點
#創(chuàng)建鏈表
lk_head = creat_linklist_head([1,2,3])
lk_tail = creat_linklist_tail([1,4,8,6,3])
# 刪除鏈表元素
curNode = lk_tail # 定義目前的節(jié)點，是lk_tail的head
p = curNode.next # 要刪除的點是curNode后面的元素
curNode.next = curNode.next.next #將curNode與p后面的元素連接
print_lk(lk_tail)
# 插入鏈表
p = Node(6) # 插入的點
curNode = lk_head # curNode的值
p.next = curNode.next # p點尾部與插入位置的后一個元素連接
curNode.next = p # p點與前面的curNode連接
print_lk(lk_head)輸出結果：
1 8 6 3 3 6 2 1 （4）時間復雜度
由于鏈表不是按照順序存儲的，而是通過next連接在一起，因此刪除和插入不需要大量的移動列表其他元素的位置，時間復雜度=O(1)。
七、雙鏈表
1、雙鏈表定義
雙鏈表的每個節(jié)點有兩個指針：一個指向后一個節(jié)點，另一個指向前一個節(jié)點。示意圖如下：
2、創(chuàng)建雙鏈表
class Node(object):
? ? def __init__(self,item):
? ? ? ? self.item =item
? ? ? ? self.next = None
? ? ? ? self.prior = None3、雙鏈表的插入和刪除
（1）雙鏈表的插入
1)工作思路
|
|
|
|
|
工作思路如上圖，p點先與后面的節(jié)點創(chuàng)建鏈接，在于前面的點創(chuàng)建鏈接，與單鏈表的插入流程類似。
代碼實現(xiàn)思路：
p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p（2）雙鏈表的刪除
1）工作思路
圖1 |
圖2 |
圖3 |
如上圖所示，先創(chuàng)建CurNode點與p后面的點的雙向鏈接，再刪除p點，思路與單鏈表的刪除操作類似。
2）代碼實現(xiàn)思路
p = curNode.next # 指定p點
curNode.next = p.next # 或curNode.next.next 創(chuàng)建與后面點的鏈接
p.next.prior = curNode # 創(chuàng)建與前面的點鏈接
del p # 刪除p八、鏈表總結
1、鏈表與列表-復雜度分析
項目\數(shù)據(jù)結構 |
順序表（列表/數(shù)組） |
鏈表 |
按元素值查找 |
O(n) |
O(n) |
按下標查找 |
O(1) |
O(n) |
在某元素后插入 |
O(n) |
O(1) |
刪除某元素 |
O(n) |
O(1) |
2、鏈表的優(yōu)點
（1）鏈表在插入和刪除操作上明顯快于順序表；
（2）鏈表的內存可以更靈活分配；
列表在創(chuàng)建初始是固定的規(guī)模，擴大規(guī)模需要重新開內存。文章來源：http://www.zghlxwxcb.cn/news/detail-716207.html
（3）鏈表這種鏈式存儲的數(shù)據(jù)結構對樹和圖的結構有很大的啟發(fā)性。文章來源地址http://www.zghlxwxcb.cn/news/detail-716207.html
到了這里，關于Python數(shù)據(jù)結構與算法-數(shù)據(jù)結構(列表、棧、隊列、鏈表)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
