一、鏈表

1.1目的

解決順序表存儲(chǔ)數(shù)據(jù)有上限，并且插入和刪除操作效率低的問題

1.2概念

鏈表：鏈?zhǔn)酱鎯?chǔ)的線性表，使用隨機(jī)物理內(nèi)存存儲(chǔ)邏輯上連續(xù)的數(shù)據(jù)

鏈表的組成：由一個(gè)個(gè)結(jié)點(diǎn)組成

結(jié)點(diǎn)：由數(shù)據(jù)域和鏈接域組成，是鏈表的基本單位

數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素的區(qū)域

鏈接域：記錄下一個(gè)結(jié)點(diǎn)所在位置的區(qū)域

頭結(jié)點(diǎn)：虛設(shè)的一個(gè)結(jié)點(diǎn)，連接域?qū)ｉT記錄鏈表第一個(gè)結(jié)點(diǎn)的位置，數(shù)據(jù)域?qū)ｉT記錄鏈表的長(zhǎng)度

1.3鏈表的種類

單向鏈表、雙向鏈表、循環(huán)鏈表

二、單向鏈表

2.1單向鏈表的概念

只能通過頭結(jié)點(diǎn)或鏈表的頭，單向的訪問后繼結(jié)點(diǎn)的鏈表叫單向鏈表

2.2結(jié)點(diǎn)和鏈表類的格式

1】包含存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域

2】有一個(gè)存儲(chǔ)下一個(gè)結(jié)點(diǎn)的位置域

#封裝普通節(jié)點(diǎn)的類
class Node:#構(gòu)造函數(shù)，定義結(jié)點(diǎn)的屬性def __init__(self,data):self.data=data#普通結(jié)點(diǎn)的數(shù)據(jù)域self.next=None#普通結(jié)點(diǎn)的連接域，剛構(gòu)造的結(jié)點(diǎn)該位置域?yàn)榭?#封裝鏈表的類（封裝頭節(jié)點(diǎn)）
class Link_list():def __init__(self,node=None):self.size=0#頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)? 鏈表的長(zhǎng)度為0self.head=node#頭結(jié)點(diǎn)的連接域指向None

2.3單向列表的相關(guān)操作（成員函數(shù)的封裝）

1】單向鏈表的創(chuàng)建

2】判空

#判空def is_empty(self):return self.head#   return self.size==0  或者判斷長(zhǎng)度是否為零

3】頭插

函數(shù)功能：將一個(gè)結(jié)點(diǎn)以頭插的方式插入到頭結(jié)點(diǎn)的后面

思路：

參數(shù)：self鏈表，要插入的數(shù)據(jù)

注意事項(xiàng)：需要申請(qǐng)結(jié)點(diǎn)封裝數(shù)據(jù)

? ? ? ? ? ? ? ? ? 插入成功鏈表長(zhǎng)度自增

#頭插def add_head(self,value):#創(chuàng)建一個(gè)新的結(jié)點(diǎn)node=Node(value)node.next=self.headself.head=nodeself.size+=1

4】尾插

函數(shù)功能：將新的節(jié)點(diǎn)增加到鏈表的尾部。思路：（如上圖）

函數(shù)返回值：無

函數(shù)名：符合命名規(guī)則

參數(shù)列表：self 鏈表，要插入的數(shù)據(jù)

注意事項(xiàng)：插入成功，鏈表自增

#尾插def add_tail(self, value):#創(chuàng)建一個(gè)結(jié)點(diǎn)nodenode = Node(value)#找最后一個(gè)結(jié)點(diǎn)# q = self.head# i=1# while i<self.size:#     q=q.next#     i+=1# q.next=node# self.size+=1#第二種方法q = self.headwhile q.next:q = q.nextq.next = nodeself.size += 1#第三種# while True:#     q=q.next#     if not q.next:#         q.next = node#         self.size+=1#         break

5】任意位置插

函數(shù)功能：在指定的位置插入一個(gè)節(jié)點(diǎn) 思路：如上圖

函數(shù)返回值：無

函數(shù)名：符合命名規(guī)則

參數(shù)列表：self鏈表、要插入的位置、要插入的數(shù)據(jù)

注意事項(xiàng)：1、判斷要插入的位置是否合理

2、成功插入 ；鏈表長(zhǎng)度自增

3、如果是第一個(gè)位置，做頭插

#任意位置插def add_any(self, id, value):node = Node(value)if id == 1:self.add_head(value)elif id == self.size+1:self.add_tail(value)elif id>self.size+1:print('插入失敗')returnelse:q = self.headi = 1while i < id - 1:q = q.nexti += 1node.next = q.nextq.next = nodeself.size += 1

6】頭刪

#頭刪def del_head(self):self.head = self.head.nextself.size -= 1

7】尾刪

#尾刪def del_tail(self):if self.size==1:self.head=Noneelse:q = self.headfor i in range(self.size - 2):q = q.nextq.next = Noneself.size -= 1

8】任意位置刪

#任意位置刪def del_any(self,id):if id==1:self.del_head()else:q = self.headfor i in range(id - 2):q = q.nextq.next = q.next.nextself.size -= 1

9】遍歷

函數(shù)功能：從頭到尾打印出鏈表中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)域的數(shù)據(jù)

函數(shù)返回值：無

函數(shù)名：符合命名規(guī)則

參數(shù)列表：self 鏈表

注意事項(xiàng)：判空

#遍歷def show(self):#判空if self.is_empty():print('遍歷失敗')returnelse:q = self.headwhile q :print(q.data,end=' ')q = q.nextprint()