免费服务器建站,东莞网络优化排名,网站 站外链接,自适应网站建设软件#x1f308;个人主页: Aileen_0v0 #x1f525;系列专栏:PYTHON学习系列专栏 #x1f4ab;没有罗马,那就自己创造罗马~ 目录
知识回顾及总结
有序表的引入
编辑 实现有序表
1.有序表-类的构造方法
2.有序表-search方法的实现
3.有序表-add方法的实现… 个人主页: Aileen_0v0 系列专栏:PYTHON学习系列专栏 没有罗马,那就自己创造罗马~ 目录
知识回顾及总结
有序表的引入
编辑 实现有序表
1.有序表-类的构造方法
2.有序表-search方法的实现
3.有序表-add方法的实现
有序链表 - 完整实现过程
链表分析 知识回顾及总结 上一次我们学习了无序表之链表和列表,知道了链表的特点是顺藤摸瓜结构
通俗的讲就是链表相当于火车(如果元素放在链表后面,找那个车厢需要从头开始往后找)
有序表的引入
今天,我们来学习有序表- OrderedList-需要增加属性进行位置参照-所以需要对表头进行处理
有序表是一种数据项依照其某可比性质如整数大小、字母表先后)来决定在列表中的位置数值越小位置越前,数值越大位置越后. 实现有序表
1.有序表-类的构造方法
class Orderedlist:def __init__(self):self.head None
2.有序表-search方法的实现 之前,我们无序表搜索,需要遍历节点,直到找到目标节点,或者没有节点可以继续访问. 但是,对于有序表,如果目标元素不在列表中,可以利用元素有序的特点终止寻找. 只要节点中的值比正在查找的值更大,搜索会立刻结束并返回False,因为查找的元素不可能存在于链表后续的节点中. def search(self,item):current self.headfound Falsestop Falsewhile current ! None and not found and not stop:if current.get_data() item:found Trueelse:if current.get_data() item:stop Trueelse:current current.get_next()return found
3.有序表-add方法的实现 相对于无序列表来说,有序列表,需要修改最多的是add方法. 对于无序表:add方法将一个节点放在最容易访问的位置,即列表头部. 对于有序列表:需要在需要在已有链表中,为新节点找到正确的插入位置. 当访问完所有节点(current是None) 或者 当前值大于要添加的元素时,就找到了插入位置,如上图中,找到54即可停止查找. 有序表和无序表一样,由于current本身无法提供对待修改节点进行访问, 因此我们需要额外引用previous def add(self,item):#初始化两个外部引用(作用相当于指针)current self.head#指针1previous None#p2stop False#判断循环是否继续执行,---循环停止,就是找到了新节点的插入位置while current ! None and not stop:#发现插入位置if current.get_data() item:stop Trueelse:previous currentcurrent current.get_next()temp Node(item)#插在表头if previous None:temp.set_next(self.head)self.head temp#插在表中else:temp.set_next(current)previous.set_next(temp)
有序链表 - 完整实现过程
其它实现过程类似于无序表,可以自己尝试练习一下~
这里是我的实现过程,仅供大家学习参考.
class Node:#结点Node相当于车厢def __init__(self,init_data):self.data init_dataself.next None#获得数据项def get_data(self):return self.data#获得节点def get_next(self):return self.next#设置数据项def set_data(self,new_data):self.data new_data#属性#设置节点def set_next(self,new_next):self.next new_next#属性class Orderedlist:def __init__(self):self.head Nonedef search(self,item):current self.headfound Falsestop Falsewhile current ! None and not found and not stop:if current.get_data() item:found Trueelse:if current.get_data() item:stop Trueelse:current current.get_next()return founddef add(self,item):current self.head#指针1previous None#p2stop Falsewhile current ! None and not stop:#发现插入位置if current.get_data() item:stop Trueelse:previous currentcurrent current.get_next()temp Node(item)#插在表头if previous None:temp.set_next(self.head)self.head temp#插在表中else:temp.set_next(current)previous.set_next(temp)def size(self):current self.headcount 0while current ! None:count 1current current.get_next()return countdef remove(self, item):current self.headprevious Nonefound Falsewhile not found and current ! None:if current.get_data() item:found Trueelse:previous currentcurrent current.get_next()if found:if previous None:self.head current.get_next()else:previous.set_next(current.get_next())def traverse(self):current self.headwhile current ! None:print(current.get_data())current current.get_next()ol Orderedlist()
ol.add(7)
ol.add(9)
ol.add(6)
ol.add(8)
ol.add(10)
print(ol.search(6))
ol.traverse()
链表分析
