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
刚好实现了目标需求。
总结
今天的内容还是比较基础,也没什么难点。但是看懂和会写还是两码事,没事的时候写写这样的代码还是很有收获的。