别再瞎学数据结构了！真・胎教级入门教程 | NO.1 从原理到代码 一次搞懂顺序表(C语言)-下篇
这里是顺序表超详解的下半部分,与首页上篇一起使用效果更佳哦,可供初学者更加深刻的理解各种概念/不同功能的代码实现和原理,也供学过的同学复习.刚看过上篇的同学请看过来(狗头).
内容涵盖元素插入 / 元素删除 / 元素查找 / 元素更改 / 顺序表销毁等顺序表功能函数的功能讲解和代码实现.
4.元素插入函数
在上篇实现了顺序表的定义 / 初始化 / 检查并扩容等功能后,我们来到顺序表章节最重要,最常用的功能之一: '增' (插入元素) 这里我们直接讲解插入任意合理位置的功能函数,例如头插 / 尾插这种子功能函数就只作展示在下方,而内容都会被包含在本函数中.
代码如下:(单独的头插尾插放在第二个代码块中)
void listinsert(sqlist* L, int pos, datatype e) //pos是要插入的位序,并不是下标
{
assert(L != NULL);
assert(pos >= 1 && pos <= L->length + 1); //pos的取值下面详细介绍
check_and_expand(L); //检查顺序表是否已满
int end = L->length - 1;
while (end >= pos - 1) //到指定位置为止
{
L->data[end + 1] = L->data[end]; //将一部分元素按顺序分别向后移动一为
end--;
}
L->data[pos - 1] = e; //在指定位序插入指定元素
L->length++; //所存元素个数加一
}
(1). pos的取值合法性仅与顺序表长度length相关，与数组容量capacity无关： 即使length小于容量capacity，也绝对不允许pos > length + 1。 因为数组下标 = 位序pos - 1，当pos取值为length+2时，对应下标为length+1， 而顺序表最后一个有效元素的下标是length-1，中间会跳过下标length的位置， 导致顺序表出现「空洞」，破坏元素连续存储的特性，属于严重的逻辑越界错误。 同时pos < 1也非法，对应下标为负数，会触发物理内存越界。
(2). 对于长度为length的顺序表，合法的插入位序范围是 1 ≤ pos ≤ length+1
pos=1：插入到表头（对应下标0的位置），所有元素依次后移一位。 pos=length+1：插入到表尾（对应下标length的位置，即尾插），无需移动元素，直接追加。 1 < pos < length+1：插入到中间位置，pos对应位置及之后的元素全部后移一位。
(3). 插入函数算法中，要将所插位序(pos)对应的元素及其之后的所有元素都向后移动一位。 这里要注意移动的顺序：一定是元素从后向前的顺序移动，先移动最后一个元素， 再逐个移动前一个元素，直至将下标为pos-1的元素移动完成。 从后往前移动是为了避免覆盖未移动的元素，保证数据完整性。 移动完成后，将新元素写入下标pos-1的位置，最后将顺序表长度length加1，完成插入。
int ListInsertTail(sqlist *L, datatype e) // 尾插：在顺序表末尾插入元素 e
{
if (L == NULL) // 判断指针是否合法
return 0;
check_and_expand(L);
L->data[L->length] = e;
L->length++;
return 1;
}
int ListInsertHead(sqlist *L, datatype e) // 头插：在顺序表最前面插入元素 e
{
if (L == NULL)
return 0;
check_and_expand(L);
for (int i = L->length; i > 0; i--) // 所有元素从后往前移动一位
{
L->data[i] = L->data[i - 1];
}
L->data[0] = e; // 插入到第 0 号位置
L->length++;
return 1;
}
5.元素删除函数
与元素插入函数相比,元素删除函数简单的多,没有了赋值操作,只需要像插入一样,但是把元素从前往后移动,覆盖指定的元素,以达到删除元素的目的.
代码如下:(单独的头插尾插放在第二个代码块中)
void listdelete(sqlist* L, int pos)
{
assert( L != NULL );
assert(pos >= 1 && pos <= L->length); //pos的合法位置
while (pos <= (L->length - 1))
{
L->data[pos - 1] = L->data[pos]; //覆盖指定元素
pos++;
}
L->length--; //元素个数减一
}
(1). 对于长度为length的顺序表，合法的删除位序范围是 1 ≤ pos ≤ length： pos=1：删除表头（对应下标0的位置），所有元素依次向前移动一位。 pos=length：删除表尾（对应下标length-1的位置），无需移动元素，直接将length减1。 1 < pos < length：删除中间位置的元素，pos对应位置之后的元素全部向前移动一位。
(2). 删除函数算法中，要将所删位序(pos)之后的所有元素都向前移动一位。 这里要注意移动的顺序：一定是元素从前向后的顺序移动，先移动删除位置的下一个元素， 再逐个移动后一个元素，直至将最后一个元素移动完成。 从前向后移动是为了用后一个元素覆盖前一个，保证元素连续存储，避免数据丢失。 移动完成后，将顺序表长度length减1，完成删除。
int ListDeleteTail(sqlist *L)
{ // 尾删：删除顺序表最后一个元素
if (L == NULL) // 判空
return 0;
if (L->length == 0)
{ // 表空，不能删
printf("顺序表为空，无法尾删！\n");
return 0;
}
L->length--; // 只需长度 -1（逻辑删除）
return 1; // 删除成功
}
int ListDeleteHead(sqlist *L) // 头删：删除顺序表第一个元素
{
if (L == NULL) // 判空
return 0; // 表空，不能删
if (L->length == 0)
{
printf("顺序表为空，无法头删！\n");
return 0;
} // 从第 1 位开始，所有元素往前挪一位
for (int i = 0; i < L->length - 1; i++)
{
L->data[i] = L->data[i + 1];
}
L->length--; // 长度 -1
return 1; // 删除成功
}
6.元素查找函数
当我们想要查找某个特定元素并得知它的位序时,可以使用元素查找函数,因为代码实现特别简单,我再次就不多赘述了,各位请看代码:
int listsearch(sqlist* L, datatype e) //返回位序,不是元素下标
{
assert(L != NULL); //传入指针不为空
int i = 0;
while (i < L->length) //遍历数组,找到指定元素
{
if (L->data[i] == e)
{
return i + 1; //找到元素,返回位序
}
i++;
}
return 0;
}
7.元素修改函数
在此终于来到"增删查改"中最后一个的改,这部分与查找相比还要更加简单,废话不多说,请看下方代码:
void listupdata(sqlist* L, int pos, datatype e)
{
assert(L != NULL); //传入指针不为空,指定位置合法
assert(pos >= 1 && pos <= L->length);
L->data[pos - 1] = e; //直接修改指定位置的数据
}
8.顺序表销毁函数
在使用完顺序表后,我们要及时的将顺序表销毁,这和及时释放动态内存开辟的内存一样是个好习惯!除此之外,使用后销毁还有(1). 释放动态分配的内存(防止内存泄漏) 和 (2). 将顺序表指针置空、长度置 0（避免野指针）等功能,值得使用.
下面请看代码:
void DestroySeqList(sqlist* L)
{
assert(L != NULL ); // 校验：指针不能为空
free(list->data); // 释放动态分配的数组内存（核心！）
list->data = NULL; // 置空指针，防止野指针
list->length = 0; // 重置长度和容量
list->capacity = 0;
}
注意: (1). 必须传指针,参考上文中提到要修改原顺序表的成员或改变顺序表内指针变量指向，必须传入SeqList*指针. (2).先 free 再置空：释放内存后一定要把指针置NULL. (3). 如果是直接设定内存的静态顺序表,系统自动管理内存,函数结束后内存自动释放，无需销毁.
9.输入和预期输出
如下:
=== 初始化后 ===
SqList is empty
=== 插入后 ===
SqList (length: 4, capacity: 4): 5 15 10 20
=== 查找测试 ===
值为10的元素位序：3
=== 修改后 ===
SqList (length: 4, capacity: 4): 5 15 99 20
=== 删除头元素后 ===
被删除元素：5
SqList (length: 3, capacity: 4): 15 99 20
=== 删除尾元素后 ===
SqList (length: 2, capacity: 4): 15 99
=== 销毁后 ===
SqList is empty
10.两道编程题
那么在此顺序表详解内容就顺利完结了, 我在这里再贴上两道经典例题(有点关系), 大家有兴趣的可以自己做一下,因为内容不多,我过几天也会写一篇小文章讲解一下.
第一道题<<原地移除元素>> : https://leetcode-cn.com/problems/remove-element
第二道题<<合并两个有序数组>> : https://leetcode-cn.com/problems/merge-sorted-array/
如果觉得我写的还可以,还请多多点赞和收藏(人工狗头).
如果觉得所写内容对您有些许帮助,可以关注一下
正在写基础版贪吃蛇小游戏,持续更新,敬请期待.
菜鸟一枚,如有错误还请不吝赐教,关于文章表达形式的建议也请直接告知我.
正在学习中,你我共勉!
2026. 3.27
7:05
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)