四川省建设厅职改办网站,上海品牌网站建设公,电商网站模板建站,青岛的互联网企业文章目录 一、Python实现数据结构1.1 python实现单向链表1.2 python实现单向循环链表1.3 python实现双向链表 一、Python实现数据结构
1.1 python实现单向链表
singleLinkedList.py
class SingleNode:the node of single link listdef … 文章目录 一、Python实现数据结构1.1 python实现单向链表1.2 python实现单向循环链表1.3 python实现双向链表 一、Python实现数据结构
1.1 python实现单向链表
singleLinkedList.py
class SingleNode:the node of single link listdef __init__(self, item):self.item itemself.next Nonedef __str__(self):return str(self.item)class SingleLinkList:sing link listdef __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指向最后一个节点nextNonecur.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()
