1.数据结构的介绍
⚀基本概念
数据结构 == 数据 + 结构
- 数据：
- 数据就是所有描述客观事物的符号。
- 比如：我们常见的文字，“你今天学习了吗？”；数字，“1，2，3，4，5，...”；每天刷的视频，拍的照片，听的音乐......这些都是数据。【大家应该都知道什么数据的，抽象的概念，小编也不能完全解释清楚】
- 对于计算机而言：简单的数据可以是一个整形数字，一个字符，一个浮点型数字；稍微复杂点，可以是一串字符，一堆存放在结构体中的复杂数据等等。
- 结构：
- 结构是指数据元素之间的相互关系。
- 简单的说：有了数据，就要交给计算机进行存储，而存储数据就有不同的方式，我们将存储数据的方式称为数据的结构。
- 比如：数据是一个接着一个的存放，数据是像一棵树一样，从主干到分支等等。
- 数据结构：
- 现在来谈数据结构就更容易理解了，数据结构就是一句话：数据存放的方式。
- 数据结构是计算机存储、组织数据的方式。
⚁常见的数据结构
当我们了解了数据结构的基本概念之后，再为大家介绍一下常见的数据结构：
数据结构可以从两方面来分析：逻辑结构和物理结构
- 逻辑结构：
- 逻辑结构就是指我们实际看见的存放数据的结构。
- 物理结构：
- 物理结构就是指数据实际在内存上的存储方式。
- 以下面要介绍的线性表为例子，线性表就是数据元素串联起来，形成一条线，如图，在表面看来这些数据一个接着一个存储的（逻辑结构），但是在底层的实现时，这些数据在内存上，可能是连续的，分散的（物理结构）。
2.线性表的介绍
⚀基本概念
小编的理解：
线性表就是将n个具有相同特性、相同类型的数据一个一个地链接起来，使得数据存放的方式在逻辑结构上看起来是一条直线，一条连续的存放数据的直线。
星火的解释：
线性表是数据结构的一种，它是由n个具有相同特性的数据元素组成的有限序列。
线性表是一种最基本的数据结构，它可以看作是一组有序的元素集合，每个元素都有唯一的前驱和后继（除了第一个和最后一个元素）（小编注解：每个元素前面和后面都有元素，除了开头和结尾）。
【补充】这种结构体现了数据元素之间的一对一关系。线性表可以进一步分为一般线性表和受限线性表，其中受限线性表可能对元素的排列或操作有一定的限制。
⚁线性表的分类
线性表在逻辑结构上看起来是一条直线，数据都在直线线上，那么按照物理结构来分，就会存在真~直线和假~直线两种，就是数据之间存储是连续的和不连续的两种，连续的被称作顺序表，不连续的被称为链表：
- 顺序表：
- 顺序表中的元素按逻辑顺序依次存储在计算机内存中连续的物理地址空间中。
- 链表：
- 链表是用一组任意的物理地址来存储数据元素，数据元素（节点）之间的关系通过指针来进行链接。
3.顺序表的实现
顺序表就物理上连续存放的数据结构，那么底层其实就是数组，只有数组才是连续存放的，我们所讲的顺序表大家就将其理解为数组就可以了，顺序表只不过在数组上对其进行封装成了结构体（添加了数组的实际元素个数和数组的容量）。
而数组又分为两种静态开辟的数组和动态开辟的数组两种：
- 静态开辟的数组：
- 创建方式：使用类型加上数组的下标引用符表示一个数组的创建
- 特点：空间连续，大小一开始规定好了，无法调整。
- 动态开辟的数组：
- 创建方式：使用动态开辟函数开辟一块空间，再结合不同类型的指针进行访问，就形成了数组。
- 解释：指针的类型决定了指针一次性访问多少个字节的空间，决定了加一时跳过几个字节的空间，通过不同类型的指针去访问空间，由于不同类型指针的特性，一次性访问空间大小就不同，
- 比如int*去访问空间，一次就能读取int（字节）个空间，那不就访问一个整形数据吗？再配合指针运算的特性，加一不就跳过一个int类型的元素吗？那我开辟n个int类型的空间，再用int*去访问，这不就是长度为n的整形数组了
- 特点：空间连续，大小可变，可以调整。
那么了解完静态和动态后，大家觉得我们要基于哪种去实现顺序表？
答案肯定是动态啦，静态的大小不可变，如果你以后工作了使用静态的存储数据，那么如果数据量比较大，就会面临空间不够用，小了就会面对数据存不下溢出导致数据丢失，哪种情况哪都担待不起，丢了重要数据那你只剩下手铐作伴了，而动态开辟的就能防止这种情况。
下面就基于动态开辟的数组，来为大家一步一步剖析顺序表的实现
⚀大致思路
顺序表的实现大致就是顺序表的定义、顺序表功能的实现和功能的测试等。
而代码的量比较大，我们采用模块化编程，将声明、定义和测试/使用分开放置，进行实现，可以提高代码的可维护性、可读性和重用性：
- 创建三个文件：
- 文件1：头文件SeqList.h，顺序表的定义和顺序表功能的定义。
- 文件2：源文件SeqList.c，存放顺序表功能的实现。
- 文件3：源文件SeqList_test.c，存放顺序表的测试和使用。
使用头文件和源文件分开代码的好处
⚁拆解分析
首先，先在头文件SeqList.h定义好我们的结构体，声明好所有要实现的功能，这样你才知道大致需要实现哪些功能，思路才会清晰。接着再去源文件SeqList.c实现函数，最后再在源文件SeqList_test.c测试实现的功能。
(1).头文件SeqList.h
🌵#include包含头文件🌵
#pragma once//头文件只被重复包含一次
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>头文件包含了库文件之后，再顺序表的函数实现的源文件中就不需要再包含了，只需要包含SeqList.h即可
🌵顺序表的声明与定义🌵
struct SeqList
{
SLDataType* arr;//指向顺序表空间的地址
int size;//顺序表实际元素个数
int capacity;//顺序表的总容量
};前面我们说过顺序表就是动态开辟的数组之上，加上数组的元素实际大小和总容量这两个参数进行封装，那不用多说肯定是用到结构体，当然出了这个数和容量这两个参数，还可以添加其他的。
如果觉得创建顺序表的关键字太长了，可以重新命名一下：
//顺序表创建的关键字太长了，重新命名一下
typedef struct SeqList SL;注意的是：这里指向顺序表的指针采用的类型是我们自己定义的类型，就是方便适用于不同类型的数据，所以在定义顺序表前，我们再加上一句对顺序表元素类型关键字的重命名语句：
//先来定义一下顺序表的元素类型名
typedef int SLDataType;🌵顺序表功能的声明🌵
下面的函数我统一采用了传地址调用，因为传值调用是对拷贝值修改，不对实际参数做修改，那么初始化、插入、删除、修改、销毁就会出错，而打印函数你们可以选择传值，这里不涉及到实参的修改。
//顺序表功能的定义
//顺序表的初始化和销毁
void SLInit(SL* ps);//对顺序表的实际值进行修改，不能传值，因为传值是对原顺序表的拷贝，修改的拷贝值
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL* ps);
//顺序表的内存大小的判断
void SLCheckCapacity(SL* ps);
//顺序表的插入数据
//1.头部插入数据
void SLPushHead(SL* ps,SLDataType x);
//2.尾部插入数据
void SLPushTail(SL* ps, SLDataType x);
//3.指定位置前插入数据
void SLPushFront(SL* ps,int pos,SLDataType x);
//4.指定位置后插入数据
void SLPushBack(SL* ps,int pos, SLDataType x);
//顺序表的删除数据
//1.头部删除数据
void SLPopHead(SL* ps);
//2.尾部删除数据
void SLPopTail(SL* ps);
//3.指定位置前删除数据
void SLPopFront(SL* ps,int pos);
//4.指定位置后删除数据
void SLPopBack(SL* ps,int pos);
//5.指定位置删除
void SLPop(SL* ps, int pos);
//顺序表的查找数据
void SLFind(SL* ps, SLDataType x);
//顺序表的修改数据
void SLModfiy(SL* ps,int pos,SLDataType);
(2).源文件SeqList.c
🌵顺序表的初始化🌵
初始化的方式分为两种：
- 初始化不开辟空间，将指针置为NULL，则将个数和容量都置为0
- 初始化时开辟空间，一般采用4/8个元素大小进行开辟，此时容量就要置为4/8，而个数为0
这里小编采用第一种。还需注意的时初始化的方式不同，导致容量的初始值不同，那么在实现判断容量大小函数时，一般都会扩容容量的2/3倍，采用第一种方式容量可能0，那么在扩容前一定要判断容量是否0的情况。
void SLInit(SL* ps)//对顺序表的实际值进行修改，不能传值，因为传值是对原顺序表的拷贝，修改的拷贝值
{
assert(ps);//传指针就要断言一下，防止为空指针，后面都是如此
//初始化可以选择设置有效初始大小和无效初始大小（NULL和0）
//我们这里选择后者，不开辟初始空间
ps->arr = NULL;//置为空，无初始空间
ps->size = ps->capacity = 0;
}🌵顺序表的销毁🌵
void SLDestroy(SL* ps)
{
assert(ps);
if (ps->arr != 0)//空间有效才销毁，没有开辟空间就没必要销毁了
{
free(ps->arr);//销毁空间，防止内存泄漏
ps->arr = NULL;//指针置为空，规避野指针
}
ps->size = ps->capacity = 0;//个数和容量置为初始状态的值
}🌵容量判断函数🌵
易错点：
- 忽略capacity为0的情况，直接扩容为2/3倍
- 忽略动态开辟函数可能存在失败的情况，直接就将新地址和新容量的值赋值给变量，如果扩容失败的情况那么原来的参数就丢失，所以必须再验证后，再将参数设置为新的数值
//顺序表的内存大小的判断
void SLCheckCapacity(SL* ps)
{
//判断容量大小就是判断实际元素个数size和总容量的数目是否相等
if (ps->size == ps->capacity)//如果相等就扩容2倍
{
//存在问题1：实际元素个数和容量大小可能等于0，那就是还没有开辟空间
//使用三目操作符判断一下
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//如果等于0，我们就将它设置为4，不等于就返回2倍的大小，同时使用新的容量变量接收
//此时要扩容容量的数值就不为0了，可以开始扩容
SLDataType* arr_tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
//realloc可能扩容失败，所以不直接使用ps->arr进行接收，会导致原空间起始地址丢失的情况
if (arr_tmp == NULL)//判断是否失败
{
perror("realloc");//打印错误
return;//扩容失败了，可以结束函数了
}
//扩容成功，新空间的地址赋值给存原空间的变量，新容量大小赋值给存旧容量大小的变量
ps->arr = arr_tmp;
ps->capacity = newcapacity;
}
//不相等就不要扩容
}🌵头部插入和尾部插入🌵
//顺序表的插入数据
//1.头部插入数据
void SLPushHead(SL* ps,SLDataType x)
{
assert(ps);
//插入数据前，判断空间是否足够
SLCheckCapacity(ps);
//保证足够后开始插入数据
//分析：头部插入，所有数据向后移动一位，从前向后会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从后向前移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
int count = ps->size;//这里要移动所有数据，那么进行size次
for (int i = 0; i < count; i++)
{
ps->arr[ps->size - i] = ps->arr[ps->size - i - 1];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[ps->size]=ps->arr[ps->size-1];就是最后一个元素的值赋值到后面一个元素的位置
//最后一次：i=count-1=ps->size-1;ps->arr[1]=ps->arr[0];就是第一个元素的值赋值到第二个元素的位置
}
//移动完后就开始插入数据
ps->arr[0] = x;//把第一个位置的值置为目标变量值x
//插入一个数据后不要忘记实际元素个数+1
ps->size++;
}
//2.尾部插入数据
void SLPushTail(SL* ps, SLDataType x)
{
assert(ps);
//插入数据前，判断空间是否足够
SLCheckCapacity(ps);
//保证足够后开始插入数据
//分析：尾部插入不需要移动数据，直接在后面插入数据
ps->arr[ps->size] = x;//下标为size的元素是第size+1个元素，下标和序号差-1，不知道的数组在内存中的存储就没学好
//插入一个数据后不要忘记实际元素个数+1
ps->size++;
}🌵指定位置前插入🌵
//3.指定位置前插入数据
void SLPushFront(SL* ps, int pos, SLDataType x)
{
assert(ps);
//插入数据前，判断空间是否足够
assert(pos > 0 && pos <= ps->size);
SLCheckCapacity(ps);
//保证足够后开始插入数据
//分析：头部插入，指定数据向后移动一位，从前向后会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从后向前移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
//第1个元素前有0个元素，第3个元素前有2个元素，那么第pos个元素前就有pos-1个元素
int count = ps->size - (pos - 1);//移动的是指定位置后的数据，那么包括第pos个元素也要移动，就是总的减去第pos前的元素个数
for (int i = 0; i < count; i++)
{
ps->arr[ps->size - i] = ps->arr[ps->size - i - 1];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[ps->size]=ps->arr[ps->size-1];就是最后一个元素的值赋值到后面一个元素的位置
//最后一次：i=count-1=ps->size-pos;ps->arr[pos]=ps->arr[pos-1];就是第pos个元素的值赋值到第pos个元素后一个元素的位置
}
//此时第pos个元素(下标pos-1)的位置处没有数据，就插入给定数据x
ps->arr[pos - 1] = x;
//插入一个数据后不要忘记实际元素个数+1
ps->size++;
}
🌵头部删除和尾部删除🌵
//顺序表的删除数据
//1.头部删除数据
void SLPopHead(SL* ps)
{
assert(ps);
//分析：头部删除，所有数据向前移动一位，从后向前会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从前向后移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
int count = ps->size;//这里要移动所有数据，那么进行size次
for (int i = 0; i < count; i++)
{
ps->arr[i] = ps->arr[i + 1];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[0]=ps->arr[1];就是第二个元素的值赋值到第一个元素的位置
//最后一次：i=count-1=ps->size-1;ps->arr[ps->size - 2]=ps->arr[ps->size - 1];就是第size个元素的值赋值到第size-1个元素的位置
}
//移动完后让实际元素的个数减一即可
ps->size--;
}//2.尾部删除数据
void SLPopTail(SL* ps)
{
assert(ps);
//尾部删除很简单，只需要将实际元素的个数-1即可，就访问不到了
ps->size--;
}🌵指定位置删除🌵
//5.指定位置删除
void SLPop(SL* ps, int pos)
{
assert(ps);
//分析：指定位置删除，指定数据向前移动一位，从后向前会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从前向后移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
//第1个元素前有0个元素，第3个元素前有2个元素，那么第pos个元素前就有pos-1个元素
int count = ps->size - (pos - 1) - 1;//移动的是指定位置后的数据，那么不包括第pos个元素也要移动，就是总的减去第pos前的元素个数，再-1
for (int i = 0; i < count; i++)
{
ps->arr[pos - 1 + i] = ps->arr[pos + i];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[pos-2]=ps->arr[pos-1];就是第pos+1个元素的值赋值到第pos个元素的位置
//最后一次：i=count-1=ps->size-pos-1;ps->arr[ps->size-2]=ps->arr[ps->size-1];就是第size个元素的值赋值到第size-1个元素后一个元素的位置
}
//移动完后让实际元素的个数减一即可
ps->size--;
}🌵顺序表数据查找函数🌵
不同数据的类型，实现方法不同，这里顺序表的元素时int类型，那么只需要调用"=="比较值即可，而如果是结构体，那么比较方式可能就有几种不同的成员变量比较查找的方式
//顺序表的查找数据
void SLFind(SL* ps,SLDataType x)
{
assert(ps);
int n = 0;//计算找到的次数
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
n++;
printf("找到了，为第%d个元素\n", i + 1);
}
if (i == ps->size - 1 && n==0)//如果最后一次还没有找到
printf("没有找到\n");
}
}还有许多函数的实现，比如指定位置后插入，指定位置前删除，查找函数等等，请参考后面的源码
(3).源文件SeqList_test.c
测试顺序表的功能，一般是测试不同的函数就将封装在测试函数中，再在主函数中调用，这样代码的客观性更好。
int main()
{
test1_SLPushHead();
test2_SLPushTail();
test3_SLPushFront();
test4_SLPushBack();
test5_SLPopHead();
test6_SLPopTail();
test7_SLPopFront();
test8_SLPopBack();
test9_SLPop();
test10_SLFind();
test11_SLModfiy();
}具体函数内容参考下面的源码。
⚂源码分享
SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//先来定义一下顺序表的元素类型名
typedef int SLDataType;
//顺序表的定义
struct SeqList
{
SLDataType* arr;//指向顺序表空间的地址
int size;//顺序表实际元素个数
int capacity;//顺序表的总容量
};
//顺序表创建的关键字太长了，重新命名一下
typedef struct SeqList SL;
//顺序表功能的定义
//顺序表的初始化和销毁
void SLInit(SL* ps);//对顺序表的实际值进行修改，不能传值，因为传值是对原顺序表的拷贝，修改的拷贝值
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL* ps);
//顺序表的内存大小的判断
void SLCheckCapacity(SL* ps);
//顺序表的插入数据
//1.头部插入数据
void SLPushHead(SL* ps,SLDataType x);
//2.尾部插入数据
void SLPushTail(SL* ps, SLDataType x);
//3.指定位置前插入数据
void SLPushFront(SL* ps,int pos,SLDataType x);
//4.指定位置后插入数据
void SLPushBack(SL* ps,int pos, SLDataType x);
//顺序表的删除数据
//1.头部删除数据
void SLPopHead(SL* ps);
//2.尾部删除数据
void SLPopTail(SL* ps);
//3.指定位置前删除数据
void SLPopFront(SL* ps,int pos);
//4.指定位置后删除数据
void SLPopBack(SL* ps,int pos);
//5.指定位置删除
void SLPop(SL* ps, int pos);
//顺序表的查找数据
void SLFind(SL* ps, SLDataType x);
//顺序表的修改数据
void SLModfiy(SL* ps,int pos,SLDataType);SeqList.c
#include"SeqList.h"
//顺序表功能的实现
//顺序表的初始化和销毁
void SLInit(SL* ps)//对顺序表的实际值进行修改，不能传值，因为传值是对原顺序表的拷贝，修改的拷贝值
{
assert(ps);//传指针就要断言一下，防止为空指针，后面都是如此
//初始化可以选择设置有效初始大小和无效初始大小（NULL和0）
//我们这里选择后者，不开辟初始空间
ps->arr = NULL;//置为空，无初始空间
ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
assert(ps);
if (ps->arr != 0)//空间有效才销毁，没有开辟空间就没必要销毁了
{
free(ps->arr);//销毁空间，防止内存泄漏
ps->arr = NULL;//指针置为空，规避野指针
}
ps->size = ps->capacity = 0;//个数和容量置为初始状态的值
}
//顺序表的打印
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)//打印次数为size次，有多少个元素就打印多少个
{
printf("%d ", ps->arr[i]);
}
printf("\n");//打印完换行
}
//顺序表的内存大小的判断
void SLCheckCapacity(SL* ps)
{
//判断容量大小就是判断实际元素个数size和总容量的数目是否相等
if (ps->size == ps->capacity)//如果相等就扩容2倍
{
//存在问题1：实际元素个数和容量大小可能等于0，那就是还没有开辟空间
//使用三目操作符判断一下
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//如果等于0，我们就将它设置为4，不等于就返回2倍的大小，同时使用新的容量变量接收
//此时要扩容容量的数值就不为0了，可以开始扩容
SLDataType* arr_tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
//realloc可能扩容失败，所以不直接使用ps->arr进行接收，会导致原空间起始地址丢失的情况
if (arr_tmp == NULL)//判断是否失败
{
perror("realloc");//打印错误
return;//扩容失败了，可以结束函数了
}
//扩容成功，新空间的地址赋值给存原空间的变量，新容量大小赋值给存旧容量大小的变量
ps->arr = arr_tmp;
ps->capacity = newcapacity;
}
//不相等就不要扩容
}
//顺序表的插入数据
//1.头部插入数据
void SLPushHead(SL* ps,SLDataType x)
{
assert(ps);
//插入数据前，判断空间是否足够
SLCheckCapacity(ps);
//保证足够后开始插入数据
//分析：头部插入，所有数据向后移动一位，从前向后会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从后向前移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
int count = ps->size;//这里要移动所有数据，那么进行size次
for (int i = 0; i < count; i++)
{
ps->arr[ps->size - i] = ps->arr[ps->size - i - 1];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[ps->size]=ps->arr[ps->size-1];就是最后一个元素的值赋值到后面一个元素的位置
//最后一次：i=count-1=ps->size-1;ps->arr[1]=ps->arr[0];就是第一个元素的值赋值到第二个元素的位置
}
//移动完后就开始插入数据
ps->arr[0] = x;//把第一个位置的值置为目标变量值x
//插入一个数据后不要忘记实际元素个数+1
ps->size++;
}
//2.尾部插入数据
void SLPushTail(SL* ps, SLDataType x)
{
assert(ps);
//插入数据前，判断空间是否足够
SLCheckCapacity(ps);
//保证足够后开始插入数据
//分析：尾部插入不需要移动数据，直接在后面插入数据
ps->arr[ps->size] = x;//下标为size的元素是第size+1个元素，下标和序号差-1，不知道的数组在内存中的存储就没学好
//插入一个数据后不要忘记实际元素个数+1
ps->size++;
}
//3.指定位置前插入数据
void SLPushFront(SL* ps, int pos, SLDataType x)
{
assert(ps);
//插入数据前，判断空间是否足够
assert(pos > 0 && pos <= ps->size);
SLCheckCapacity(ps);
//保证足够后开始插入数据
//分析：头部插入，指定数据向后移动一位，从前向后会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从后向前移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
//第1个元素前有0个元素，第3个元素前有2个元素，那么第pos个元素前就有pos-1个元素
int count = ps->size - (pos - 1);//移动的是指定位置后的数据，那么包括第pos个元素也要移动，就是总的减去第pos前的元素个数
for (int i = 0; i < count; i++)
{
ps->arr[ps->size - i] = ps->arr[ps->size - i - 1];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[ps->size]=ps->arr[ps->size-1];就是最后一个元素的值赋值到后面一个元素的位置
//最后一次：i=count-1=ps->size-pos;ps->arr[pos]=ps->arr[pos-1];就是第pos个元素的值赋值到第pos个元素后一个元素的位置
}
//此时第pos个元素(下标pos-1)的位置处没有数据，就插入给定数据x
ps->arr[pos - 1] = x;
//插入一个数据后不要忘记实际元素个数+1
ps->size++;
}
//4.指定位置后插入数据
void SLPushBack(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
//插入数据前，判断空间是否足够
SLCheckCapacity(ps);
//保证足够后开始插入数据
//分析：插入，指定数据向后移动一位，从前向后会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从后向前移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
//第1个元素前有0个元素，第3个元素前有2个元素，那么第pos个元素前就有pos-1个元素
int count = ps->size - pos;//移动的是指定位置后的数据，那么第pos个元素不需要移动，就是总的减去第pos+1前的元素个数
for (int i = 0; i < count; i++)
{
ps->arr[ps->size - i] = ps->arr[ps->size - i - 1];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[ps->size]=ps->arr[ps->size-1];就是最后一个元素的值赋值到后面一个元素的位置
//最后一次：i=count-1=ps->size-pos - 1;ps->arr[pos+1]=ps->arr[pos];就是第pos+1个元素的值赋值到第pos+1个元素后一个元素的位置
}
//此时第pos个元素(下标pos-1)的后一个元素的位置处(下标pos)没有数据，就插入给定数据x
ps->arr[pos] = x;
//插入一个数据后不要忘记实际元素个数+1
ps->size++;
}
//顺序表的删除数据
//1.头部删除数据
void SLPopHead(SL* ps)
{
assert(ps);
//分析：头部删除，所有数据向前移动一位，从后向前会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从前向后移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
int count = ps->size;//这里要移动所有数据，那么进行size次
for (int i = 0; i < count; i++)
{
ps->arr[i] = ps->arr[i + 1];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[0]=ps->arr[1];就是第二个元素的值赋值到第一个元素的位置
//最后一次：i=count-1=ps->size-1;ps->arr[ps->size - 2]=ps->arr[ps->size - 1];就是第size个元素的值赋值到第size-1个元素的位置
}
//移动完后让实际元素的个数减一即可
ps->size--;
}
//2.尾部删除数据
void SLPopTail(SL* ps)
{
assert(ps);
//尾部删除很简单，只需要将实际元素的个数-1即可，就访问不到了
ps->size--;
}
//3.指定位置前删除数据
void SLPopFront(SL* ps,int pos)
{
assert(ps);
assert(pos > 1 && pos <= ps->size);
//分析：指定位置前删除，指定数据向前移动一位，从后向前会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从前向后移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
//第1个元素前有0个元素，第3个元素前有2个元素，那么第pos个元素前就有pos-1个元素
int count = ps->size - (pos - 1);//移动的是指定位置后的数据，那么包括第pos个元素也要移动，就是总的减去第pos前的元素个数
for (int i = 0; i < count; i++)
{
ps->arr[pos - 2 + i] = ps->arr[pos - 1 + i];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[pos-2]=ps->arr[pos-1];就是第pos个元素的值赋值到第pos-1个元素的位置
//最后一次：i=count-1=ps->size-pos;ps->arr[ps->size-2]=ps->arr[ps->size-1];就是第size个元素的值赋值到第size-1个元素后一个元素的位置
}
//移动完后让实际元素的个数减一即可
ps->size--;
}
//4.指定位置后删除数据
void SLPopBack(SL* ps,int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
//分析：指定位置后删除，指定数据向后移动一位，从后向前会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从前向后移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
//第1个元素前有0个元素，第3个元素前有2个元素，那么第pos个元素前就有pos-1个元素
int count = ps->size - pos - 1;//移动的是指定位置后的数据，那么第pos个元素和第pos+1个元素不需要移动，就是总的减去第pos+1前的元素个数，再-1
for (int i = 0; i < count; i++)
{
ps->arr[pos + i] = ps->arr[pos + 1 + i];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[pos]=ps->arr[pos+1];就是第pos+2个元素的值赋值到第pos+1个元素的位置
//最后一次：i=count-1=ps->size-pos - 2;ps->arr[ps->size-2]=ps->arr[ps->size-1];就是第size个元素的值赋值到第size-1个元素的位置
}
//移动完后让实际元素的个数减一即可
ps->size--;
}
//5.指定位置删除
void SLPop(SL* ps, int pos)
{
assert(ps);
//分析：指定位置删除，指定数据向前移动一位，从后向前会导致还未被移动的数据被覆盖掉，影响后续移动
// 所以采用从前向后移动
//这里给推荐大家一个方法：如果你不知道循环进行几次，先定义一个变量count存放循环的次数，先分析count的值，再循环
//第1个元素前有0个元素，第3个元素前有2个元素，那么第pos个元素前就有pos-1个元素
int count = ps->size - (pos - 1) - 1;//移动的是指定位置后的数据，那么不包括第pos个元素也要移动，就是总的减去第pos前的元素个数，再-1
for (int i = 0; i < count; i++)
{
ps->arr[pos - 1 + i] = ps->arr[pos + i];
//不清楚的同学还可以假设第一次循环和最后一次循环来验证一下
//第一次：ps->arr[pos-2]=ps->arr[pos-1];就是第pos+1个元素的值赋值到第pos个元素的位置
//最后一次：i=count-1=ps->size-pos-1;ps->arr[ps->size-2]=ps->arr[ps->size-1];就是第size个元素的值赋值到第size-1个元素后一个元素的位置
}
//移动完后让实际元素的个数减一即可
ps->size--;
}
//顺序表的查找数据
void SLFind(SL* ps,SLDataType x)
{
assert(ps);
int n = 0;//计算找到的次数
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
n++;
printf("找到了，为第%d个元素\n", i + 1);
}
if (i == ps->size - 1 && n==0)//如果最后一次还没有找到
printf("没有找到\n");
}
}
//顺序表的修改数据
void SLModfiy(SL* ps,int pos,SLDataType x)
{
assert(ps);
ps->arr[pos - 1] = x;//pos-1就是第pos个元素的下标
}SeqList_test.c
#include<stdio.h>
#include"SeqList.h"
void test1_SLPushHead()
{
printf("****头部插入函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
//打印
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("************************\n");
printf("\n");
}
void test2_SLPushTail()
{
printf("****尾部插入函数测试****\n");
SL S;
//初始化
SLInit(&S);
//尾部插入数据
SLPushTail(&S, 1);
SLPushTail(&S, 2);
SLPushTail(&S, 3);
SLPushTail(&S, 4);
//打印
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("************************\n");
printf("\n");
}
void test3_SLPushFront()
{
printf("****指定位置前插入函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
//打印
SLPrint(&S);
printf("在第1个元素前插入数字8：\n");
SLPushFront(&S, 1, 8);
SLPrint(&S);
printf("在第4个元素前插入数字10：\n");
SLPushFront(&S, 5, 10);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test4_SLPushBack()
{
printf("****指定位置后插入函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
//打印
SLPrint(&S);
printf("在第0个元素后插入数字8：\n");
SLPushBack(&S, 0, 8);
SLPrint(&S);
printf("在第5个元素前插入数字10：\n");
SLPushBack(&S, 5, 10);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test5_SLPopHead()
{
printf("****头部删除函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
SLPushHead(&S, 5);
SLPushHead(&S, 6);
//打印
SLPrint(&S);
printf("头部删除1次：\n");
SLPopHead(&S);
SLPrint(&S);
printf("头部删除2次：\n");
SLPopHead(&S);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test6_SLPopTail()
{
printf("****尾部删除函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
SLPushHead(&S, 5);
SLPushHead(&S, 6);
//打印
SLPrint(&S);
printf("尾部删除1次：\n");
SLPopTail(&S);
SLPrint(&S);
printf("尾部删除2次：\n");
SLPopTail(&S);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test7_SLPopFront()
{
printf("****指定位置前删除函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
SLPushHead(&S, 5);
SLPushHead(&S, 6);
//打印
SLPrint(&S);
printf("删除第1个元素前的数据：\n");
SLPopFront(&S,2);
SLPrint(&S);
printf("删除第5个元素前的数据：\n");
SLPopFront(&S, 5);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test8_SLPopBack()
{
printf("****指定位置后删除函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
SLPushHead(&S, 5);
SLPushHead(&S, 6);
//打印
SLPrint(&S);
printf("删除第0个元素后的数据：\n");
SLPopBack(&S, 0);
SLPrint(&S);
printf("删除第3个元素后的数据：\n");
SLPopBack(&S, 3);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test9_SLPop()
{
printf("****指定位置删除函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
SLPushHead(&S, 5);
SLPushHead(&S, 6);
//打印
SLPrint(&S);
printf("删除第1个元素的数据：\n");
SLPop(&S, 1);
SLPrint(&S);
printf("删除第5个元素后的数据：\n");
SLPop(&S, 5);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test10_SLFind()
{
printf("****查找数据函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
SLPushHead(&S, 5);
SLPushHead(&S, 6);
//打印
SLPrint(&S);
printf("查找值为1的数据：\n");
SLFind(&S, 1);
printf("查找值为5的数据：\n");
SLFind(&S, 5);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
void test11_SLModfiy()
{
printf("****修改指定位置数据函数测试****\n");
SL S;
//初始化
SLInit(&S);
//头部插入数据
printf("插入数据：\n");
SLPushHead(&S, 1);
SLPushHead(&S, 2);
SLPushHead(&S, 3);
SLPushHead(&S, 4);
SLPushHead(&S, 5);
SLPushHead(&S, 6);
//打印
SLPrint(&S);
printf("将第1个元素的数据修改为99：\n");
SLModfiy(&S,1,99);
SLPrint(&S);
printf("将第6个元素的数据修改为66：\n");
SLModfiy(&S, 6,66);
SLPrint(&S);
//销毁
SLDestroy(&S);
printf("******************************\n");
printf("\n");
}
int main()
{
test1_SLPushHead();
test2_SLPushTail();
test3_SLPushFront();
test4_SLPushBack();
test5_SLPopHead();
test6_SLPopTail();
test7_SLPopFront();
test8_SLPopBack();
test9_SLPop();
test10_SLFind();
test11_SLModfiy();
}
