今天介绍数据结构中的顺序表。
顺序表和链表都是最基础和最常见的实用的数据结构。
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。（也就是说在逻辑上是依次存储的）但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表Sequential List
顺序表是用一段 物理地址连续的存储单元 依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表简单来说就是一个数组，要求这个数组的空间是连续的，且存储的数据也必须是从头开始连续存储。
静态顺序表
静态顺序表：使用定长数组存储元素。
静态顺序表的长度是固定的。 虽然在不少的书籍和课本上都喜欢实用静态顺序表去讲解和测试。但是静态顺序表的空间是固定的，空间给大了，很浪费；空间给小了，不够实用。所以在我们后面的学习中，我们需要去学习动态的顺序表。它的实用性实践性更高，当然更加难。
动态顺序表
动态顺序表：使用动态开辟的数组存储。
动态顺序表虽然可以规避一些空间浪费，但是还是会有一点点浪费。
实用动态内存开辟函数去开辟空间的时候，每次空间不够的时候都会扩容，每次扩容都会付出一定程度上的代价。所以每次扩容可以稍微多扩容一点点，减少扩容的频率。扩容是根据需求扩容，那我们最常用的扩容倍数就是：2倍 1.5倍。但是不是一定要求是这些倍数。2倍数是一个相对合适的量，扩容的频率会越来越低，具体情况具体分析！
主函数Test.c
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。本章实现顺序表的头插尾插头删和尾删等功能进行实现。
int main() { SL ps;//创建一个结构题变量-传地址调用🆗-形参是实参的一份临时拷贝 test1(&ps);//测试尾插 test2(&ps);//测试头插 test3(&ps);//测试尾删 test4(&ps);//测试头删 return 0; }
test1
#include"SeqList.h" void test1(SL*ps)//测试尾插 { SLInit(ps); SLPushBack(ps, 10); SLPushBack(ps, 20); SLPushBack(ps, 30); SLPushBack(ps, 40); SLPrint(ps); SLDestroy(ps); }
test2
void test2(SL*ps)//测试头插 { SLInit(ps); SLPushFront(ps, 10); SLPushFront(ps, 20); SLPushFront(ps, 30); SLPushFront(ps, 40); SLPrint(ps); SLDestroy(ps); }
test3
void test3(SL*ps)//测试头删 { SLInit(ps); SLPushBack(ps, 10); SLPushBack(ps, 20); SLPushBack(ps, 30); SLPushBack(ps, 40); SLPopBack(ps); SLPopBack(ps); SLPrint(ps); SLDestroy(ps); }
test4
void test4(SL*ps)//测试尾删 { SLInit(ps); SLPushBack(ps, 10); SLPushBack(ps, 20); SLPushBack(ps, 30); SLPushBack(ps, 40); SLPopFront(ps); SLPopFront(ps); SLPrint(ps); SLDestroy(ps); }
头文件&函数声明SeqList.h
头文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h>//断言
函数声明
- SeqList声明
//声明一个结构体 typedef int SLDataType; typedef struct SeqList { SLDataType* a;//如果后期a的类型改变就很方便 int size;//有效数据 int capacity;//空间容量 }SL;//SL是这个结构体的类型，用typedef定义更加方便了
- SeqList初始化
1. //初始化 2. void SLInit(SL* ps);
- SeqList释放&销毁
1. //释放销毁 2. void SLDestroy(SL* ps);
- SeqList展示
1. //展示 2. void SLPrint(SL* ps);
- 尾插 头插 尾删 头删
void SLPushBack(SL* ps, SLDataType x);//尾插 void SLPushFront(SL* ps, SLDataType x);//头插 void SLPopBack(SL* ps);//尾删 void SLPopBack(SL* ps);//头删
函数实现SeqList.c
初始化SLInit
#include"SeqList.h" //初始化 void SLInit(SL* ps) { ps->a = NULL; ps->size = 0; ps->capacity = 0; } //关于初始化 可以首先置为NULL 也可以首先放点值 // memset一般用于数组初始化 直接初始化更加清晰
释放销毁SLDestroy
//销毁 void SLDestroy(SL* ps) { if (ps->a != NULL) { free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0; } }
扩容SLCheckCapacity
这个函数是我们自己封装，可以不用去函数声明，秘密。但是记住一定要在使用这个CheckCapacity 之前我们一定要声明或者放在使用之前。
扩容就要用到我们在【动态内存管理】讲解的realloc函数了，扩容分为原地扩容和异地扩容，忘记的小伙伴再复习一下哦，一定要熟悉【戳一戳】：C语言之动态内存管理篇（1）-CSDN博客
原地扩容和异地扩容判断和最优写法
realloc函数存储空间起始位置是可以传NULL空指针的
realloc函数所需要开辟的空间一定要包含旧空间的大小
异地扩容对之前的空间不需要手动free,而是操作系统已经帮助释放了原来旧的空间
//扩容 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity)//容量满了需要扩容的条件 { int newcapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity); SLDataType* tmp = (SLDataType*)raelloc(ps->a, sizeof(SLDataType) * newcapacity); if (tmp == NULL) { perror("CheckCapacity");// return; } ps->a = tmp; ps->capacity = newcapacity; } }
打印SLPrint
//展示 void SLPrint(SL* ps) { int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
尾插SLPushBack
- 首先在size位置放值x
- size往后移动++
//尾插 void SLPushBack(SL* ps, SLDataType x) { SLCheckCapacity(ps);//扩容 ps->a[ps->size] = x; ps->size++; }
头插SLPushFront
在顺序表的前面插入数据，是没有向前扩容和插入空间这种做法的。这段空间整体是连续的，地址是连续的，又要求数据是连续的。所以我们唯一可用的方法就是把数据往后挪动。当然我们可以用函数memcpy和memove来实现，这里我们就手动来写。如果不想挪动数据，只有一种方法就是使用链表。
- 首先把size-1的位置移动到size的位置，整体挪动完成。
- 再在第一个位置放数值
void SLPushFront(SL* ps, SLDataType x) { SLCheckCapacity(ps); int end = ps->size - 1; while (end >= 0)//注意可以等于0 size为1 但是不能为负数会越界访问 { ps->a[end+1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; }
还想补充到的是：尽量别频繁的使用头插法，大量的使用不太行。 
尾删SLPopBack
尾删也是非常简单的，有人可能会说把要删除的值赋值为-1或者NULL。但是我们并不能确定顺序表元素的类型，万一类型改变，这里再去改变就不方便了。而且万一这个值本来就是-1。所以直接size--即可。后期插入等操作会把这个值给覆盖掉。
- size-- 意味着着只有--之后的数值有效。意味着我们头尾插会把无效数据覆盖。
- 无效数据不需要free
- 第一动态内存是不支持分期free。
- 第二后续操作会覆盖无效数据，空间可以重复利用。
- 第三单独free,顺序表的空间就不连续了
//尾删 void SLPopBack(SL* ps) { assert(ps->size);//本质问题就是害怕这个顺序表空了还在删除 ps->size--; }
规避过度头删
头删SLPopFront
- 头插是从后向前挪动数据覆盖
- 头删是从前向后挪动数据覆盖
- size--即可
//头删 void SLPopFront(SL* ps) { assert(ps->size); int begin = 1; while (begin < ps->size) { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; }
✔✔✔✔✔最后，感谢大家的阅读，若有错误和不足，欢迎指正。下章继续顺序表。
- 结构体传址调用，形式参数是实际参数的一份临时拷贝
- size永远指向所存储元素的下一个位置，顺序表是数组，下标从0开始。
- realloc函数的注意点
- assert的点
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱：2784139418@qq.com】
