目录
一.线性表
线性表（linear_list）是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。
再稍复杂的线性表中，一个数据元素可以由若干个数据项（item）组成。在这种情况下，常把数据元素成为记录（record），含有大量记录的线性表又称文件（file）。
有且只有一个开始的结点，并且除了开始结点外，其余结点都有直接前驱，并且除了结束外，其余结点都有直接后继。
线性表按照其数据的存储方式分为两种：
1.顺序表：数据结点之间，逻辑相邻，物理也相邻
2.链表：数据结点之间，逻辑相邻，物理不一定相邻
二.顺序表的实现
1.基础知识
将逻辑上相邻的数据元素，存储在物理上也相邻的存储单元中。用一组地址连续的存储单元依次存储线性表的数据元素。
2.代码实现
头文件的设计：
#pragma once
//可扩容的顺序表的结构体设计
#define LIST_INIT_SIZE 100 //初始大小
#define LISTINCREMENT 10
typedef int ELEM_TYPE;
typedef struct Sqlist {
ELEM_TYPE* elem;//存储空间基址（用来接收malloc返回值在堆上申请的连续空间块开始地址）
int length;
int listsize;
}Sqlist,*PSqlist;
//初始化
void Init_Sqlist(struct Sqlist*sq);
//头插
bool Insert_head(struct Sqlist* sq,ELEM_TYPE val);
//尾插
bool Insert_tail(struct Sqlist* sq,ELEM_TYPE val);
//按位置插
bool Insert_pos(struct Sqlist* sq,int pos, ELEM_TYPE val);
//头删
bool Del_head(struct Sqlist* sq);
//尾删
bool Del_tail(struct Sqlist* sq);
//按位置删
bool Del_pos(struct Sqlist* sq,int pos);
//按值删
bool Del_val(struct Sqlist* sq, int val);
//判空
bool IsEmpty(struct Sqlist* sq);
//判满
bool IsFull(struct Sqlist* sq);
//扩容函数
void Inc(struct Sqlist *sq);
//查找
int Search(struct Sqlist* sq,ELEM_TYPE val);
//清空
void Clear(struct Sqlist* sq);
//销毁
void Destory(struct Sqlist* sq);
//打印
void Show(struct Sqlist* sq);功能实现：
（1）顺序表初始化
首先申请一段连续的内存空间用于构建顺序表，并对头结点成员赋值
#define LIST_INIT_SIZE 100
//初始化 对头节点里面的成员赋值
void Init_Sqlist(struct Sqlist* sq) {
sq->elem = (ELEM_TYPE*)malloc(LIST_INIT_SIZE*sizeof(int));//申请内存
assert(sq->elem != NULL);//安全性处理
sq->length = 0;//初始有效数据个数赋值为0
sq->listsize = LIST_INIT_SIZE;//长度为初始长度（申请的内存空间）
}（2）头插，尾插，按位置插
若顺序表已满，则需要进行扩容之后在进行添加数据；若未满则直接进行操作
//头插
bool Insert_head(struct Sqlist* sq, ELEM_TYPE val) {
//1.判断指针sq是否为NULL
assert(sq->elem!=NULL);
//2.判满，满了扩容
if (IsFull(sq)) {
Inc(sq);
}
//3.向后挪动元素
for (int i = sq->length-1; i > 0;i--) {
sq->elem[i+1] = sq->elem[i];
}
//4.插入有效值
sq->elem[0] = val;
//5.length+1
sq->length++;
return true;
}
//尾插
bool Insert_tail(struct Sqlist* sq, ELEM_TYPE val) {
//1.判断指针sq是否为NULL
assert(sq!=NULL);
//2.判满，满了扩容
if (IsFull(sq)) {
Inc(sq);
}
//3.插入有效值
sq->elem[sq->length] = val;
//4.length+1
sq->length++;
return true;
}
//按位置插
bool Insert_pos(struct Sqlist* sq, int pos, ELEM_TYPE val) {
//将插入位置元素和后面的元素整体向后挪动
//1.判断指针sq是否为NULL
assert(sq!=NULL);
//2.判满，满了则扩容
if (IsFull(sq)) {
Inc(sq);
}
//3.向后挪动元素
for (int i = sq->length - 1; i >= pos;i++) {
sq->elem[i+1] = sq->elem[i];
}
//4.插入有效值
sq->elem[pos] = val;
//5.length+1
sq->length++;
return true;
}（3）头删，尾删，按位置删
若顺序表为空，则不需要进行删除；若不为空，则删除
//头删
bool Del_head(struct Sqlist* sq) {
//插入需要判满，删除需要判空
assert(sq!=NULL);
//1.判空
if (IsEmpty(sq)) {
return false;
}
//2.待删元素后面的值向前覆盖
for (int i = 0; i < sq->length-1;i++) {
sq->elem[i] = sq->elem[i+1];
}
//3.length-1
sq->length--;
return true;
}
//尾删
bool Del_tail(struct Sqlist* sq) {
//安全性处理
assert(sq!=NULL);
//1.判空
if (IsEmpty(sq)) {
return false;
}
//2.删除（有效长度减一）
sq->length--;
return true;
}
//按位置删
bool Del_pos(struct Sqlist *sq, int pos) {
//1.安全性处理 断言（判断sq指针不指向NULL）
assert(sq!=NULL);
//2.判断pos的合法性 pos为0时为头删
if (pos>=0&&pos<sq->length) {
return false;
}
//3.判空 （判断sq指向的不是一个空的顺序表）
if (IsEmpty(sq)) {
return false;
}
//4.向前覆盖
for (int i = pos; i < sq->length-1; i++) {
sq->elem[i]=sq->elem[i+1];
}
//5.length-1
sq->length--;
return true;
}（4）查找，按值删
按值删除元素时，需要确定该值所在的数据在什么位置，得到该数据的位置之后，进行按位置删即可。
//查找
int Search(struct Sqlist* sq, ELEM_TYPE val) {
//查找这个元素在顺序表中第一次出现的位置
//遍历
assert(sq!=NULL);
for (int i = 0; i < sq->length;i++) {
if (sq->elem[i] == val) {
return i;
}
}
return -1;
}
//按值删（这个值在顺序表中第一次出现的位置，然后删除）
bool Del_val(struct Sqlist* sq, int val) {
//1.断言 安全性处理
assert(sq!=NULL);
//2.查找元素所在的位置 找到返回下标 没找到返回-1
int tmp = Search(sq, val);
if (tmp == -1) {
return false;
}
//3.按位置删
return Del_pos(sq, tmp);
}（5）判空，判满，扩容，清空，销毁，打印
在顺序表的增删过程中，由于存在数据已满或者数据为空的情况，在此基础上进行增删数据，程序容易崩溃。所以在进行增删数据操作之前，要进行判空，判满等安全性处理。
在删除数据时，若已经为空，则不需要进行删除；增加数据时，若已满，则需要进行扩容。
//判空
bool IsEmpty(struct Sqlist* sq) {
assert(sq!=NULL);
//有效长度是否为0
return sq->length == 0;
}
//判满
bool IsFull(struct Sqlist* sq) {
assert(sq!=NULL);
//有效长度和顺序表总容量进行比较
return sq->length == sq->listsize;
}
//扩容函数
void Inc(struct Sqlist* sq) {
sq->elem =(ELEM_TYPE*)realloc(sq->elem,(sq->listsize*sizeof(int)*2));
assert(sq!=NULL);
//按两倍扩容
sq->listsize *= 2;
}
//清空
void Clear(struct Sqlist* sq) {
//有效长度为0
sq->length = 0;
}
//销毁
void Destory(struct Sqlist* sq) {
//将数据存储空间都释放掉
free(sq->elem);
sq->length = 0;
sq->listsize = 0;
}
//打印
void Show(struct Sqlist* sq) {
//遍历
for (int i = 0; i < sq->listsize;i++) {
printf("%d", sq->elem[i]);
}
printf("\n");
}三.顺序表的优缺点
顺序表的操作需要挪动元素，插入的话，需要向后挪动，删除的话，需要向前覆盖，时间复杂度O(n)，效率不高。但是，如果在尾部（尾删尾插）操作，则效率极高为O(1),因为尾部操作不需要挪动元素。
顺序表使用的场景：
适合的场景：支持直接访问；在尾部的插入和删除
不适合的场景：在头部和中间位置，插入和删除操作较多；频繁的扩容，扩容代价高。