当前位置： 首页 > news >正文

【数据结构初阶】--顺序表(二)

news 2025/7/13 14:50:49

 

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。  

 前言：各位朋友们，从今天开始博主将恢复数据结构与算法专栏的更新，为大家分享数据结构初阶相关知识，用C语言与大家一起实现一些数据结构，那么我们这篇文章将会接着上次顺序表的初始化继续往后详细实现顺序表的头插，尾插，头删，尾删等功能。那么这里特别声明一下，博主会将这些功能分开实现，最后再单独为大家呈现本节所有内容的完整代码。

目录

一.顺序表的尾插

二.顺序表的头插

三.顺序表的尾删 

四.顺序表的头删

五.代码展现以及时间复杂度对比

SeqList.h：

SeqList.c： 

test.c： 

尾插，头插，尾删，头删时间复杂度对比：

一.顺序表的尾插

--这里分布实现的时候主要展示SeqList.c文件和test.c文件，头文件这里就不展示了。

SeqList.c：

//尾插
void SLPushBack(SL* ps, SLTDataType x)
{//空间不够if (ps->size == ps->capacity){//增容int newCapacity = ps->capacity ==0 ? 4 : 2 * ps->capacity;SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity*sizeof(SLTDataType));if (tmp = NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->size++] = x;//插入完后，size往后走
}

 重点提示： 

增容：我们一般成倍数增加，最好是两倍。这样可以有效降低增容的次数，就算可能会存在空间的浪费，但是不会太多。

我们再来看看在此过程中要注意的一些问题：

为了方便观察，我们再来实现一个打印顺序表的函数，很简单，这里就不解释了 

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

test.c： 

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);//1SLPushBack(&s, 2);//12SLPushBack(&s, 3);//123SLPushBack(&s, 4);//1234SLPrint(&s);//1 2 3 4}int main()
{test1();
}

--测试结果如下，成功打印出了经过4次尾插之后的顺序表

二.顺序表的头插

--头插和尾插都离不开空间的检查增容，所以我们在实现尾插之前可以直接用一个函数实现空间的检查，后续需要时直接复用就可以了。

//检查空间
void SLCheckCapacity(SL*ps)
{//扩容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, newcapacity * sizeof(SLdatatype));if (tmp == NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;
}

 SeqList.c：

//头插
void SLPushFront(SL* ps, SLdatatype x)
{assert(ps);//ps！=NULL//检查空间是否足够SLCheckCapacity(ps);//空间足够for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

 重点提示：

这里其实没啥坑了，该说的我们都在前面说过了，值得注意的就是头插，顺序表中的其它元素一定是从后往前的顺序向后移动一位，如图所示。再就是利用assert断言判断ps不为空了，用if也可以这里就不演示了。

test.c： 

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4
}int main()
{test1();
}

--测试出来也没啥问题，在前面头插了一个5。 

三.顺序表的尾删 

--顺序表的尾删其实就很简单了，大家可以想想我们是使用free释放掉还是令ps->arr[ps->size-1]=0，然后ps->size--呢？其实两者都不需要，直接ps->size--就结束了，不需要其它的过程。

 SeqList.c：

//尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}

重点提示： 

尾删这里直接就是ps->size--就可以了，不用其它的操作了。这里断言的时候注意ps->size也不能为0就行，不然删除不了。

test.c： 

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4SLPopBack(&s);SLPopBack(&s);SLPrint(&s);// 5 1 2
}int main()
{test1();
}

--测试之后没问题，尾删掉了两个数据，打印出来结果为5 1 2

四.顺序表的头删

SeqList.c：

//头删
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--;
}

重点提示： 

头删的断言和尾删一样，值得注意的是我们需要将数据按从前往后的顺序依次向前移动一位，注意最后循环的终止条件是i=ps->size-1，所以循环进行的条件就是i<ps->size-1。如图所示，1覆盖掉了原来的5。实现了头删，删除完后ps->size--就可以了。

test.c： 

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4SLPopBack(&s);SLPopBack(&s);SLPrint(&s);// 5 1 2SLPopFront(&s);SLPrint(&s);//1 2
}int main()
{test1();
}

--测试没有问题，头删掉一个5，最终结果打印出来是正确的

五.代码展现以及时间复杂度对比

SeqList.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLdatatype;
typedef struct SeqList
{SLdatatype* arr;int size;int capacity;
}SL;//顺序表初始化
void SLInit(SL* ps);//打印顺序表
void SLPrint(SL* ps);//尾插
void SLPushBack(SL* ps, SLdatatype x);
//头插
void SLPushFront(SL* ps, SLdatatype x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);

SeqList.c： 

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}//打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//检查空间
void SLCheckCapacity(SL*ps)
{//扩容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, newcapacity * sizeof(SLdatatype));if (tmp == NULL){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;
}//尾插
void SLPushBack(SL* ps, SLdatatype x)
{//检查空间是否足够SLCheckCapacity(ps);//空间足够ps->arr[ps->size++] = x;
}//头插
void SLPushFront(SL* ps, SLdatatype x)
{assert(ps);//检查空间是否足够SLCheckCapacity(ps);//空间足够for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}//尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}//头删
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--;
}

test.c： 

#include"SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);//1 2 3 4SLPushFront(&s, 5);SLPrint(&s);// 5 1 2 3 4SLPopBack(&s);SLPopBack(&s);SLPrint(&s);// 5 1 2SLPopFront(&s);SLPrint(&s);//1 2
}int main()
{test1();
}

尾插，头插，尾删，头删时间复杂度对比：

结论：我们通过对比可以看出顺序表的尾插，尾删的时间复杂度比头插，头删要好很多，所有我们可以看出如果操作尾部数据比较多的话，顺序表这个数据结构是比较优秀的。 

往期回顾：

【数据结构初阶】--算法复杂度的深度解析

【数据结构初阶】--顺序表(一)

结语：继上篇博客中我们实现的动态顺序表的初始化后，在本篇中我们完成了顺序表的尾插，头插，尾删，头删这四个接口的实现，那么顺序表的实现我们其实还没完全完成，博主将会在后续的博客中继续和大家一起实现顺序表中指定位置的插入和删除以及查找和修改这四个接口，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持

http://www.lryc.cn/news/586446.html

相关文章：

  • Compose笔记(三十四)--LayoutModifier
  • Raft-领导者选举
  • 基于YOLO11的垃圾分类AI模型训练实战
  • C语言课程设计--电子万年历
  • 第十八天，7月12日，八股
  • Agent 设计模式
  • 卫星通信终端天线的5种对星模式之二：DVB跟踪
  • Mamba架构的模型 （内容由deepseek辅助汇总）
  • 关于赛灵思的petalinux zynqmp.dtsi文件的理解
  • C++ Primer（第5版）- Chapter 7. Classes -001
  • Web学习笔记3
  • Windows环境下JS计时器精度差异揭秘
  • Qt：QCustomPlot类介绍
  • LangChain极速入门：用Python构建AI应用的新范式
  • zcbus使用数据抽取相当数据量实况
  • Scrapy爬虫中间件核心技术解析：定制化爬虫的神经中枢
  • CCS-MSPM0G3507-2-基础篇-定时器中断
  • 69 局部变量的空间分配
  • 通俗范畴论13 鸡与蛋的故事番外篇
  • C++类模板继承部分知识及测试代码
  • Golang操作MySQL json字段优雅写法
  • Hap包引用的Hsp报签名错误怎么解决
  • 【数据分析】03 - Matplotlib
  • LangChain 内存（Memory）
  • Java 大视界 -- Java 大数据机器学习模型在电商用户复购行为预测与客户关系维护中的应用（343）
  • C语言基础知识--动态内存管理
  • AD芯片（模数转换器）的有效位数（ENOB)
  • scrapy项目开发流程
  • C++中的容斥原理
  • Springboot aop面向切面编程