欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

单向循环链表的操作

程序员文章站 2022-04-09 16:21:26
# 创建节点类class Node(): def __init__(self, elem): self.elem = elem self.next = None# 创建单向循环链表类class SingleCycleLinkList(): """单向循环链表""" def __init__(self): self.__head = None # 创建指针并私有化 def is_empty(self):...
# 创建节点类
class Node():
    def __init__(self, elem):
        self.elem = elem
        self.next = None


# 创建单向循环链表类
class SingleCycleLinkList():
    """单向循环链表"""

    def __init__(self):
        self.__head = None  # 创建指针并私有化

    def is_empty(self):
        """链表是否为空"""
        return self.__head is None

    def length(self):
        """链表长度"""
        # 1.如果循环链表的长度为空,返回0
        if self.is_empty():
            return 0
        # 2.如果循环链表的长度不为空
        cur = self.__head  # 创建指针指向第一个节点
        count = 1  # 创建计数器默认从1开始
        while cur.next != self.__head:  # 不断循环,移动指针,计数器同时加1
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍历整个链表"""
        # 1.如果循环链表的长度为空
        if self.is_empty():
            print()
        # 2.如果循环链表的长度不为空
        else:
            cur = self.__head  # 创建指针cur指向第一个节点
            while cur.next != self.__head:  # 不断循环,移动指针,打印所有节点元素
                print(cur.elem, end=" ")
                cur = cur.next
            # 跳出循环后,在打印最后一个元素
            print(cur.elem)

    def add(self, item):
        """链表头部添加元素"""
        # 1.创建节点
        node = Node(item)
        # 2.如果循环链表的长度为空
        if self.is_empty():
            self.__head = node
            node.next = node
        # 3.如果循环链表的长度不为空
        else:

            # 3.1 把新节点的next指向到原始链表的第一个节点
            node.next = self.__head
            # 3.2 把原始链表的最后一个节点的next指向到新的节点
            cur = self.__head  # 创建指针cur指向原始链表第一个节点
            while cur.next != self.__head:
                cur = cur.next
            # 3.3 跳出循环时,指针就是在最后一个节点,然后让最后一个节点指向新的节点
            cur.next = node
            # 3.4 再把self.__head指向新的node
            self.__head = node

    def append(self, item):
        """链表尾部添加元素"""
        # 1.创建item的节点
        node = Node(item)
        # 2.判断当前链表是否为空
        if self.is_empty():
            # 为空的话就直接把self.__head指向到node
            self.__head = node
            # 在把node节点的next指向它自己
            node.next = node
        else:
            # 不为空
            # 先把新节点的next指向到第一个节点
            node.next = self.__head

            # 再找到当前链表的最后一个节点
            cur = self.__head  # 创建指针cur指向第一个节点
            while cur.next != self.__head:
                # while循环,不断地移动指针,直到最后一个节点为止
                cur = cur.next
            # 跳出循环后,指针cur指的就是最后一个节点
            # 把最后一个节点的next指向到新的node节点
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素"""
        # 1.创建节点
        node = Node(item)
        # 2.如果pos<=0,直接调用开头插入方法
        if pos <= 0:
            self.add(item)
        # 如果pos>链表长度,直接调用尾部追加方法
        elif pos > self.length():
            self.append(item)
        # 如果在中间插入
        else:
            cur = self.__head  # 创建指针cur指向第一个节点
            count = 0  # 创建计数器
            # 循环到pos前面位置的一个节点
            while count < pos - 1:
                count += 1
                cur = cur.next
            # 先把新节点的next指向到cur的next
            node.next = cur.next
            # 然后把cur的next指向新节点
            cur.next = node

    def remove(self, item):
        """删除节点"""
        # 1.判断循环链表是否为空,为空返回False
        if self.is_empty():
            return False
        # 2.不为空
        # 定义两个指针,cur指向第一个节点,pre指向None
        cur = self.__head
        pre = None

        # 循环链表,查找要删除的元素
        while cur.next != self.__head:
            # 找到元素
            if cur.elem == item:
                # 如果第一个节点就是要找的元素
                if cur == self.__head:
                    # 要再次创建循环查找到最后一个节点,
                    # 然后指向到第一个节点的next,也就是cur.next
                    sec = self.__head  # 定义一个指针sec,去循环
                    while sec.next != self.__head:
                        sec = sec.next
                    sec.next = cur.next
                    # 把self._head 指向到 cur.next
                    self.__head = cur.next
                # 如果要删除的元素在中间
                else:
                    pre.next = cur.next
                return
            # 循环里如果没找到要删除的元素
            else:
                pre = cur
                cur = cur.next
        # 如果要删除的元素是最后一个节点
        # 跳出循环后进行判断
        if cur.elem == item:
            # 判断当前链表是否只有一个节点
            # 如果只有一个
            if self.length() == 1:
                self.__head = None

            else:
                pre.next = self.__head
        # 没有找到要删除的元素
        else:
            return False

    def search(self, item):
        """查找节点是否存在"""
        #  1.如果循环链表的长度为空,返回False
        if self.is_empty():
            return False
        else:
            cur = self.__head  # 创建指针指向第一个节点
            # 不断循环,判断当前的节点的元素是否是要查找的元素
            # 如果是就返回True,如果不是,继续移动指针
            while cur.next != self.__head:
                # 如果指针所在节点和要查找的元素相同,返回True
                if cur.elem == item:
                    return True
                else:
                    cur = cur.next
            # 如果找的是最后一个元素,那么需要在跳出循环之后再次判断
            # 是否是要查找的元素
            if cur.elem == item:
                return True
            return False


if __name__ == '__main__':
    s = SingleCycleLinkList()

    # 访问类的私有属性,不建议这么用
    # print(s._SingleLinkList__head)

    print(s.search(20))
    print(s.length())
    s.add(500)
    s.travel()
    print(s.remove(100))
    s.travel()
    print('-----------')
    s.append(10)
    s.append(20)
    s.add(100)
    s.travel()  # 100 500 10 20
    print(s.length())
    s.append(30)
    s.add(200)  # 200 100 500 10 20 30
    s.travel()

    s.insert(2, 60)  # 200 100 60 500 10 20 30
    s.travel()
    s.insert(100, 120)
    s.travel()
    print("问题所在地")
    print(s.search(500))
    print(s.search(120))
    print(s.search(300))
    s.remove(10)
    print('=========')
    s.travel()
    s.remove(200)
    s.travel()
    s.remove(120)
    s.travel()

下面是单向链表的操作,可以对比着看,找寻其中的差别,更利于学习

单向链表的操作

本文地址:https://blog.csdn.net/weixin_47744974/article/details/114004784