?? 最近在重溫資料結構的知識, 這篇blog主要寫資料結構中的線性表, 記錄自己用python實作這些資料結構以及對應的基本操作方法，方便今后回顧，
一 . 線性表定義:
零個或多個資料元素的有限序列;
二. 線性表的存盤結構:
-
順序存盤 -- eg.陣列List 、 元組Tupple
線性表的順序存盤結構, 是指用一段地址連續的存盤單元依次存盤線性表中的資料元素. 線性表是用陣列來實作的, 支持隨機存取,即訪問元素的時間復雜度為O(1); 但是在操作插入和洗掉元素的時候，由于要滿足地址的連續性，所以要移動很多的元素位置，因此，插入或者洗掉一個順序表的元素的時間復雜度是O(n)，
-
鏈式存盤 -- 鏈表(linked_list)
鏈表是指物理存盤單元上非連續的、非順序的存盤結構，資料元素的邏輯順序是通過鏈表的指標地址實作的，每個元素包含兩個結點，一個是存盤元素的資料域 (記憶體空間)，另一個是指向下一個結點地址的指標域，根據指標的指向，鏈表能形成不同的結構，例如單鏈表，雙向鏈表，回圈鏈表等，鏈表失去了順序表的隨機存取特點，即每次從中取一個元素都要從頭開始找，這樣耗費了一些時間，查找的時間復雜度為O(n)；但是在做插入和洗掉的時候，就方便了很多，只需要做一點指標修改就可以了( O(1) )，
三. 陣列
陣列下標是從0開始的, 陣列中存盤的資料連續，支持快速隨機訪問，
(Python中list是封裝好的陣列, 可以直接使用)，
四. 單鏈表
單鏈表是鏈表的一種，鏈表由結點所構成, 結點包括存放資料元素的資料域和存放后繼元素地址的指標域.
- python實作單鏈表
# -*- coding=utf-8 -*- # Python版本實作的單鏈表 class Node(object): def __init__(self, item): self.item = item # item存放的是資料元素 self.next = None # next指向下一元素的地址 ''' get_length() 獲取鏈表長度; is_empty() 判斷鏈表是否為空 travel() 遍歷整個鏈表 insert(index, value) 指定位置添加元素 remove(value) 洗掉結點 ''' class Single_linked_list(object): def __init__(self, node = None): self.head = None # 頭部 def get_length(self): '''獲取鏈表長度''' length = 0 cur = self.head while cur != None: length += 1 cur = cur.next return length def is_empty(self): '''判斷鏈表是否為空''' if self.head == None: return True else: return False def travel(self): '''遍歷鏈表''' cur = self.head while cur != None: print(cur.item) cur = cur.next def insert(self, index, value): '''指定位置添加元素''' if index < 0 or index > self.get_length(): print('error index') elif index == 0: # 在頭部插入結點 node = Node(value) cur = self.head node.next = cur self.head = node else: cur = self.head # 用來指向index-1 的位置，初始從頭結點開始移動到指定位置 count = 0 node = Node(value) # 初始化要插入的值 while count < index - 1: count += 1 cur = cur.next node.next = cur.next # 先將新節點node的next指向插入位置的節點 cur.next = node # 再將插入位置的前一個節點的next指向新節點 def remove(self, index): '''洗掉指定下標的結點''' if index < 0 or index >= self.get_length()-1: print('Wrong index') elif self.is_empty(): print('No node exists') elif index == 0: cur = self.head self.head = cur.next elif index == self.get_length(): cur = self.head for i in range(self.get_length()-2): cur = cur.next cur.next = None else: cur = self.head for i in range(index -1): cur = cur.next cur.next = cur.next.next if __name__ == "__main__": obj = Single_linked_list() obj.insert(0,2) obj.insert(1,5) obj.insert(2,4) obj.travel() print('------') obj.remove(1) obj.travel()
五. 順序表與鏈表的對比
<總結>:
- 若線性表需要頻繁查找, 很少進行插入和洗掉操作時, 宜采用順序存盤結構.
- 對于插入和洗掉資料越頻繁的操作, 單鏈表的優勢就越是明顯.
- 當線性表中元素個數變化比較大時, 最好用單鏈表結構, 這樣可以不考慮存盤空間大小的問題.
?? ??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/180089.html
標籤：其他
上一篇：做網站應該注意哪些細節？