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

✨ 坚持用清晰易懂的图解代码语言 让每个知识点都简单直观个人主页不呆头 · CSDN代码仓库不呆头 · Gitee专栏系列 《C语言》 《数据结构》 《C》 《Linux》座右铭“不患无位患所以立。”顺序表续目录头插尾删头删在指定位置之前插入数据删除POS位置的数据查找销毁目录头插解释 定义一个i在size下标位置每当头插一个数据将i-1的数据赋值给i然后i–继续上述操作直到i 0时i-1没有数据放到i中所以跳出循环然后将X插入到下表为0的位置size是有效数据的下一个位置代表有效数据个数因为不管是尾插头插任意位置插入都需要判断空间是否足够所以我们可以把判断空间的代码提出来自建一个函数然后调用voidSL_CheckCapacity(SL*ps){//判断空间是否足够-不够if(ps-sizeps-capacity){intnewCapacity(ps-capacity0)?4:ps-capacity*2;//空间不足需要动态申请空间 malloc申请固定大小空间,callocmalloc初始化,realloc继续申请新空间并拷贝原有数据释放原有空间//realloc的第二个数据是字节SLDataType*tmp(SLDataType*)realloc(ps-arr,newCapacity*sizeof(SLDataType));if(tmpNULL){printf(realloc failed!\n);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}}//头插voidSL_PushFront(SL*ps,SLDataType x){//防止空地址解引用造成错误if(psNULL){return;}//判断空间是否足够SL_CheckCapacity(ps);for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];ps-arr[0]x;ps-size;}}尾删当我想要删掉3有效数据个数size需要从下标4移到下标3有效数据个数变为3个被删除的位置应该如何处理答案是 直接–减减就行并不影响其他操作//尾删voidSL_PopBack(SL*ps){assert(psps-size);//顺序表不能为空且ps不能为NULL--ps-size;}这里我们可以定义一个打印函数来验证一下//打印voidSL_Print(SL*ps){for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}printf(\n);}#includeSeqList.hvoidtest01(){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将i1位置的数据赋值给i然后i最后size–//头删voidSL_PopFront(SL*ps){assert(psps-size);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}--ps-size;}打印出来观察回顾在尾部操作的时间复杂度为O1 在头部操作的时间复杂度为On。在指定位置之前插入数据定义size位置为i然后将i-1的数据赋值到i的位置然后i–直到i走到pos的位置就跳出循环然后将5赋值到i然后size但是如果空间不足够不能插入数据所以需要判断如果不够需要扩容。//指定位置之前插入数据voidSL_Insert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos0posps-size);SL_ChekCapacity(ps);//pos之后的数据整体往后挪动一位for(ips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;ps-size;}运行查看删除POS位置的数据这里需要将pos后的数据整体往前挪一位这里我们将pos位置定义为i我们就将i1的位置赋值给i然后i直到i size-1就跳出循环。//删除POS位置的数据voidSL_Erase(SL*ps,intpos){assert(ps);assert(pos0posps-size);for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}--ps-size;}运行观察查找//查找intSL_Find(SL*ps,SLDataType x){for(inti0;ips-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);intfindSL_Find(sl,3);if(find0){printf(找到了! \n);}else{printf(没有找到! \n);}}销毁//顺序表的销毁voidSL_Destroy(SL*ps){assert(ps);if(ps-arr)free(ps-arr);ps-arrNULL;//避免成为野指针ps-capacityps-size0;}不是呆头将一直坚持用清晰易懂的图解代码语言让每个知识点变得简单️ 【关注】 看一个非典型程序员如何用野路子解决正经问题 【点赞】 给“不写八股文”的技术分享一点鼓励 【收藏】 把这些“奇怪但有用”的代码技巧打包带走 【评论】 来聊聊——你遇到过最“呆头”的 Bug 是啥️ 【投票】 您的投票是支持我前行的动力技术没有标准答案让我们一起用最有趣的方式写出最靠谱的代码