python数据结构： 有序表_python 有序表

1. 有序表

❖有序表是一种数据项依照其某可比性质（如整数大小、字母表先后）来决定在列表中的位置
❖越“小”的数据项越靠近列表的头，越靠“前”

2.抽象数据类型：有序表OrderedList

❖OrderedList所定义的操作如下：

OrderedList()：创建一个空的有序表
add(item)：在表中添加一个数据项，并保持整体顺序，此项原不存在
remove(item)：从有序表中移除一个数据项，此项应存在，有序表被修改
search(item)：在有序表中查找数据项，返回是否存在
isEmpty()：是否空表
size()：返回表中数据项的个数
index(item)：返回数据项在表中的位置，此项应存在
pop()：移除并返回有序表中最后一项，表中应至少存在一项
pop(pos)：移除并返回有序表中指定位置的数据项，此位置应存在

3.有序表OrderedList实现

❖在实现有序表的时候，需要记住的是，数据项的相对位置，取决于它们之间的“大小”比较
由于Python的扩展性，下面对数据项的讨论并不仅适用于整数，可适用于所有定义了__gt__方法（即’>'操作符）的数据类型
❖以整数数据项为例，(17,26,31,54,77,93)的链表形式如图