84.【C语言】数据结构之顺序表的头部插入和删除
目录
3.操作顺序表
1.分析头部插入函数
SeqList.c写入
void SLPushFront(SL* ps,SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
int end = ps->size-1;//定义尾部,一开始a[end-1]指向最后一个元素
while (end >= 0)//注意循环条件
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}容量检查函数
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("realloc");
return;//错误返回
}
ps->capacity *= 2;
ps->a = tmp;
}
}注意
头插时,元素会逐个向后移动,因此要先进行容量检查,再移动元素,最后不要忘记为有效元素个数size+1;
main.c改为
#include "SeqList.h"
//定义测试顺序表的函数
void TestSeqList1()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s);
SLPushFront(&s, 1);
SLPrint(&s);
SLDestory(&s);
}
int main()
{
TestSeqList1();
return 0;
}SeqList.h添加SLPushFront的声明
运行结果
头插N个元素的时间复杂度为,运行效率不高,尽量避免头插,使用尾插(尾插N个元素的时间复杂度为
)
2.分析头部删除函数
SLPopFront代码
void SLPopFront(SL * ps)
{
assert(ps);
assert(ps->size);
int begin = 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}注:ps->size可能为负数,因此要断言ps->size的正负
main.c改为
void TestSeqList1()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLDestory(&s);
}
SeqList.h添加SLPopFront的声明
图分析
运行结果
原文地址：https://blog.csdn.net/2401_85828611/article/details/143033360
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！