|
定義: 雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環(huán)鏈表。  代碼: ''' 雙鏈表 優(yōu)點: 可以找到前驅和后繼，可進可退； 缺點: 增加刪除節(jié)點復雜，需要多分配一個指針存儲空間。 適用于需要雙向查找節(jié)點值的情況'''#創(chuàng)建一個結點類class Node: def __init__(self, value=None): self.value = value self.prev = None self.next = None''' 創(chuàng)建一個雙鏈表'''class doubleLink: def __init__(self): self.header = None # 初始化頭結點 self.length = 0 # 鏈表的長度 # 判斷鏈表是否為空 def is_empty(self): return self.length == 0 ''' 實現(xiàn)向雙鏈表添加元素的功能 有三種實現(xiàn)方式: 1.頭插法 2.尾插法 3.向雙鏈表的指定位置添加元素 ''' # 1.頭插法 def __add__(self, value): node = Node(value) if self.is_empty(): node.prev = self.header self.header = node self.length += 1 return else: node.next = self.header self.header.prev = node self.header = node self.length += 1 # 2.尾插法 def append(self, value): node = Node(value) if self.is_empty(): self.__add__(value) else: cur = self.header while cur.next is not None: cur = cur.next cur.next = node node.prev = cur self.length += 1 # 3.向雙鏈表的指定位置添加元素 def insert(self, index, value): node = Node(value) cur = self.header if index <= 0 or index > self.length: print('您輸入的信息有誤') return ' ' if index == 1: self.__add__(value) for i in range(2, index): cur = cur.next node.next = cur.next cur.next.prev = node cur.next = node node.prev = cur self.length += 1 return value ''' 實現(xiàn)插尋雙鏈表元素的功能 有三種實現(xiàn)方式: 1.根據索引查詢元素 2.直接查詢元素 3.遍歷整個雙鏈表，并打印出所有的元素 ''' # 1.根據索引查詢元素 def __getitem__(self, index): cur = self.header for i in range(index - 1): cur = cur.next return cur.value # 2.直接查詢元素，并返回該元素的索引 def getIndex(self, value): cur = self.header temp = 0 while cur.next is not self.header: if cur.value == value: return temp + 1 cur = cur.next temp += 1 # 3.遍歷整個雙鏈表，并打印出所有的元素 def getAll(self): if self.is_empty(): print('目前雙鏈表中沒有元素！') return cur = self.header for i in range(self.length): print('%d' % cur.value, end=' ') cur = cur.next # 4.查詢某個元素的后繼節(jié)點 def getItem(self, value): cur = self.header temp = 0 while cur.next is not self.header: if cur.value == value: if cur.next is not None: return cur.next.value else: return -1 cur = cur.next temp += 1 # 5.查詢某個元素的前驅節(jié)點 def getPrevItem(self, value): cur = self.header temp = 0 while cur.next is not self.header: if cur.value == value: if cur.prev is not None: return cur.prev.value else: return -1 cur = cur.next temp += 1 ''' 實現(xiàn)修改指定位置元素的功能 ''' def __setitem__(self, index, value): cur = self.header for i in range(index - 1): cur = cur.next cur.value = value return value ''' 實現(xiàn)刪除雙鏈表元素的功能 ''' # 直接刪除元素 def __delete__(self, value): cur = self.header if self.getIndex(value) == 1: self.header = cur.next self.length -= 1 elif self.getIndex(value) != 1: while self.getIndex(value) != self.length: cur = cur.next cur=None self.length -= 1 else: while cur.value != value: cur = cur.next cur.prev.next = cur.next cur.next.prev = cur.prev self.length -= 1if __name__ == '__main__': s = doubleLink() s.__add__(12) s.__add__(13) s.__add__(14) s.__add__(15) s.append(22) s.getAll() print('\n第%d個位置的元素是%d.' % (1, s.__getitem__(1))) print('\n元素%d在雙鏈表的第%d個位置' % (14, s.getIndex(14))) print('獲取元素%d的后繼節(jié)點%d' % (12, s.getItem(12))) print('獲取元素%d的前驅節(jié)點%d' % (13, s.getPrevItem(13))) print('在第%d個位置插入元素%d:' % (2, s.insert(2, 45))) s.getAll() print('\n將第%d個位置的元素修改為%d:' % (1, s.__setitem__(1, 900))) s.getAll() print('\n刪除元素22:') s.__delete__(22) s.getAll() |
|
|
