CS5040 中级数据结构与算法

Chapter 7 Linear Structures

| 关于   «  1. 章节引言：线性表   ::   目录   ::   3. 基于数组的线性表实现  »

2. 线性表 ADT

2.1. 线性表 ADT

我们对“线性表”的含义都有直观的理解。我们希望将这种直观理解转化为具有操作实现的具体数据结构。与线性表相关的最重要概念是 位置 。换句话说，我们感知到线性表中存在第一个元素、第二个元素，依此类推。因此，将 线性表 定义为由称为 元素 的数据项组成的有限有序序列。这与数学上的 序列 概念非常接近。

此定义中的“有序”是指线性表中的每个元素都有一个位置。

每个线性表元素必须具有某种数据类型。 在本章讨论的简单线性表实现中，通常假定线性表的所有元素都有 相同的数据类型，尽管从概念上讲，只要应用需要，元素具有不同 数据类型的线性表并无不可。 作为线性表 ADT 一部分定义的操作并不依赖于元素的 数据类型。 例如，线性表 ADT 可以用于整数线性表、字符线性表、工资记录 线性表，甚至是线性表的线性表。

当线性表不含任何元素时，称它为 空 的。 当前存储的元素个数称为线性表的 长度。 线性表的开头称为 表头，结尾称为 表尾。

我们需要一些记号来表示线性表的内容，因此我们将使用通常用于表示 序列 的尖括号记号。为了与标准的数组索引保持一致，线性表的第一个位置记为 0。因此，如果线性表中有 \(n\) 个元素，它们的位置将从 0 到 \(n-1\) ，记作 \(\langle\ a_0,\ a_1,\ ...,\ a_{n-1}\ \rangle\) 。下标表示元素在线性表中的位置。使用这种记号，空线性表将显示为 \(\langle\ \rangle\) 。

2.1.1. 定义 ADT

我们希望线性表支持哪些基本操作？我们对线性表的普遍直觉告诉我们，线性表应当能够在插入和删除元素时动态调整大小。我们应当能够在线性表的任意位置插入和删除元素。我们应当能够访问任意元素的值，无论是读取还是修改。我们必须能够创建和清空（或重新初始化）线性表。此外，从“当前”元素访问其下一个或前一个元素也很方便。

现在我们可以针对线性表对象、用一组操作来定义它的 ADT 了。 我们将用接口来形式化地定义线性表 ADT。 List 定义了继承它的任何线性表实现都必须支持的成员函数， 以及它们的参数和返回类型。

忠于 ADT 的本义，接口不规定操作如何实现。 后面的模块会给出两种完整的实现，二者都用同一个线性表 ADT 来定义它们的操作。 但它们在方法和空间/时间权衡上差别相当大。

下面的代码给出我们的线性表 ADT。 像线性表这样的 容器类 的任何实现都应当能支持 元素的不同数据类型。 在 Java 中做到这一点的一种方式是存储 Object 类型的数据值。 支持泛型（Java）或模板（C++）的语言对元素类型有更多控制。

每个成员函数的注释都描述了该函数的用途，但对基本设计作一些解释应有助于把问题说得更清楚。既然我们希望支持“序列”这一概念并能够访问线性表中的任意位置，那么 insert 和 moveToPos 等许多成员函数的必要性就是显而易见的。该 ADT 所体现的关键设计决策是对 当前位置 概念的支持。例如，成员函数 moveToStart 把当前位置设置为线性表的第一个元素，而 next 和 prev 方法则分别把当前位置移动到下一个和上一个元素。其意图是，该 ADT 的任何实现都支持当前位置这一概念。当前位置是插入或删除等操作发生的地方。另一种设计是把位置抽取为一个独立的位置对象，有时称之为 迭代器 。

// List class ADT. Generalize by using "Object" for the element type.
public interface List { // List class ADT
  // Remove all contents from the list, so it is once again empty
  public void clear();

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  public boolean insert(Object it);

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  public boolean append(Object it);

  // Remove and return the current element
  public Object remove();

  // Set the current position to the start of the list
  public void moveToStart();

  // Set the current position to the end of the list
  public void moveToEnd();

  // Move the current position one step left, no change if already at beginning
  public void prev();

  // Move the current position one step right, no change if already at end
  public void next();

  // Return the number of elements in the list
  public int length();

  // Return the position of the current element
  public int currPos();

  // Set the current position to "pos"
  public boolean moveToPos(int pos);

  // Return true if current position is at end of the list
  public boolean isAtEnd();

  // Return the current element
  public Object getValue();
  
  public boolean isEmpty();
}

// List class ADT. Generalize the element type using Java Generics.
public interface List<E> { // List class ADT
  // Remove all contents from the list, so it is once again empty
  public void clear();

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  public boolean insert(E it);

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  public boolean append(E it);

  // Remove and return the current element
  public E remove();

  // Set the current position to the start of the list
  public void moveToStart();

  // Set the current position to the end of the list
  public void moveToEnd();

  // Move the current position one step left, no change if already at beginning
  public void prev();

  // Move the current position one step right, no change if already at end
  public void next();

  // Return the number of elements in the list
  public int length();

  // Return the position of the current element
  public int currPos();

  // Set the current position to "pos"
  public boolean moveToPos(int pos);

  // Return true if current position is at end of the list
  public boolean isAtEnd();

  // Return the current element
  public E getValue();
  
  // Tell if the list is empty or not
  public boolean isEmpty();
}

// List class ADT.
class List { // List class ADT
public:
  // Destructor
  virtual ~ List () =default;

  // Remove all contents from the list, so it is once again empty
  virtual void clear() =0;

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  virtual bool insert(const ListItemType& it) =0;

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  virtual bool append(const ListItemType& it) =0;

  // Remove and return the current element
  virtual ListItemType remove() =0;

  // Set the current position to the start of the list
  virtual void moveToStart() =0;

  // Set the current position to the end of the list
  virtual void moveToEnd() =0;

  // Move the current position one step left, no change if already at beginning
  virtual void prev() =0;

  // Move the current position one step right, no change if already at end
  virtual void next() =0;

  // Return the number of elements in the list
  virtual int length() =0;

  // Return the position of the current element
  virtual int currPos() =0;

  // Set the current position to "pos"
  virtual bool moveToPos(int pos) =0;

  // Return true if current position is at end of the list
  virtual bool isAtEnd() =0;

  // Return the current element
  virtual ListItemType getValue() =0;
  
  virtual bool isEmpty() =0;
};

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

List 成员函数允许你按任意期望顺序构建包含元素的线性表，并访问线性表中任意期望位置。你可能会注意到 clear 方法是一种“便捷”方法，因为它可以通过其他成员函数以相同的渐近时间实现。

线性表可以按如下方式遍历：

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
  it = L.getValue();
  doSomething(it);
}

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
  it = L.getValue();
  doSomething(it);
}

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
  it = L.getValue();
  doSomething(it);
}

在此示例中，线性表的每个元素依次存储在 it 中，并传递给 doSomething 函数。当当前位置到达线性表末尾时，循环终止。

这里给出的线性表类声明只是对线性表众多可能诠释中的一种。 我们的线性表接口提供了人们自然期望对线性表执行的大多数操作， 并足以说明与实现线性表数据结构相关的各种问题。 作为线性表 ADT 的使用示例，下面这个函数在线性表中存在给定 整数时返回 true，否则返回 false。 find 方法不需要知道线性表的具体实现，只需要线性表 ADT。

// Return true if k is in list L, false otherwise
static boolean find(List L, Object k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next())
    if (k == L.getValue()) return true; // Found k
  return false;                         // k not found
}

// Return true if k is in list L, false otherwise
static boolean find(List<T> L, int k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next()) {
    if (k == L.getValue()) {
      return true; // Found k
    }
  }
  return false;                         // k not found
}

// Return true if k is in list L, false otherwise
static bool find(List &L, ListItemType k) {
  for (L.moveToStart(); !L.isAtEnd(); L.next())
    if (k == L.getValue()) return true; // Found k
  return false;                       // k not found
}

在支持该特性的语言中， find 的这种实现可以针对元素类型重写为泛型或模板。虽然这使得实现更加灵活，但即使是泛型类型，在处理线性表中存储的不同数据类型时能力仍然有限。特别是对于 find 函数，仅当被搜索对象的描述（即函数中的 k ）与对象本身类型相同时，泛型类型才能正常工作。使用 == 运算符时，它们还必须具备可比较性。更现实的情况是，我们正在搜索一条记录，该记录包含一个 键 字段，其值与 k 匹配。可以使用线性表实现创建类似的函数来基于键值查找并返回 复合类型 ，但要做到这一点，需要线性表抽象数据类型与 find 函数在键概念以及 how keys may be compared 上达成一致。

实现线性表有两种标准方法： 基于数组的线性表 和 链表。

2.2. 线性表 ADT 编程练习

   «  1. 章节引言：线性表   ::   目录   ::   3. 基于数组的线性表实现  »

© Copyright 2011-2025 by OpenDSA Project Contributors and distributed under an MIT license. 最后更新于 9月 30, 2026. Created using Sphinx 8.2.0.
关闭窗口