目录
一、顺序表
二、静态顺序表
三、动态顺序表
3.1、动态顺序表的实现
3.2、动态顺序表的实现
3.3.1、结构体创建
3.3.2、初始化
3.3.3、销毁数据
3.3.4、增容空间
3.3.5、尾插数据
3.3.6、头插数据
3.3.7、删除尾数据
3.3.8、打印数据
3.3.9、删除头数据
3.3.10、在指定位置之前插入数据
3.3.11、删除指定位置的数据
3.3.12、查找数据是否存在
四、全部代码
顺序表是数据结构的基础知识，通过学习次内容，可以让我们了解顺序表中数据中是如何进行存储，删除，插入数据的。
一、顺序表
顺序表在逻辑上与物理上是连续存放的，比如我们之前学习的数组，数组中包含许多数，每个数据在内存中存储都是连续的，在我们逻辑思维上存储也是连续的，当然，据我自己所了解，所以数据都需要是具有逻辑存储的，如果不是逻辑存储，那么根本就无法找到此数据。
以下是数组存储的数据：
顺序表与数组的区别：
顺序表的底层结构是数组，对于数组进行封装，实现了增删查改的接口。
使用数组很单一，无法进行修改，而使用顺序表进行存储数据，我们可以任意进行数据的修改。
二、静态顺序表
使用静态顺序表存储数据：
静态顺序表的大小被限制死了，无法进行扩容。
空间给少了不够用，空间给多了浪费。
三、动态顺序表
SLDataType* a;为什么在这动态顺序表中，数据需要加上“*”,这是因为创建的是一个动态的顺序表，我们可以使用malloc，realloc进行开辟新空间来存储a，如果使用静态数据“a”的话，数据的存储位置就无法变动，当我们在增加数据时候，数据不够了，我们使用realloc开辟新空间，并且空间的其实位置进行改变，那么a就地址就会更改。
3.1、动态顺序表的实现
我们需要创建三个文件，node.h , node.c , test.c
node.h存储头文件与函数的参数
node.c实现函数
test.c为我们的主函数
代码小提示：
在编写代码的时候，我们需要勤测试，在完成一个函数体时，就需要测试，避免写完一大堆函数以后再测试，这样会无从下手。
3.2、动态顺序表的实现
在这部分，我只进行函数的讲解，想要查看全部源码的同学，可以拉到博客的最后进行查看
3.3.1、结构体创建
typedef int SLDatatype;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDatatype* arr;int size; // 有效数据个数int capacity; // 空间容量
}SL;我们把int类型的名字改变成了SLDatatype，这样可以方便进行数据类型大小的修改。
3.3.2、初始化
test.cSL s; //新建结构体
SLInit(&s); //取地址传给函数进行初始化//初始化
void SLInit(SL* ps) //进行传址调用，否则堆栈在运行完如何销毁的时候，内容也会消失
{ps->arr = NULL; //把数据给置空ps->size = ps->capacity = 0; //把数据大小与空间也置零
}因为是顺序表，无需修改首元素的地址，所以我们不需要进行SL* lisk=NULL；把新创建的内容给置为空。我们只要在一个空间进行增删改查。
初始化时我们需要把结构体中的arr置为空，数据大小与空间大小置为0
3.3.3、销毁数据
//销毁
void SLDestroy(SL* ps)
{if (ps->arr) //相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}当需要销毁数据时，需要把有数据的空间给释放掉，把释放掉空间的地址给置为NULL，避免这个地址变为野指针，影响其他软件的运行，然后我们把size数据大小与capacity 空间大小都置为0。
3.3.4、增容空间
//增容空间
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容//0*2 = 0//若capacity为0，给个默认值，否则×2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}
对于动态顺序表来说，每次增容的大小我们统一规定为：新空间大小 = 2 * 原空间大小。
当原空间大小为0时，我们可以增加一行进行判断，如果原空间等于0那么我们就随机给个默认值，我们这里默认值给的是4个整型。
在扩容完以后，我们将原空间的数据与空间大小都指向为新的地址。
3.3.5、尾插数据
//插入数据
void SLPushBack(SL* ps, SLDatatype x)
{//粗暴的解决方法---断言assert(ps);//等价于assert(ps != NULL)温柔的解决方式//if (ps == NULL)//{// return;//}SLCheckCapacity(ps);ps->arr[ps->size++] = x; //每插入一个数据，有效数据大小size就会+1
}assert（ps）断言是为了判断ps是一个空指针。
当ps->arr[0]=1;进行完这个操作，我们如果想继续插入2，那么我们就要让arr的大小增加1位，此时就变成了ps->arr[1]=2。因此得出代码：ps->arr[ps->size++] = x;
3.3.6、头插数据
void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);//判断空间是否足够SLCheckCapacity(ps);//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来ps->arr[0] = x;ps->size++;
}这段代码里的注释应该是很清楚的表示了
我们需要把表中数据集体往后移动一位，让新数据放到首元素。
3.3.7、删除尾数据
//删除
void SLPopBack(SL* ps)
{assert(ps); //判断ps不为空，如果为空，代码没必要运行assert(ps->size); //判断有效数据大小不为空，如果为空，代码没必要运行//ps->arr[ps->size - 1] = -1; //多余了ps->size--; //直接将有效数据个数-1就达到我们尾删的效果
}我们可以直接将有效数据个数-1就达到我们尾删的效果
3.3.8、打印数据
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}这个很好理解，不过多阐述了。
3.3.9、删除头数据
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//数据整体向前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1]; //i = size-2}ps->size--;
}将数据集体往前移动一位。
移动前：
移动后：
3.3.10、在指定位置之前插入数据
//在指定位置之前插入数据(空间足够才能直接插入数据）
void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(ps); //判断ps是否为空assert(pos >= 0 && pos <= ps->size); //判断指定位置的数据是否在顺序表中有效SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1]; //pos+1 -> pos}ps->arr[pos] = x;ps->size++;
}插入前：
插入后：
3.3.11、删除指定位置的数据
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//还有更多的限制：如顺序表不能为空....//pos之后的数据整体向前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];// size-2 <- size-1}ps->size--;
}删除前：
删除后：
3.3.12、查找数据是否存在
//查找数据
int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x) //如果arr指向的数据等于x那么就return i{return i;}}//没有找到：返回一个无效的下标return -1;
}test.cint find = SLFind(&s, 222);
if (find < 0)
{printf("没找到\n");
}
else
{printf("找到了\n");
}如果return返回的数字小于零，打印没找到，否则就打印找到了
四、全部代码
node.htypedef int SLDatatype;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDatatype* arr;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 SLPushFront(SL* ps, SLDatatype x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//查找指定数据
int SLFind(SL* ps, SLDatatype x);
//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLDatatype x);
//指定位置之前删除数据
void SLErase(SL* ps, int pos);node.c#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
//销毁
void SLDestroy(SL* ps)
{if (ps->arr)//相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容//0*2 = 0//若capacity为0，给个默认值，否则×2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}
//插入数据
void SLPushBack(SL* ps, SLDatatype x)
{//粗暴的解决方法---断言assert(ps);//等价于assert(ps != NULL)温柔的解决方式//if (ps == NULL)//{// return;//}SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);//判断空间是否足够SLCheckCapacity(ps);//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来ps->arr[0] = x;ps->size++;
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}//删除
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//ps->arr[ps->size - 1] = -1;//多余了ps->size--;
}
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//数据整体向前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];//i = size-2}ps->size--;
}
//在指定位置之前插入数据(空间足够才能直接插入数据）
void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1]; //pos+1 -> pos}ps->arr[pos] = x;ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//还有更多的限制：如顺序表不能为空....//pos之后的数据整体向前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];// size-2 <- size-1}ps->size--;}int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}//没有找到：返回一个无效的下标return -1;
}test.c#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"void SLtest01()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);//SLPushBack(&s, 5);//SLPushBack(&s, 6);//SLPushBack(NULL , 6);////SLPushFront(&s, 1);//SLPushFront(&s, 2);//SLPushFront(&s, 3);//SLPushFront(&s, 4);SLPrint(&s); //1 2 3 4//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);//SLPopBack(&s);//SLPrint(&s);////SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLPopFront(&s);//SLPrint(&s);//SLInsert(&s, 11, 0);//SLPrint(&s);//SLInsert(&s, 22, s.size);//SLPrint(&s);//SLInsert(&s, 33, 1);//SLPrint(&s);//SLErase(&s, 1);//SLPrint(&s); //1 3 4//SLErase(&s,s.size-1);//SLPrint(&s);//2 3int find = SLFind(&s, 222);if (find < 0){printf("没找到\n");}else{printf("找到了\n");}SLDestroy(&s);//SLDestroy(&s);//ctrl+d
}int main()
{SLtest01();return 0;
}
