本文共 5522 字,大约阅读时间需要 18 分钟。
class DoubleLinkedNode(object): def __init__(self, data): self.data = data self.next = None self.prev = Noneclass DoubleLinkedList(object): def __init__(self): self.head = DoubleLinkedNode("头结点") def GetLength(self): """获取双链表长度 """ currentNode = self.head.next length = 0 while currentNode != None: length += 1 currentNode = currentNode.next return length def IsEmpty(self): """判断链表是否为空 """ if self.GetLength() == 0: print("该链表为空!") return True else: return False def Traval(self): """遍历双链表 """ if self.IsEmpty(): return currentNode = self.head print("当前链表为:") while currentNode != None: print(currentNode.data, end="<->") currentNode = currentNode.next print("") def Create(self): data = input("请输入元素:") cNode = self.head while data != '#': nNode = DoubleLinkedNode(data) cNode.next = nNode nNode.prev = cNode cNode = nNode data = input("请输入元素:") self.Traval() def InsertElementInTail(self): """尾插法 """ element = input("待从尾部插入的结点的数据:") if element == "#": return currentNode = self.head newNode = DoubleLinkedNode(element) while currentNode.next != None: currentNode = currentNode.next currentNode.next = newNode newNode.prev = currentNode self.Traval() def InsertElementInHead(self): """头插法 """ element = input("待从头部插入的结点的数据:") if element == "#": return currentNode = self.head newNode = DoubleLinkedNode(element) newNode.next = currentNode.next currentNode.next = newNode newNode.prev = currentNode self.Traval() def InsertElementInSpecifiedPosition(self): """在指定位置插入结点 """ Pos = 0 currentNode = self.head element, position = input("结点的数据 待插入的结点在双链表中的位置").split(" ") newNode = DoubleLinkedNode(element) if int(position) < 1 or int(position) > self.GetLength()+1: print("位置不合法!请重新确定位置!") return while currentNode.next != None: Pos += 1 if Pos == int(position): newNode.next = currentNode.next currentNode.next = newNode newNode.prev = currentNode self.Traval() return else: currentNode = currentNode.next def FindElement(self): """查找所有有指定数据的结点的位置 """ Position = [] Pos = 0 currentNode = self.head element = input("待查找的数据:") if self.IsEmpty(): print("当前双链表为空!无法查找!") return while currentNode.next != None: currentNode = currentNode.next Pos += 1 if currentNode.data == element: Position.append(Pos) if Position: print("查找成功,值为", element, "的结点位于该双链表的第", Position, "位。") else: print("查找失败!当前双链表中不存在含有", element, "的结点") def DeleteElementInSpecifiedPosition(self): """在指定位置删除结点 """ print("在指定位置删除结点") Pos = 0 currentNode = self.head position = int(input("待删除的位置:")) if self.IsEmpty(): print("当前双链表为空!无法删除结点!") return if position < 1 or position > self.GetLength(): print("位置不合法!请重新确定位置!") return while currentNode.next != None: removedNode = currentNode.next Pos += 1 if Pos == position: currentNode.next = removedNode.next if removedNode.next == None: del removedNode else: removedNode.next.prev = currentNode del removedNode else: currentNode = currentNode.next self.Traval() def DeleteElement(self): """删除所有有指定数据的结点 """ if self.IsEmpty(): print("当前双链表为空!") return element = input('请输入待删除结点的值:') currentNode = self.head while currentNode.next != None: removedNode = currentNode.next if removedNode.data == element: currentNode.next = removedNode.next if currentNode.next == None: del removedNode else: removedNode.next.prev = currentNode del removedNode else: currentNode = currentNode.next print("成功删除所有含值为", element, "的结点") self.Traval() def Destory(self): print("正在销毁该链表...") del self.head print("已销毁该双链表!")dl = DoubleLinkedList()dl.Create()dl.InsertElementInTail()dl.InsertElementInHead()dl.InsertElementInSpecifiedPosition()dl.FindElement()dl.DeleteElementInSpecifiedPosition()dl.DeleteElement()-----------------------------------------------------------------------请输入元素:1请输入元素:2请输入元素:3请输入元素:4请输入元素:#当前链表为:头结点<->1<->2<->3<->4<->待从尾部插入的结点的数据:4当前链表为:头结点<->1<->2<->3<->4<->4<->待从头部插入的结点的数据:0当前链表为:头结点<->0<->1<->2<->3<->4<->4<->结点的数据 待插入的结点在双链表中的位置100 1当前链表为:头结点<->100<->0<->1<->2<->3<->4<->4<->待查找的数据:4查找成功,值为 4 的结点位于该双链表的第 [6, 7] 位。在指定位置删除结点待删除的位置:1当前链表为:头结点<->0<->1<->2<->3<->4<->4<->请输入待删除结点的值:4成功删除所有含值为 4 的结点当前链表为:头结点<->0<->1<->2<->3<->
带头结点的双链表的实现与带头结点的单链表的实现也有相当高的相似性,最大的区别就是前者会多一个结点指针域指向前一个结点的操作。
转载地址:http://jnzrz.baihongyu.com/