提示：文章寫完後，目錄可以自動生成，如何生成可參考右邊的幫助文檔
提示：這裡可以添加本文要記錄的大概內容：
提示：以下是本篇文章正文內容，下面案例可供參考
線性表有兩種存儲方式:順序表和鏈表
1定義:
線性表是相同數據類型的n個元素的有限序列.數據元素類型相同
2結構特點:
第一個元素只有後繼沒有前驅;
最後一個元素只有前驅沒有後繼,
其他元素只有唯一一個前驅和唯一一個後繼
定義:線性表的順序存儲
1 什麼是內存
存儲器: 外存,內存
外存: c盤,d盤 u盤 長期保持,存取速度慢
內存: 存取速度快
cpu: 只能直接訪問內存,在內存中取數據進行該操作
注意:順序表不適合用來存儲頻繁用來插入和刪除的數據
2 python 中順序表的實現
python中list和tuple兩種類型采用了順序表的實現技術;python中list和tuple底層是基於數組的;
不同類型的元素不能存放在基本的順序表中;基本的順序表要求元素的類型必須是相同的;
若我們非要將不同類型的數據放到順序表,我們可以使用順序表來存放各個元素的地址,這種叫元素外置的順序表,對於元素外置的順序表使用插入,刪除等是通過對元素地址操作來實現的
一個順序表的完整信息包括兩部分:
1 數據區:表中的元素集合
2 表頭: 記錄表的整體情況的信息,元素存儲區的容量;已有元素個數兩項;
a 一體式結構,存儲表信息的單元與元素存儲區以連續的方式安排在一塊存儲區裡,兩部分數據的整體形成一個完整的順序表對象
b 分離式結構,表對象只保存整個表有關的信息(容量和元素個數),實際數據元素存放在另一個獨立元素存儲區裡,通過鏈接與基本表對象關聯
這兩種結構如何選取?
若我們的數據經常擴容,我們就使用分離式動態表;若我們數據不經常改變就使用一體式順序表,便於管理;
動態順序表: 當你執行添加數據操作時,python中的列表自動的去擴容,即換一塊更大的存儲區域,這就是所謂的動態順序表
列表就是動態順序表,采用的是分離式結構.
而且列表是元素外置的順序表
優點:
邏輯相鄰,物理相鄰: 存儲空間使用緊湊,不必為節點間的邏輯關系而增加額外的存儲開銷
可隨機存儲任意元素 O(1)
python 列表也引用的是數組結構
缺點:
插入,刪除操作需要移動大約表中一半的元素,對n大的順序表效率低
用一組任意的存儲單元(可連續,可不連續)存儲線性表的數據元素
順序表呢,是物理上先後關系體現邏輯上先後關系;
鏈表是不連續的如何體現數據之間的線性關系呢?
答:每個數據元素ai,除了存儲本省信息外,還需要存儲其直接後繼或者直接前驅的信息,即利用地址(指針)實現了用不相鄰的存儲單元存放邏輯上相鄰的元素
1數據域: 數據元素本身信息
2鏈接域(地址域,指針域): 直接後繼或直接前驅的存儲地址
3 線性鏈表的分類:
1 單鏈表: 每個結點除包含數據域外,只設置一個鏈接域,用於指向其後繼結點
2 雙向鏈表: 每個結點除包含數據域外,設置兩個鏈接域,分別用以指向其前驅結點和後繼結點.
# 單鏈表類定義
4 掃描指針和遍歷單鏈表
單鏈表的特點是每個結點只保存其直接後繼的地址,在已知單鏈表的head首地址的情況下,如果要訪問到單鏈表中的所有結點,需要一個掃描指針(掃描游標)
https://www.bilibili.com/video/BV1Aa4y1E75k?p=12&spm_id_from=pageDriver&vd_source=f0e2d9965dd28bc650e022a3c8d84457
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
class List(object):
def __init__(self):
self.__head = None
def is_empty(self):
if self.__head is None:
return 1
else:
return 0
def add(self, item): # 頭插入法插入元素
s = Node(item) # 生成一個帶插入節點的對象
s.next = self.__head # 修改鏈接
self.__head = s # 修改鏈接
def travel(self): # 遍歷單鏈表,並打印輸出
# 對鏈表中的n個元素掃描一遍,時間復雜度為O(n)
p = self.__head # 定義指針p p從表頭開始
while p is not None: # 判斷指針是否指向了鏈表末尾
print(p.data, end=" ") # 打印p指向的結點數據
p = p.next # 指針下移到下一個元素
def length(self):
count = 0
p = self.__head
while p is not None:
p = p.next
count += 1
return count
def searchpos(self, pos): # 按序號查找, pos是待查找的位置
# 性能分析:與pos取值有關,平均時間復雜度O(n)
len1 = self.length()
if pos > len1:
return
p = self.__head
count = 1
if pos == 0:
return None
else:
while p is not None and count != pos:
p = p.next
count += 1
print(p.data)
return p
pass
def search(self, item): # 按值查找
# 性能分析: 平均時間復雜度 O(n)
p = self.__head
while p is not None and item != p.data:
p = p.next
if p is not None:
if p.data == item:
print(f"數據找到了 {
p.data}")
elif p is None:
return None
return p
def append(self, x):
# 因為需要移動指針,時間復雜度是 O(n)
p = self.__head # 找到頭結點
n = Node(x) # 實例化新節點
if p is None:
self.__head = n
return
while p.next is not None:
p = p.next
p.next = n
def insert(self, pos, x):
# 時間復雜度為O(n),若按照序號插入,需要先找到位置,按位置
# 僅僅插入操作時間復雜度是O(1)
p = self.__head
count = 1
s = Node(x)
# if pos >= self.length():
# return -1
while p.next is not None and count != pos: # 找到要插入的位置
p = p.next
count += 1
if 0 == pos:
s.next = self.__head
self.__head = s
elif p.next is not None:
s.next = p.next
p.next = s
elif p.next is None:
p.next = s
def remove(self, item): # 按值刪除操作
# 查找操作 時間復雜度是 O(n)
# 刪除操作 時間復雜度是 O(1)
p = self.__head
if item == p.data: # 如果刪除的是一個節點
self.__head = p.next
else:
# while p.next is not None and item != p.data:
# pre = p
# p = p.next
# else:
# pre.next = p.next
while p is not None:
if p.data != item:
pre = p
p = p.next
else:
pre.next = p.next
break
return p
l = List()
# l.add(6)
# l.add(9)
# l.add(11)
l.append(6)
l.append(9)
l.append(11)
l.append(13)
l.travel()
print(f"\r\n鏈表的長度為: {
l.length()}")
l.searchpos(2)
l.search(11)
l.insert(0, 44)
l.travel()
print('-------')
l.remove(13)
l.travel()
單鏈表特點:
1 它是一種動態結構, 整個內存空間為多個鏈表公用
2 不需要預先分配空間
3 鏈接域占用額外存儲空間
4 不能隨機存取,查找速度慢.
不論查哪一個元素都是從第一個元素開始查找;
1 每個結點包含兩個鏈接域,一個指向直接前驅(prior),一個指向直接後繼(next)
2雙鏈表由頭指針head唯一確定
3 將雙鏈表中的頭結點和尾結點鏈接起來可以構成循環鏈表,並稱之為雙向鏈表
https://www.bilibili.com/video/BV1Aa4y1E75k?p=14&spm_id_from=pageDriver&vd_source=f0e2d9965dd28bc650e022a3c8d84457
提示：這裡對文章進行總結：
