本页使用了标题或全文手工转换

串列 (抽象資料型別)

维基百科,自由的百科全书
跳转至: 导航搜索

計算機科學中,串列是一種抽象資料型別,一種有限的有序的集合,其中每个值可以出现多次。列表的一个实例是在計算機中用來表現出數學上有限序列的概念;列表的无限类似是。列表是容器的一个基本例子,因为它们包含其他值。在串列中的每個值(value),稱為項目(item)、條目(entry)或元素(element);如果相同的值出现多次,每一次出现都认为是分立的一个项目。列表和数组区别在列表只允许顺序访问,而数组允许随机访问。

資料結構中,也使用這個名稱,來表達實作出串列的資料結構,尤指連結串列(linked list)。

所谓静态列表结构只允许对值的审查和枚举。一个可变对象或动态列表在其生存周期内允许项目被插入、替换或删除。

许多编程语言对列表数据类型提供支持,并且有特定的语法和逻辑针对列表和列表运算。通常可以通过写入序列中的元素来建立列表。元素用逗号、分号或空格分开,位于一对括号(如圆括号 '()', 方括号, '[]', 花括号 '{}', 以及尖括号 '<>')内部。

运算[编辑]

实现列表数据结构可以提供以下一些运算:

  • 一个生成空列表的构造函数
  • 用于测试列表是否为空的运算;
  • 向列表前端加入元素的运算;
  • 向列表末端入元素的运算;
  • 确定列表头元素的运算;
  • 用于引用除首项外所有部分的列表(这被称为列表的“尾部”。)

特征[编辑]

列表有下列属性:

  • 列表大小. 它表明列表中有多少元素。
  • 列表相等:
    • 在数学里,有时列表相等定义为: 两个列表是相等的当且仅当它们是相同的对象。
    • 在现代编程语言中, 列表相等一般定义为相应条目结构上相等,要是列表具有类型,那么与列表类型也有关联。
  • 列表会具有类型。这表明列表中的条目必须有与列表类型兼容的类型。当列表由数组实现的时候常常会具有类型。
  • 列表中每个元素有一个标号。首元素一般标号为0或1(或其他一些预定义的整数)。后面的元素的标号比前一个大1。 尾元素的标号为<首标号> + <size> − 1。
    • 可以检索特定标号(index)的元素。
    • 可以按照标号增加的顺序遍历列表。
    • 可以改变特定标号的元素的值,同时不影响其他元素。
    • 可以向特定标号插入一个元素。后面的元素标号增加1。
    • 可以在特定标号删除一个元素。后面的元素标号减少1。