Python에서 단방향 순환 연결 목록을 구현하는 방법

단방향 순환 연결 리스트

모든 것을 하나로 연결합니다. 각 노드는 데이터 저장 영역과 링크 영역으로 구분되며, 링크 영역은 다음 노드에 연결됩니다.

항목: 데이터를 저장하려면
next : 다음 노드에 연결
참고: 단방향 순환 연결 목록은 첫 번째 링크입니다. 즉, 꼬리 노드가 헤드 노드에 연결되어야 합니다

단방향 연결 목록 작업

1. 연결리스트가 비어 있는지 여부
2. 연결리스트의 길이
3. 연결리스트 탐색
4. 연결리스트의 선두에 요소 추가
5.
6. 연결리스트의 지정된 위치에 요소를 추가합니다
7. 연결리스트에서 노드를 삭제합니다
8. 노드가 존재하는지 확인합니다

코드 구현

# 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

테스트 실행

# 程序的入口
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

위 내용은 Python에서 단방향 순환 연결 목록을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!