数据结构与算法--单向循环链表

阅读目录

概念单向循环链表分步实现节点实现模拟一个单向循环链表分步实现功能 单向循环链表完整实现

概念

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None， 而是指向链表的头节点

单向循环链表分步实现

节点实现

# 节点 class Node(object): def __init__(self, item): self.item = item self.next = None

模拟一个单向循环链表

# 单向循环链表 class SinCycLinkedlist(object): def __init__(self, node=None): self.__head = None # 如果是空节点，就指向None if node: node.next = node ''' 可以这样理解，假设只有一个节点，虚拟节点的指针必然是指向第一个节点的， 即self.__head=node ,因为只有一个节点node， node的指针区域要指向开头才能形成循环； 所以node.next应该指向虚拟指针指向的区域， 即是自己，所以 如果存在节点的情况，node.next=node ''' ''' # 直接等于None 也没问题 def __init__(self): self.__head = None '''

分步实现功能

# 判断链表是否为空 def is_empty(self): return self.__head == None # 返回链表的长度 def length(self): # 如果链表为空，返回长度0 if self.is_empty(): return 0 count = 1 cur = self.__head while cur.next != self.__head: # 只要不等于头节点（即当前还没到尾节点），就要一直移动 count += 1 cur = cur.next return count ''' 关于count为什么从1开始的解答： 联系此前 单链表 长度的写法，来写单向循环链表： def length(self): cur = self.__head count = 0 # 此处存在计数错误 while cur.next != self.__head: # 这一步，假设只有一个节点，不会进入循环 # 因为self.__head=node, cur.next=node.next 而 node.next 应该指向头节点 # 即 node.next=node,cur.next=self.__head, # 所以没进入循环count，但是存在一个节点，应计数一个 count += 1 cur = cur.next return count 因此也是得知：while cur.next!=self.__head: 条件成立，表明链表必须是大于1个节点的 ''' # 遍历链表 def travel(self): if self.is_empty(): return cur = self.__head print(cur.item, end="") # 只有一个节点，即是头节点 while cur.next != self.__head: # 节点个数>1 的情况 cur = cur.next # 先偏移 再打印 （和单链表区别） print(cur.item, end="") print("") ''' 比较一下单链表： def travel(self): if self.is_empty(): return cur = self.__head while cur ！= None: # 如果只有一个节点的情况，满足循环，直接打印 print(cur.item, end="") cur = cur.next # 注意这句偏移，不能放在打印之前 print("") # 只是换行作用 ''' # 头部添加节点（头插法） def add(self, item): node = Node(item) if self.is_empty(): self.__head = node node.next = self.__head else: # 添加的节点指向 第一个节点 node.next = self.__head # 移到链表尾部，将尾部节点的next指向node cur = self.__head while cur.next != self.__head: cur = cur.next cur.next = node # 虚拟指针指向新添加node的 self.__head = node

# 尾部添加节点（尾插法） def append(self, item): node = Node(item) if self.is_empty(): self.__head = node node.next = self.__head else: # 移到链表尾部 cur = self.__head while cur.next != self.__head: cur = cur.next # 将尾节点指向node cur.next = node # 将node指向头节点__head node.next = self.__head # 在指定位置添加节点 def insert(self, pos, item): if pos <= 0: self.add(item) elif pos > (self.length() - 1): self.append(item) else: node = Node(item) cur = self.__head count = 0 # 移动到指定位置的前一个位置 while count < (pos - 1): count += 1 cur = cur.next node.next = cur.next cur.next = node

# 删除一个节点 def remove(self, item): if self.is_empty(): # 若链表为空，则直接返回 return cur = self.__head # 将cur指向头节点 if cur.item == item: # 若头节点的元素就是要查找的元素item if cur.next != self.__head: # 如果链表不止一个节点 while cur.next != self.__head: # 先找到尾节点，将尾节点的next指向第二个节点 cur = cur.next # 循环结束，cur指向了尾节点 cur.next = self.__head.next # 尾结点指向了第二个节点 self.__head = self.__head.next # 虚拟指针指向了第二个节点 else: # 链表只有一个节点 self.__head = None # 将虚拟指针指向None即可 else: # 要删除的元素不是头节点 pre = None # 写成 pre=self.__head 结果一样，单不合理 # 第一个节点不是要删除的 while cur.next != self.__head: # 节点>1;cur从头节点开始移动，且非尾节点 if cur.item == item: # 找到了要删除的元素 pre.next = cur.next # 头节点 指向 cur下一个节点 return else: # 还没找到，移动pre 和 cur 指针 pre = cur cur = cur.next # 移动两个指针 # 退出循环，指的是刚好要删除的是尾节点 if cur.item == item: # cur 指向尾节点 # 尾部删除 pre.next = cur.next # 查找节点是否存在 def search(self, item): if self.is_empty(): return False cur = self.__head if cur.item == item: # 如果要找的就是头节点 return True while cur.next != self.__head: # 如果要找的不是头，且节点>1 cur = cur.next # cur 是可以移动到尾结点，并指向他的 if cur.item == item: return True return False

单向循环链表完整实现

class Node(object): """节点""" def __init__(self, item): self.item = item self.next = None class SinCycLinkedlist(object): """单向循环链表""" # def __init__(self,node=None): # self.__head = None # if node: # node.next=node def __init__(self): self.__head = None def is_empty(self): """判断链表是否为空""" return self.__head == None def length(self): """返回链表的长度""" # 如果链表为空，返回长度0 if self.is_empty(): return 0 count = 1 cur = self.__head while cur.next != self.__head: count += 1 cur = cur.next return count def travel(self): """遍历链表""" if self.is_empty(): return cur = self.__head print(cur.item, end="") while cur.next != self.__head: cur = cur.next print(cur.item, end="") print("") def add(self, item): """头部添加节点""" node = Node(item) if self.is_empty(): self.__head = node node.next = self.__head else: # 添加的节点指向__head node.next = self.__head # 移到链表尾部，将尾部节点的next指向node cur = self.__head while cur.next != self.__head: cur = cur.next cur.next = node # __head指向添加node的 self.__head = node def append(self, item): """尾部添加节点""" node = Node(item) if self.is_empty(): self.__head = node node.next = self.__head else: # 移到链表尾部 cur = self.__head while cur.next != self.__head: cur = cur.next # 将尾节点指向node cur.next = node # 将node指向头节点__head node.next = self.__head def insert(self, pos, item): """在指定位置添加节点""" if pos <= 0: self.add(item) elif pos > (self.length() - 1): self.append(item) else: node = Node(item) cur = self.__head count = 0 # 移动到指定位置的前一个位置 while count < (pos - 1): count += 1 cur = cur.next node.next = cur.next cur.next = node def remove(self, item): """删除一个节点""" # 若链表为空，则直接返回 if self.is_empty(): return # 将cur指向头节点 cur = self.__head pre = None # 若头节点的元素就是要查找的元素item if cur.item == item: # 如果链表不止一个节点 if cur.next != self.__head: # 先找到尾节点，将尾节点的next指向第二个节点 while cur.next != self.__head: cur = cur.next # cur指向了尾节点 cur.next = self.__head.next self.__head = self.__head.next else: # 链表只有一个节点 self.__head = None else: pre = self.__head # 第一个节点不是要删除的 while cur.next != self.__head: # 找到了要删除的元素 if cur.item == item: # 删除 pre.next = cur.next return else: pre = cur cur = cur.next # cur 指向尾节点 if cur.item == item: # 尾部删除 pre.next = cur.next def search(self, item): """查找节点是否存在""" if self.is_empty(): return False cur = self.__head if cur.item == item: return True while cur.next != self.__head: cur = cur.next if cur.item == item: return True return False if __name__ == "__main__": ll = SinCycLinkedlist() ll.add(1) ll.add(2) ll.append(3) ll.insert(2, 4) ll.insert(4, 5) ll.insert(0, 6) ll.insert(0, 8) ll.insert(0, 6) ll.insert(5, 5) print(ll.search(5)) print("length:", ll.length()) ll.travel() print(ll.search(3)) print(ll.search(7)) ll.remove(1) ll.remove(5) ll.remove(6) ll.remove(5) print("length:", ll.length()) ll.travel() print(ll.search(3)) print(ll.search(4)) ''' True length: 9 686215435 True False length: 5 86243 True True '''