3.22.有序列表抽象数据结构

我们现在将考虑一种称为有序列表的列表类型。例如,如果上面所示的整数列表是有序列表(升序),则它可以写为17,26,31,54,77和93。由于 17 是最小项,它占据第一位置。同样,由于 93 是最大的,它占据最后的位置。

有序列表的结构是项的集合,其中每个项保存基于项的一些潜在特性的相对位置。排序通常是升序或降序,并且我们假设列表项具有已经定义的有意义的比较运算。许多有序列表操作与无序列表的操作相同。

  • OrderedList() 创建一个新的空列表。它不需要参数,并返回一个空列表。

  • add(item) 向列表中添加一个新项。它需要 item 作为参数,并不返回任何内容。假定该 item 不在列表中。

  • remove(item) 从列表中删除该项。它需要 item 作为参数并修改列表。假设项存在于列表中。

  • search(item) 搜索列表中的项目。它需要 item 作为参数,并返回一个布尔值。

  • isEmpty() 检查列表是否为空。它不需要参数,并返回布尔值。

  • size()返回列表中的项数。它不需要参数,并返回一个整数。

  • index(item) 返回项在列表中的位置。它需要 item 作为参数并返回索引。假定该项在列表中。

  • pop() 删除并返回列表中的最后一个项。假设该列表至少有一个项。

  • pop(pos) 删除并返回位置 pos 处的项。它需要 pos 作为参数并返回项。假定该项在列表中。

Last updated