Maison > Article > développement back-end > [Python Learning] Implémentation de la syntaxe Python d'une liste chaînée circulaire unidirectionnelle
La liste chaînée est une structure de données de base commune, mais elle ne stocke pas les données en continu comme une liste séquentielle. informations (c'est-à-dire adresse) du nœud suivant dans chaque nœud (unité de stockage de données).
Une variante de liste chaînée unique est une liste chaînée circulaire unidirectionnelle , le dernier de la liste chaînée. Le champ suivant du nœud n'est plus Aucun, mais pointe vers le nœud principal de la liste chaînée.
Implémentation de la grammaire :
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
[Recommandation de cours : Tutoriel vidéo Python]
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!