数据结构基础（4）线性表的顺序存储结构——顺序表

本文主要介绍了线性表的顺序存储结构，以及基于 C++ 的具体实现.

目录（更新中）

• 第一章 绪论

  (1) 数据结构的基本概念

  (2) 算法及算法分析

• 第二章 线性表

  (3) 线性表的逻辑结构

  (4) 线性表的顺序存储结构——顺序表

参考资料

[1] 王红梅编著. 数据结构（C++版本）（第2版）. 北京：清华大学出版社，2011.

[2] 钱能著. C++ 程序设计教程（第二版）. 北京：清华大学出版社，2005.

---

顺序表（sequential list）

线性表的顺序存储结构称为顺序表.

需要辨析的是，线性表的链接存储结构被称为链表，链表又分为单链表、循环链表、双链表等，他们都是线性表属于线性结构的分类. 本文讨论的是顺序表.

顺序表是用一段地址连续的存储单元依次存储线性表的数据元素. 由于线性表中每个数据元素的类型相同，通常用一维数组来实现顺序表，也就是把线性表中相邻的元素存储在数组中相邻的位置.

顺序表的实现

将线性表的抽象数据类型定义用 C++ 的类实现，由于线性表的数据元素类型不确定，所以采用 C++ 的模板机制.

这里我们规定顺序表序号从 $1$ 开始，因此与数组的下标相差 $1$.

const int MaxSize = 100;

template <typename DataType>
class SeqList {
 public:
  SeqList();
  SeqList(DataType a[], int n);
  ~SeqList(){};
  int getLength();
  DataType get(int i);
  int locate(DataType x);
  void insert(int i, DataType x);
  DataType remove(int i);
  void printList();

 private:
  DataType data[MaxSize];
  int length = 0;
};

下面实现成员函数：

构造函数

• 无参构造函数 SeqList()

  创建一个空顺序表.

  template <typename DataType>
  SeqList<DataType>::SeqList() {
      length = 0;
  }

• 有参构造函数 Seqlist(DataType a[], int n)

  使用传入的数组构造顺序表，并指定顺序表长度.

  template <typename DataType>
  SeqList<DataType>::SeqList(DataType a[], int n) {
      if (n > MaxSize) throw "参数非法";
  
      for (int i = 0; i < n; i++)
      data[i] = a[i];
  
      length = n;
  }

求线性表的长度

template <typename DataType>
int SeqList<DataType>::getLength() {
    return length;
}

查找操作

• 按位查找 get(int i)

  由于使用数组存储数据，则查找第 i 个元素直接返回数组 data[] 中的第 i - 1 个元素. 时间复杂度为 $O(1)$.

  template <typename DataType>
  DataType SeqList<DataType>::get(int i) {
    if (i < 1 && i > length)
      throw "查找位置非法";
    return data[i - 1];
  }

• 按值查找 locate(DataType x)

  对顺序表进行遍历，返回第一个匹配元素的序号（注意不是数组下标）；如果查找不到该值则返回失败的标志 0.

  template <typename DataType>
  int SeqList<DataType>::locate(DataType x) {
    for (int i = 0; i < length; i++)
      if (data[i] == x) return i + 1;
    return 0;
  }

  平均情况下，假设数据平均分布，时间复杂度为 $O(n)$.

插入操作

注意插入位置的合法性. 同时由于插入后元素的逻辑关系发生改变，所以应由存储关系反应这一变化，即调整相应元素在数组中的位置.

template <typename DataType>
void SeqList<DataType>::insert(int i, DataType x) {
    if (length > MaxSize - 1)
    throw "顺序表已满，无法插入";
    if (i < 1 || i > length + 1)
    throw "非法位置";

    for (int j = length; j > i - 1; j--)
    data[j] = data[j - 1];

    length++;
    data[i - 1] = x;
}

同理考虑时间复杂度，为 $O(n)$.

删除操作

同理考虑位置的合理性，并且通过调整存储关系来反映逻辑关系的变化.

时间复杂度为 $O(n)$.

template <typename DataType>
DataType SeqList<DataType>::remove(int i) {
    if (i < 1 || i > length)
    throw "非法位置";

    DataType temp = data[i - 1];

    for (int j = i - 1; j < length; j++)
    data[j] = data[j + 1];

    length--;
    return temp;
}

遍历操作

按顺序打印顺序表中的元素. 以可直接打印的数据类型为例.

template <typename DataType>
void SeqList<DataType>::printList() {
    for (int i = 0; i < length; i++)
    std::cout << data[i] << " --> ";

    std::cout << "end";
}

显然时间复杂度为 $O(n)$