Python实现循环单链表
＂＂＂ 创建一个节点类 ＂＂＂ class Node: def __init__(self, data): self.data = data self.next = None ＂＂＂ 定义一个循环单链表 ＂＂＂ class CycleLink: def __init__(self): self.header = None self.length = 0 # 判断链表是否为空 def is_empty(self): return not self.header ＂＂＂ 实现向链表添加数据的功能 有三种实现方式: 1.头插法 2.尾插法 3.根据指定位置向单链表插入元素 ＂＂＂ # 1.头插法 def __add__(self, value): node = Node(value) if self.is_empty(): self.header = node node.next = self.header self.length += 1 return cur = self.header while cur.next != self.header: cur = cur.next cur.next = node node.next = self.header self.header = node self.length += 1 # 2.尾插法 def append(self, value): node = Node(value) cur = self.header if self.is_empty(): self.__add__(value) return while cur.next != self.header: cur = cur.next cur.next = node node.next = self.header self.length += 1 # 3.根据指定位置向单链表插入元素 def insert(self, index, value): if index <= 1: self.__add__(value) elif index > self.length - 1: self.append(value) else: cur = self.header node = Node(value) temp = 1 while temp != index - 1: cur = cur.next temp += 1 node.next = cur.next cur.next = node self.length += 1 return value ＂＂＂ 实现查询循环链表的功能 有三种实现方式: 1.根据索引查询单链表的对应元素 2.直接查询元素 3.遍历整个单链表,并打印出所有元素 ＂＂＂ # 1.根据索引查询单链表的对应元素 def __getitem__(self, index): if index < 0 or index > self.length: raise IndexError cur = self.header for i in range(index - 1): cur = cur.next return cur.data # 2.直接查询元素,并返回元素的索引 def is_Exist(self, value): if self.is_empty(): return -1 temp = 0 cur = self.header while cur.next != self.header: if cur.data == value: return temp + 1 cur = cur.next temp += 1 if cur.data == value: return temp + 1 return -1 # 3.遍历整个单链表,并打印出所有元素 def getAll(self): if self.is_empty(): print(＂目前链表中没有元素！＂) return cur = self.header while cur.next is not self.header: print(＂%d＂ % cur.data, end=＂ ＂) cur = cur.next print(＂%d＂ % cur.data, end=＂ ＂) ＂＂＂ 实现修改元素的功能 ＂＂＂ def __setitem__(self, index, value): if index < 0 or index > self.length: raise IndexError cur = self.header for i in range(index - 1): cur = cur.next cur.data = value return value ＂＂＂ 实现删除元素的功能 有三种实现方式: 1.根据索引删除元素 2.直接删除元素 3.清空循环单链表 ＂＂＂ # 1.根据索引删除元素 def __delitem__(self, index): cur = self.header pre = None for i in range(index - 1): pre = cur cur = cur.next if cur == self.header: pre = self.header while pre.next != self.header: pre = pre.next pre.next = self.header.next self.header = self.header.next self.length -= 1 return ＂ ＂ pre.next = cur.next self.length -= 1 return ＂ ＂ # 2.直接删除元素 def __delete__(self, value): cur = self.header pre = None while cur.next != self.header: if cur.data == value: if cur == self.header: pre = self.header while pre.next != self.header: pre = pre.next pre.next = cur.next self.header = cur.next self.length -= 1 return ＂ ＂ pre.next = cur.next self.length -= 1 return ＂ ＂ pre = cur cur = cur.next if cur.data == value: pre.mext = cur.next pre.next = cur.next self.length -= 1 return ＂ ＂ # 3.清空循环单链表 def clear(self): self.header=None if __name__ == ＂__main__＂: s = CycleLink() s.__add__(12) s.__add__(13) s.__add__(15) s.append(22) s.append(23) s.append(25) s.getAll() print(＂ 在链表的第%d个位置插入元素%d:＂ % (2, s.insert(2, 44))) s.getAll() print(＂ 目前链表中元素的数量:＂, s.length) print(＂查询链表第%d个位置的元素是 %d.＂ % (4, s.__getitem__(4))) print(＂修改第%d个元素为%d!＂ % (1, s.__setitem__(1, 90))) s.getAll() print(＂删除第%d个元素＂ % 1, s.__delitem__(1)) s.getAll() print(＂ 目前链表中元素的数量:＂, s.length) print(＂删除链表元素%d＂ % 22, s.__delete__(22)) s.getAll() print(＂ 目前链表中元素的数量:＂, s.length) print(＂ 清空链表中的元素:＂) s.clear() s.getAll()