这里有新鲜出炉的 Python 入门,程序狗速度看过来!
Python 是一种面向对象、解释型计算机程序设计语言,由 Guido van Rossum 于 1989 年底发明,第一个公开发行版发行于 1991 年。Python 语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是 C/C++)很轻松地联结在一起。
这篇文章主要介绍了 Python 实现链表实例代码的相关资料, 需要的朋友可以参考下
Python 实现链表实例代码
前言
算法和数据结构是一个亘古不变的话题,作为一个程序员,掌握常用的数据结构实现是非常非常的有必要的。
实现清单
实现链表,本质上和语言是无关的。但是灵活度却和实现它的语言密切相关。今天用 Python 来实现一下,包含如下操作:
- ['addNode(self, data)']
- ['append(self, value)']
- ['prepend(self, value)']
- ['insert(self, index, value)']
- ['delNode(self, index)']
- ['delValue(self, value)']
- ['isempty(self)']
- ['truncate(self)']
- ['getvalue(self, index)']
- ['peek(self)']
- ['pop(self)']
- ['reverse(self)']
- ['delDuplecate(self)']
- ['updateNode(self, index, value)']
- ['size(self)']
- ['print(self)']
生成这样的一个方法清单肯定是不能手动写了,要不然得多麻烦啊,于是我写了个程序,来匹配这些自己实现的方法。代码比较简单,核心思路就是匹配源文件的每一行,找到符合匹配规则的内容,并添加到总的结果集中。
代码如下:
- # coding: utf8
- # @Author: 郭 璞
- # @File: getmethods.py
- # @Time: 2017/4/5
- # @Contact: 1064319632@qq.com
- # @blog: http://blog.csdn.net/marksinoberg
- # @Description: 获取一个模块或者类中的所有方法及参数列表
- import re
- def parse(filepath, repattern):
- with open(filepath, 'rb') as f:
- lines = f.readlines()
- # 预解析正则
- rep = re.compile(repattern)
- # 创建保存方法和参数列表的结果集列表
- result = []
- # 开始正式的匹配实现
- for line in lines:
- res = re.findall(rep, str(line))
- print("{}的匹配结果{}".format(str(line), res))
- if len(res)!=0 or res is not None:
- result.append(res)
- else:
- continue
- return [item for item in result if item !=[]]
- if __name__ == '__main__':
- repattern = "def (.[^_0-9]+\(.*?\)):"
- filepath = './SingleChain.py'
- result = parse(filepath, repattern)
- for item in result:
- print(str(item))
链表实现
- # coding: utf8
- # @Author: 郭 璞
- # @File: SingleChain.py
- # @Time: 2017/4/5
- # @Contact: 1064319632@qq.com
- # @blog: http://blog.csdn.net/marksinoberg
- # @Description: 单链表实现
- class Node(object):
- def __init__(self, data, next):
- self.data = data
- self.next = next
- class LianBiao(object):
- def __init__(self):
- self.root = None
- # 给单链表添加元素节点
- def addNode(self, data):
- if self.root==None:
- self.root = Node(data=data, next=None)
- return self.root
- else:
- # 有头结点,则需要遍历到尾部节点,进行链表增加操作
- cursor = self.root
- while cursor.next!= None:
- cursor = cursor.next
- cursor.next = Node(data=data, next=None)
- return self.root
- # 在链表的尾部添加新节点,底层调用addNode方法即可
- def append(self, value):
- self.addNode(data=value)
- # 在链表首部添加节点
- def prepend(self, value):
- if self.root == None:
- self.root = Node(value, None)
- else:
- newroot = Node(value, None)
- # 更新root索引
- newroot.next = self.root
- self.root = newroot
- # 在链表的指定位置添加节点
- def insert(self, index, value):
- if self.root == None:
- return
- if index<=0 or index >self.size():
- print('index %d 非法, 应该审视一下您的插入节点在整个链表的位置!')
- return
- elif index==1:
- # 如果index==1, 则在链表首部添加即可
- self.prepend(value)
- elif index == self.size()+1:
- # 如果index正好比当前链表长度大一,则添加在尾部即可
- self.append(value)
- else:
- # 如此,在链表中部添加新节点,直接进行添加即可。需要使用计数器来维护插入未知
- counter = 2
- pre = self.root
- cursor = self.root.next
- while cursor!=None:
- if counter == index:
- temp = Node(value, None)
- pre.next = temp
- temp.next = cursor
- break
- else:
- counter += 1
- pre = cursor
- cursor = cursor.next
- # 删除指定位置上的节点
- def delNode(self, index):
- if self.root == None:
- return
- if index<=0 or index > self.size():
- return
- # 对第一个位置需要小心处理
- if index == 1:
- self.root = self.root.next
- else:
- pre = self.root
- cursor = pre.next
- counter = 2
- while cursor!= None:
- if index == counter:
- print('can be here!')
- pre.next = cursor.next
- break
- else:
- pre = cursor
- cursor = cursor.next
- counter += 1
- # 删除值为value的链表节点元素
- def delValue(self, value):
- if self.root == None:
- return
- # 对第一个位置需要小心处理
- if self.root.data == value:
- self.root = self.root.next
- else:
- pre = self.root
- cursor = pre.next
- while cursor!=None:
- if cursor.data == value:
- pre.next = cursor.next
- # 千万记得更新这个节点,否则会出现死循环。。。
- cursor = cursor.next
- continue
- else:
- pre = cursor
- cursor = cursor.next
- # 判断链表是否为空
- def isempty(self):
- if self.root == None or self.size()==0:
- return True
- else:
- return False
- # 删除链表及其内部所有元素
- def truncate(self):
- if self.root == None or self.size()==0:
- return
- else:
- cursor = self.root
- while cursor!= None:
- cursor.data = None
- cursor = cursor.next
- self.root = None
- cursor = None
- # 获取指定位置的节点的值
- def getvalue(self, index):
- if self.root is None or self.size()==0:
- print('当前链表为空!')
- return None
- if index<=0 or index>self.size():
- print("index %d不合法!"%index)
- return None
- else:
- counter = 1
- cursor = self.root
- while cursor is not None:
- if index == counter:
- return cursor.data
- else:
- counter += 1
- cursor = cursor.next
- # 获取链表尾部的值,且不删除该尾部节点
- def peek(self):
- return self.getvalue(self.size())
- # 获取链表尾部节点的值,并删除该尾部节点
- def pop(self):
- if self.root is None or self.size()==0:
- print('当前链表已经为空!')
- return None
- elif self.size()==1:
- top = self.root.data
- self.root = None
- return top
- else:
- pre = self.root
- cursor = pre.next
- while cursor.next is not None:
- pre = cursor
- cursor = cursor.next
- top = cursor.data
- cursor = None
- pre.next = None
- return top
- # 单链表逆序实现
- def reverse(self):
- if self.root is None:
- return
- if self.size()==1:
- return
- else:
- # post = None
- pre = None
- cursor = self.root
- while cursor is not None:
- # print('逆序操作逆序操作')
- post = cursor.next
- cursor.next = pre
- pre = cursor
- cursor = post
- # 千万不要忘记了把逆序后的头结点赋值给root,否则无法正确显示
- self.root = pre
- # 删除链表中的重复元素
- def delDuplecate(self):
- # 使用一个map来存放即可,类似于变形的"桶排序"
- dic = {}
- if self.root == None:
- return
- if self.size() == 1:
- return
- pre = self.root
- cursor = pre.next
- dic = {}
- # 为字典赋值
- temp = self.root
- while temp!=None:
- dic[str(temp.data)] = 0
- temp = temp.next
- temp = None
- # 开始实施删除重复元素的操作
- while cursor!=None:
- if dic[str(cursor.data)] == 1:
- pre.next = cursor.next
- cursor = cursor.next
- else:
- dic[str(cursor.data)] += 1
- pre = cursor
- cursor = cursor.next
- # 修改指定位置节点的值
- def updateNode(self, index, value):
- if self.root == None:
- return
- if index<0 or index>self.size():
- return
- if index == 1:
- self.root.data = value
- return
- else:
- cursor = self.root.next
- counter = 2
- while cursor!=None:
- if counter == index:
- cursor.data = value
- break
- cursor = cursor.next
- counter += 1
- # 获取单链表的大小
- def size(self):
- counter = 0
- if self.root == None:
- return counter
- else:
- cursor = self.root
- while cursor!=None:
- counter +=1
- cursor = cursor.next
- return counter
- # 打印链表自身元素
- def print(self):
- if(self.root==None):
- return
- else:
- cursor = self.root
- while cursor!=None:
- print(cursor.data, end='\t')
- cursor = cursor.next
- print()
- if __name__ == '__main__':
- # 创建一个链表对象
- lianbiao = LianBiao()
- # 判断当前链表是否为空
- print("链表为空%d"%lianbiao.isempty())
- # 判断当前链表是否为空
- lianbiao.addNode(1)
- print("链表为空%d"%lianbiao.isempty())
- # 添加一些节点,方便操作
- lianbiao.addNode(2)
- lianbiao.addNode(3)
- lianbiao.addNode(4)
- lianbiao.addNode(6)
- lianbiao.addNode(5)
- lianbiao.addNode(6)
- lianbiao.addNode(7)
- lianbiao.addNode(3)
- # 打印当前链表所有值
- print('打印当前链表所有值')
- lianbiao.print()
- # 测试对链表求size的操作
- print("链表的size: "+str(lianbiao.size()))
- # 测试指定位置节点值的获取
- print('测试指定位置节点值的获取')
- print(lianbiao.getvalue(1))
- print(lianbiao.getvalue(lianbiao.size()))
- print(lianbiao.getvalue(7))
- # 测试删除链表中指定值, 可重复性删除
- print('测试删除链表中指定值, 可重复性删除')
- lianbiao.delNode(4)
- lianbiao.print()
- lianbiao.delValue(3)
- lianbiao.print()
- # 去除链表中的重复元素
- print('去除链表中的重复元素')
- lianbiao.delDuplecate()
- lianbiao.print()
- # 指定位置的链表元素的更新测试
- print('指定位置的链表元素的更新测试')
- lianbiao.updateNode(6, 99)
- lianbiao.print()
- # 测试在链表首部添加节点
- print('测试在链表首部添加节点')
- lianbiao.prepend(77)
- lianbiao.prepend(108)
- lianbiao.print()
- # 测试在链表尾部添加节点
- print('测试在链表尾部添加节点')
- lianbiao.append(99)
- lianbiao.append(100)
- lianbiao.print()
- # 测试指定下标的插入操作
- print('测试指定下标的插入操作')
- lianbiao.insert(1, 10010)
- lianbiao.insert(3, 333)
- lianbiao.insert(lianbiao.size(), 99999)
- lianbiao.print()
- # 测试peek 操作
- print('测试peek 操作')
- print(lianbiao.peek())
- lianbiao.print()
- # 测试pop 操作
- print('测试pop 操作')
- print(lianbiao.pop())
- lianbiao.print()
- # 测试单链表的逆序输出
- print('测试单链表的逆序输出')
- lianbiao.reverse()
- lianbiao.print()
- # 测试链表的truncate操作
- print('测试链表的truncate操作')
- lianbiao.truncate()
- lianbiao.print()
代码运行的结果如何呢?是否能满足我们的需求,且看打印的结果:
D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py 链表为空1 链表为空0 打印当前链表所有值 1 2 3 4 6 5 6 7 3 链表的size: 9 测试指定位置节点值的获取 1 3 6 测试删除链表中指定值, 可重复性删除 can be here! 1 2 3 6 5 6 7 3 1 2 6 5 6 7 去除链表中的重复元素 1 2 6 5 7 指定位置的链表元素的更新测试 1 2 6 5 7 测试在链表首部添加节点 108 77 1 2 6 5 7 测试在链表尾部添加节点 108 77 1 2 6 5 7 99 100 测试指定下标的插入操作 10010 108 333 77 1 2 6 5 7 99 99999 100 测试peek 操作 100 10010 108 333 77 1 2 6 5 7 99 99999 100 测试pop 操作 100 10010 108 333 77 1 2 6 5 7 99 99999 测试单链表的逆序输出 99999 99 7 5 6 2 1 77 333 108 10010 测试链表的truncate操作 Process finished with exit code 0
刚好实现了目标需求。
总结
今天的内容还是比较基础,也没什么难点。但是看懂和会写还是两码事,没事的时候写写这样的代码还是很有收获的。
来源: http://www.phperz.com/article/17/0430/333844.html