数据结构（1）：顺序表（上）

不可言诉的深渊

发布于 2021-03-24 21:03:50

1.2K0

发布于 2021-03-24 21:03:50

就在昨天，我查了一下考研成绩的排名，果不其然第 1 名！因为我没有特别低的单科分数，外加上估摸着国家线十之八九不会大涨，所以我感觉我能进复试！考虑到我的复试专业课是数据结构，所以从今天开始，我将一直写数据结构的文章，直到复试结束。接下来先说几件事情，然后介绍第一个数据结构——顺序表！

一些小事

数据结构的代码会尽量使用 Python，实在不行会选择 C/C++。
我按照复试大纲来，复试大纲里面没有提到的东西我不会去写。
一个数据结构分两篇文章，第一篇实现这个数据结构，第二篇是这个数据结构相关的一些算法题。

顺序表

顺序表的定义

顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑上相邻的元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧接着存储的是第 i+1 个元素，称 i 为元素 ai 的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

注意：线性表中元素的位序是从 1 开始的，而数组中元素的下标是从 0 开始的。

大家一看完定义之后就会明白，这不就是 Python 中的 list 数据类型吗？确实如此，所以我就不用 Python 的 list 套一个壳实现一个顺序表了，换成用 C/C++ 来实现顺序表。首先看到顺序表存储类型的描述，代码如下：

#define MaxSize 50//定义顺序表的最大长度
template<class ElemType>class SqList//顺序表的类型定义
{
private:
  ElemType data[MaxSize];//顺序表的元素
  int length;//顺序表的当前长度
};

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为顺序表一次性的划分所有空间。下面看一下动态分配的顺序表存储类型的描述，代码如下：

#define InitSize 100//表长度的初始定义
template<class ElemType>class SeqList//动态分配数组顺序表的类型定义
{
private:
  ElemType* data;//指示动态分配数组的指针
  int MaxSize, length;//数组的最大容量和当前个数
};

C 的初始动态分配语句为

data = (ElemType*)malloc(sizeof(ElemType) * InitSize);

C++ 的初始动态分配语句为

data = new ElemType[InitSize];

注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。

顺序表最主要的特点是随机访问，即通过首地址和元素序号可以在时间 O(1) 内找到指定的元素。

顺序表的存储密度高，每个结点只存储数据元素。

顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

顺序表上基本操作的实现

顺序表的基本操作一共有 9 个，分别是：初始化表、求表长、按值查找操作、按位查找操作、插入操作、删除操作、输出操作、判空操作、销毁操作。

我在这里基于动态分配数组顺序表来实现这 9 个基本操作。

初始化表

首先看到初始化表操作，因为我把顺序表存储类型描述为 C++ 的类，所以初始化表选用这个类的构造方法。

  SeqList(int max_size = 200)//初始化表
  {
    data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    //data = new ElemType[InitSize];
    MaxSize = max_size;
    length = 0;
  }

初始化表是为了构造一个空的顺序表，所以只需要给 data 分配空间即可，并不需要在里面存放数据。

求表长

返回顺序表的长度，即顺序表中数据元素的个数。

   int Length()//求表 长
  {
    return length;
  }

按值查找操作

在顺序表中查找第一个元素值等于 e 的元素，并返回其位序。

   int LocateElem(ElemType e)//按值查找操作
  {
    for (int i = 0; i < length; i++)
      if (data[i] == e)
        return i + 1;//下标为 i 的元素值等于 e，返回其位序 i+1
    return 0;//退出循环，说明查找失败
  }

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为 O(1)。

最坏情况：查找的元素在表尾（或不存在）时，需要比较 n 次，时间复杂度为 O(n)。

因此，顺序表按值查找算法的平均时间复杂度为 O(n)。

按位查找操作

获取表中第 i 个位置的元素的值

    ElemType GetElem(int i)//按位查找操作
{
    ElemType e = NULL;
    if (i<1 || i>length)
      return e;
    e = data[i - 1];
    return e;
  }

插入操作

在顺序表的第 i（1≤i≤length+1）个位置插入新元素 e。若 i 的输入不合法，结束，表示插入失败；否则，将顺序表的第 i 个元素及其后的所有元素右移一个位置，腾出一个空位置插入新元素 e，顺序表长度增加 1，插入成功。

  void ListInsert(int i, ElemType e)//插入操作
  {
    if (i<1 || i>length + 1)//判断 i 的范围是否有效
      return;
    if (length >= MaxSize)//当前存储空间已满，不能插入
      return;
    if (length >= InitSize)
    {
      ElemType* temp = (ElemType*)realloc(data, sizeof(ElemType) * (length + 1));
      data = temp;
      if (!data)
        return;
    }
    for (int j = length; j >= i; j--)//将第 i 个元素及之后的元素后移
      data[j] = data[j - 1];
    data[i - 1] = e;//在位置 i 处放入 e
    length++;//顺序表长度加 1
  }

注意：区别线性表的位序（从 1 开始）和数组下标（从 0 开始）。

最好情况：在表尾插入（即 i=n+1），元素后移语句不执行，时间复杂度为 O(1)。

最坏情况：在表头插入（即 i=1），元素后移语句将执行 n 次，时间复杂度为 O(n)。

因此，顺序表插入算法的平均时间复杂度为 O(n)。

删除操作

删除顺序表中第 i（1≤i≤length）个位置的元素，若成功则返回被删元素值，否则返回 NULL。

  ElemType ListDelete(int i)//删除操作
  {
    ElemType e = NULL;
    if (i<1 || i>length)//判断 i 的范围是否有效
      return e;
    e = data[i - 1];//将被删除元素赋值给 e
    for (int j = i; j < length; j++)//将第 i 个位置后的元素前移
      data[j - 1] = data[j];
    length--;//顺序表长度减 1
    return e;
  }

最好情况：删除表尾元素（即 i=n），无需移动元素，时间复杂度为 O(1)。

最坏情况：删除表头元素（即 i=1），需要移动除第一个元素外的所有元素，时间复杂度为 O(n)。

因此，顺序表删除算法的平均时间复杂度为 O(n)。

输出操作

按前后顺序输出顺序表的所有元素值。

 void PrintList()//输出操作
{
    printf("[");
    if (length)
    {
      for (int i = 0; i < length - 1; i++)
        cout << data[i] << ", ";
      cout << data[length - 1] << "]\n";
    }
    else
      printf("]\n");
  }

判空操作

若为空表，则返回 true，否则返回 false。

 bool Empty()//判空操作
  {
    return length == 0 ? true : false;
  }

销毁操作

既然初始化表我用的是构造方法，那么执行销毁操作没什么可以解释的，用析构方法就可以了。

 ~SeqList()//销毁操作
  {
    free(data);
    data = NULL;
  }~SeqList()//销毁操作  {    free(data);    data = NULL;  }

总结

最后先给出完整的源代码以及一个简单的测试程序，完整源代码放在了一个头文件（seq_list.h）中，代码如下：

#pragma once
#include<iostream>
using namespace std;
#define InitSize 100//表长度的初始定义
template<class ElemType>class SeqList//动态分配数组顺序表的类型定义
{
private:
  ElemType* data;//指示动态分配数组的指针
  int MaxSize, length;//数组的最大容量和当前个数
public:
  SeqList(int max_size = 200)//初始化表
  {
    data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    //data = new ElemType[InitSize];
    MaxSize = max_size;
    length = 0;
  }
  int Length()//求表长
{
    return length;
  }
  int LocateElem(ElemType e)//按值查找操作
{
    for (int i = 0; i < length; i++)
      if (data[i] == e)
        return i + 1;//下标为 i 的元素值等于 e，返回其位序 i+1
    return 0;//退出循环，说明查找失败
  }
  ElemType GetElem(int i)//按位查找操作
{
    ElemType e = NULL;
    if (i<1 || i>length)
      return e;
    e = data[i - 1];
    return e;
  }
  void ListInsert(int i, ElemType e)//插入操作
{
    if (i<1 || i>length + 1)//判断 i 的范围是否有效
      return;
    if (length >= MaxSize)//当前存储空间已满，不能插入
      return;
    if (length >= InitSize)
    {
      ElemType* temp = (ElemType*)realloc(data, sizeof(ElemType) * (length + 1));
      data = temp;
      if (!data)
        return;
    }
    for (int j = length; j >= i; j--)//将第 i 个元素及之后的元素后移
      data[j] = data[j - 1];
    data[i - 1] = e;//在位置 i 处放入 e
    length++;//顺序表长度加 1
  }
  ElemType ListDelete(int i)//删除操作
{
    ElemType e = NULL;
    if (i<1 || i>length)//判断 i 的范围是否有效
      return e;
    e = data[i - 1];//将被删除元素赋值给 e
    for (int j = i; j < length; j++)//将第 i 个位置后的元素前移
      data[j - 1] = data[j];
    length--;//顺序表长度减 1
    return e;
  }
  void PrintList()//输出操作
{
    printf("[");
    if (length)
    {
      for (int i = 0; i < length - 1; i++)
        cout << data[i] << ", ";
      cout << data[length - 1] << "]\n";
    }
    else
      printf("]\n");
  }
  bool Empty()//判空操作
{
    return length == 0 ? true : false;
  }
  ~SeqList()//销毁操作
  {
    free(data);
    data = NULL;
  }
};

简单测试程序源代码如下所示：

#include"seq_list.h"
int main()
{
  SeqList<int> L = SeqList<int>();
  printf("L:");
  L.PrintList();
  cout << "L.Empty():" << boolalpha << L.Empty() << "\n";
  printf("L.Length():%d\n", L.Length());
  for (int i = 0; i < InitSize; i++)
    L.ListInsert(i + 1, i);
  cout << "L.Empty():" << boolalpha << L.Empty() << "\n";
  printf("L.Length():%d\n", L.Length());
  printf("L:");
  L.PrintList();
  L.ListInsert(90, 10);
  cout << "L.Empty():" << boolalpha << L.Empty() << "\n";
  printf("L.Length():%d\n", L.Length());
  printf("L:");
  L.PrintList();
  cout << "L.ListDelete(90):" << L.ListDelete(90) << "\n";
  cout << "L.Empty():" << boolalpha << L.Empty() << "\n";
  printf("L.Length():%d\n", L.Length());
  printf("L:");
  L.PrintList();
}

运行结果如下所示：