博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
python实现链表
阅读量:5869 次
发布时间:2019-06-19

本文共 3666 字,大约阅读时间需要 12 分钟。

 

 

数据结构是计算机科学必须掌握的一门学问,之前很多的教材都是用C语言实现链表,因为c有指针,可以很方便的控制内存,很方便就实现链表,其他的语言,则没那么方便,有很多都是用模拟链表,不过这次,我不是用模拟链表来实现,因为python是动态语言,可以直接把对象赋值给新的变量。

好了,在说我用python实现前,先简单说说链表吧。在我们存储一大波数据时,我们很多时候是使用数组,但是当我们执行插入操作的时候就是非常麻烦,看下面的例子,有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组,我们会怎么做?当然是将5之后的数据往后退一位,然后再插入4,这样非常麻烦,但是如果用链表,我就直接在3和5之间插入4就行,听着就很方便。

那么链表的结构是怎么样的呢?顾名思义,链表当然像锁链一样,由一节节节点连在一起,组成一条数据链。

链表的节点的结构如下:

data next

data为自定义的数据,next为下一个节点的地址。

链表的结构为,head保存首位节点的地址:

接下来我们来用python实现链表

python实现链表

首先,定义节点类Node:

class Node:    '''    data: 节点保存的数据    _next: 保存下一个节点对象    '''    def __init__(self, data, pnext=None):        self.data = data        self._next = pnext    def __repr__(self):        '''         用来定义Node的字符输出,        print为输出data         '''        return str(self.data)

然后,定义链表类:

链表要包括:

属性:

链表头:head

链表长度:length

方法:

判断是否为空: isEmpty()

def isEmpty(self):    return (self.length == 0

增加一个节点(在链表尾添加): append()

def append(self, dataOrNode):    item = None    if isinstance(dataOrNode, Node):        item = dataOrNode    else:        item = Node(dataOrNode)    if not self.head:        self.head = item        self.length += 1    else:        node = self.head        while node._next:            node = node._next        node._next = item        self.length += 1

删除一个节点: delete()

#删除一个节点之后记得要把链表长度减一def delete(self, index):    if self.isEmpty():        print "this chain table is empty."        return    if index < 0 or index >= self.length:        print 'error: out of index'        return    #要注意删除第一个节点的情况    #如果有空的头节点就不用这样    #但是我不喜欢弄头节点    if index == 0:        self.head = self.head._next        self.length -= 1        return    #prev为保存前导节点    #node为保存当前节点    #当j与index相等时就    #相当于找到要删除的节点    j = 0    node = self.head    prev = self.head    while node._next and j < index:        prev = node        node = node._next        j += 1    if j == index:        prev._next = node._next        self.length -= 1

修改一个节点: update()

def update(self, index, data):    if self.isEmpty() or index < 0 or index >= self.length:        print 'error: out of index'        return    j = 0    node = self.head    while node._next and j < index:        node = node._next        j += 1    if j == index:        node.data = data

查找一个节点: getItem()

def getItem(self, index):    if self.isEmpty() or index < 0 or index >= self.length:        print "error: out of index"        return    j = 0    node = self.head    while node._next and j < index:        node = node._next        j += 1    return node.data

查找一个节点的索引: getIndex()

def getIndex(self, data):    j = 0    if self.isEmpty():        print "this chain table is empty"        return    node = self.head    while node:        if node.data == data:            return j        node = node._next        j += 1    if j == self.length:        print "%s not found" % str(data)        return

插入一个节点: insert()

def insert(self, index, dataOrNode):    if self.isEmpty():        print "this chain tabale is empty"        return    if index < 0 or index >= self.length:        print "error: out of index"        return    item = None    if isinstance(dataOrNode, Node):        item = dataOrNode    else:        item = Node(dataOrNode)    if index == 0:        item._next = self.head        self.head = item        self.length += 1        return    j = 0    node = self.head    prev = self.head    while node._next and j < index:        prev = node        node = node._next        j += 1    if j == index:        item._next = node        prev._next = item        self.length += 1

清空链表: clear()

def clear(self):    self.head = None    self.length = 0

以上就是链表类的要实现的方法。

执行的结果:

接下来是完整代码:

 
python链表

 


 

作者:陈栋权

时间:2016/09/19

转载于:https://www.cnblogs.com/xc1234/p/8611344.html

你可能感兴趣的文章
我的友情链接
查看>>
rpm软件包安装
查看>>
JAVA中判断一个字符串是否包含另一个字符串
查看>>
org.eclipse.birt.report.exception.ViewerException: 没有可用的报表设计对象.
查看>>
linux通过mail命令发送到外部邮件
查看>>
BGP的社团属性
查看>>
JS获取服务上下文,兼容上下文为空场景
查看>>
实现简单的字符串队列
查看>>
AF_INET是什么?
查看>>
我的友情链接
查看>>
ALSA音频工具amixer,aplay,arecord
查看>>
TCC-Transaction TCC 实现
查看>>
Neo4j HA环境配置
查看>>
你可以不成功,但是不能不成长-----杨澜
查看>>
学习笔记 十八: kickstart
查看>>
COM多线程原理与应用
查看>>
zabbix监控iptables防火墙状态之是否有丢弃的包(攻-击)
查看>>
SFB 项目经验-82-Active Directory Replication Status
查看>>
技术随笔八——仰望夜空 仰望Git
查看>>
gfirefly 框架分析
查看>>