《从数组到动态顺序表：数据结构与算法如何优化内存管理？》 - 教程
@晨非辰Tong：个人主页
专栏：《C语言》、《数据结构与算法》
学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”
引言：
在上一篇中，我们初步认识了动态顺序表的基本结构和特性，了解了它如何通过动态扩容来解决固定数组的长度限制。今天，我们将继续深入探索顺序表的核心操作——增删查改的实现细节。从高效的头部插入到底层的内存管理，每一个操作背后都蕴含着数据结构设计的智慧，让我们一起来揭开这些关键技术的神秘面纱。
目录
四、动态顺序表的应用（续）
4.3 在尾部删除数据
4.4 在头部删除数据
4.5 在指定位置查找数据
4.6 在指定位置插入
4.7 在指定位置删除
4.8 修改、销毁
四、动态顺序表的应用（续）
4.3 在尾部删除数据
SeqList.c文件
#include "SeqList.h"
//初始化_函数
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = 0, ps->capacity = 0;
}
//尾删_函数
void SLPopBack(SL* ps)
{assert(ps && ps->size);//断言//前移sizeps->size--;
}
//输出_函数
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}--进行顺序表尾部删除数据的前提是顺序表不能为空（不能传空参数NULL），得有数据才能删除——>也就是size不能为空。
test.c文件
#include "SeqList.h"
void test02()
{SL s2;//创建结构体变量SLInit(&s2);//初始化SLPushFront(&s2, 1);SLPushFront(&s2, 2);SLPushFront(&s2, 3);SLPrint(&s2);//尾删//上面先头插输入数据->321SLPopBack(&s2);SLPrint(&s2);//32SLPopBack(&s2);SLPrint(&s2);//3
}
int main()
{test02();return 0;
}
4.4 在头部删除数据
SeqList.c文件
#include "SeqList.h"
//头删_函数
void SLPopFront(SL* ps)
{assert(ps && ps->size);//循环移动for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
//输出_函数
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}--头删与尾删一样，顺序表不能为空。
#include "SeqList.h"
void test02()
{SL s2;//创建结构体变量SLInit(&s2);//初始化//先头插输入数据->4321SLPushFront(&s2, 1);SLPushFront(&s2, 2);SLPushFront(&s2, 3);SLPushFront(&s2, 4);SLPrint(&s2);//4321//头删SLPopFront(&s2);SLPrint(&s2);//321SLPopFront(&s2);SLPrint(&s2);//21SLPopFront(&s2);SLPrint(&s2);//1
}
int main()
{test02();return 0;
}
4.5 在指定位置查找数据
--在进行指定插入、指定删除操作，都需要先找到对应数据：
SeqList.c文件
#include "SeqList.h"
//查找_函数
int SLFind(SL* ps, SLTDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了,返回下标return i;}}//未找到return -1;//返回任意不是下标的数值
}test.c文件
#include "SeqList.h"
void test02()
{//头插数据->4321SLPushFront(&s2, 1);SLPushFront(&s2, 2);SLPushFront(&s2, 3);SLPushFront(&s2, 4);SLPrint(&s2);//4321//查找//pos-下标int pos = SLFind(&s2, 4);if (pos >= 0){printf("找到了，下标是%d：\n", pos);}else{printf("未找到！\n");}pos = SLFind(&s2, 3);if (pos >= 0){printf("找到了，下标是%d：\n", pos);}else{printf("未找到！\n");}pos = SLFind(&s2, 2);if (pos >= 0){printf("找到了，下标是%d：\n", pos);}else{printf("未找到！\n");}pos = SLFind(&s2, 0);if (pos >= 0){printf("找到了，下标是%d：\n", pos);}else{printf("未找到！\n");}
}
int main()
{test02();return 0;
}
4.6 在指定位置插入
--利用前面的查找函数
SeqList.c文件_主要实现
#include "SeqList.h"
//指定位置之前插入_函数
void SLInsert(SL* ps, int pos, SLTDataType x)
{assert(ps);//0<= pos < ps->sizeassert(pos >= 0 && pos < ps->size);//插入前判断空间是否足够SLCheckCapacity(ps);//pos及之后数据向后挪动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}注意：元素在向后移动时，要注意空间大小是否足够。
test.c文件
#include "SeqList.h"
void test02()
{//指定插入//头插数据->4321SLPushFront(&s2, 1);SLPushFront(&s2, 2);SLPushFront(&s2, 3);SLPushFront(&s2, 4);SLPrint(&s2);//4321//在数据3前插入int pos = SLFind(&s2, 3);SLInsert(&s2, pos, 100);SLPrint(&s2);
}
int main()
{test02();return 0;
}
4.7 在指定位置删除
SeqList.c文件_主要实现
#include “SeqList.h”
//指定位置删除_函数
void SLErase(SL* ps, int pos)
{assert(ps);//pos:[0,ps->size)assert(pos >= 0 && pos < ps->size);//将pos后的数据依次向前移动for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}//有效数据-1ps->size--;
}指定位置删除逻辑与头删类似，只是多了要进行指定行为。
test.c文件
#include "SeqList.h"
void test02()
{//测试_指定删除//头插数据->4321SLPushFront(&s2, 1);SLPushFront(&s2, 2);SLPushFront(&s2, 3);SLPushFront(&s2, 4);SLPrint(&s2);//4321//删除3int pos = SLFind(&s2, 3);//查找3的下标SLErase(&s2, pos);SLPrint(&s2);
}
int main()
{test02();rerurn 0;
}
4.8 修改、销毁
--修改
SeqList.c文件
#include "SeqList.h"
//修改_函数
void SLModify(SL* ps, int pos, SLTDataType x)
{assert(ps);ps->arr[pos] = x;
}
test.c文件
#include "SeqList.h"
void test02()
{//测试_修改//头插数据->4321SLPushFront(&s2, 1);SLPushFront(&s2, 2);SLPushFront(&s2, 3);SLPushFront(&s2, 4);SLPrint(&s2);//4321//修改3int pos = SLFind(&s2, 3);SLModify(&s2, pos, 100);SLPrint(&s2);
}
int main()
{test02();return 0;
}
--销毁
SeqList.c文件
#include "SeqList.h"
//销毁_函数
void SLDestory(SL* ps)
{if(ps->arr)free(ps->arr);ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}free掉ps->arr，所有都恢复为初始化状态。
结语：
通过对动态顺序表的深入学习，我们理解了连续存储结构的优势与局限。从顺序表到链表，体现了数据结构设计中的“空间换时间”思想。掌握了这两种基础线性结构，就为我们学习更复杂的树、图等非线性结构打下了坚实基础。下篇文章，我们将开启链表之旅，感受指针连接的魅力。