[파이썬 학습] 단방향 순환 연결 리스트의 Python 구문 구현

이전 연구에서는 연결 목록 구현을 C 언어로 작성했습니다. 오늘은 Python으로 단방향 순환 연결 목록을 작성하는 방법을 배우도록 하겠습니다.

연결된 목록

연결된 목록은 일반적인 기본 데이터 구조입니다. 그러나 순차 목록처럼 연속적으로 데이터를 저장하지 않습니다. 노드의 위치 정보(즉, 주소)입니다.

Python

                      단방향 순환 연결 목록

단일 연결 목록의 변형은 연결 목록의 마지막 노드의 다음 필드가 더 이상 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__ == &#39;__main__&#39;:
    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 구문 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!