上一节我们认识到了什么是数据结构
这一节我们就来实现第一个数据结构的实现
思考一个问题：
假定一个数组，空间为10，已经使用了5个，向其中插入数据的步骤：
1.插入数据，我们先要求数组长度，其中有效数据的个数，判断空余空间的大小，向下标中放入有效数据；（这里需要判断数组是否太满了，剩余空间是否还足够）；
2.如果数据量庞大，我们就要频繁获取数组有限个数，就会影响程序运行速率；
这时候我们就要利用其余数据结构（顺序表、链表、二叉树；更甚至红黑树、B树等更为高级的数据结构）；
那我们就进入，顺序表的学习吧；
顺序表
顺序表是一种线性表
线性表（List）：零个或多个数据元素的有限序列。线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件
顺序表（对数组的封装）的分类
静态顺序表
顾名思义：即是使用定长数组来储存元素
typedef int SLdataTapy; #define N 10 //数组的大小由N决定 typedef struct seqlist { SLdataTapy arr[N];//定长数组 int size;//有效数组个数 }SL;
注意：这就会出现：空间小了不够用，空间大了，空间浪费。
想一想呢，根据之前的学习，是什么可以动态增删内存呢
没错，就是利用malloc、relloc、calloc内存函数了
（忘记的小朋友可以回顾一下往期的博客，动态内存的管理（内存储存的god）-CSDN博客）
动态顺序表
typedef int SLdataTapy; typedef struct seqlist { SLdataTapy* a;//用来开辟动态内存 int size;//有效数组个数 int capacity;//剩余容量；判断是否需要新添加内存 }SL;
顺序表的实现
#define INIT_CAPACITY 4 typedef int SLDataType; // 动态顺序表 -- 按需申请 typedef struct SeqList { SLDataType* a; int size; // 有效数据个数 int capacity; // 空间容量 }SL; //初始化和销毁 void SLInit(SL* ps); void SLDestroy(SL* ps); void SLPrint(SL* ps); //扩容 void SLCheckCapacity(SL* ps); //头部插⼊删除 / 尾部插⼊删除 void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); void SLPushFront(SL* ps, SLDataType x); void SLPopFront(SL* ps); //指定位置之前插⼊/删除数据 void SLInsert(SL* ps, int pos, SLDataType x); void SLErase(SL* ps, int pos); int SLFind(SL* ps, SLDataType x);
以上则是我们需要实现顺序表的作用
顺序表的初始化
将其中的数组置为NULL；其余置为0；
void SLInit(SL* ps) { ps->a = NULL;//置为NULL,以防野指针的出现 ps->size = ps->capacity = 0; }
有初始化就有销毁
销毁则是需要将数组重新置为NULL；其余置为0；
void SLDestroy(SL* ps) { if (ps->a) {//判断数组中是否为空 free(ps->a);//因为动态顺序表需要使用malloc开辟内存，所以需要注意释放内存 } ps->a = NULL; ps->size = ps->capacity = 0; }
当我们设置好一切后，就要对数组进行扩容
//扩容 void SLCheckCapacity(SL* ps) { //先要判断内存够不够 if (ps->size == ps->capacity) { //使用malloc relloc celloc int newcappacity = ps->capacity * 2;//一般增容原来内存的二到三倍； SLDataType*tmp = (SLDataType*)relloc(ps->a,newcappacity * sizeof(SLDataType)); //注：这里没有直接使用ps->a直接申请，是为了防止内存申请失败；防止数据丢失 if (tmp == NULL) { //也可以使用assert直接终止程序；需要使用aseert.h的头文件 perror("relloc fail"); exit(1); //直接退出程序；也可使用return； } //空间增容成功 ps->a = tmp; ps->capacity = newcappacity; } }
其中出现了一点小问题，是否发现了呢；
果然聪明的你一眼就发现问题了呢；
int newcappacity = ps->capacity * 2;//一般增容原来内存的二到三倍； SLDataType*tmp = (SLDataType*)relloc(ps->a,newcappacity * sizeof(SLDataType));
在使用这句的前提是capacity为0；就会导致开辟为0的空间，就会出现错误；
就可以利用到三目操作符，使其完成扩容：如以下代码
int newcappacity = ps->capacity == 0 ? 4 :ps->capacity*2
ps->capacity是否为0；如果是则为4；否则乘以2；
总结：
//初始化和销毁 void SLInit(SL* ps) { ps->a = NULL; ps->size = ps->capacity = 0; } void SLDestroy(SL* ps) { if (ps->a) {//判断数组中是否为空 free(ps->a);//因为需要使用malloc，所以需要注意释放内存 } ps->a = NULL; ps->size = ps->capacity = 0; } //扩容 void SLCheckCapacity(SL* ps) { //先要判断内存够不够 if (ps->size == ps->capacity) { //使用malloc relloc celloc int newcappacity = ps->capacity == 0 ? 4 :ps->capacity*2;//一般增容原来内存的二到三倍； SLDataType*tmp = (SLDataType*)relloc(ps->a,newcappacity * sizeof(SLDataType)); //注：这里没有直接使用ps->a直接申请，是为了防止内存申请失败；防止数据丢失 if (tmp == NULL) {//也可以使用assert直接终止程序；需要使用aseert.h的头文件 perror("relloc fail"); exit(1);//直接退出程序；也可使用return； } //空间增容成功 ps->a = tmp; ps->capacity = newcappacity; } }
我们已经完成了初始化，销毁与扩容，你可以尝试剩余代码的编写；
点关注，不迷路，up将会在接下来揭晓如何编写！！！
