Comment implémenter une liste chaînée circulaire unidirectionnelle en python

Liste chaînée circulaire unidirectionnelle

relie tout ensemble. Chaque nœud est divisé en une zone de stockage de données et une zone de liaison. La zone de données stocke les données et la zone de liaison est liée au nœud suivant

élément : Où. pour stocker des données
suivant : Lien vers le nœud suivant
Remarque : La liste chaînée circulaire unidirectionnelle est le premier lien, c'est-à-dire que le nœud de queue doit être lié au nœud principal

Opération de liste chaînée unidirectionnelle

1. Si la liste chaînée est vide
2. La longueur de la liste chaînée
3. Parcourez la liste chaînée
4. Ajoutez des éléments à la fin de la liste chaînée.
6. Ajoutez des éléments à la position spécifiée de la liste chaînée
7. Supprimez les nœuds de la liste chaînée
8. Recherchez si le nœud existe

Implémentation du code

# Functions  函数声明
class Node():
    """实例化节点类"""
    def __init__(self, item):
        self.item = item
        self.next = None

class Linklist():
    """
    存放节点类
    """
    def __init__(self):
        self.head = None

    # 1. 链表是否为空
    def is_empty(self):
        return self.head == None

    # 2. 链表的长度
    def length(self):
        """
        返回链表的长度
        遍历所有的节点，使用计数器计数
        1、链表为空情况
        """
        # 实例化节点
        cur = self.head
        if self.is_empty():
            return 0
        else:
            # 计数
            count = 1
            # 遍历链表
            while cur.next != self.head:
                count+=1
                cur = cur.next
            return count

    # 3. 遍历链表
    def travel(self):
        """
        遍历链表，获取所有的数据
        实例游标，遍历数据，输出数据
        1、 空链表情况
        2、 只有头部节点情况
        3、 只有尾部节点情况
        """
        # 实例化游标
        cur = self.head
        if self.is_empty():
            return None
        else:
            # 遍历数据
            while cur.next != self.head:
                print(cur.item, end=' ')
                cur = cur.next
            # 最后一个节点要单独输出
            print(cur.item)

    # 4. 链表头部添加元素
    def add(self, item):
        """
        往链表头部添加数据
        分析
        链表为空
            self.head 直接指向node， 再讲node指向自己
        链表不为空
            node.next = self.head
        """
        # 实例化游标
        cur = self.head
        # 实例化节点
        node = Node(item)
        # 判断是否为空
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            # 不为空的情况
            # 要将最后一个节点指向node
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            self.head = node
            cur.next = node

    # 5. 链表尾部添加元素
    def append(self, item):
        """
        往尾部添加数据
        分析
        实例化节点，再实例化游标先指向最后一个节点
        调换指向
        1、空链表情况
        2、只有一个链表情况

        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            self.add(item)
        else:
            # 不为空的情况,移动游标指向最后一个节点
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            cur.next = node
            pass

    # 6. 链表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加数据
        实例化节点， 实例化游标指向索引的数据，更改指向
        位置大小
        链表是否为空

        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        if index <=0:
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 判断链表是否为空
            if self.is_empty():
                self.add(item)
            else:
                # 移动游标，指向指定的索引位置
                count = 0
                while count < index-1:
                    count+=1
                    cur = cur.next
                node.next = cur.next
                cur.next = node
            pass

    # 7. 链表删除节点
    def remove(self, item):
        """
        删除指定的节点
        实例化游标，遍历链表插件这个节点是否存在，存在则更改指向
        不存在，则不修改
        空链表情况
        头节点情况
        尾结点情况
        """
        # 实例化游标
        cur = self.head
        if self.is_empty():
            return None
        else:
            # 不为空，遍历链表，对比数据是否相等
            # 如果头节点是要删除的数据
            if cur.item == item:
                self.head=cur.next
                # 找出最后的节点，将最后的节点指向，删除后面的那个节点
                while cur.next != self.head:
                    cur = cur.next
                cur.next = cur.next
            else:
                pro = None
                while cur.next != self.head:
                    if cur.item == item:
                        if cur.item == item:
                            pro.next = cur.next
                            return True
                    else:
                        pro = cur
                        cur = cur.next
                if cur.item == item:
                    pro.next = self.head
            pass

    # 8. 查找节点是否存在
    def search(self, item):
        """
        查找该节点是否存在
        实例化游标，遍历所有的节点
        查看当前节点的数据是否和item 相等
        空链表
        头节点
        尾结点
        """
        # 实例化游标
        cur = self.head
        # 判断空链表
        if self.is_empty():
            return None
        else:
            # 不为空遍历整个链表
            if cur.item == item:
                return True
            else:
                while cur.next != self.head:
                    if cur.item == item:
                        return True
                    else:
                        cur = cur.next
                if cur.item == item:
                    return True
            pass

Test

# 程序的入口
if __name__ == "__main__":
    a = Linklist()
    a.add(400)
    a.add(300)
    a.add(200)
    a.add(100)
    # a.append(10)
    a.insert(4,6)
    # a.remove(6)
    print(a.length())  # 5
    a.travel()         # 100 200 300 400 6
    print(a.search(100)) # True
    pass

.

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!