一、线性表
线性表是一种逻辑结构，表示元素与元素之间的相邻关系，顺序表和链表是一种存储结构
第一个元素具有唯一后继，最后一个元素具有唯一前驱，中间的元素具有唯一的前驱和后继
二、顺序表
顺序表是线性表的顺序存储，用一段连续的内存空间依次存放数据元素
逻辑地址相邻的元素，内存地址也相邻
优点：支持随机访问；空间利用率高；尾插尾删效率高O(1)
缺点：扩容代价大；头插，按位置插，删除需要搬动数据
适用于：适用于需要大量随机访问，插入删除操作较少，就算需要这些操作也是在尾部进行
顺序表的分类：分为定容顺序表和可扩容顺序表
1. 顺序表的创建
1.1 定容顺序表
定长数组存储
typedef int Elementype; #define N 6 //定容顺序表结构体定义 typedef struct seqlist { //连续存储空间 int arr[N]; //有效元素长度 int length; //最大容量 int maxsize; }seqlist;1.2 可扩容顺序表
动态开辟的数组存储
//可扩容顺序表 //类型重定义 typedef int Elementype; //初始格子数,初始化时malloc申请的格子数量 #define INTSIZE 10 //顺序表结构体定义 typedef struct seqlist { //内存连续的存储空间 Elementype* arr; //有效元素长度 int length; //最大容量 int maxsize; }seqlist;2. 顺序表的初始化
//顺序表的初始化 void Init_seqlist(seqlist* plist) { //1.先安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.申请空间 plist->arr = (ElemType*)malloc(INTSIZE * sizeof(ElemType)); //判空 if (plist->arr == nullptr) exit(EXIT_FAILURE); //3.有效元素为0 plist->length = 0; //4.初始申请的空间个数为 plist->maxsize = INTSIZE; }首先要对函数进行安全判断，DeBug版本用的是断言，release版本用的是if-else判空
然后用malloc在堆区购买一片连续的内存空间
一开始有效元素个数为0,容量为初始宏定义的个数
3. 顺序表扩容
//扩容 bool InCrease(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.购买新结点 ElemType* p = (ElemType*)realloc(plist->arr, plist->maxsize * 2 * sizeof(ElemType)); //3.判断空间是否申请成功，成功的话再将新申请的空间给arr if (p == NULL) return false; plist->arr = p; //更新容量 plist->maxsize = plist->maxsize * 2; return true; }首先需要安全处理，然后使用新指针接收realloc购买2倍原来使用malloc和calloc购买的容量的大小（注意：这里不能是宏的二倍，因为如果是宏定义的二倍，会导致每一次扩容后的数量都是2*INTSIZE），判断空间申请是否成功，成功后再将地址传给顺序表，否则会导致顺序表丢失
4. 判满
//判满 bool IsFull(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.若有效元素个数==最大容量则已满 return plist->length == plist->maxsize; }如果有效元素个数和申请的空间容量相等则已满，返回true
5. 判空
//判空 bool IsEmpty(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.若有效元素个数==0则为空 return plist->length == 0; }如果有效元素个数==0则为空，返回true
6. 顺序表插入
6.1 头插
//顺序表头插 bool Insert_head(seqlist* plist,int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判满，若已满则扩容,如果扩容失败则退出 if (IsFull(plist)) { if (InCrease(plist) == false) return false; } //3.将原来顺序表中的元素从尾部开始挨个后移 memmove(plist->arr + 1, plist->arr, sizeof(ElemType) * plist->length); //4.再将新的元素插入arr[0] plist->arr[0] = val; //5.再更新有效元素个数 plist->length++; return true; }首先安全处理
然后判满，如果已满扩容，如果扩容失败直接退出
使用memmove将元素从尾部挨个后移
【memmove在处理内存折叠时：如果目标地址高于源地址，从高地址往低地址复制，避免未复制就被覆盖的现象】
再将val插入空出来的地方
再更新有效元素个数
6.2 尾插
//顺序表的尾插 bool Insert_back(seqlist* plist, int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判满 if (IsFull(plist)) { if (InCrease(plist) == false) return false; } //3.尾部插入 plist->arr[plist->length] = val; //4.更新有效元素个数 plist->length++; return true; }首先安全处理
然后判满，如果已满扩容，扩容失败则退出
然后直接在尾部插入val
插入完成后更新有效元素个数
6.3 按位置插
//按位置插 bool Insert_pos(seqlist* plist, int val, int pos) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判满 if (IsFull(plist)) { if (InCrease(plist) == false) return false; } //3.边界判断 if (pos > plist->length + 1 || pos < 0) return false; //4.在pos位置插入 //2 3 4 5 要在pos=3 下标2位置插入 7 //2 3 7 4 5 memmove(plist->arr + pos, plist->arr + pos - 1, sizeof(ElemType) * (plist->length - pos + 1)); plist->arr[pos - 1] = val; plist->length++; return true; }首先进行安全判断
然后判满，如果已满扩容，扩容失败则退出
然后进行位置插入的边界值判断
然后将插入位置以及之后的元素，从最后一个元素开始，挨个往后移一位
将val插入
有效元素个数++
7. 顺序表删除
7.1 头删
//头删 bool delete_head(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.将所有元素从前往后挨个前移一位 memmove(plist->arr, plist->arr + 1, sizeof(ElemType) * (plist->length - 1)); //4.更新有效元素个数 plist->length--; return true; }首先安全判断
然后判断表是否为空，如果表为空直接退出
如果表不空，将元素从头开始挨个前移
然后将有效元素个数减一
7.2 尾删
//尾删 bool delete_back(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.尾部删除，元素个数直接减一 plist->length--; return true; }首先安全判断
然后判断表是否为空，如果表为空直接退出
如果表不空，然后将有效元素个数减一
7.3 按位置删
//按位置删 bool delete_pos(seqlist* plist, int pos) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.判断要删除的位置的界限 if (pos < 1 || pos > plist->length + 1)return false; //4.从前往后，元素挨个前移 //2 3 4 5 要删除第3位的 memmove(plist->arr + pos - 1, plist->arr + pos, sizeof(ElemType) * (plist->length - pos)); //有效元素个数减1 plist->length--; return true; }首先安全判断
然后判断表是否为空，如果表为空直接退出
如果表不空，将pos位置之后的元素从前往后依次前移一位
有效元素个数减一
7.4 按值删（只删除这个值出现的第一次）
//按值删（只删除这个值出现的第一次） bool Del_val_first(seqlist* plist,int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.查找这个元素第一次出现的位置 int pos = search_seqlist(plist, val) + 1; //4.删除 memmove(plist->arr + pos - 1, plist->arr + pos, sizeof(ElemType) * (plist->length - pos)); plist->length--; return true; }首先安全判断
然后判断表是否为空，如果表为空直接退出
如果表不空，查找要删除元素的下标(注意：此时返回的是下标，pos是当前元素的位置，所以需要+1，才是位置)，然后赋值给pos
将pos位置之后的元素从前往后依次前移一位
有效元素个数减一
7.4 按值删（删除这个值出现的所有）
//按值删（只删除这个值出现的所有次） bool Del_val_ALL(seqlist* plist, int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.将不是val的值存入一个从头开始存 int len = 0; for (int i = 0; i < plist->length; i++) { if (plist->arr[i] != val) plist->arr[len++] = plist->arr[i]; } //4.更新有效元素个数 plist->length = len; return true; }首先安全判断
然后判断表是否为空，如果表为空直接退出
如果表不空，申请一个新的计数器，将不是val的值从头存入arr
有效元素个数更新为计数器的值
8. 查找有效元素是否存在
遍历整个顺序表，有效元素存在返回元素下标，不存在返回-1
int search_seqlist(seqlist* plist, int val) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.遍历顺序表，查找有效元素 for (int i = 0; i < plist->length; i++) { if (plist->arr[i] == val)return i; } return -1; }9. 清空
将有效元素个数置为0即可
//清空 void clear(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } plist->length = 0; }10. 销毁
释放在堆区申请的空间，然后将plist->arr=nullptr，目的是为了避免二次释放，然后将有效元素个数和容量置为0即可
//销毁 void Dstory(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.释放堆空间 free(plist->arr); plist->arr = nullptr; plist->length = 0; plist->maxsize = 0; }11. 打印顺序表
//打印函数 void show(seqlist* plist) { //1.安全处理 assert(plist != nullptr); if (plist == nullptr) { exit(EXIT_FAILURE); } //2.循环打印 printf("当前顺序表中的元素有："); for (int i = 0; i < plist->length; i++) { printf("%d ", plist->arr[i]); } printf("\n"); }12. 测试
int main() { seqlist s; Init_seqlist(&s); printf("length==%d maxsize==%d\n", s.length, s.maxsize); Insert_head(&s, 2); show(&s); Insert_back(&s, 3); Insert_back(&s, 4); Insert_back(&s, 5); Insert_back(&s, 3); Insert_back(&s, 4); Insert_back(&s, 5); Insert_back(&s, 3); Insert_back(&s, 4); Insert_back(&s, 5); show(&s); Insert_pos(&s, 7, 1); show(&s); delete_head(&s); show(&s); delete_pos(&s, 4); show(&s); Del_val_first(&s, 4); show(&s); Del_val_ALL(&s, 3); show(&s); clear(&s); printf("%d\n",s.length); Dstory(&s); }
