【数据结构与算法】—顺序表（续）

✨ 坚持用清晰易懂的图解+代码语言， 让每个知识点都简单直观！
🚀个人主页：不呆头 · CSDN
🌱代码仓库：不呆头 · Gitee
📌专栏系列：

• 📖 《C语言》
• 🧩 《数据结构》
• 💡 《C++》
• 🐧 《Linux》

💬座右铭：“不患无位，患所以立。”

目录

头插

解释： 定义一个i在size下标位置，每当头插一个数据，将i-1的数据赋值给i；然后i–，继续上述操作，直到i = 0时，i-1没有数据放到i中，所以跳出循环，然后将X插入到下表为0的位置（size是有效数据的下一个位置，代表有效数据个数）

因为不管是尾插，头插，任意位置插入都需要判断空间是否足够，所以我们可以把判断空间的代码提出来，自建一个函数，然后调用

voidSL_CheckCapacity(SL*ps){//判断空间是否足够-不够if(ps->size==ps->capacity){intnewCapacity=(ps->capacity==0)?4:ps->capacity*2;//空间不足，需要动态申请空间 malloc（申请固定大小空间）,calloc（malloc+初始化）,realloc（继续申请新空间，并拷贝原有数据，释放原有空间）//realloc的第二个数据是字节SLDataType*tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataType));if(tmp==NULL){printf("realloc failed!\n");exit(1);}ps->arr=tmp;ps->capacity=newCapacity;}}

//头插voidSL_PushFront(SL*ps,SLDataType x){//防止空地址解引用造成错误if(ps==NULL){return;}//判断空间是否足够SL_CheckCapacity(ps);for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];ps->arr[0]=x;++ps->size;}}

尾删

当我想要删掉3，有效数据个数size需要从下标4移到下标3，有效数据个数变为3个；被删除的位置应该如何处理？

答案是 直接–（减减）就行，并不影响其他操作

//尾删voidSL_PopBack(SL*ps){assert(ps&&ps->size);//顺序表不能为空且ps不能为NULL--ps->size;}

这里我们可以定义一个打印函数来验证一下

//打印voidSL_Print(SL*ps){for(inti=0;i<ps->size;i++){printf("%d ",ps->arr[i]);}printf("\n");}

#include"SeqList.h"voidtest01(){SL sl;SL_Init(&sl);SL_PushBack(&sl,1);SL_PushBack(&sl,2);SL_PushBack(&sl,3);SL_PushBack(&sl,4);SL_Print(&sl);/*SL_PushFront(&sl, 1); SL_PushFront(&sl, 2); SL_PushFront(&sl, 3); SL_PushFront(&sl, 4);*/SL_PopBack(&sl);SL_Print(&sl);SL_PopBack(&sl);SL_Print(&sl);SL_PopBack(&sl);SL_Print(&sl);}intmain(){test01();return0;}

头删

这里我们让下标为0的位置2为i，将i+1位置的数据赋值给i，然后i++，最后size–

//头删voidSL_PopFront(SL*ps){assert(ps&&ps->size);for(inti=0;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}--ps->size;}

打印出来观察

回顾：在尾部操作的时间复杂度为O（1）； 在头部操作的时间复杂度为O（n）。

在指定位置之前插入数据

定义size位置为i，然后将i-1的数据赋值到i的位置，然后i–，直到i走到pos的位置就跳出循环，然后将5赋值到i，然后size++；

但是如果空间不足够不能插入数据，所以需要判断，如果不够需要扩容。

//指定位置之前插入数据voidSL_Insert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos>=0&&pos<=ps->size);SL_ChekCapacity(ps);//pos之后的数据整体往后挪动一位for(i=ps->size;i>pos;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[pos]=x;++ps->size;}

运行查看

删除POS位置的数据

这里需要将pos后的数据整体往前挪一位，这里我们将pos位置定义为i，我们就将i+1的位置赋值给i，然后i++，直到i = size-1就跳出循环。

//删除POS位置的数据voidSL_Erase(SL*ps,intpos){assert(ps);assert(pos>=0&&pos<ps->size);for(inti=pos;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}--ps->size;}

运行观察

查找

//查找intSL_Find(SL*ps,SLDataType x){for(inti=0;i<=ps->size;i++){if(ps->arr[i]=x){//找到了returni;}}//未找到return-1;}

voidtest01(){SL sl;SL_Init(&sl);SL_PushBack(&sl,1);SL_PushBack(&sl,2);SL_PushBack(&sl,3);SL_PushBack(&sl,4);SL_Print(&sl);/*SL_PushFront(&sl, 1); SL_PushFront(&sl, 2); SL_PushFront(&sl, 3); SL_PushFront(&sl, 4);*///SL_PopBack(&sl);//SL_PopFront(&sl);//SL_Insert(&sl, 1, 520);// SL_Erase(&sl, 0);//SL_Print(&sl);//SL_PopBack(&sl);// SL_PopFront(&sl);// SL_Print(&sl);// SL_PopBack(&sl);//SL_PopFront(&sl);// SL_Print(&sl);intfind=SL_Find(&sl,3);if(find>=0){printf("找到了! \n");}else{printf("没有找到! \n");}}

销毁

//顺序表的销毁voidSL_Destroy(SL*ps){assert(ps);if(ps->arr)free(ps->arr);ps->arr=NULL;//避免成为野指针ps->capacity=ps->size=0;}

不是呆头将一直坚持用清晰易懂的图解+代码语言，让每个知识点变得简单！
👁️ 【关注】 看一个非典型程序员如何用野路子解决正经问题
👍 【点赞】 给“不写八股文”的技术分享一点鼓励
🔖 【收藏】 把这些“奇怪但有用”的代码技巧打包带走
💬 【评论】 来聊聊——你遇到过最“呆头”的 Bug 是啥？
🗳️ 【投票】 您的投票是支持我前行的动力
技术没有标准答案，让我们一起用最有趣的方式，写出最靠谱的代码！ 🎮💻