【Python資料結構系列】《線性表》——知識點講解+程式碼實現

語言: CN / TW / HK

靈魂拷問:為什麼要學資料結構? 資料結構,直白地理解,就是研究資料的儲存方式。資料儲存只有一個目的,即為了方便後期對資料的再利用。因此,資料在計算機儲存空間的存放,決不是胡亂的,這就要求我們選擇一種好的方式來儲存資料,而這也是資料結構的核心內容。 可以說,資料結構是一切程式設計的基本。學習資料結構是學習一種思想:如何把現實問題轉化為計算機語言的表示。 對於學計算機的朋友來說,學習資料結構是基本功。而對於非計算機專業,但是未來想往資料分析、大資料方向發展、或者在Python的使用上能有一個大的跨越的朋友來說,學習資料結構是一種非常重要的邏輯思維能力的鍛鍊,在求職、職業發展、問題解決等方面都能有潛移默化的大幫助。

tips:本文介紹的知識只是作為一個引子,供小夥伴們參考學習,在學習過程中如果遇到問題,一定要多去搜索相關部落格、文章、書籍等其他資料,作為補充學習。 廢話不多說,我們開整! @TOC

1.線性表(線性儲存結構)

線性表是資料結構中最簡單的資料儲存結構,可以理解為“線性的表”。線性,是說資料在邏輯結構上具有線性關係。將具有“一對一”關係的資料“線性”地儲存到物理空間中,這種儲存結構就稱為線性儲存結構(簡稱線性表)。

1.1 線性表基本介紹

線性表,資料結構中最簡單的一種儲存結構,專門用於儲存邏輯關係為"一對一"的資料。基於資料在實際物理空間中的儲存狀態,又可細分為順序表(順序儲存結構)和連結串列(鏈式儲存結構)。

線性表,全名為線性儲存結構。使用線性表儲存資料的方式可以這樣理解,即"把所有資料用一根線兒串起來,再儲存到物理空間中"。

Image Name

如圖 1 所示,這是一組具有“一對一”關係的資料,我們接下來採用線性表將其儲存到物理空間中。

首先,用“一根線兒”把它們按照順序“串”起來,如圖 2 所示:

Image Name

圖 2 中,左側是“串”起來的資料,右側是空閒的物理空間。把這“一串兒”資料放置到物理空間,我們可以選擇以下兩種方式,如圖 3 所示。

Image Name

圖 3a) 是多數人想到的儲存方式,而圖 3b) 卻少有人想到。我們知道,資料儲存的成功與否,取決於是否能將資料完整地復原成它本來的樣子。如果把圖 3a) 和圖 3b) 線的一頭扯起,你會發現資料的位置依舊沒有發生改變(和圖 1 一樣)。因此可以認定,這兩種儲存方式都是正確的。

將具有“一對一”關係的資料“線性”地儲存到物理空間中,這種儲存結構就稱為線性儲存結構(簡稱線性表)。

使用線性表儲存的資料,如同向陣列中儲存資料那樣,要求資料型別必須一致,也就是說,線性表儲存的資料,要麼全部都是整形,要麼全部都是字串。一半是整形,另一半是字串的一組資料無法使用線性表儲存。   

1.2 順序儲存結構和鏈式儲存結構

圖 3 中我們可以看出,線性表儲存資料可細分為以下 2 種:

(1) 如圖 3a) 所示,將資料依次儲存在連續的整塊物理空間中,這種儲存結構稱為順序儲存結構(簡稱順序表);

(2)如圖 3b) 所示,資料分散的儲存在物理空間中,通過一根線儲存著它們之間的邏輯關係,這種儲存結構稱為鏈式儲存結構(簡稱連結串列);

也就是說,線性表儲存結構可細分為順序儲存結構和鏈式儲存結構

1.3 前驅和後繼

資料結構中,一組資料中的每個個體被稱為“資料元素”(簡稱“元素”)。例如,圖 1 顯示的這組資料,其中 1、2、3、4 和 5 都是這組資料中的一個元素。

另外,對於具有“一對一”邏輯關係的資料,我們一直在用“某一元素的左側(前邊)或右側(後邊)”這樣不專業的詞,其實線性表中有更準確的術語:

某一元素的左側相鄰元素稱為“直接前驅”,位於此元素左側的所有元素都統稱為“前驅元素”;

某一元素的右側相鄰元素稱為“直接後繼”,位於此元素右側的所有元素都統稱為“後繼元素”;

以圖 1 資料中的元素 3 來說,它的直接前驅是 2 ,此元素的前驅元素有 2 個,分別是 1 和 2;同理,此元素的直接後繼是 4 ,後繼元素也有 2 個,分別是 4 和 5。如下圖所示:

Image Name

2. 順序表(順序儲存結構)

2.1 順序表基本介紹

順序表,全名順序儲存結構,是線性表的一種。通過《什麼是線性表》一節的學習我們知道,線性表用於儲存邏輯關係為“一對一”的資料,順序表自然也不例外。

不僅如此,順序表對資料的物理儲存結構也有要求。順序表儲存資料時,會提前申請一整塊足夠大小的物理空間,然後將資料依次儲存起來,儲存時做到資料元素之間不留一絲縫隙。

例如,使用順序表儲存集合 {1,2,3,4,5},資料最終的儲存狀態如圖1所示:

Image Name

由此我們可以得出,將“具有 '一對一' 邏輯關係的資料按照次序連續儲存到一整塊物理空間上”的儲存結構就是順序儲存結構。

通過觀察圖 1 中資料的儲存狀態,我們可以發現,順序表儲存資料同陣列非常接近。其實,順序表儲存資料使用的就是陣列。

2.2 順序表基本操作之插入元素

向已有順序表中插入資料元素,根據插入位置的不同,可分為以下 3 種情況:   ① 插入到順序表的表頭;   ② 在表的中間位置插入元素;   ③ 尾隨順序表中已有元素,作為順序表中的最後一個元素;

雖然資料元素插入順序表中的位置有所不同,但是都使用的是同一種方式去解決,即:通過遍歷,找到資料元素要插入的位置,然後做如下兩步工作:   ① 將要插入位置元素以及後續的元素整體向後移動一個位置;   ② 將元素放到騰出來的位置上;

例如,在 {1,2,3,4,5} 的第 3 個位置上插入元素 6,實現過程如下:

① 遍歷至順序表儲存第 3 個數據元素的位置,如圖 1 所示:

Image Name

② 將元素 3 以及後續元素 4 和 5 整體向後移動一個位置,如圖 2 所示:

Image Name

③ 將新元素 6 放入騰出的位置,如圖 3 所示:

Image Name

2.3 順序表基本操作之刪除元素

從順序表中刪除指定元素,實現起來非常簡單,只需找到目標元素,並將其後續所有元素整體前移 1 個位置即可。

【注】:後續元素整體前移一個位置,會直接將目標元素刪除,可間接實現刪除元素的目的。

例如,從 {1,2,3,4,5} 中刪除元素 3 的過程如圖 4 所示:

Image Name

2.4 順序表基本操作之查詢元素

順序表中查詢目標元素,可以使用多種查詢演算法實現,比如說二分查詢演算法、插值查詢演算法等。

2.5 順序表基本操作之更改元素

順序表更改元素的實現過程是:   (1)找到目標元素;   (2)直接修改該元素的值;    關於順序表Python程式設計實現程式碼可參考↓(個人編寫,僅供參考,歡迎提出寶貴建議)

```python

!/usr/bin/env python

-- coding: utf-8 --

@Time : 2021/7/20 15:42

@Author : vaxtiandao

@File : ds_1.py

import random random.seed(10)

定義順序表的類

class SqList(): # 初始化 def init(self, length): self.length = length # 先指定陣列的長度 self.sqlist = [random.randint(1, 100) for j in range(length)] # 生成length長度的隨機陣列

# 輸出所有元素
def ShowList(self):
    return self.sqlist

# 遍歷所有元素
def ErgodicList(self):
    for i in range(self.length):
        print("第{}個元素值為{}".format(i+1, self.sqlist[i]))

# 取值
def GetElem(self, i):
    # 首先判斷插入的位置是否在合法範圍內(1,length)
    if i < 1 or i > self.length:
        pass
        return False
    return self.sqlist[i-1]  # 在的話,直接返回值

# 查詢
def LocateElem(self, e):
    # 通過迴圈遍歷列表,找到列表中等於e的元素,返回其位置索引
    for j in range(self.length):
        if e == self.sqlist[j]:
            return j
            break
    # 否則,輸出一句話:"列表中不存在查詢的元素",然後返回False
    print("列表中不存在查詢的元素")

# 插入
def ListInsert(self, i, e):
    # 首先判斷插入的位置是否在合法範圍內(1,length),不在的話,直接返回False
    if i < 1 or i > self.length:
        return False
    return self.sqlist.insert(i,e)  # 列表中有insert()函式

# 刪除
def ListDelete(self, i):
    # 首先判斷插入的位置是否在合法範圍內(1,length),不在的話,直接返回False
    if i < 1 or i > self.length:
        return False
    return self.sqlist.pop(i)  # 列表有個pop()函式,該函式會返回刪除的值

定義一個順序表物件

length = 10 my_sqlist = SqList(length) print("初始化的順序表:", my_sqlist) print("_______")

輸出所有引數

mylist = my_sqlist.ShowList() print("輸出所有引數:", mylist) print("_______")

呼叫遍歷函式

print("遍歷順序表") my_sqlist.ErgodicList() print("_______")

插入

print("插入前的列表:{}".format(my_sqlist.ShowList())) i = 4 # 插入的索引位置 e = 10 # 插入的值 my_sqlist.ListInsert(i, e) # 在指定索引位置插入值 print("插入後的順序表:{}".format(my_sqlist.ShowList())) print("_______")

刪除

i = 5 # 刪除的索引位置 print("刪除前的順序表:{}".format(my_sqlist.ShowList())) my_sqlist.ListDelete(i) # 刪除i索引所在位置上的值 print("刪除後的順序表:{}".format(my_sqlist.ShowList())) print("_______")

取值

index = 8 # 這裡代表的是第10個數,不是位置索引為10的數,索引+1才是具體第幾個數; value = my_sqlist.GetElem(index) if value: print("順序表中第{}個數等於{}".format(index, value)) print("_______")

查詢

e = 55 # 要查詢的數 index = my_sqlist.LocateElem(e) if index: print("元素{}在順序表中的索引為{}".format(e, index)) ``` 如下是實現效果: 在這裡插入圖片描述 關於順序表基本操作的C語言程式碼,可以看這:順序表的基本操作

3. 單鏈表,鏈式儲存結構

3.1 單鏈表基本介紹

前面詳細地介紹了順序表,本節給大家介紹另外一種線性儲存結構——連結串列

連結串列,別名鏈式儲存結構單鏈表,用於儲存邏輯關係為 "一對一" 的資料。與順序表不同,連結串列不限制資料的物理儲存狀態,換句話說,使用連結串列儲存的資料元素,其物理儲存位置是隨機的。

例如,使用連結串列儲存 {1,2,3},資料的物理儲存狀態如圖1所示:

Image Name

我們看到,上圖根本無法體現出各資料之間的邏輯關係。對此,連結串列的解決方案是,每個資料元素在儲存時都配備一個指標,用於指向自己的直接後繼元素。如圖2所示:

Image Name

像圖2這樣,資料元素隨機儲存,並通過指標表示資料之間邏輯關係的儲存結構就是鏈式儲存結構。

3.2 連結串列的節點

從上圖可以看到,連結串列中每個資料的儲存都由以下兩部分組成:   (1)資料元素本身,其所在的區域稱為資料域;
  (2) 指向直接後繼元素的指標,所在的區域稱為指標域;

即連結串列中儲存各資料元素的結構如圖3所示:

Image Name

上圖所示的結構在連結串列中稱為節點。也就是說,連結串列實際儲存的是一個一個的節點,真正的資料元素包含在這些節點中,如圖4所示:

Image Name

3.3 頭節點,頭指標和首元節點

其實,圖 4 所示的連結串列結構並不完整。一個完整的連結串列需要由以下幾部分構成:

1. 頭指標:一個普通的指標,它的特點是永遠指向連結串列第一個節點的位置。很明顯,頭指標用於指明連結串列的位置,便於後期找到連結串列並使用表中的資料;

2. 節點:連結串列中的節點又細分為頭節點、首元節點和其他節點:   (1)頭節點:其實就是一個不存任何資料的空節點,通常作為連結串列的第一個節點。對於連結串列來說,頭節點不是必須的,它的作用只是為了方便解決某些實際問題;   (2)首元節點:由於頭節點(也就是空節點)的緣故,連結串列中稱第一個存有資料的節點為首元節點。首元節點只是對連結串列中第一個存有資料節點的一個稱謂,沒有實際意義;   (3)其他節點:連結串列中其他的節點;

因此,一個儲存 {1,2,3} 的完整連結串列結構如圖5所示:

Image Name

【注】:連結串列中有頭節點時,頭指標指向頭節點;反之,若連結串列中沒有頭節點,則頭指標指向首元節點。

明白了連結串列的基本結構,下面我們來學習如何建立一個連結串列。

3.4 連結串列的建立(初始化)

建立一個連結串列需要做如下工作:

1. 宣告一個頭指標(如果有必要,可以宣告一個頭節點);

2. 建立多個儲存資料的節點,在建立的過程中,要隨時與其前驅節點建立邏輯關係;

3.5 單鏈表基本操作

本節將詳細介紹對連結串列的一些基本操作,包括對連結串列中資料的新增、刪除、查詢(遍歷)和更改。

插入元素

同順序表一樣,向連結串列中增添元素,根據新增位置不同,可分為以下 3 種情況:   (1)插入到連結串列的頭部(頭節點之後),作為首元節點;   (2)插入到連結串列中間的某個位置;   (3)插入到連結串列的最末端,作為連結串列中最後一個數據元素;

雖然新元素的插入位置不固定,但是連結串列插入元素的思想是固定的,只需做以下兩步操作,即可將新元素插入到指定的位置:   (1)將新結點的 next 指標指向插入位置後的結點;   (2)將插入位置前結點的 next 指標指向插入結點;

例如,我們在連結串列 {1,2,3,4} 的基礎上分別實現在頭部、中間部位、尾部插入新元素 5,其實現過程如圖 1 所示:

Image Name

從圖中可以看出,雖然新元素的插入位置不同,但實現插入操作的方法是一致的,都是先執行步驟 1 ,再執行步驟 2。

【注意】:連結串列插入元素的操作必須是先步驟 1,再步驟 2;反之,若先執行驟步 2,除非再新增一個指標,作為插入位置後續連結串列的頭指標,否則會導致插入位置後的這部分連結串列丟失,無法再實現步驟 1

刪除元素

從連結串列中刪除指定資料元素時,實則就是將存有該資料元素的節點從連結串列中摘除,但作為一名合格的程式設計師,要對儲存空間負責,對不再利用的儲存空間要及時釋放。因此,從連結串列中刪除資料元素需要進行以下 2 步操作:   (1)將結點從連結串列中摘下來;   (2)手動釋放掉結點,回收被結點佔用的儲存空間;

其中,從連結串列上摘除某節點的實現非常簡單,只需找到該節點的直接前驅節點 temp,例如,從存有 {1,2,3,4} 的連結串列中刪除元素 3,則此程式碼的執行效果如圖 2 所示:

Image Name

查詢元素

在連結串列中查詢指定資料元素,最常用的方法是:從表頭依次遍歷表中節點,用被查詢元素與各節點資料域中儲存的資料元素進行比對,直至比對成功或遍歷至連結串列最末端的 NULL(比對失敗的標誌)。

注意,遍歷有頭節點的連結串列時,需避免頭節點對測試資料的影響,因此在遍歷連結串列時,建立使用上面程式碼中的遍歷方法,直接越過頭節點對連結串列進行有效遍歷。

更新元素

更新連結串列中的元素,只需通過遍歷找到儲存此元素的節點,對節點中的資料域做更改操作即可。    關於連結串列Python程式設計實現程式碼可參考↓(個人編寫,僅供參考,歡迎提出寶貴建議)

```python

!/usr/bin/env python

-- coding: utf-8 --

@Time : 2021/7/21 17:12

@Author : vaxtiandao

@File : ds_12.py

單向連結串列的實現

每個節點包含兩部分,資料區和指向下個節點的連結

單向列表:每個節點包含兩部分:資料區與連結區(指向下一個節點),最後一個元素的連結區為None

單向列表只要找到頭節點,就可以訪問全部節點

定義結點類,包含兩個成員:結點元素值和指向下一結點的指標

class SingleNode(): # 結點類初始化 def init(self, item): self.item = item # item存放結點的數值 self.next = None # 下一指標指向

定義單鏈表

class SingleLinkList(): # 連結串列類初始化 def init(self): self.head = None

# 判斷連結串列是否為空
def is_empty(self):
    return self.head == None

# 輸出連結串列長度
def get_length(self):
    return len(self.travel())

# 遍歷整個連結串列
def travel(self):
    # 思路就是先判斷連結串列是否為空
    # 為空直接返回None,
    # 不為空的話,就先定義一個列表,然後通過next指標從頭指標開始遍歷,依次將結點儲存的值加入列表中,直到下一指標指向為空,則停止遍歷;
    if self.is_empty():
        return None
    else:
        curlist = []
        cur = self.head
        while cur != None:
            curlist.append(cur.item)
            cur = cur.next
        return curlist

# 頭插法建立單鏈表
def add(self, newItem):
    node = SingleNode(newItem)
    node.next = self.head  # 指標變換
    self.head = node

# 尾插法
def append(self, newItem):
    node = SingleNode(newItem)
    if self.is_empty():
        return self.add(newItem)
    # 從頭結點開始遍歷
    nod = self.head
    while nod.next != None:  # 當下一個結點的next為None時,停止遍歷//  注:跟網上不一樣,回頭用尾插法新建單鏈表試試
        nod = nod.next
    nod.next = node

# 指定位置新增元素
def insert(self, pos, newItem):  # 在指定pos位置上新增newItem元素
    # 連結串列的插入需要分幾種情況
    # 第一步 判斷pos是否在合理範圍內,如果不在,則直接終止
    # 第二步 判斷pos是否在第一個,如果是則採用頭插法
    # 第三步 如果pos在最後一個,則採用尾插法
    # 第四步 如果既不在頭,也不再尾,則通過迴圈遍歷到pos位置,再用Insert插入
    node = SingleNode(newItem)
    cur = self.head
    count = 0
    if pos == 0:
        return self.add(newItem)
    elif pos < (self.get_length()):
        while count < pos - 1:
            cur = cur.next
            count += 1
        node.next = cur.next
        cur.next = node
    elif pos == (self.get_length()):
        return self.append(newItem)
    else:
        return '輸入的位置有誤,請確認'

# 刪除指定位置上的結點
def remove(self, pos):
    # 第一步 判斷給定的pos是否再合理範圍內
    # 第二步 通過迴圈,遍歷到pos位置,遍歷期間通過next指標依次指向下一結點
    # 第三步 找到指定位置的結點後,通過nod.next = nod.next.next刪除
    cur = self.head
    count = 0
    if 1 <= pos < (self.get_length()):
        while count < pos - 1:
            cur = cur.next
            count += 1
        cur.next = cur.next.next
    elif pos == 0:
        self.head = cur.next
    else:
        return '輸入的位置有誤,請確認'

# 查詢指定位置的結點值
def find(self, pos):
    cur = self.head
    count = 0
    if 0 <= pos < (self.get_length()):
        while count < pos:
            cur = cur.next
            count += 1
        return cur.item
    else:
        return '輸入的位置有誤,請確認'

# 更新連結串列中某個位置的值
def update(self, pos, newItem):
    cur = self.head
    count = 0
    if 0 <= pos < (self.get_length()):
        while count < pos:
            cur = cur.next
            count += 1
        cur.item = newItem
    else:
        return '輸入的位置有誤,請確認'

## 清空連結串列
def clear(self):
    self.head = None

singlelinklist = SingleLinkList() # 例項化物件 print("初始化單鏈表:",singlelinklist) print("______________") print("判斷單鏈表是否為空:",singlelinklist.is_empty()) print("________________")

新增資料

import random for i in range(10): singlelinklist.add(random.randint(1,100))

遍歷資料

singlelinklist.travel() print("遍歷單鏈表:",singlelinklist.travel()) print("______________") print("判斷單鏈表是否為空:",singlelinklist.is_empty()) print("________________")

末尾新增資料

singlelinklist.append(10) print("末尾新增元素後的單鏈表遍歷結果:", singlelinklist.travel()) print("__________________")

開頭新增資料

singlelinklist.add(1) print("開頭新增元素後的單鏈表遍歷結果:", singlelinklist.travel()) print("__________________")

檢視資料長度

print("單鏈表長度:",singlelinklist.get_length()) print("__________________")

指定位置插入資料,位置從0開始

singlelinklist.insert(1, 13) print("插入資料後的遍歷單鏈表:", singlelinklist.travel()) print("__________________")

刪除指定位置資料

singlelinklist.remove(0) print("刪除資料後的遍歷單鏈表:", singlelinklist.travel()) print("__________________")

更新指定位置資料

singlelinklist.update(2,2) print("更新資料後的遍歷單鏈表:", singlelinklist.travel()) print("__________________")

清空所有資料

singlelinklist.clear() print("清空資料後的遍歷單鏈表:", singlelinklist.travel()) print("__________________") ``` 如下是程式碼實現效果: 在這裡插入圖片描述 關於單鏈表基本操作詳細的C語言程式碼,見這👉:單鏈表的基本操作

4. 單向迴圈連結串列

對於單鏈表以及雙向連結串列,其就像一個小巷,無論怎麼樣最終都能從一端走到另一端,然而迴圈連結串列則像一個有傳送門的小巷,因為迴圈連結串列當你以為你走到結尾的時候,其實你又回到了開頭。

迴圈連結串列和非迴圈連結串列其實建立的過程以及思路幾乎完全一樣,唯一不同的是,非迴圈連結串列的尾結點指向空(NULL),而迴圈連結串列的尾指標指向的是連結串列的開頭。通過將單鏈表的尾結點指向頭結點的連結串列稱之為迴圈單鏈表(Circular linkedlist)

如圖,為一個完整的迴圈單鏈表;

1562924138210258.png

4.1 迴圈連結串列結點設計(以單迴圈連結串列為例)

對於迴圈單鏈表的結點,可以完全參照於單鏈表的結點設計,如圖:

1562924163903311.png

data表示資料,其可以是簡單的型別(如int,double等等),也可以是複雜的結構體(struct型別);

next表示指標,它永遠指向自身的下一個結點,對於只有一個結點的存在,這個next指標則永遠指向自身,對於一個連結串列的尾部結點,next永遠指向開頭。

4.2 迴圈單鏈表初始化

如同單鏈表的建立,我們需要先建立一個頭結點並且給其開闢記憶體空間,但與單鏈表不同的是,我們需要在開闢記憶體空間成功之後將頭結點的next指向head自身,我們可以建立一個init函式來完成這件事情,為了以後的重複建立和插入,我們可以考慮在init重建立的結點next指向空,而在主函式呼叫建立之後手動講head頭結點的next指標指向自身。

這樣的操作方式可以方便過後的建立單鏈表,直接利用多次呼叫的插入函式即可完成整體建立。

4.3 迴圈單鏈表的基本操作

迴圈單鏈表基本操作包括:初始化、判空、遍歷、建立(頭插/尾插)、輸出長度、新增、刪除、查詢、更新以及清空;    關於連結串列Python程式設計實現程式碼可參考↓(個人編寫,僅供參考,歡迎提出寶貴建議)

```python

!/usr/bin/env python

-- coding: utf-8 --

@Time : 2021/7/21 17:16

@Author : vaxtiandao

@File : ds_13.py

定義結點類,包含兩個成員:結點元素值和指向下一結點的指標

class SingleNode(): # 結點類初始化 def init(self, item): self.item = item # 存放結點的數值 self.next = None # 下一指標指向

定義單鏈表

class SingleLinkList(): # 連結串列類初始化 def init(self, node=None): self.head = node # 指向頭結點 if node: node.next = node # 如果例項化物件時輸入了結點,定義結點迴圈

# 判斷連結串列是否為空
def is_empty(self):
    return self.head == None

# 輸出連結串列長度
def get_length(self):
    if self.is_empty():
        return 0
    cur = self.head
    count = 1
    while cur.next != self.head:
        count += 1
        cur = cur.next
    return count

# 遍歷整個連結串列
def travel(self):
    curlist = []
    if self.is_empty():
        return curlist
    cur = self.head
    while cur.next != self.head:
        curlist.append(cur.item)
        cur = cur.next
    curlist.append(cur.item)
    return curlist

# 頭插法建立單鏈表
def add(self, newItem):
    node = SingleNode(newItem)
    cur = self.head
    if self.head is None:
        self.head = node
        node.next = node
    else:
        while cur.next != self.head:
            cur = cur.next
        node.next = self.head
        self.head = node
        cur.next = node

# 尾插法建立單鏈表
def append(self, newItem):
    node = SingleNode(newItem)
    # 從尾結點開始遍歷
    cur = self.head
    if self.is_empty():
        self.head = node
        node.next = node
    else:
        while cur.next != self.head:
            cur = cur.next
        node.next = self.head
        cur.next = node

# 指定位置新增元素,pos從零開始
def insert(self, pos, newItem):
    node = SingleNode(newItem)
    if pos <= 0:
        self.add(newItem)
    elif pos > (self.get_length() - 1):
        self.append(newItem)
    else:
        count = 0
        cur = self.head
        while count < (pos - 1):
            count += 1
            cur = cur.next
        node.next = cur.next
        cur.next = node

# 刪除指定位置上的結點
def remove(self, pos):
    if pos <= 0:
        return '資料為空'
    elif pos > (self.get_length() - 1):
        return '超過連結串列範圍'
    else:
        count = 0
        cur = self.head
        while count < (pos - 1):
            count += 1
            cur = cur.next
        cur.next = cur.next.next

# 查詢指定位置的結點值
def find(self, pos):
    if pos <= 0:
        return '資料為空'
    elif pos > (self.get_length() - 1):
        return '超過連結串列範圍'
    else:
        count = 0
        cur = self.head
        while count < pos:
            count += 1
            cur = cur.next
        return cur.item

# 更新連結串列中的某個位置的值
def update(self, pos, newItem):
    if pos <= 0:
        return '資料為空'
    elif pos > (self.get_length() - 1):
        return '超過連結串列範圍'
    else:
        count = 0
        cur = self.head
        while count < pos:
            count += 1
            cur = cur.next
        cur.item = newItem

# 清空連結串列
def clear(self):
    self.head = None

例項化物件

import random

singlelinklist = SingleLinkList() print("初始化物件:", singlelinklist) print("__________________")

檢視連結串列是否為空

print("初始化後,判斷當前連結串列是否為空:", singlelinklist.is_empty()) print("__________________")

隨機新增資料

for i in range(10): singlelinklist.add(random.randint(1, 100))

檢視連結串列是否為空

print("判斷當前連結串列是否為空:", singlelinklist.is_empty()) print("__________________")

檢視連結串列資料

print("遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) print("__________________")

查詢連結串列的長度

print("當前連結串列長度為", singlelinklist.get_length()) print("__________________")

頭插法

print("頭插前,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) singlelinklist.add(0) print("頭插後,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) print("__________________")

尾插法

print("尾插前,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) singlelinklist.append(100) print("尾插後,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) print("__________________")

指定位置插入值

print("指定位置插入前,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) singlelinklist.insert(3, 3) print("指定位置插入後,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) print("__________________")

查詢指定位置的結點值

print("查詢指定位置的結點值:", singlelinklist.find(5)) print("__________________")

刪除指定位置的值

print("刪除前,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) singlelinklist.remove(6) print("刪除後,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) print("__________________")

更新指定位置的值

print("更新前,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) singlelinklist.update(3, 15) print("更新後,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) print("__________________")

清空結點

print("清空前,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) singlelinklist.clear() print("清空後,遍歷連結串列檢視連結串列元素:", singlelinklist.travel()) print("__________________") ``` 以下是上述程式碼實現效果: 在這裡插入圖片描述

關於迴圈單鏈表基本操作,見這👉:迴圈單鏈表的基本操作

5. 雙向連結串列

5.1 雙向連結串列基本介紹

目前我們所學到的連結串列,無論是動態連結串列還是靜態連結串列,表中各節點中都只包含一個指標(遊標),且都統一指向直接後繼節點,通常稱這類連結串列為單向連結串列(或單鏈表)。

雖然使用單鏈表能100%解決邏輯關係為 "一對一" 資料的儲存問題,但在解決某些特殊問題時,單鏈表並不是效率最優的儲存結構。比如說,某場景中需要大量地查詢某結點的前趨結點,這種情況下使用單鏈表無疑是災難性的,因為單鏈表更適合 "從前往後" 找,"從後往前" 找並不是它的強項。

對於逆向查詢(從後往前)相關的問題,使用本節講解的雙向連結串列,會更加事半功倍。

雙向連結串列,簡稱雙鏈表。從名字上理解雙向連結串列,即連結串列是 "雙向" 的,如圖1所示:

Image Name

所謂雙向,指的是各節點之間的邏輯關係是雙向的,但通常頭指標只設置一個,除非實際情況需要,可以為最後一個節點再設定一個“頭指標”。

根據圖 1 不難看出,雙向連結串列中各節點包含以下 3 部分資訊(如下圖所示):   (1)指標域:用於指向當前節點的直接前驅節點;   (2)資料域:用於儲存資料元素;   (3)指標域:用於指向當前節點的直接後繼節點。

Image Name

5.2 雙向連結串列的建立

同單鏈表相比,雙鏈表僅是各節點多了一個用於指向直接前驅的指標域。因此,我們可以在單鏈表的基礎輕鬆實現對雙鏈表的建立。

和建立單鏈表不同的是,建立雙向連結串列的過程中,每一個新節點都要和前驅節點之間建立兩次連結,分別是:   (1)將新節點的 prior 指標指向直接前驅節點;   (2)將直接前驅節點的 next 指標指向新節點;

5.3 雙向連結串列基本操作

前面學習瞭如何建立一個雙向連結串列,本節學習有關雙向連結串列的一些基本操作,即如何在雙向連結串列中新增、刪除、查詢或更改資料元素。

本節知識基於已熟練掌握雙向連結串列建立過程的基礎上,我們繼續上節所建立的雙向連結串列來學習本節內容,建立好的雙向連結串列如圖 1 所示:

Image Name

雙向連結串列新增節點

根據資料新增到雙向連結串列中的位置不同,可細分為以下 3 種情況:        (1)新增至表頭   將新資料元素新增到表頭,只需要將該元素與表頭元素建立雙層邏輯關係即可。   換句話說,假設新元素節點為 temp,表頭節點為 head,則需要做以下 2 步操作即可:    ① temp->next=head; head->prior=temp;    ② 將head 移至 temp,重新指向新的表頭;

例如,將新元素 7 新增至雙鏈表的表頭,則實現過程如圖 2 所示:

Image Name

(2)新增至表的中間位置   同單鏈表新增資料類似,雙向連結串列中間位置新增資料需要經過以下 2 個步驟,如圖 3 所示:    ① 新節點先與其直接後繼節點建立雙層邏輯關係;    ② 新節點的直接前驅節點與之建立雙層邏輯關係;

Image Name

(3)新增至表尾   與新增到表頭是一個道理,實現過程如下(如圖 4 所示):    ① 找到雙鏈表中最後一個節點;    ② 讓新節點與最後一個節點進行雙層邏輯關係;

Image Name

雙向連結串列刪除節點

雙鏈表刪除結點時,只需遍歷連結串列找到要刪除的結點,然後將該節點從表中摘除即可。

例如,從圖 1 基礎上刪除元素 2 的操作過程如圖 5 所示:

Image Name

雙向連結串列查詢節點

通常,雙向連結串列同單鏈表一樣,都僅有一個頭指標。因此,雙鏈表查詢指定元素的實現同單鏈表類似,都是從表頭依次遍歷表中元素。

雙向連結串列更改節點

更改雙鏈表中指定結點資料域的操作是在查詢的基礎上完成的。實現過程是:通過遍歷找到儲存有該資料元素的結點,直接更改其資料域即可。    關於連結串列Python程式設計實現程式碼可參考↓(個人編寫,僅供參考,歡迎提出寶貴建議)

```python

!/usr/bin/env python

-- coding: utf-8 --

@Time : 2021/7/22 9:14

@Author : vaxtiandao

@File : ds_14.py

定義結點類,包含兩個成員:結點元素值和指向下一結點的指標

class SingleNode(): # 結點類初始化 def init(self, item): self.item = item # 存放結點的數值 self.next = None # 下一指標指向 self.hail = None # 上一指標指向

定義單鏈表

class DoubleLinkList(): # 連結串列類初始化 def init(self): self.head = None # 指向頭結點 self.hail = None # 指向尾結點

# 判斷連結串列是否為空
def is_empty(self):
    return self.head == None

# 輸出連結串列長度
def get_length(self):
    return len(self.travel())

# 遍歷整個連結串列
def travel(self):
    curlist = []
    cur = self.head
    while cur != None:
        curlist.append(cur.item)
        cur = cur.next
    return curlist

# 頭插法建立單鏈表
def add(self, newItem):
    node = SingleNode(newItem)
    if self.head is not None:
        node.next = self.head
        self.head = node
        node.next.prev = node
    else:
        self.head = node
        self.hail = node

# 尾插法建立單鏈表
'''def append(self,newItem):
    node = SingleNode(newItem)
    # 從尾結點開始遍歷
    cur = self.head
    if self.is_empty():
        self.head = node
    while cur.next != None:
        cur = cur.next
    cur.next = node
    node.prev = cur'''

def append(self, newItem):
    node = SingleNode(newItem)
    if self.hail is not None:
        self.hail.next = node
        node.prev = self.hail
        self.hail = node
    else:
        self.hail = node
        self.head = node

# 指定位置新增元素,pos從零開始
def insert(self, pos, newItem):
    node = SingleNode(newItem)
    if pos <= 0:
        self.add(newItem)
    elif pos > (self.get_length() - 1):
        self.append(newItem)
    else:
        count = 0
        cur = self.head
        while count < pos:
            count += 1
            cur = cur.next
        node.next = cur
        node.prev = cur.prev
        cur.prev.next = node
        cur.prev = node

# 刪除指定位置上的結點
def remove(self, pos):
    cur = self.head
    count = 0
    if 1 <= pos < (self.get_length()):
        while count < pos - 1:
            cur = cur.next
            count += 1
        cur.next = cur.next.next
        cur.next.prev = cur
    elif pos == 0:
        self.head = cur.next
    else:
        return '輸入的位置有誤,請確認'

# 查詢指定位置的結點值
def find(self, pos):
    cur = self.head
    count = 0
    if 0 <= pos < (self.get_length()):
        while count < pos:
            cur = cur.next
            count += 1
        return cur.item
    else:
        return '輸入的位置有誤,請確認'

# 更新連結串列中的某個位置的值
def update(self, pos, newItem):
    cur = self.head
    count = 0
    if 0 <= pos < (self.get_length()):
        while count < pos:
            cur = cur.next
            count += 1
        cur.item = newItem
    else:
        return '輸入的位置有誤,請確認'

# 清空連結串列
def clear(self):
    self.head = None
    self.hail = None

例項化物件

doublelinklist = DoubleLinkList() print("初始化雙向連結串列:", doublelinklist) print("__________________")

檢查連結串列是否為空

print("未插入元素之前連結串列為空:", doublelinklist.is_empty(), end="") print("__________________")

使用頭插法隨機新增資料

import random for i in range(10): doublelinklist.add(random.randint(1, 100))

判斷連結串列是否為空

print("插入元素之後連結串列不為空:", doublelinklist.is_empty()) print("__________________")

查詢連結串列長度

print("當前連結串列長度為:", doublelinklist.get_length()) print("__________________")

檢視資料

print("當前雙向連結串列遍歷後元素為:", doublelinklist.travel()) print("__________________")

使用尾插法

print("尾插法之前,雙向連結串列遍歷後元素為:", doublelinklist.travel()) doublelinklist.append(10) print("尾插法之後,雙向連結串列遍歷後元素為:", doublelinklist.travel()) print("__________________")

使用頭插法

print("頭插法之前,雙向連結串列遍歷後元素為:", doublelinklist.travel()) doublelinklist.add(0) print("頭插法之後,雙向連結串列遍歷後元素為:", doublelinklist.travel()) print("__________________")

指定位置插入值

print("指定位置插入之前,雙向連結串列遍歷後元素為:", doublelinklist.travel()) doublelinklist.insert(1, 1) print("指定位置插入之後,雙向連結串列遍歷後元素為:", doublelinklist.travel()) print("__________________")

查詢指定位置的值

t = 5 print("當前連結串列第{} 個元素數值為:".format(t), doublelinklist.find(t)) print("__________________")

刪除指定位置的值

print("刪除指定位置值之前,雙向連結串列遍歷後元素為:", doublelinklist.travel()) doublelinklist.remove(4) print("刪除指定位置值之前,雙向連結串列遍歷後元素為:", doublelinklist.travel()) print("__________________")

更新指定位置的值

doublelinklist.update(5, 5) print("當前雙向連結串列遍歷後元素為:", doublelinklist.travel()) print("__________________")

清空連結串列資料

doublelinklist.clear() print("當前雙向連結串列遍歷後元素為:", doublelinklist.travel()) print("__________________")

``` 以下是如上程式碼實現效果: 在這裡插入圖片描述   關於雙向連結串列基本操作的C語言程式碼,見這👉:雙向連結串列的基本操作