一、 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的。
线性表在物理上存储时，通常以数组和链式结构的形式.
二、 顺序表概念及结构
顺序表一般可以分为:
1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。
三、接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
基本增删查改接口
//对数据管理 --- 增删查改 void SLInit(SL* ps); //初始化 void SLDestory(SL* ps); //释放 void SLPrint(SL* ps); //打印 void SLCheakCapacity(SL* ps); //检查容量 -- 扩容 //头插头删 尾插尾删 void SLPushBack(SL* ps, SLDateType x); //尾插 void SLPopBack(SL* ps); //尾删 void SLPushFront(SL* ps, SLDateType x);//头插 void SLPopFront(SL* ps); //头删 //返回下标，没找到返回-1 int SLFind(SL* ps, SLDateType); //查找元素，返回下标 //在pos位置插入x void SLInsert(SL* ps, int pos, SLDateType x); //任意位置插入 //在pos位置删除x void SLErase(SL* ps, int pos); //任意位置删除 void SLModify(SL* ps, int pos, SLDateType x);//修改
1. 创建
由于在实际工程中，项目的实现都是采用模块化进行实现的。所以在此处博主也采用了模块化的方式进行实现。
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> //动态顺序表 typedef int SLDateType; typedef struct SeqList { SLDateType* a;//指向动态开辟的数组 int size; //有效数据的个数 int capacity;//容量空间的大小 }SL;
为了后续好修改类型数据，在此采用typedef将结构体类型struct SeqList 重新命名为SL。
在实际开发过程中，为了开发人员更好的输入数据，一般我们会将输入数据的数据类型重命名为SLDateType。（在本篇博客中，采用typedef将其数据类型int重命名为SLDateType）
2. 初始化
初始化时，理论上我们只需要开辟一个空间并置为空指针，并将结构体中的数据全部初始化为0即可。
但在实际开发过程中，我们一般会开辟一定大小的空间（本篇博客开4个空间，但具体开多少，各位可自行选择）。
代码实现：
void SLInit(SL* ps) { assert(ps); ps->a = (SLDateType*)malloc(4 * sizeof(SLDateType));//开辟4个空间 if (ps->a == NULL) { perror("malloc"); exit(-1); } //开辟成功 ps->capacity = 4;//开辟多少空间，容量变为多少 ps->size = 0; }
3. 扩容
在后续我们插入数据时，已开辟容量可能已经无法满足需求了。这是就需要扩容。
那一次扩到多少呢？
在实际开发过程中我们一般是扩到原有空间的两倍。（当然你也可以开1000倍，只要后台空间足够大）
代码实现：
void SLCheakCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity) { //开辟空间X2 SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * sizeof(SLDateType) * 2); if (tmp == NULL) { perror("realloc"); exit(-1); } //开辟成功 ps->a = tmp; ps->capacity *= 2; } }
4. 打印
上述函数定义完成后，我们通常需要测试打印以下相关数据，来判断相关函数定义是否成功.
代码实现：
void SLPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
5. 销毁
由于上述空间是动态开辟的。所以当我们使用完时，要及时销毁，释放空间。
代码实现：
void SLDestory(SL* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; }
6. 尾插
尾插：在尾部插入一个数据。
但是在数据的尾部插入一个数据时，我们需要考虑一个问题：原有空间是否可以容纳新的数据，是否需要扩容。
所以我们在插入数据时，要先调用 SLCheakCapacity函数来检查是否需要扩容。
代码实现：
void SLPushBack(SL* ps, SLDateType x) { assert(ps); SLCheakCapacity(ps);//检查是否需要扩容 ps->a[ps->size] = x; ps->size++; }
7. 尾删
尾删：删除尾部最后的一个元素。
但尾删同样也要考虑一个问题，空间中是否还有数据给我们删除。
所以在进行尾删时，我们可以采用assert函数断言空间中还有数据。
代码实现：
void SLPopBack(SL* ps) { assert(ps); assert(ps->size >= 0);//断言空间中还有元素 ps->size--;//下标减1 }
在删除数据时，我们不用将原有数据删除。只需要下标减1即可。
原因在于我们时根据下标来使用数据的，当下标减1后，尾部最后一个数据便无法进行访问。
Tips:
- 越界是不一定报错的，系统对越界的检查是一种设岗抽查。
- 以VS2022为例，微软公司在数据的开始前和结尾后的一小段空间设有一些特殊值。当程序结束或内存空间释放时，编译器就会检查这些值是否发生改变, 从而触发程序的保护机制。但如果这些值没有发生改变，即使发生越界访问，程序也不会报错。就像如果你酒驾，交警只在二环设关卡，但只要你不去二环，你就没事不会被发现。（每个编译器略有差异）
8. 头插
头插：在数据最开始地方插入数据。
同样，头插也要调用 SLCheakCapacity函数来检查空间是否足够，是否需要扩容。
代码实现：
void SLPushFront(SL* ps, SLDateType x) { assert(ps); SLCheakCapacity(ps);//检查是否需要扩容 //移动数据 int i = ps->size-1; while (i >= 0) { ps->a[i + 1] = ps->a[i]; i--; } //移动数据完成，插入元素。同时有效个数加1 ps->a[0] = x; ps->size++; }
9. 头删
头删：删除数据最开始的元素。
思路和头插类似，只要下标从1开始，所有数据依次向前移动1位，再把有限个数减1即可。
同时头删也需要使用assert函数断言原有空间中还有数据可以删除。
代码实现：
void SLPopFront(SL* ps) { assert(ps); assert(ps->size >= 0);//空间中还有数据可以删除 //移动数据 for (int begin = 1; begin < ps->size; begin++) { ps->a[begin - 1] = ps->a[begin]; } ps->size--;//有效个数减1 }
10. 插入任意位置数据
由于顺序表要求数据是连续存放的,所以我们只需要找到输入位置的下标pos即可。
【代码思路】：首先我们要检查输入下标是否合法，是有效下标；并检查是否有足够空间来容纳新数据，是否需要扩容。之后从输入的数据下标开始，所有元素向后移动一位，并把新数据插入到下标为pos处即可。
代码实现：
void SLInsert(SL* ps, int pos, SLDateType x) { assert(ps); assert(pos >= 0 && pos <= ps->size);//检查下标是否合法 SLCheakCapacity(ps); //检查空间是否足够 //移动数据 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; }
11. 删除任意位置数据
【代码思路】：和插入任何位置数据思想类似。首先我们要检查输入下标pos是否合法。之后从输入下标开始，后一个元素拷贝到前一个元素空间。
代码实现：
void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);//下标是否合法 //移动数据 int begin = pos+1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
12. 查找
【代码思路】：要查找某个元素。由于这里只是最简单的查找，我们直接暴力查找，遍历整个数组返回下标即可。更为复杂的数据查找，会有更高阶的数据结构来实现。
代码实现：
int SLFind(SL* ps, SLDateType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (x == ps->a[i]) return i; } return -1; }
13. 修改
【代码思路】： 要实现修改数据，我们只需要先判断输入下标是否合法。在将对应下标数据进行修改即可。
代码实现：
void SLModify(SL* ps, int pos, SLDateType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
四：所有代码
SeqList.h源文件
#include <assert.h> #include <stdlib.h> //动态顺序表 typedef int SLDateType; typedef struct SeqList { SLDateType* a; int size; int capacity; }SL; //对数据管理 --- 增删查改 void SLInit(SL* ps); void SLDestory(SL* ps); void SLPrint(SL* ps); void SLCheakCapacity(SL* ps); //头插头删 尾插尾删 void SLPushBack(SL* ps, SLDateType x); void SLPopBack(SL* ps); void SLPushFront(SL* ps, SLDateType x); void SLPopFront(SL* ps); //返回下标，没找到返回-1 int SLFind(SL* ps, SLDateType); //在pos位置插入x void SLInsert(SL* ps, int pos, SLDateType x); //在pos位置删除x void SLErase(SL* ps, int pos); void SLModify(SL* ps, int pos, SLDateType x);
SeqList.c头文件
#define _CRT_SECURE_NO_WARNINGS #include "SeqList.h" void SLInit(SL* ps) { assert(ps); ps->a = (SLDateType*)malloc(4 * sizeof(SLDateType)); if (ps->a == NULL) { perror("malloc"); exit(-1); } //开辟成功 ps->capacity = 4; ps->size = 0; } void SLDestory(SL* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; } void SLPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } void SLCheakCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity) { SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * sizeof(SLDateType) * 2); if (tmp == NULL) { perror("realloc"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } } void SLPushBack(SL* ps, SLDateType x) { assert(ps); /*SLCheakCapacity(ps); ps->a[ps->size] = x; ps->size++;*/ SLInsert(ps, ps->size, x); } void SLPopBack(SL* ps) { assert(ps); assert(ps->size >= 0); /*ps->size--;*/ SLErase(ps, 0); } void SLPushFront(SL* ps, SLDateType x) { assert(ps); SLCheakCapacity(ps); //移动数据 /*int i = ps->size-1; while (i >= 0) { ps->a[i + 1] = ps->a[i]; i--; } ps->a[0] = x; ps->size++;*/ SLInsert(ps, 0, x); } void SLPopFront(SL* ps) { assert(ps); assert(ps->size >= 0); /*for (int begin = 1; begin < ps->size; begin++) { ps->a[begin - 1] = ps->a[begin]; } ps->size--;*/ SLErase(ps, 0); } int SLFind(SL* ps, SLDateType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (x == ps->a[i]) return i; } return -1; } void SLInsert(SL* ps, int pos, SLDateType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheakCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; } void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos+1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; } void SLModify(SL* ps, int pos, SLDateType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
