Python实现环形链表

本文实例为大家分享了Python实现环形链表的具体代码,供大家参考,具体内容如下

我们将单向链表的最后一个节点的指针指向链表的头部(第一个节点),那么就形成了一个环形链表。环形节点可以从任意节点开始遍历其他的节点。

这里主要实现了环形链表节点的遍历、添加、插入、删除,反转。

代码如下:

class Player:
    """节点类"""
    def __init__(self):
        """初始化姓名,分数,指针"""
        self.name = ''
        self.score = 0
        self.next = None
 
 
def ergodic(head, num=None, is_print=False):
    """遍历函数,num是遍历到哪一个位置序号,is_print是否触发打印方法"""
    if head.next is None:
        return None
    ptr = head
    count = 0
    while True:
        count += 1
        if is_print:
            print('No.'+str(count), ptr.name, ptr.score, '--->', ptr.next.name)
        if count == num:
            break
        if ptr.next == head:
            break
        ptr = ptr.next
    return ptr  # 返回遍历完成后的最后一个节点
 
 
def invert(x):  # x是链表的第一个节点
    """反转环形链表"""
    y = x.next  # y是x原来的next
    x.next = ergodic(x)  # 将第一个节点的next指向最后一个节点(因为反转了)
    while True:  # 循环反转后面的所有节点
        r = y.next
        y.next = x
        if r == head:  # r是head说明y已经是原本链表的最后一个节点了
            return y  # 返回y,这个y是反转后的链表的第一个节点
        x = y
        y = r
 
 
head = Player()
ptr = head
 
 
while True:
    select = input("(1).新增   (2).查看   (3).插入   (4).删除   (5).反转   (6).离开\n输入:")
    if select == "1":  # 新增节点
        ptr = ergodic(head)  # 获取当前链表最后一个节点
        if ptr is None:  # ptr为None说明当前在添加第一个节点head
            head.name = input("姓名:")
            head.score = input("分数:")
            head.next = head
        else:  # 添加第一个节点之后的节点
            next_data = Player()
            next_data.name = input("姓名:")
            next_data.score = input("分数:")
            next_data.next = head
            ptr.next = next_data
 
    elif select == "2":  # 遍历查看链表所有节点
        ergodic(head, is_print=True)  # 遍历链表,将打印参数设为True
 
    elif select == '3':  # 向链表中任意位置插入节点,位置以序号表示,即第一个节点序号为1,第二个节点序号为2,以此类推
        try:
            num = int(input("请输入需要插入的节点位置序号:"))  # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则插入到最后一个节点之后
            if num < 1:
                print("输入必须为大于0的正整数")
                continue
        except ValueError:
            print("输入有误")
            continue
        ptr = ergodic(head, num-1)  # 获取需要插入位置的前一个节点
        insert_data = Player()
        insert_data.name = input("姓名:")
        insert_data.score = input("分数:")
        insert_data.next = ptr.next
        ptr.next = insert_data
        if num == 1:  # 如果插入位置是1的话,那么head将发生变化
            head = insert_data
 
    elif select == '4':  # 删除链表中任意位置的节点
        try:
            num = int(input("请输入需要删除的节点位置序号:"))  # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则删除最后一个节点
            if num < 1:
                print("输入必须为大于0的正整数")
                continue
        except ValueError:
            print("输入有误")
            continue
        ptr = ergodic(head, num - 1)  # 获取需要删除位置的前一个节点
        if ptr == ergodic(head, num):  # 输入序号过大时需要做特殊处理,因为输入序号过大也代表删除最后一个节点,那么这时我需要获取这最后一个节点的前一个节点
            ptr = ergodic(ptr)
        ptr.next = ptr.next.next
        if num == 1:  # 如果删除位置是1的话,那么head将发生变化
            head = ptr.next
 
    elif select == '5':  # 反转链表
        new_first = invert(head)  # 获取新的第一个节点
        head = new_first  # head指向新的第一个节点
        print('成功反转')
 
    elif select == '6':
        print("成功离开")
        break
    else:
        print("输入错误,请重试")

部分运行结果如下:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python实现的数据结构与算法之链表详解

    本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin

  • 浅谈Python单向链表的实现

    链表由一系列不必在内存中相连的结构构成,这些对象按线性顺序排序.每个结构含有表元素和指向后继元素的指针.最后一个单元的指针指向NULL.为了方便链表的删除与插入操作,可以为链表添加一个表头. 删除操作可以通过修改一个指针来实现. 插入操作需要执行两次指针调整. 1. 单向链表的实现 1.1 Node实现 每个Node分为两部分.一部分含有链表的元素,可以称为数据域:另一部分为一指针,指向下一个Node. class Node(): __slots__=['_item','_next'] #限定N

  • Python数据结构与算法之列表(链表,linked list)简单实现

    Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

  • Python单链表的简单实现方法

    本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置 具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.

  • Python3实现的判断环形链表算法示例

    本文实例讲述了Python3实现的判断环形链表算法.分享给大家供大家参考,具体如下: 给定一个链表,判断链表中是否有环. 方案一:快慢指针遍历,若出现相等的情况,说明有环 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self,

  • python单链表实现代码实例

    链表的定义:链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址.由于每个结点都包含了可以链接起来的地址信息,所以用一个变量就能够访问整个结点序列.也就是说,结点包含两部分信息:一部分用于存储数据元素的值,称为信息域:另一部分用于存储下一个数据元素地址的指针,称为指针域.链表中的第一个结点的地址存储在一个单独的结点中,称为头结点或首结点.链表中的最后一个结点没有后继元素,其指针域为空. python单链表实现代码: 复制代码

  • Python实现针对给定单链表删除指定节点的方法

    本文实例讲述了Python实现针对给定单链表删除指定节点的方法.分享给大家供大家参考,具体如下: 题目: 初始化定义一个单链表,删除指定节点,输出链表 下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:给定一个单链表删除指定节点 ''' class Node(object): ''''' 节点类 ''' def __init__(self,data): self.num=data self.next=N

  • Python 实现链表实例代码

    Python 实现链表实例代码 前言 算法和数据结构是一个亘古不变的话题,作为一个程序员,掌握常用的数据结构实现是非常非常的有必要的. 实现清单 实现链表,本质上和语言是无关的.但是灵活度却和实现它的语言密切相关.今天用Python来实现一下,包含如下操作: ['addNode(self, data)'] ['append(self, value)'] ['prepend(self, value)'] ['insert(self, index, value)'] ['delNode(self,

  • 使用python实现链表操作

    一.概念梳理 链表是计算机科学里面应用应用最广泛的数据结构之一.它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧.环形缓冲和队列) 简单的说,一个列表就是单数据通过索引集合在一起.在C里面这叫做指针.比方说,一个数据元素可以由地址元素,地理元素.路由信息活着交易细节等等组成.但是链表里面的元素类型都是一样的,是一种特殊的列表. 一个单独的列表元素叫做一个节点.这些节点不像数组一样都按顺序存储在内存当中,相反,你可以通过一个节点指向另外一个节点的指针在内存不同的地方找到这些元素.列表最

  • python双向链表实现实例代码

    示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object):    def __init__(self,val,p=0):        self.data = val        self.next = p        self.prev = p class LinkList(object):    def __init__(self):        self.he

随机推荐