知识回顾及总结
上一次我们学习了无序表之链表和列表,知道了链表的特点是顺藤摸瓜结构
通俗的讲就是链表相当于火车(如果元素放在链表后面,找那个车厢需要从头开始往后找)
有序表的引入
今天,我们来学习有序表- OrderedList-需要增加属性进行位置参照-所以需要对表头进行处理
有序表是一种数据项依照其某可比性质如整数大小、字母表先后)来决定在列表中的位置
数值越小位置越前,数值越大位置越后.
实现有序表
1.有序表-类的构造方法
class Orderedlist: def __init__(self): self.head = None
2.有序表-search方法的实现
之前,我们无序表搜索,需要遍历节点,直到找到目标节点,或者没有节点可以继续访问.
但是,对于有序表,如果目标元素不在列表中,可以利用元素有序的特点终止寻找.
只要节点中的值比正在查找的值更大,搜索会立刻结束并返回False,因为查找的元素不可能存在于链表后续的节点中.
def search(self,item): current = self.head found = False stop = False while current != None and not found and not stop: if current.get_data() == item: found = True else: if current.get_data() > item: stop = True else: current = current.get_next() return found
3.有序表-add方法的实现
相对于无序列表来说,有序列表,需要修改最多的是add方法.
对于无序表:add方法将一个节点放在最容易访问的位置,即列表头部.
对于有序列表:需要在需要在已有链表中,为新节点找到正确的插入位置.
当访问完所有节点(current是None) 或者 当前值大于要添加的元素时,就找到了插入位置,如上图中,找到54即可停止查找.
有序表和无序表一样,由于current本身无法提供对待修改节点进行访问,
因此我们需要额外引用previous
def add(self,item): #初始化两个外部引用(作用相当于指针) current = self.head#指针1 previous = None#p2 stop = False #判断循环是否继续执行,---循环停止,就是找到了新节点的插入位置 while current != None and not stop: #发现插入位置 if current.get_data() > item: stop = True else: previous = current current = 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_data self.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 = None def search(self,item): current = self.head found = False stop = False while current != None and not found and not stop: if current.get_data() == item: found = True else: if current.get_data() > item: stop = True else: current = current.get_next() return found def add(self,item): current = self.head#指针1 previous = None#p2 stop = False while current != None and not stop: #发现插入位置 if current.get_data() > item: stop = True else: previous = current current = 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.head count = 0 while current != None: count += 1 current = current.get_next() return count def remove(self, item): current = self.head previous = None found = False while not found and current != None: if current.get_data() == item: found = True else: previous = current current = 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.head while 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()
链表分析
