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

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

news 2025/7/13 15:14:38

 

🔥个人主页：@草莓熊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.xdnf.cn/news/1111411.html

相关文章：

  • 【读书笔记】《C++ Software Design》第一章《The Art of Software Design》
  • 【一起来学AI大模型】RAG系统组件：检索器（LangChain）
  • Python 实战：构建可扩展的命令行插件引擎
  • 试用了10款翻译软件后，我只推荐这一款！完全免费还超好用
  • 挖矿病毒判断与处理 - 入门
  • DBeaver连接MySQL8.0报错Public Key Retrieval is not allowed
  • Redis集群会有写操作丢失吗？为什么?
  • 1. 好的设计原则
  • C++法则21：避免将#include放在命名空间内部。
  • 箭头函数（Arrow Functions）和普通函数（Regular Functions）
  • 【JVM|类加载】第三天
  • 《汇编语言：基于X86处理器》第7章 整数运算（3）
  • AI：机器人未来的形态是什么？
  • 商业智能（BI）系统深度解析
  • 希尔排序和选择排序及计数排序的简单介绍
  • 【学习笔记】Nginx常用安全配置
  • QWidget的属性
  • 华为业务变革项目IPD基本知识
  • 前端面试宝典---项目难点2-智能问答对话框采用虚拟列表动态渲染可视区域元素（10万+条数据）
  • 一文理解缓存的本质：分层架构、原理对比与实战精粹
  • TinyBERT：知识蒸馏驱动的BERT压缩革命 | 模型小7倍、推理快9倍的轻量化引擎
  • 多模态大模型》多模态基础模型》多模态对齐、融合和表示
  • 27. 移除元素
  • 浅谈 Python 中的 yield——yield的返回值与send()的关系
  • 关于数字签名
  • 容器化改造避坑指南：传统应用迁移K8s的10个关键节点（2025实战复盘）
  • 【Go + Gin 实现「双 Token」管理员登录】
  • linux系统----LVS负载均衡集群（NET/DR）模式
  • Arduino 无线通信实战：使用 RadioHead实现 315MHz 433M模块数据传输
  • net.createServer详解