数据结构（顺序表）
🌏个人博客主页：心.c
前言： 前段时间学习了顺序表，想和大家分享以下，虽然顺序表和数组很像，但是它还是很神奇，可以自动创建内存和进行销毁，希望大家可以有所所获，如果有哪里讲的不太好，希望家人们可以积极给我提出问题，我将万分感谢
🔥🔥🔥文章专题：顺序表
😽感谢大家的点赞👍收藏⭐️评论✍您的一键三连是我更新的动力 💓
目录
顺序表的概念：
定义：顺序表是一种线性表的存储结构，其中的数据元素存储在一块连续的内存区域中，通过元素在内存中的相对位置来表示元素之间的逻辑关系，在程序中，顺序表通常使用数组来实现。
静态数组实现：在大多数情况下，顺序表使用静态数组实现，这意味着数组的大小是在编译时确定的。这种情况下，数组是在栈上分配的，通常不需要手动释放。
动态数组实现：如果你使用动态内存来实现顺序表，那么数组的大小可以在运行时动态调整。在这种情况下，数组是在堆上分配的，需要手动释放。
顺序表的特点：
- 连续存储：所有元素都存储在连续的内存空间中。
- 随机访问：可以通过下标快速访问任何一个元素。
- 固定长度：一旦分配了一定大小的空间，其容量就固定不变了，除非重新分配内存。
- 插入和删除操作涉及移动元素：在顺序表中插入或删除一个元素时，需要移动大量元素以保持顺序。
下面我将主讲顺序表中的动态数组实现
顺序表的创建：
//定义不确定数据类型
typedef int SLDateType;
typedef struct SeqList {
SLDateType* arr;
int size;
int capacity;
}SL;顺序表的优点：
- 随机访问速度快：由于使用数组存储，可以使用下标直接访问元素。
- 空间利用率高：没有额外的指针开销。
顺序表的缺点：
- 插入和删除操作效率低：需要移动大量元素。
- 固定容量限制：当表满时，无法直接插入新元素，需要重新分配内存空间。
实现顺序表：
实现顺序表有以下几种功能，给大家参考
//数据表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDistroy(SL* ps);
void SLPrint(SL s);
//头部插入删除/尾部插入删除/像中间某一个地方添加数据
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, SLDateType x, int pos);
void SLErase(SL* ps, int pos);在进行这些操作之前，我们要先判断内存够不够用，下面是用来判断内存是否够用的函数
//判断内存是否够用，不够继续申请
void SLCheckCapacity(SL* ps) {
if (ps->size == ps->capacity) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDateType* tmp = (SLDateType*)realloc(ps->arr, newCapacity * sizeof(SLDateType));
//如果申请内存空间失败
if (tmp == NULL) {
perror("realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}初始化：
//初始化
void SLInit(SL* ps) {
ps->arr = NULL;
ps->size = ps->capacity = 0;
}尾部插入数据：
顺序表使用连续的内存空间存储数据，因此在尾部插入数据时，通常不需要移动已有的元素，只需将新元素添加到最后即可。但是，需要注意顺序表的容量限制。
//尾部插入数据
void SLPushBack(SL* ps, SLDateType x) {
//如果传入的为NULL没有传入指针
assert(ps);
//判断是否还有内存
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}头部插入数据：
使用assert(ps); 检查传入的顺序表指针
ps是否非空。如果ps为空，程序将终止执行使用for 循环，逐个向前移动，直到第一个元素。这一步是为了腾出位置给新插入的元素。然后更新到最后一个元素的索引ps->arr[0] = x;将新元素
x插入到数组的第一个位置（索引为 0）。ps->size++;增加顺序表的大小计数器，以反映新插入的元素。
//头部插入数据
void SLPushFront(SL* ps, SLDateType x) {
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i > 0; i--) {
ps->arr[i] = ps->arr[i-1];
}
ps->arr[0] = x;
ps->size++;
}中间插入数据：
向中间插入数据，实现判断ps是否为null，然后通过for循环判断从表中pos位开始向后移动，移动完成之后将pos位赋值x，然后让内容size加1
//中间插入数据
void SLInsert(SL* ps, int pos, SLDateType x) {
//判断ps是否为空
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--) {
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}尾部删除数据：
尾部删除数据很简单，只需要将表中的size存储元素的个数减一就可以实现了
//尾部删除
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
//顺序表不为空
--ps->size;
}头部删除数据：
头部删除数据，只需要将除第一个元素之外的其他数据通过for循环整体向前挪动一位，就可以实现了，最后将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];
}
ps->size--;
}中间删除数据：
向中间删除数据，实现判断ps是否为null，然后通过for循环判断从表中pos位开始向前移动一位，实现覆盖功能，然后让内容size减1
//中间删除中间位置的数据
void SLErase(SL* ps, int pos) {
assert(ps);
assert(pos >= 0 && pos <= ps->size);
for (int i = pos; i < ps->size-1; i++) {
ps->arr[i] == ps->arr[i + 1];
}
ps->size--;
}其他方法函数：
查找下标：
//查找下标
int SLFind(SL* ps, SLDateType x) {
assert(ps);
for (int i = 0; i < ps->size; i++) {
if (ps->arr[i] == x) {
return i;
}
}
return -1;
}打印数据：
//打印数据
void SLPrint(SL s) {
for (int i = 0; i < s.size; i++) {
printf("%d",s.arr[i]);
}
}消除所创建的动态内存：
//消除所创建的动态内存
void SLDestroy(SL* ps) {
if (ps->arr) {
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}功能实现：
好了到这里就讲完了，谢谢大家的观看！
原文地址：https://blog.csdn.net/2301_81253185/article/details/140735613
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！