Python玩转单链表——逆转单向链表pythonic版-低调大师

Python玩转单链表——逆转单向链表pythonic版

2018-03-25 537

[本文出自天外归云的博客园]

链表是由节点构成的，一个指针代表一个方向，如果一个构成链表的节点都只包含一个指针，那么这个链表就是单向链表。

单向链表中的节点不光有代表方向的指针变量，也有值变量。所以我们定义链表，就是要定义链表中的节点，对链表的操作最后也就是对节点的操作。

这些包含数据的节点们在一种指定的结构下连接起来，成为了一种数据结构——单向链表。以上是我对单向链表的理解。

以下是我用python3对单向链表这种数据结构的一种实现，其中我用到了生成器来完成逆转单向链表这一操作，非常pythonic啊！代码如下：

'''
    Python版单向链表-单向链表简称单链表
    单链表中所包含的基本操作：
    初始化
    创建
    链表生成器
    打印
    显示调用过程
    计算长度
    判空
    获取
    删除
    插入
    修改
    追加
    逆转单向链表
'''


class Node(object):
    # 节点初始化
    def __init__(self, value, p=None):
        self.value = value
        self.next = p


class LinkList(object):
    # 初始化单链表
    def __init__(self):
        self.head = None

    # 创建单链表
    def create(self, node_value_list):
        self.head = Node(node_value_list[0])
        p = self.head
        for i in node_value_list[1:]:
            p.next = Node(i)
            p = p.next

    # 生成单链表
    def generate(self):
        p = self.head
        while p != None:
            yield p.value
            p = p.next

    # 打印单链表
    def print(self):
        print([i for i in self.generate()])

    # 显示方法调用前后的单链表
    def show(func):
        def wrapper(self, *args):
            print("方法{func_name}执行前".format(func_name=func.__name__))
            self.print()
            print("方法{func_name}执行中".format(func_name=func.__name__))
            func(self, *args)
            print("方法{func_name}执行后".format(func_name=func.__name__))
            self.print()

        return wrapper

    # 获取单链表的长度
    def length(self):
        p = self.head
        length = 0
        while p != None:
            length += 1
            p = p.next
        return length

    # 判断单链表是否为空
    def is_null(self):
        return self.length() == 0

    # 获取单链表偏移位元素返回并打印其节点值
    # 支持顺序索引和逆序索引：0代表索引0位，-1代表倒数第一位，-2代表倒数第二位
    # 获取不存在的位返回None
    def get(self, offset):
        p = self.head
        index = 0
        length = self.length()
        if offset > length - 1:
            print(None)
            return None
        if offset < 0 and offset + length < 0:
            print(None)
            return None
        if offset < 0 and offset + length >= 0:
            offset = length + offset
        while index < length - 1 and index < offset:
            p = p.next
            index += 1
        print("获取索引{index}位节点-值为{value}".format(index=index, value=p.value))
        return p

    # 删除单链表偏移位元素并打印
    # 支持顺序索引和逆序索引：0代表索引0位，-1代表倒数第一位，-2代表倒数第二位
    # 删除不存在的位返回None
    @show
    def remove(self, offset):
        p = self.head
        length = self.length()
        index = 0
        if offset > length - 1:
            print(None)
            return None
        if offset == 0 or offset + length == 0:
            print("删除索引{index}位节点-值为{value}".format(index=index, value=self.head.value))
            self.head = p.next
            return None
        if offset < 0 and length + offset > 0:
            offset = length + offset
        while index < length - 1 and index < offset - 1:
            p = p.next
            index += 1
        print("删除索引{index}位节点-值为{value}".format(index=index + 1, value=p.next.value))
        p.next = p.next.next

    # 在指定index位插入节点-值为value
    # 什么是插入——在两个节点之间加入才叫插入
    # 所以在末尾插入的意思就是在索引倒数第二位和倒数第一位之间插入
    @show
    def insert(self, offset, value):
        length = self.length()
        # 如果偏移量对应的索引位不在链表对应索引位范围内-返回None
        if offset > length - 1 or offset + length < 0:
            return None
        if offset < 0:
            offset = offset + length
        node = Node(value)
        if offset == 0 or offset + length == 0:
            p = self.head
            self.head = node
            node.next = p
        else:
            previous_node = self.get(offset - 1)
            current_node = self.get(offset)
            previous_node.next = node
            node.next = current_node
        print("在索引{index}位插入节点-值为{value}".format(index=offset, value=value))

    # 在链表索引末位追加一个节点-值为value
    @show
    def append(self, value):
        last_node = self.get(self.length() - 1)
        last_node.next = Node(value)

    # 修改链表索引位节点值
    @show
    def modify(self, offset, value):
        self.get(offset).value = value

    # 逆向生成单向链表
    @show
    def reverse(self):
        # 将节点生成器转变为列表并逆序
        reverse_list = [i for i in self.generate()][::-1]
        self.head = Node(reverse_list[0])
        p = self.head
        for i in reverse_list[1:]:
            p.next = Node(i)
            p = p.next


if __name__ == '__main__':
    list = [1, 2, 33, 4, 55, 6, 76, 78]
    # 初始化链表
    link_list = LinkList()
    # 创建链表
    link_list.create(list)
    # 获取节点
    link_list.get(-1)
    # 删除节点
    link_list.remove(0)
    # 插入节点
    link_list.insert(-2, 0.2)
    # 末位追加节点
    link_list.append(3)
    # 修改节点值
    link_list.modify(-1, 666)
    # 逆转
    link_list.reverse()

微信关注我们

原文链接：https://yq.aliyun.com/articles/575669

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

py查找第三方库安装的位置

python 以keras为例： import keras print(keras.__file__)

2018-03-26

604

在上一篇文章中，我们主要介绍了javaScript的变量、对象，这一篇的内容我们主要学习JavaScript的条件判断、循环、break和continue语句。条件判断： if 语句- 只有当指定条件为 true 时，使用该语句来执行代码 if...else 语句- 当条件为 true 时执行代码，当条件为 false 时执行其他代码 if...else if....else 语句- 使用该语句来选择多个代码块之一来执行 switch 语句- 使用该语句来选择多个代码块之一来执行这个条件判断语法跟Java的条件判断语法几乎一样，判断条件初体验 default 关键词来规定匹配不存在时所执行的事情循环： JavaScript的循环有两种，一种是for循环，通过初始条件、结束条件和递增条件来循环执行语句块；还有一种是while循环，while循环只有一个判断条件，条件满足，就不断循环，条件不满足时则退出循环。 for循环： for循环初体验我们简单的分析下上面的代码：（document.write 是写入网页的意思，br标签是换行的意思）首先：i = 0 这是初始条件，将变量...

2018-03-26

716

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。