数据结构：顺序表定义、操作与经典题解

一、顺序表的定义

顺序表，本质就是线性表的顺序存储结构形式。

它的实现逻辑，是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同（顺序存储），且顺序表中元素的位序是从 1 开始的，而数组中元素的下标是从 0 开始的。

注意：顺序表的顺序存取结构天然支持随机存取结构。所谓随机存取，访问表里任意位置的元素，耗时都是恒定的，可直接访问表中任意位置的元素，无需从头遍历；而与之相对应的顺序存取结构的访问时间线性，取决于数据的排列顺序，只能顺序访问，不支持直接跳转访问某个位置，是链表的特点之一。

对于易搞混的顺序存储和顺序存取也应当区分：顺序存储是物理存储结构的概念，描述数据在内存 / 磁盘中的物理空间布局；顺序存取是数据访问方式的概念，描述读写数据的逻辑规则。简单的区分就是顺序存储，说的是数据在内存里挨不挨着；顺序存取，说的是访问数据要不要从头挨个找。

顺序表的数据存在静态分配和动态分配两种。

静态分配会由于所分配的空间大小已经事先固定，不能二次更改，所以遇到空间占满不够用的情况下，会产生数据溢出导致程序崩溃。

静态分配顺序表定义代码实现如下：

#define MaxSize 100 //定义顺序表数组的最大长度
typedef struct {
    ElemType data[MaxSize]; //顺序表中的元素
    int length; //顺序表的当前长度
} SqList; //静态分配顺序表的名称

而动态分配不同，其通过动态分配语句实时分配空间，在空间占满不够用的情况下可以直接另辟蹊径一块内存空间，并且将源元素如数拷贝到新创建的空间当中，从而达到动态扩容的效果，所以这种操作可以预防为了防止内存不够用而一次性分配大量空间导致空间过剩造成浪费的情况出现。

动态分配顺序表定义代码实现如下：

#define InitSize 100 //定义顺序表数组的初始长度
typedef struct {
    ElemType *data; //定义顺序表动态分配数组的指针
    int MaxSize, length; //动态分配数组的最大容量和当前个数
} SeqList; //动态分配数组顺序表的名称
L.data = (ElemType*) malloc(sizeof(ElemType) * InitSize); //动态分配语句

顺序表的优点：

①可进行随机访问，即可通过首地址和元素序号可以在 O(1) 的时间复杂度内找到指定的元素；

②存储密度高，每个节点只存储数据元素。

对于优点的补充解析：

①定义于顺序存取结构的它说白了就是找元素快。因为它所有元素在内存里都是连续挨着放的，我们只要知道第一个元素的地址，还有单个元素占多大内存，直接就能算出第 n 个或者你想要的目标元素的地址，不用像链表那样必须从头挨个往下找。不管找第 1 个还是第 1000 个元素，耗时都一样，也就是常说的 O(1) 时间复杂度随机访问。