上一篇文章我们讲了怎样用Python 实现无序表，那什么是有序表呢？
有序表是一种数据项依照其某可比性质（如数据项大小、字母表先后）来决定在列表的位置。越“小”的数据项越靠近列表的头。如下图：
有序表
OrdererList所定义的操作如下：
OrdererList() ：创建一个新的有序列表。
add(item) ：向列表中添加一个新项，并保存整体顺序，假定该 item 原先不在列表中。
remove(item) ：从列表中删除item ，并修改列表。该项原先存在于列表中。
search(item) ：搜索列表中的项目，并返回一个布尔值。
isEmpty() ：检查列表是否为空，并返回布尔值。
size（）：返回列表中的项数，并返回一个整数。
append(item) ：将一个新项添加到列表的末尾，假定该项原先不在列表中。
index(item) ：返回该项在列表中的位置，此项应存在。
pop() ：删除并返回列表中的最后一个项，假设该列表至少有一个项。
pop(pos) ：删除位置为 pos 处的项，假定该项存在在列表中。
在实现有序表数据结构，需要记住，数据项的相对位置取决于他们之间的“大小”比较。由于python的扩展性，我们对数据项的讨论并不仅适用于整数，可适用于所有定义了__gt__方法（即'>'操作符）的数据类型。
有序表我们通用可以用链表方法实现，且Node定义相同。OrdererList的初始化函数、isEmpty、remove方法也一致，因为无关顺序，但search和add方法需要修改。
def search(self,item): #有序表的search能节省不存在数据项的查找时间
current = self.head
found = False
stop = False #判定一旦当前节点数据项大于所要查找的数据项，直接返回False
while current != None and not found and not stop: #优化点
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
有序表add方法如下图，跟remove方法类型，引入一个previous，跟随当前节点current。
有序表add
有序表add方法的代码如下图所示：
add方法代码
我们来分析下链表实现有序表的算法复杂度，isEmpty是O(1)，size、search、remove和add是O(n)，相比于无序表的add方法是O(1)，因为只需要插入表头。
网友评论