发布于 2018-02-14 07:58:48 | 29 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的Python3 官方中文指南,程序狗速度看过来!

Python编程语言

Python 是一种面向对象、解释型计算机程序设计语言,由Guido van Rossum于1989年底发明,第一个公开发行版发行于1991年。Python语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是C/C++)很轻松地联结在一起。


链表是计算机科学里面应用最广泛的数据结构之一。这篇文章主要介绍了使用python实现链表操作,需要的朋友可以参考下

一、概念梳理

链表是计算机科学里面应用应用最广泛的数据结构之一。它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧、环形缓冲和队列)

简单的说,一个列表就是单数据通过索引集合在一起。在C里面这叫做指针。比方说,一个数据元素可以由地址元素,地理元素、路由信息活着交易细节等等组成。但是链表里面的元素类型都是一样的,是一种特殊的列表。

一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储在内存当中,相反,你可以通过一个节点指向另外一个节点的指针在内存不同的地方找到这些元素。列表最后一项习惯用NIL表示,相当于python里面的None

这里介绍两种不同的列表——单链表和双链表。双链表中的某个节点只会指向列表中的下一个元素,但是在双链表里面,当前节点同时也会指向前一个节点。所以双链表会占用更多的内存,因为它需要额外的变量去存储索引

图一、单链表

图2:双链表

单链表可以从头到尾顺序查询,但是反过来就不是那么容易了。然而,双链表不管你是从哪个节点开始,从任意方向查询都是一样的。在单链表中增加和删除节点只需要两步,但是在双链表里就需要四步了。

但是在python里面没有提供像双链表一样的数据结构,所以我们可以自己创建一个这样的数据结构

二、如果使用python创建链表

(1).将节点定义成一个数据结构

首先我们将节点类定义成ListNode,该类在初始化实例对象时,定义了两个实例变量,其中data用来存储节点的值,next用来存储下一个节点的索引,下面详细介绍一下一个节点要定义的方法和属性


__init__():初始化节点
self.data:存储节点的值
self.next:存储指向下一个节点的索引
has_value():将当前节点值和其他的值比较

上面的方法和属性涵盖了一个节点应有的基本属性和行为

Listing1:The ListNode class

上面创建了最简单的节点类,下面初始化ListNode的对象

Listing2:初始化节点

上面创建了三个独立的节点

(2)创建一个单链表类

现在我们定义一个名为SingleLinkedList的类去管理我们的节点,它包含了下面这些方法:


__init__():初始化对象
list_length():返回节点数量
output_list():输出节点值
add_list_item():在列表末尾增加一个新的节点
unordered_search():根据一个特殊值去查询列表
remove_list_item_by_id():根据节点id移除节点

下面一一讲解这些方法

__init__()定义了head和tail,都初始化为None

Listing3:The SingleLinkedList class(part one)

 

(3)、添加节点

通过add_list_item()添加列表元素。先检测是不是ListNode的实例,如果不是,就新建一个节点。如果列表还是空的话,就把该节点当作头节点,如果不是空,就将当前节点指向下一个元素(也就是刚新添加的节点)。把新节点添加到列表当中

Listing4:The SinglelinkedList class(part two)

list_length()方法计算节点数量,返回列表的长度。在一个循环当中循环列表,self.next依次指向下一个节点

Listing5:The SingleLinkedList class(part three)

output_list()用来输出新的节点值

Listing6:The SingleLinkedList class(part four)

下面我们初始化SingleLinkedList的实例track,然后创建4个节点。

(4)查询列表

查询整个列表使用unordered_search()。它需要使用一个额外的参数帮助查询。列表的头是切入点。

(5)、从列表中移除一个元素

从列表中移除一个节点 时,指向该节点索引需要被移动到,被移除节点的下一个节点。被移除的节点会由python的垃圾回收机制清除

Listing10:Removing a node by node number

 

(6)、创建一个双链表

创建双链表其实就是在ListNode的基础上,在创建一个previous的属性

Listing11:Extended list node class

然后我们就可以依据上面的定义新建一个双链表类

添加新的节点跟单链表有所不同

移除双链表中的节点

python实际运用

输出结果

 

(7)、使用队列实现双向列表



相关阅读 :
使用python实现链表操作
Python 实现链表实例代码
使用Python实现BT种子和磁力链接的相互转换
浅谈Python单向链表的实现
使用python实现拉钩网上的FizzBuzzWhizz问题示例
python双向链表示例代码
使用python实现baidu hi自动登录的代码
使用Python实现下载网易云音乐的高清MV的代码
使用python实现正则匹配检索远端FTP目录下的文件
使用Python实现一个简单的项目监控示例
使用python实现strcmp函数功能示例
菜鸟使用python实现正则检测密码合法性
最新网友评论  共有(0)条评论 发布评论 返回顶部
月排行榜

Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务