鍊錶(Linked list)是一種常見的基礎資料結構,是⼀種線性表,但是不像順序表一樣連續儲存數據,是在每個節點(資料儲存單元)存放下一個節點的位置資訊(即位址)。
單鍊錶的一個變形是單向循環鍊錶,鍊錶中最後一個節點的next域不再為None,而是指向鍊錶的頭節點。
語法實作:
class Node(object): """结点类""" def __init__(self, item): self.item = item self.next = None class CyclesSingleLinkList(): """单向循环链表""" def __init__(self, node=None): self.__head = node def is_empty(self): """链表是否为空 :return 如果链表为空 返回真 """ return self.__head is None def length(self): """链表长度""" # 如果是空链表 if self.is_empty(): return 0 cur = self.__head count = 1 while cur.next != self.__head: count += 1 cur = cur.next return count def travel(self): """遍历整个链表""" if self.is_empty(): print("") return cur = self.__head while cur.next != self.__head: print(cur.item, end=" ") cur = cur.next # 从循环退出,cur指向的是尾结点 print(cur.item) def add(self, item): """链表头部添加元素 :param item: 要保存的具体数据 """ node = Node(item) if self.is_empty(): self.__head = node node.next = node # 寻找尾结点 cur = self.__head while cur.next != self.__head: cur = cur.next # 从循环中退出,cur指向尾结点 node.next = self.__head self.__head = node cur.next = self.__head def append(self, item): """链表尾部添加元素""" node = Node(item) #如果列表为空,直接添加结点 if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next #退出循环的时候,cur指向尾结点 cur.next = node node.next = self.__head def insert(self, pos, item): """指定位置添加元素""" # 在头部添加元素 if pos <= 0: self.add(item) # 在尾部添加元素 elif pos >= self.length(): self.append(item) else: cur = self.__head count = 0 while count < (pos - 1): count += 1 cur = cur.next # 退出循环的时候,cur指向pos前一个位置 # node插入到pos位置前 node = Node(item) node.next = cur.next cur.next = node def remove(self,item): """删除结点""" if self.is_empty(): return # 当前游标 cur = self.__head # 当前游标的上一个游标 pre = None while cur.next != self.__head: # 找到了要删除的元素 if cur.item == item: # 在头部找到了元素 if cur == self.__head: # 先找到尾结点 rear = self.__head while rear.next != self.__head: rear = rear.next # 退出循环后,rear指向尾结点 self.__head = cur.next rear.next = self.__head else: # 在中间位置找到了元素 pre.next = cur.next return # 不是要找的元素,移动游标 pre = cur cur = cur.next # 退出循环后,cur指向尾结点 if cur.item == item: # 链表只有一个节点 if cur == self.__head: self.__head = None else: pre.next = self.__head def search(self,item): """查找结点是否存在""" if self.is_empty(): return False cur = self.__head while cur.next != self.__head: if cur.item == item: return True cur = cur.next # 退出循环后,cur指向为尾结点 if cur.item == item: return True return False if __name__ == '__main__': ll = CyclesSingleLinkList() print(ll.length()) ll.travel() ll.append(1) print(ll.length()) #1 ll.travel() #1 ll.add(2) print(ll.length()) #2 ll.travel()#2 1 ll.insert(1,3) ll.travel() #2 3 1 ll.remove(1) ll.travel() #2 3
【課程推薦:Python影片教學】
以上是【python學習】單向循環鍊錶的python語法實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!