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

【数据结构】顺序表（c语言实现）（附源码）

news 来源：原创 2024/9/20 5:35:57

​

🌟🌟作者主页：ephemerals__

🌟🌟所属专栏：数据结构

目录

前言

1.顺序表的概念与结构

2.顺序表的分类

3.顺序表的实现

3.1 结构定义及方法的声明

3.2 方法的实现

3.2.1 初始化

3.2.2 销毁

3.2.3 打印顺序表

3.2.4 检查空间大小，不够则增容

3.2.5 尾插

3.2.6 头插

3.2.7 尾删

3.2.8 头删

3.2.9 指定位置之前插入

3.2.10 指定位置删除 

3.2.11 查找

4.程序全部代码

总结

前言

        在我们学习顺序表之前，先引入一个概念：线性表。那么线性表是什么呢？

线性表，是n个具有相同特性的数据元素的有限序列。线性表在数据结构当中广泛使用。常见的线性表有：顺序表、链表、栈、队列、字符串......线性表在逻辑上是线性结构，也就是说数据元素就像一条线一样串联在一起，但是它的每一个数据元素的地址并不一定是连续的。

了解到顺序表是线性表的一种，接下来我们进入正题，开始正式学习顺序表。

1.顺序表的概念与结构

顺序表的概念：顺序表是一段按照连续的内存地址将数据元素依次存储的数据结构。一般情况下，它的底层逻辑是数组。也就是说，顺序表的每个元素的内存地址是连续的。

​

顺序表和数组的区别：虽然顺序表的底层结构是数组，但是我们在实现顺序表的过程中，对数组进行了封装，在数组的基础上增加了对它的一些方法，例如增删查改等操作。

2.顺序表的分类

        顺序表可以分为静态顺序表和动态顺序表。顾名思义，静态顺序表的大小是固定不变的。它的结构定义如下：

#define N 10typedef int SLDataType;//静态顺序表
typedef struct SeqList
{SLDataType arr[N];//固定大小的数组int size;//有效数据的个数
}SL;

显然，这种结构是有缺陷的。当我们需要存放的数据很多时，它的内存大小是不够的。当存放的数据过少时，又会造成空间的浪费。所以，就有了动态顺序表。动态顺序表的内存大小可以根据数据的数量发生改变。它的结构定义如下：

typedef int SLDataType;//动态顺序表
typedef struct SeqList
{SLDataType* arr;//定义起始指针，后续动态开辟内存空间int size;//有效数据的个数int capacity;//数组的空间大小
}SL;

由于动态顺序表强大的灵活性和实用性，我们平时所谈到的顺序表一般都指的是动态顺序表。接下来我们在以上结构的基础上，一一实现动态顺序表的基本功能。

3.顺序表的实现

3.1 结构定义及方法的声明

#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 SLDestroy(SL* ps);//打印顺序表
void SLPrint(SL* ps);//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType n);//头插
void SLPushFront(SL* ps, SLDataType n);//尾删
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n);//指定位置删除数据
void SLErase(SL* ps, int pos);//查找
void SLFind(SL* ps, SLDataType n);

以上就是关于顺序表的定义和一些方法的的声明。接下来，我们尝试一一实现这些方法。

3.2 方法的实现

3.2.1 初始化

        初始化时，我们将结构体赋一个初值就可以。代码如下：

//初始化
void SLInit(SL* ps)
{assert(ps);//断言一下，确保传入的不是空指针ps->arr = NULL;ps->capacity = ps->size = 0;
}

初始情况下，arr是一个空指针，结构的空间大小和数据个数都为0。

3.2.2 销毁

        销毁顺序表时，我们将arr的内存释放掉，然后将空间大小和数据个数调整尾0就好了。代码如下：

//销毁
void SLDestroy(SL* ps)
{assert(ps);//防止传空指针if (ps->arr != NULL)//防止多次释放{free(ps->arr);ps->arr = NULL;}ps->capacity = ps->size = 0;
}

3.2.3 打印顺序表

//打印顺序表
void SLPrint(SL* ps)
{assert(ps);//防止传空指针for (int i = 0; i < ps->size; i++)//遍历打印{printf("%d ", ps->arr[i]);}printf("\n");
}

3.2.4 检查空间大小，不够则增容

        在我们插入数据的时候，数据的总数有可能会超出顺序表的空间大小，此时我们就需要检查空间大小，如果不够就需要增容。我们将增容封装为一个函数来实现：

//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->capacity == ps->size)//空间大小与数据个数相等则说明空间已满{int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//设定一个新空间大小，第一次增容时大小为4，之后每次以2倍的形式增容SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));//防止内存丢失，创建局部变量暂时接收起始地址if (tmp == NULL)//内存开辟失败退出程序{perror("realloc");exit(1);}ps->arr = tmp;//将调整好的内存赋值给arrps->capacity = NewCapacity;}
}

3.2.5 尾插

//尾插
void SLPushBack(SL* ps, SLDataType n)
{assert(ps);SLCheckCapacity(ps);//检查空间大小ps->arr[ps->size++] = n;//在下标为size的位置插入元素，然后size自增
}

3.2.6 头插

        在头插的过程中，我们需要先将所有的数据全部后移一位，然后在第一个位置插入数据。

​

代码如下：

//头插
void SLPushFront(SL* ps, SLDataType n)
{assert(ps);SLCheckCapacity(ps);//检查空间大小for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];//所有元素后移一位}ps->arr[0] = n;//第一个位置插入数据ps->size++;//元素个数加1
}

3.2.7 尾删

//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//若数据为空，则不能删除ps->size--;//size自减，则最后一个元素无法被访问到，相当于删除了最后一个元素
}

这里只需要将size自减，使得最后一个元素无法被访问，相当于完成了删除操作。

3.2.8 头删

        头删时，我们将第一个元素之后的所有元素向前移动一位即可。代码如下：

//头删
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--;//元素个数减1
}

3.2.9 指定位置之前插入

        在我们实现指定位置插入时，需要将该位置及之后的所有元素整体向后移动一位，然后再插入元素即可。代码如下：

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n)//这里的参数pos是下标
{assert(ps && pos >= 0 && pos <= ps->size);//确保pos在合理范围内SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];//将pos位置后的元素整体向后移动一位}ps->arr[pos] = n;//插入ps->size++;//元素个数加1
}

3.2.10 指定位置删除

        指定位置删除时，将该位置之后的元素整体向前移动一位，覆盖该元素即可。代码如下：

//指定位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps && ps->size && pos >= 0 && pos < ps->size);//确保pos在合理范围内for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];//pos之后的元素整体向前移动一位，覆盖pos位置元素}ps->size--;//元素个数减1
}

3.2.11 查找

        查找元素时，我们只需要遍历顺序表，找到符合的元素即可。

//查找
void SLFind(SL* ps, SLDataType n)
{assert(ps);for (int i = 0; i < ps->size; i++)//遍历顺序表{if (ps->arr[i] == n){return i;//匹配成功则返回对应下标}}return -1;//找不到返回-1
}

4.程序全部代码

        程序全部代码如下：

#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 SLDestroy(SL* ps);//打印顺序表
void SLPrint(SL* ps);//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType n);//头插
void SLPushFront(SL* ps, SLDataType n);//尾删
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n);//指定位置删除数据
void SLErase(SL* ps, int pos);//查找
void SLFind(SL* ps, SLDataType n);//初始化
void SLInit(SL* ps)
{assert(ps);//断言一下，确保传入的不是空指针ps->arr = NULL;ps->capacity = ps->size = 0;
}//销毁
void SLDestroy(SL* ps)
{assert(ps);//防止传空指针if (ps->arr != NULL)//防止多次释放{free(ps->arr);ps->arr = NULL;}ps->capacity = ps->size = 0;
}//打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->capacity == ps->size)//空间大小与数据个数相等则说明空间已满{int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//设定一个新空间大小，第一次增容时大小为4，之后每次以2倍的形式增容SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));//防止内存丢失，创建局部变量暂时接收起始地址if (tmp == NULL)//内存开辟失败退出程序{perror("realloc");exit(1);}ps->arr = tmp;//将调整好的内存赋值给arrps->capacity = NewCapacity;}
}//尾插
void SLPushBack(SL* ps, SLDataType n)
{assert(ps);SLCheckCapacity(ps);//检查空间大小ps->arr[ps->size++] = n;//在下标为size的位置插入元素，然后size自增
}//头插
void SLPushFront(SL* ps, SLDataType n)
{assert(ps);SLCheckCapacity(ps);//检查空间大小for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];//所有元素后移一位}ps->arr[0] = n;//第一个位置插入数据ps->size++;//元素个数加1
}//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//若数据为空，则不能删除ps->size--;//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--;//元素个数减1
}//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n)//这里的参数pos是下标
{assert(ps && pos >= 0 && pos <= ps->size);//确保pos在合理范围内SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];//将pos位置后的元素整体向后移动一位}ps->arr[pos] = n;//插入ps->size++;//元素个数加1
}//指定位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps && ps->size && pos >= 0 && pos < ps->size);//确保pos在合理范围内for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];//pos之后的元素整体向前移动一位，覆盖pos位置元素}ps->size--;//元素个数减1
}//查找
void SLFind(SL* ps, SLDataType n)
{assert(ps);for (int i = 0; i < ps->size; i++)//遍历顺序表{if (ps->arr[i] == n){return i;//匹配成功则返回对应下标}}return -1;//找不到返回-1
}

总结

        以上就是我们顺序表的概念及功能实现。不难发现，它的许多方法都需要遍历数组，时间复杂度为O(N)，运行效率不是很高。之后博主将会介绍链表的相关知识和功能，他会弥补顺序表的一些不足。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • STM32的GPIO输入输出方式设置示例
  • 了解Selenium中的WebElement
  • VulnHub：funbox10
  • 日常开发记录分享-SQL中的partition分区功能使用
  • 前端渲染模式
  • SSRF (服务端请求伪造)
  • Java的@DateTimeFormat注解与@JsonFormat注解的使用对比
  • 微服务-MybatisPlus下
  • vue3双向绑定的原理
  • Sping项目只能勾选17和21 (已解决) 导致的后续Invalid bound statement (not found):
  • 壹佰全家桶全应用源码在线更新升级
  • Redis快速入门基础
  • springboot集成mybatis时，dao层的mapper类需要添加@Repository注解吗？
  • C++树形结构（3 树的中心、重心）
  • Keil5软件仿真error65报错解决
  • 【Leetcode】101. 对称二叉树
  • magento2项目上线注意事项
  • markdown编辑器简评
  • MySQL数据库运维之数据恢复
  • Python 使用 Tornado 框架实现 WebHook 自动部署 Git 项目
  • Python实现BT种子转化为磁力链接【实战】
  • tensorflow学习笔记3——MNIST应用篇
  • text-decoration与color属性
  • 阿里云应用高可用服务公测发布
  • 第十八天-企业应用架构模式-基本模式
  • 机器人定位导航技术 激光SLAM与视觉SLAM谁更胜一筹？
  • 基于Javascript， Springboot的管理系统报表查询页面代码设计
  • 技术攻略】php设计模式(一)：简介及创建型模式
  • 前言-如何学习区块链
  • 浅谈Golang中select的用法
  • 如何邀请好友注册您的网站(模拟百度网盘)
  • ＂无招胜有招＂nbsp;史上最全的互…
  • # windows 安装 mysql 显示 no packages found 解决方法
  • #HarmonyOS：Web组件的使用
  • #includecmath
  • (09)Hive——CTE 公共表达式
  • （4）STL算法之比较
  • （C语言）求出1,2,5三个数不同个数组合为100的组合个数
  • (差分)胡桃爱原石
  • （四）Tiki-taka算法（TTA）求解无人机三维路径规划研究（MATLAB）
  • （已解决）vue+element-ui实现个人中心，仿照原神
  • （转）大型网站的系统架构
  • (转载)在C#用WM_COPYDATA消息来实现两个进程之间传递数据
  • .gitattributes 文件
  • .java 指数平滑_转载：二次指数平滑法求预测值的Java代码
  • .NET CF命令行调试器MDbg入门（四） Attaching to Processes
  • .NET Core实战项目之CMS 第一章 入门篇-开篇及总体规划
  • .NET MVC、 WebAPI、 WebService【ws】、NVVM、WCF、Remoting
  • .NET 指南：抽象化实现的基类
  • .NET/C# 将一个命令行参数字符串转换为命令行参数数组 args
  • .NET面试题解析(11)-SQL语言基础及数据库基本原理
  • /proc/stat文件详解（翻译）
  • ::什么意思
  • @Data注解的作用
  • @ohos.systemParameterEnhance系统参数接口调用：控制设备硬件(执行shell命令方式)