前兩天一個鄰居發出了靈魂質問：“為什麼我買的180平和你的169平看上去一樣大？” “因為咱倆的套內面積都是138平......” 我們去看房子，比較不同樓盤的價格，看的都是單價，可這個單價，卻是用（總價 ÷ 建築面積）計算的。而我們實際買到手裡的，是套內面積。 套內面積 = 使用面積+牆體厚度+陽 ...
鏈式結構記憶體不連續的，而是一個個串起來的，每個鏈接表的節點保存一個指向下一個節點的指針。
⭐ 鏈式結構包含：node（節點）還有value（值），由於記憶體不連續的，那麼對於數據的插入，只需找到一個節點便可以插入數據，這也是鏈表優於列表的一個優點，反之，對於數據的刪除，由於不是連續的，不能通過索引刪除數據，只能一一遍歷刪除元素。 ⭐ 接下來上代碼 單鏈表的增刪功能# 定義一個結點的類 class Node(): def __init__(self,value=None,next=None): self.next = next self.value = value def __str__(self): return "Node:{}".format(self.value) # 定義一個連接點的類 class Linklist(): def __init__(self): self.root = Node() self.size = 0 self.next = None # 增加新數據時，將信數據的地址與誰關聯 # 只要是追加 就要創造節點 def append(self,value): node = Node(value) # 判斷root節點下麵是否有數據 if not self.next: # 如果沒有節點 self.root.next = node # 將新節點掛在root後面 else: self.next.next = node # 將新節點掛在最後一個節點上 self.next = node # 重新賦值 一開始的是None self.size += 1 def append_first(self,value): # 只要是追加 就要創造節點 node = Node(value) # 判斷root下麵是否存在節點 if not self.next: self.root.next = node self.next = node else: temp = self.root.next # 獲取原來root後面的那個節點 self.root.next = node # 將新節點掛在root後面 node.next = temp # 新的節點的下一個節點是原來的root的節點 # 迭代鏈表 def __iter__(self): # 獲得root節點下麵的數據 current = self.root.next # 判斷current是否有之 由於一開始賦予value和next沒有值 所以進行判斷 否則報錯 if current: # 判斷時候有下一個節點 有的話則返回下一個結點的值 while current is not self.next: # self.next可以列結成最後一個節點 yield current current = current.next yield current # 查找數據 def find(self,value): for n in self.__iter__(): if n.value == value: return n # 查找出現的次數 def find_count(self,value): count = 0 for n in self.__iter__(): if n.value == value: count += 1 return count # 移除數據(鏈表的移除，需要逐一遍歷，找到當前元素的節點，再刪除) def remove(self,value): prve = self.root for n in self.__iter__(): # 判斷節點的值與要刪除的值是否相等 if n.value == value: # 查看是不是最後一個節點 if n == self.next: # 更新倒數第二節點的關係 prve.next = None # 更新最後一個節點為原倒數第二個節點 self.next = prve prve.next = None # 刪除當前節點 del n # 鏈表大小減少 self.size -= 1 return True prve = n def remove_all(self,value): prve =self.root for n in self.__iter__(): if n.value == value: if n == self.next: prve.next = None self.next = prve prve.next = n.next # 刪除當前節點 del n # 鏈表大小減少 self.size -= 1 return True prve = n if __name__ == "__main__": link = Linklist() link.append("孫悟空") link.append("豬八戒") link.append("孫悟空") link.append("豬八戒") link.append("豬八戒") link.append("唐僧") link.append_first("唐僧") link.append_first("唐僧") # for v in link: # print(v) # print(link.find('孫悟空')) # print(link.find_count('唐僧')) print("**************刪除之前的數據******************") for v in link: print(v) link.remove('唐僧') link.remove('唐僧') link.remove('唐僧') link.remove('唐僧') link.remove('孫悟空') link.remove('豬八戒') link.remove_all("豬八戒") link.remove_all("孫悟空") link.remove_all("唐僧") print("**************刪除之後的數據******************") for v in link: print(v)
⭐ 接下來上代碼 雙鏈表的增刪功能：
# 定義一個結點的類 class Node(): def __init__(self,value=None,node=None,next=None): self.value = value self.node = node self.next = next def __str__(self): return "Node:{}".format(self.value) # 定義一個連接點的類 class DoubleLinkedList(): def __init__(self): self.root = Node() self.size = 0 self.end = None def append(self,value): node = Node(value) # 判斷root節點下麵是否有數據 if not self.end: # 如果沒有元素 self.root.next = node # 將root 的下一個節點 設置為新的node節點 node.prev = self.root # 設置新節點的 上一個節點 為 root else: self.end.next = node # 將原來最後節點的下一個節點 設置為新的node節點 node.prev = self.end # 設置新節點的 上一個節點 為 原來的最後一個節點 self.end = node # 更新最後 一個節點新加的node節點 self.size += 1 def append_first(self,value): node = Node(value) # 封裝節點對象 # 判斷是否已經有數據 if not self.end:# 如果沒有元素 self.end = node # 更新最後 一個節點新加的node節點 else: # temp指向node，node指向root，root指向temp temp = self.root.next # 保存原來的第一個節點 node.next = temp # 設置新節的下一個節為原來的 第一個節點 temp.prev = node # 更新原來的第一個節點的上一個節點位置為 新的node節點 node.prev = self.root # 設置新節點的 上一個節點 為 root self.root.next = node # 將root 的下一個節點 設置為新的node節點 self.size += 1 # 正序迴圈 def __iter__(self): current = self.root.next if current: while current is not self.end: yield current.value current = current.next yield current.value # 倒敘迴圈 def revers_iter(self): current = self.end #獲取最後一節點 if current: while current is not self.root: yield current current = current.prev if __name__ == "__main__": link = DoubleLinkedList() link.append('孫悟空') link.append('豬八戒') link.append_first('唐三藏') for v in link: print(v) print('-'*30) for v in link.revers_iter(): print(v)
