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
刚好实现了目标需求。
总结
今天的内容还是比较基础，也没什么难点。但是看懂和会写还是两码事，没事的时候写写这样的代码还是很有收获的。
相关推荐
-
Python数据结构之翻转链表
翻转一个链表 样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null 一种比较简单的方法是用"摘除法".就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点. 那样例来说,步骤是这样的: 1. 新建空节点:None 2. 1->None 3. 2->1->None 4. 3->2->1->None 代码就非常简单了: """
-
python单链表实现代码实例
链表的定义:链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址.由于每个结点都包含了可以链接起来的地址信息,所以用一个变量就能够访问整个结点序列.也就是说,结点包含两部分信息:一部分用于存储数据元素的值,称为信息域:另一部分用于存储下一个数据元素地址的指针,称为指针域.链表中的第一个结点的地址存储在一个单独的结点中,称为头结点或首结点.链表中的最后一个结点没有后继元素,其指针域为空. python单链表实现代码: 复制代码
-
Python单链表的简单实现方法
本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置 具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.
-
python数据结构之链表的实例讲解
在程序中,经常需要将⼀组(通常是同为某个类型的)数据元素作为整体 管理和使⽤,需要创建这种元素组,⽤变量记录它们,传进传出函数等. ⼀组数据中包含的元素个数可能发⽣变化(可以增加或删除元素). 对于这种需求,最简单的解决⽅案便是将这样⼀组元素看成⼀个序列,⽤ 元素在序列⾥的位置和顺序,表示实际应⽤中的某种有意义的信息,或者 表示数据之间的某种关系. 这样的⼀组序列元素的组织形式,我们可以将其抽象为线性表.⼀个线性 表是某类元素的⼀个集合,还记录着元素之间的⼀种顺序关系.线性表是 最基本的数据结构
-
python双向链表实现实例代码
示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(object): def __init__(self): self.he
-
python数据结构链表之单向链表(实例讲解)
单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i
-
Python 数据结构之旋转链表
题目描述:给定一个链表,旋转链表,使得每个节点向右移动k个位置,其中k是一个非负数 样例:给出链表1->2->3->4->5->null和k=2:返回4->5->1->2->3->null 首先,观察一下这个题目要达到的目的,其实,换一种说法,可以这样来描述:给出一个k值,将链表从倒数第k个节点处起之后的部分移动到链表前面,就样例来说,其实是将4->5这一部分移动到整个链表前面,变成4->5->1->2->3->
-
Python实现的数据结构与算法之链表详解
本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin
-
Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】
本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表
-
Python二叉搜索树与双向链表转换实现方法
本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.