【数据结构初阶】顺序表

【数据结构——调试+思考+画图+写代码】

【重在梳理代码逻辑，标记数组元素下标】

目录

---

---

前言

顺序表 

静态顺序表

动态顺序表

实现一个顺序表

梳理顺序表逻辑

代码实现

SeqList.h文件

SeqList.c文件

test.c文件

编程题——顺序表的变相考察

移除元素

删除有序数组中的重复项

合并两个有序数组

---

---

前言

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表的数据在存储的时候是成一条线性相互紧邻存放的。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

顺序表 

顺序表就是数组。管理数组、存储数据的结构就是线性表。把数据管理起来，管理就是增删查改，即完成各个函数的实现。

数组的缺陷：在支持C99之前，数组的长度是固定的。即使是变长数组，也会面临不知道所存数据的多少。

顺序表是一段连续的物理空间，就像（是）数组。

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

顺序表相比数组还有一些额外的要求，要求存储的数据必须从0开始，必须从前向后依次连续存储，不能跳跃存储。比如数组有100个字节的空间就可以随便访问任意一个位置；而顺序表不能在任意位置存储数据，只能从第一个位置连续存储，若存2个数据则必须第0个位置存1个，第1个位置存1个。顺序表的优势：因为空间连续，所以在其空间内可以任意访问；缺点是空间释放要整体释放。

顺序表一般可以分为：静态顺序表和动态顺序表。

静态顺序表

静态顺序表使用定长数组（静态数组）存储元素——不太实用。

//1.结构的定义
#define N 100
struct SeqList//顺序表的结构体
{
	int a[N];
	int size;//记录存储了多少个数据
};
 
//2、拿这个结构定义一个变量，是对这个变量进行初始化

N是固定大小的，存在的问题是：开小了不够用；开大了存在空间浪费，不够灵活满足需求。

动态顺序表

动态顺序表使用动态开辟的数组存储——在实际中更实用

struct SeqList
{
	SLDataType* a;//用数组的指针
	int size;//记录存储数据个数
	int capacity;//存储空间大小
};

通常对数据结构首先进行操作的是在增删查改之前需要的初始化函数。

顺序表常见的几个操作是在尾部的插入和删除、头部的插入和删除。

实现一个顺序表

梳理顺序表逻辑

顺序表的头部插入：扩容——移动数据

头部插入，需要保证数据是连续的，并且保证从头到尾存储，则从头部插入数据就需要把原有数据向后移动，这里必须从后向前移动。
把4向后移一个，把3向后移一个，把2向后移一个，把1向后移一个，把0向后移一个，然后在头部放入这个数据。
这里每向后移一个，为了防止