Python实现数据结构

一、Python实现数据结构

1.1 python实现单向链表

singleLinkedList.py

class SingleNode:"""the node of single link list"""def __init__(self, item):self.item = itemself.next = Nonedef __str__(self):return str(self.item)class SingleLinkList:"""sing link list"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""获取链表长度"""cur = self._headcount = 0while cur is not None:count += 1cur = cur.nextreturn countdef travel(self):"""遍历链表"""cur = self._headwhile cur is not None:print(cur.item)cur = cur.nextprint()def add(self, item):"""链表头部添加元素"""node = SingleNode(item)node.next = self._headself._head = nodedef append(self, item):"""链表尾部添加元素"""node = SingleNode(item)if self.is_empty():self._head = nodeelse:cur = self._headwhile cur.next is not None:cur = cur.next"""此时cur指向最后一个节点，next=None"""cur.next = nodedef insert(self, pos, item):"""指定位置添加元素"""# 若pos小于0，则执行头部插入if pos <= 0:self.add(item)# 若pos大鱼链表长度，则执行尾部插入elif pos > self.length() - 1:self.append(item)else:node = SingleNode(item)cur = self._headcur_pos = 0while cur.next is not None:"""获取插入位置的上一个节点"""if pos - 1 == cur_pos:node.next = cur.nextcur.next = nodebreakcur = cur.nextcur_pos += 1def remove(self, item):"""删除节点"""if self.is_empty():returncur = self._headif cur.item == item:self._head = cur.nextelse:while cur.next is not None:if cur.next.item == item:cur.next = cur.next.nextbreakcur = cur.nextdef search(self, item):"""查找节点位置"""cur = self._headcount = 0while cur is not None:if cur.item == item:return countcur = cur.nextcount += 1return -1# if __name__ == "__main__":
#     ll = SingleLinkList()
#     ll.add(1)
#     ll.add(2)
#     ll.append(3)
#     ll.insert(2,4)
#     print("length: ", ll.length())
#     ll.travel()
#     print("search(3): ", ll.search(3))
#     print("search(5): ", ll.search(5))
#     ll.remove(1)
#     print("length: ", ll.length())
#     ll.travel()

1.2 python实现单向循环链表

sinCycLinkedList.py

class Node:def __init__(self, item):self.item = itemself.next = Nonedef __str__(self):return str(self.item)class SinCycLinkedList:"""单向循环链表"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表受否为空"""return self._head is Nonedef length(self):"""返回链表长度"""if self.is_empty():return 0cur = self._headcount = 1while cur.next != self._head:count += 1cur = cur.nextreturn countdef travel(self):"""遍历链表"""if self.is_empty():returncur = self._headprint(cur.item)while cur.next != self._head:cur = cur.nextprint(cur.item)print()def add(self, item):"""链表头部添加节点"""node = Node(item)if self.is_empty():self._head = nodenode.next = nodeelse:cur = self._headnode.next = self._headwhile cur.next != self._head:cur = cur.nextcur.next = nodeself._head = nodedef append(self, item):"""链表尾部添加节点"""node = Node(item)if self.is_empty():self._head = nodenode.next = self._headelse:cur = self._headwhile cur.next != self._head:cur = cur.nextcur.next = nodenode.next = self._headdef insert(self, pos, item):"""链表指定位置插入节点"""if pos <= 0:self.add(item)elif pos > self.length() - 1:self.append(item)else:cur = self._headcur_pos = 0node = Node(item)while cur.next != self._head:if cur_pos == pos - 1:node.next = cur.nextcur.next = nodebreakcur = cur.nextcur_pos += 1def remove(self, item):"""删除链表指定节点"""if self.is_empty():returnpre = self._headif pre.item == item:cur = prewhile cur.next != pre:cur = cur.nextcur.next = pre.nextself._head = pre.nextelse:cur = prewhile cur.next != pre:if cur.next.item == item:cur.next = cur.next.next# breakcur = cur.nextdef search(self, item):"""查找节点，返回下标"""cur = self._headcount = 0while cur.next != self._head:if cur.item == item:return countcount += 1cur = cur.nextreturn -1# if __name__ == "__main__":
#     ll = SinCycLinkedList()
#     ll.add(1)
#     ll.add(2)
#     ll.travel()
#     ll.append(3)
#     ll.insert(2, 4)
#     ll.insert(4, 5)
#     ll.insert(0, 6)
#     print("length ", ll.length())
#     ll.travel()
#     print("search(3)", ll.search(3))
#     print("search(7)", ll.search(7))
#     print("search(6)", ll.search(6))
#     print("remove(1)")
#     ll.remove(1)
#     print("length: ", ll.length())
#     print("remove(6)")
#     ll.remove(6)
#     ll.travel()

1.3 python实现双向链表

doubleLinkedList.py

class Node:def __init__(self, item):self.item = itemself.previous = Noneself.next = Nonedef __str__(self):return str(self.item)class DLinkedList:"""双向链表"""def __init__(self):self._head = Nonedef is_empty(self):"""判断链表是否为空"""return self._head is Nonedef length(self):"""返回链表长度"""if self.is_empty():return 0count = 1cur = self._headwhile cur.next is not None:count += 1cur = cur.nextreturn countdef travel(self):"""遍历链表"""if self.is_empty():returncur = self._headprint(cur.item)while cur.next is not None:cur = cur.nextprint(cur.item)print()def add(self, item):"""链表头部添加节点"""node = Node(item)if self.is_empty():self._head = nodeelse:node.next = self._headself._head.previous = nodeself._head = nodedef append(self, item):"""链表尾部添加节点"""node = Node(item)if self.is_empty():self._head = nodeelse:cur = self._headwhile cur.next is not None:cur = cur.nextcur.next = nodenode.previous = curdef insert(self, pos, item):"""链表指定位置插入节点"""if pos <= 0:self.add(item)elif pos > self.length() - 1:self.append(item)else:cur = self._headnode = Node(item)cur_pos = 0while cur is not None:if cur_pos == pos - 1:node.next = cur.nextnode.previous = curcur.next = nodecur.next.previous = nodebreakcur = cur.nextcur_pos += 1def remove(self, item):"""链表删除指定元素"""if self.is_empty():returncur = self._headif cur.item == item:self._head = cur.nextself._head.previous = Noneelse:while cur.next is not None:if cur.item == item:cur.previous.next = cur.nextcur.next.previous = cur.previousreturncur = cur.nextif cur.item == item:cur.previous.next = Nonedef search(self, item):"""查找链表指定元素，返回元素下标"""cur_pos = 0cur = self._headwhile cur is not None:if cur.item == item:return cur_poscur = cur.nextcur_pos += 1return -1if __name__ == "__main__":ll = DLinkedList()ll.add(1)ll.add(2)ll.append(3)ll.insert(2, 4)ll.insert(4, 5)ll.insert(0, 6)print("length: ", ll.length())        ll.travel()print("search(3) ", ll.search(3))print("search(4) ", ll.search(4))print("search(10) ", ll.search(10))ll.remove(1)print("length: ", ll.length())ll.travel()print("删除首节点 remove(6): ")ll.remove(6)ll.travel()print("删除尾节点 remove(5): ")ll.remove(5)ll.travel()