数据结构基础（4）线性表的顺序存储结构——顺序表
#数据结构#线性表#顺序表#C++ 2021-03-13

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

目录（更新中）

参考资料

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

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

顺序表（sequential list）

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

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

图 4-1 数据结构的分类

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

顺序表的实现

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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()

    创建一个空顺序表.

    1
    2
    3
    4
    template <typename DataType>
    SeqList<DataType>::SeqList() {
        length = 0;
    }

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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;
    }

求线性表的长度

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

查找操作

  • 按位查找 get(int i)

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

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

  • 按值查找 locate(DataType x)

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

    1
    2
    3
    4
    5
    6
    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;
    }

    平均情况下，假设数据平均分布，时间复杂度为 .

插入操作

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

同理考虑时间复杂度，为 .

删除操作

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

时间复杂度为 .

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

遍历操作

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

1
2
3
4
5
6
7
template <typename DataType>
void SeqList<DataType>::printList() {
    for (int i = 0; i < length; i++)
    std::cout << data[i] << " --> ";

    std::cout << "end";
}

显然时间复杂度为