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:获取一个模块或者类中的所有方法及参数列表
importre
defparse(filepath,repattern):
withopen(filepath,'rb')asf:
lines=f.readlines()
#预解析正则
rep=re.compile(repattern)
#创建保存方法和参数列表的结果集列表
result=[]
#开始正式的匹配实现
forlineinlines:
res=re.findall(rep,str(line))
print("{}的匹配结果{}".format(str(line),res))
iflen(res)!=0orresisnotNone:
result.append(res)
else:
continue
return[itemforiteminresultifitem!=[]]
if__name__=='__main__':
repattern="def(.[^_0-9]+\(.*?\)):"
filepath='./SingleChain.py'
result=parse(filepath,repattern)
foriteminresult:
print(str(item))
链表实现
#coding:utf8
#@Author:郭璞
#@File:SingleChain.py
#@Time:2017/4/5
#@Contact:1064319632@qq.com
#@blog:http://blog.csdn.net/marksinoberg
#@Description:单链表实现
classNode(object):
def__init__(self,data,next):
self.data=data
self.next=next
classLianBiao(object):
def__init__(self):
self.root=None
#给单链表添加元素节点
defaddNode(self,data):
ifself.root==None:
self.root=Node(data=data,next=None)
returnself.root
else:
#有头结点，则需要遍历到尾部节点，进行链表增加操作
cursor=self.root
whilecursor.next!=None:
cursor=cursor.next
cursor.next=Node(data=data,next=None)
returnself.root
#在链表的尾部添加新节点，底层调用addNode方法即可
defappend(self,value):
self.addNode(data=value)
#在链表首部添加节点
defprepend(self,value):
ifself.root==None:
self.root=Node(value,None)
else:
newroot=Node(value,None)
#更新root索引
newroot.next=self.root
self.root=newroot
#在链表的指定位置添加节点
definsert(self,index,value):
ifself.root==None:
return
ifindex<=0orindex>self.size():
print('index%d非法，应该审视一下您的插入节点在整个链表的位置！')
return
elifindex==1:
#如果index==1，则在链表首部添加即可
self.prepend(value)
elifindex==self.size()+1:
#如果index正好比当前链表长度大一，则添加在尾部即可
self.append(value)
else:
#如此，在链表中部添加新节点，直接进行添加即可。需要使用计数器来维护插入未知
counter=2
pre=self.root
cursor=self.root.next
whilecursor!=None:
ifcounter==index:
temp=Node(value,None)
pre.next=temp
temp.next=cursor
break
else:
counter+=1
pre=cursor
cursor=cursor.next
#删除指定位置上的节点
defdelNode(self,index):
ifself.root==None:
return
ifindex<=0orindex>self.size():
return
#对第一个位置需要小心处理
ifindex==1:
self.root=self.root.next
else:
pre=self.root
cursor=pre.next
counter=2
whilecursor!=None:
ifindex==counter:
print('canbehere!')
pre.next=cursor.next
break
else:
pre=cursor
cursor=cursor.next
counter+=1
#删除值为value的链表节点元素
defdelValue(self,value):
ifself.root==None:
return
#对第一个位置需要小心处理
ifself.root.data==value:
self.root=self.root.next
else:
pre=self.root
cursor=pre.next
whilecursor!=None:
ifcursor.data==value:
pre.next=cursor.next
#千万记得更新这个节点，否则会出现死循环。。。
cursor=cursor.next
continue
else:
pre=cursor
cursor=cursor.next
#判断链表是否为空
defisempty(self):
ifself.root==Noneorself.size()==0:
returnTrue
else:
returnFalse
#删除链表及其内部所有元素
deftruncate(self):
ifself.root==Noneorself.size()==0:
return
else:
cursor=self.root
whilecursor!=None:
cursor.data=None
cursor=cursor.next
self.root=None
cursor=None
#获取指定位置的节点的值
defgetvalue(self,index):
ifself.rootisNoneorself.size()==0:
print('当前链表为空！')
returnNone
ifindex<=0orindex>self.size():
print("index%d不合法！"%index)
returnNone
else:
counter=1
cursor=self.root
whilecursorisnotNone:
ifindex==counter:
returncursor.data
else:
counter+=1
cursor=cursor.next
#获取链表尾部的值，且不删除该尾部节点
defpeek(self):
returnself.getvalue(self.size())
#获取链表尾部节点的值，并删除该尾部节点
defpop(self):
ifself.rootisNoneorself.size()==0:
print('当前链表已经为空！')
returnNone
elifself.size()==1:
top=self.root.data
self.root=None
returntop
else:
pre=self.root
cursor=pre.next
whilecursor.nextisnotNone:
pre=cursor
cursor=cursor.next
top=cursor.data
cursor=None
pre.next=None
returntop
#单链表逆序实现
defreverse(self):
ifself.rootisNone:
return
ifself.size()==1:
return
else:
#post=None
pre=None
cursor=self.root
whilecursorisnotNone:
#print('逆序操作逆序操作')
post=cursor.next
cursor.next=pre
pre=cursor
cursor=post
#千万不要忘记了把逆序后的头结点赋值给root，否则无法正确显示
self.root=pre
#删除链表中的重复元素
defdelDuplecate(self):
#使用一个map来存放即可，类似于变形的“桶排序”
dic={}
ifself.root==None:
return
ifself.size()==1:
return
pre=self.root
cursor=pre.next
dic={}
#为字典赋值
temp=self.root
whiletemp!=None:
dic[str(temp.data)]=0
temp=temp.next
temp=None
#开始实施删除重复元素的操作
whilecursor!=None:
ifdic[str(cursor.data)]==1:
pre.next=cursor.next
cursor=cursor.next
else:
dic[str(cursor.data)]+=1
pre=cursor
cursor=cursor.next
#修改指定位置节点的值
defupdateNode(self,index,value):
ifself.root==None:
return
ifindex<0orindex>self.size():
return
ifindex==1:
self.root.data=value
return
else:
cursor=self.root.next
counter=2
whilecursor!=None:
ifcounter==index:
cursor.data=value
break
cursor=cursor.next
counter+=1
#获取单链表的大小
defsize(self):
counter=0
ifself.root==None:
returncounter
else:
cursor=self.root
whilecursor!=None:
counter+=1
cursor=cursor.next
returncounter
#打印链表自身元素
defprint(self):
if(self.root==None):
return
else:
cursor=self.root
whilecursor!=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.exeE:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py 链表为空1 链表为空0 打印当前链表所有值 123465673 链表的size:9 测试指定位置节点值的获取 1 3 6 测试删除链表中指定值，可重复性删除 canbehere! 12365673 126567 去除链表中的重复元素 12657 指定位置的链表元素的更新测试 12657 测试在链表首部添加节点 1087712657 测试在链表尾部添加节点 108771265799100 测试指定下标的插入操作 1001010833377126579999999100 测试peek操作 100 1001010833377126579999999100 测试pop操作 100 1001010833377126579999999 测试单链表的逆序输出 9999999756217733310810010 测试链表的truncate操作 Processfinishedwithexitcode0
刚好实现了目标需求。
总结
今天的内容还是比较基础，也没什么难点。但是看懂和会写还是两码事，没事的时候写写这样的代码还是很有收获的。