一.顺序表的概念及存储结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表可以分为静态顺序表和动态顺序表。
1.1储存结构
静态顺序表：使用定长数组存储元素；
动态顺序表：数组的大小是根据存储的数据个数，如果满了就动态开辟出来的，相对而言不会造成空间的浪费；
二.顺序表的实现
静态顺序表 只适用于确定知道需要存多少数据的场景；
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。例如：如果数组的大小定为200，却只储存了几十个数据，和动态的顺序表相比，空间浪费更大；所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
一.功能函数的实现（含图解）
1.初始化函数
功能：对结构体内成员进行初始化操作；
代码实现：
void InitList(SL* s)
{
assert(s); //断言，防止传入空指针
s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);
if (s->a == NULL) //这里最开始开辟四个存储数据类型的大小
{
perror("malloc fail");
exit(-1);
}
s->size = 0; //存储的有效数据个数为0
s->capacity = 4; //空间置成4
}2.顺序表的销毁
功能：对动态开辟的空间进行销毁，空间释放
代码实现：
void DestoryList(SL* s)
{
assert(s);
free(s->a); //释放动态开辟的空间
s->a = NULL; //置空
s->capacity = s->size = 0;
}3.顺序表的打印
代码实现：
void SListPrintf(SL* s)
{
assert(s);
if (s->size < 0) //如果没有数据，则直接返回
{
return;
}
for (int i = 0; i < s->size; i++)
{
printf("%d ", s->a[i]); //遍历依次打印
}
printf("\n"); //打印完换行
}4.扩容函数
功能：检查是否需要扩容
代码实现：
void CheckCapacity(SL* s)
{
assert(s);
if (s->capacity == s->size) //相等则说明空间已经满了
{
SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity); //二倍扩容
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
s->a = tmp;
s->capacity *= 2;
}
}5.尾插函数
功能：在顺序表最后插入一个数据
代码实现：
void PushBack(SL* s, SLDateType n)
{
assert(s);
CheckCapacity(s); //检查空间是否满
s->a[s->size] = n; //直接插入到数组最后
s->size++; //有效数据个数++
}6.尾删函数
功能: 删除顺序表的最后一个数据
代码实现：
void PopBack(SL* s)
{
assert(s);
assert(s->size > 0); //当数组中有效数据个数为0时，不能再删除
s->size--; //数据个数--
}7.头插函数
功能：在顺序表最前面插入一个数据
代码实现：
void PushFront(SL* s, SLDateType n)
{
assert(s);
CheckCapacity(s); //检查扩容
int end = s->size;
while (end>0)
{
s->a[end] = s->a[end - 1]; //挪动数据
end--;
}
s->a[0] = n;
s->size++;
}图解：
性能分析：头插一个数据，首先需要将全部数据一次往后挪一个位置，时间复杂度：O(N)
是在原数组上进行挪动的，空间复杂度：O(1)
8.头删函数
功能：删除表中第一个元素
代码实现：
void Popfront(SL* s)
{
assert(s);
assert(s->size > 0); //size为0时，不能再删除
for (int i = 0; i < s->size; i++)
{
s->a[i] = s->a[i+1]; //向前挪动数据
}
s->size--;
}图解：
性能分析：头删一个数据，首先需要将全部数据一次往前挪一个位置，将第一个元素覆盖掉，时间复杂度：O(N)
是在原数组上进行挪动的，空间复杂度：O(1)
9.插入函数
功能：在某个位置插入一个数据
代码实现：
void SListInsert(SL* s, int pos, SLDateType n)
{
assert(s);
assert(pos >= 0 && pos <= s->size); //判断pos合法
int end = s->size;
int begin = pos;
while (begin < end)
{
s->a[end] = s->a[end - 1]; //挪动数据
end--;
}
s->a[pos] = n; //修改数据
s->size++;
}
图解：
性能分析：中间插入一个数据和头插差不多，首先需要将该位置后面的全部数据依次往后挪一个位置，将该位置空出来，再将该数据插入，时间复杂度：O(N)
是在原数组上进行挪动的，空间复杂度：O(1)
10.删除函数
功能：删除数组中任何位置的数据
代码实现：
void SListErase(SL* s, int pos)
{
assert(s);
assert(pos >= 0 && pos < s->size); //pos范围合法判断
int cur = pos;
while (cur < s->size)
{
s->a[cur] = s->a[cur+1]; //挪动位置
cur++;
}
s->size--;
}
图解：
性能分析：删除一个数据与头删差不多，首先需要待删数据位置后面全部数据依次往前挪一个位置，将待删元素覆盖掉，时间复杂度：O(N)
是在原数组上进行挪动的，空间复杂度：O(1)
11.查找函数
功能：查找顺序表中某个数据，返回下标
代码实现：
int SListFind(SL* s,SLDateType n)
{
assert(s);
for (int i = 0; i < s->size; i++) //遍历寻找
{
if (s->a[i] == n) //找到了返回下标
{
return i;
}
}
printf("顺序表中无该数据\n");
exit(-1);
}性能分析：将数组中的数据遍历一遍；时间复杂度：O(N)
空间复杂度：O(1)
12.修改函数
功能：修改数组中某个数据
代码实现：
void SListModify(SL* s, int pos,SLDateType n)
{
assert(s);
assert(pos >= 0 && pos < s->size);
s->a[pos] = n; //直接通过下标访问修改
}三.总代码
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
struct SeqList
{
SLDateType* a; //指向一个数组的指针
int size; //记录数据个数
int capacity; //记录容量，如果与数据个数相等就扩容
};
typedef struct SeqList SL;
void InitList(SL* s);
void SListPrintf(SL* s);
void PushBack(SL* s, SLDateType n);
void PushFront(SL* s, SLDateType n);
void PopBack(SL* s);
void Popfront(SL* s);
int SListFind(SL* s,SLDateType n);
void SListModify(SL* s, int pos, SLDateType n);
void SListErase(SL* s, int pos);
void SListInsert(SL* s, int pos, SLDateType n);
void DestoryList(SL* s);
#include"SeqList.h"
void InitList(SL* s)
{
assert(s); //断言，防止传入空指针
s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);
if (s->a == NULL) //这里最开始开辟四个存储数据类型的大小
{
perror("malloc fail");
exit(-1);
}
s->size = 0; //存储的有效数据个数为0
s->capacity = 4; //空间置成4
}
void SListPrintf(SL* s)
{
assert(s);
if (s->size < 0) //如果没有数据，则直接返回
{
return;
}
for (int i = 0; i < s->size; i++)
{
printf("%d ", s->a[i]); //遍历依次打印
}
printf("\n"); //打印完换行
}
void CheckCapacity(SL* s)
{
assert(s);
if (s->capacity == s->size) //相等则说明空间已经满了
{
SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity); //二倍扩容
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
s->a = tmp;
s->capacity *= 2;
}
}
void PushBack(SL* s, SLDateType n)
{
assert(s);
CheckCapacity(s); //检查空间是否满
s->a[s->size] = n; //直接插入到数组最后
s->size++; //有效数据个数++
}
void PushFront(SL* s, SLDateType n)
{
assert(s);
CheckCapacity(s); //检查扩容
int end = s->size;
while (end>0)
{
s->a[end] = s->a[end - 1]; //挪动数据
end--;
}
s->a[0] = n;
s->size++;
}
void PopBack(SL* s)
{
assert(s);
assert(s->size > 0); //当数组中有效数据个数为0时，不能再删除
s->size--; //数据个数--
}
void Popfront(SL* s)
{
assert(s);
assert(s->size > 0); //size为0时，不能再删除
for (int i = 0; i < s->size; i++)
{
s->a[i] = s->a[i+1]; //向前挪动数据
}
s->size--;
}
int SListFind(SL* s,SLDateType n)
{
assert(s);
for (int i = 0; i < s->size; i++) //遍历寻找
{
if (s->a[i] == n) //找到了返回下标
{
return i;
}
}
printf("顺序表中无该数据\n");
exit(-1);
}
void SListModify(SL* s, int pos,SLDateType n)
{
assert(s);
assert(pos >= 0 && pos < s->size);
s->a[pos] = n; //直接通过下标访问修改
}
void SListErase(SL* s, int pos)
{
assert(s);
assert(pos >= 0 && pos < s->size); //pos范围合法判断
int cur = pos;
while (cur < s->size)
{
s->a[cur] = s->a[cur+1]; //挪动位置
cur++;
}
s->size--;
}
void SListInsert(SL* s, int pos, SLDateType n)
{
assert(s);
assert(pos >= 0 && pos <= s->size); //判断pos合法
int end = s->size;
int begin = pos;
while (begin < end)
{
s->a[end] = s->a[end - 1]; //挪动数据
end--;
}
s->a[pos] = n; //修改数据
s->size++;
}
void DestoryList(SL* s)
{
assert(s);
free(s->a); //释放动态开辟的空间
s->a = NULL; //置空
s->capacity = s->size = 0;
}
四.顺序表的性能分析
问题：
1. 中间/头部的插入删除，时间复杂度为O(N);
2. 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗;
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间;
