一.线性表

二.顺序表

1.概念

2.结构

3.要实现的接口函数

三.模拟实现顺序表

1.定义出顺序表的基本结构

2.实现检查扩容功能

3.实现尾插

4.实现尾删

5.实现头插和头删

6.查找

7.修改

8.遍历

9.在指定位置插入和删除

四.顺序表的优缺点及思考

a.顺序表的弊端

一.线性表

在谈顺序表前，我们要先说说线性表了，线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

说白了，线性表在逻辑上就是一条线性结构，数据之间的排列是一个接一个的，尽管它们在物理上不一定是线性的；

如下图所示两种线性表的逻辑结构，它们的数据看起来都是首尾相连的；

二.顺序表

1.概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.结构

顺序表可以分为静态顺序表和动态顺序表，静态顺序表采用定长数组的形式来存储元素，而动态顺序表则可以根据需要进行扩容，相对而言还是动态顺序表更加实用，我们这里实现的也是动态顺序表。

静态与动态顺序表的结构示意如下（c语言版）

其中，SLDataType是表示指定类型的宏定义，在c++中可以用模版来代替！size为有效元素的个数，capacity为数组的容量，不够时可以通过realloc扩容；

3.要实现的接口函数

三.模拟实现顺序表

模拟实现我们采用c++的方式来，因为写起来更方便，而且初始化和销毁都包含在构造函数和析构函数中了，无需我们手动调用；

1.定义出顺序表的基本结构

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstdlib>
#include <assert.h>
using namespace std;
using DataType = int;
class seqList
{
public:seqList():_num(nullptr),_size(0),_capacity(0){}~seqList(){delete(_num);_size = 0;_capacity = 0;}private:DataType* _num;int _size;int _capacity;
};

2.实现检查扩容功能

因为我们往数组里添加数据可能遇到数组空间不够的情况，所以要能检测到这种需要进行扩容的情况！

void SeqListCheckCapacity()
{if (_size == _capacity){int newcapacity = _capacity == 0 ? 4 : _capacity * 2;DataType* tmp = (DataType*)realloc(_num, sizeof(DataType) * newcapacity);if (tmp == nullptr){perror("扩容出错：");return;}_num = tmp;_capacity = newcapacity;}
}

3.实现尾插

插入数据之前，要先检查一下当前是否需要扩容了，这样能够确保空间足够，插入数据之后不要忘记维护代表元素个数的_size;

void SeqListPushBack(DataType x)
{SeqListCheckCapacity();_num[_size++] = x;
}

4.实现尾删

删除数据前要先确保数组内还有剩余数据，如果有，只需要将元素个数减一即可，因为我们查找和遍历顺序表时都是通过_size来进行的！

void SeqListPopBack()
{assert(_size > 0);_size--;
}

5.实现头插和头删

只要是插入，就要首先判断扩容，只要是删除，就要先判断是否有数据；

头插和头删的共同点是都要移动元素，对于头插，我们在顺序表头部插入元素之前，必须将原来的所有数据整体往右移一位，才能给插入数据腾出空间，此时要头插注意移动的方法，必须是从右往左进行的，每次都选取要移动到的位置，然后将左边的数移到该位置；如果从左往右依次移动，会出现左边值覆盖右边值的情况！

尾删要先将数据向左集体移动一位，采用从左往右依次移动一位的方式；

void SeqListPushFront(DataType x)
{SeqListCheckCapacity();for (int i = _size; i > 0; i--){_num[i] = _num[i - 1];}_num[0] = x;_size++;
}

void SeqListPopFront()
{assert(_size > 0);for (int i = 0; i < _size - 1; i++){_num[i] = _num[i + 1];}_size--;
}

6.查找

没啥好说的，就是遍历数组找关键值

int SeqListFind(DataType x)
{for (int i = 0; i < _size; i++){if (_num[i] == x){return i;}}return -1;}

7.修改

void SeqListModity(int pos,DataType x)
{assert(pos >= 0 && pos < _size);_num[pos] = x;
}

8.遍历

	void SeqListPrint(){for (int i = 0; i < _size; i++){printf("%d ", _num[i]);}}

9.在指定位置插入和删除

要注意的地方前面都已经强调过了，就是要注意插入前的检查扩容、元素的移动方式、size的维护、删除前的检查剩余数据

void SeqListInsert(int pos, DataType x)
{assert(pos >= 0 && pos < _size);SeqListCheckCapacity();for (int i = _size; i > pos; i--){_num[i] = _num[i - 1];}_num[pos] = x;_size++;
}
void SeqLIstDelete(int pos)
{assert(pos >= 0 && pos < _size);for (int i = pos; i < _size - 1; i++){_num[i] = _num[i + 1];}_size--;
}