这里有新鲜出炉的Python3 官方中文指南,程序狗速度看过来!
Python 是一种面向对象、解释型计算机程序设计语言,由Guido van Rossum于1989年底发明,第一个公开发行版发行于1991年。Python语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是C/C++)很轻松地联结在一起。
这篇文章主要为大家详细介绍了python数据结构之链表的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
数据结构是计算机科学必须掌握的一门学问,之前很多的教材都是用C语言实现链表,因为c有指针,可以很方便的控制内存,很方便就实现链表,其他的语言,则没那么方便,有很多都是用模拟链表,不过这次,我不是用模拟链表来实现,因为python是动态语言,可以直接把对象赋值给新的变量。
好了,在说我用python实现前,先简单说说链表吧。在我们存储一大波数据时,我们很多时候是使用数组,但是当我们执行插入操作的时候就是非常麻烦,看下面的例子,有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组,我们会怎么做?当然是将5之后的数据往后退一位,然后再插入4,这样非常麻烦,但是如果用链表,我就直接在3和5之间插入4就行,听着就很方便。
那么链表的结构是怎么样的呢?顾名思义,链表当然像锁链一样,由一节节节点连在一起,组成一条数据链。
链表的节点的结构如下:
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
以上就是链表类的要实现的方法。
执行的结果:
接下来是完整代码:
- # -*- coding:utf8 -*-
- #/usr/bin/env python
- class Node(object):
- def __init__(self, data, pnext = None):
- self.data = data
- self._next = pnext
- def __repr__(self):
- return str(self.data)
- class ChainTable(object):
- def __init__(self):
- self.head = None
- self.length = 0
- def isEmpty(self):
- return (self.length == 0)
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- def clear(self):
- self.head = None
- self.length = 0
- def __repr__(self):
- if self.isEmpty():
- return "empty chain table"
- node = self.head
- nlist = ''
- while node:
- nlist += str(node.data) + ' '
- node = node._next
- return nlist
- def __getitem__(self, ind):
- if self.isEmpty() or ind < 0 or ind >= self.length:
- print "error: out of index"
- return
- return self.getItem(ind)
- def __setitem__(self, ind, val):
- if self.isEmpty() or ind < 0 or ind >= self.length:
- print "error: out of index"
- return
- self.update(ind, val)
- def __len__(self):
- return self.length
来源: http://www.phperz.com/article/17/1028/350889.html