Python 实现有序表(OrderedList)抽象数据类型

    上一篇文章我们讲了怎样用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)，因为只需要插入表头。