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

​

🌟🌟作者主页：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)，运行效率不是很高。之后博主将会介绍链表的相关知识和功能，他会弥补顺序表的一些不足。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/385431.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

科技与占星的融合：AI 智能占星师

科技与占星的融合：AI 智能占星师

本文由 ChatMoney团队出品 在科技的前沿领域&#xff0c;诞生了一位独特的存在——AI占星师。它并非传统意义上的占星师&#xff0c;而是融合了先进的人工智能技术与神秘的占星学知识。 这能够凭借其强大的数据分析能力和精准的算法&#xff0c;对星辰的排列和宇宙的能量进行深…
阅读更多...
基于SpringBoot实现验证码功能

基于SpringBoot实现验证码功能

目录 一 实现思路 二 代码实现 三 代码汇总 现在的登录都需要输入验证码用来检测是否是真人登录&#xff0c;所以验证码功能在现在是非常普遍的&#xff0c;那么接下来我们就基于springboot来实现验证码功能。 一 实现思路 今天我们介绍的是两种主流的验证码&#xff0c;一…
阅读更多...
Bouncy Castle集成SM2与SM3

Bouncy Castle集成SM2与SM3

在Bouncy Castle库中&#xff0c;SM2和SM3是两种分别用于非对称加密和数字签名的密码算法&#xff0c;它们也可以结合使用&#xff0c;形成一种高安全性的加密签名方案&#xff0c;即SM2withSM3。以下是对SM2SM3的详细解释&#xff1a; 一、SM2算法 SM2是一种由中国国家密码管…
阅读更多...
GEE：设置ui.Map.Layer上交互矢量边界填充颜色为空，只显示边界

GEE：设置ui.Map.Layer上交互矢量边界填充颜色为空，只显示边界

一、目标 最近在GEE的交互功能鼓捣一些事情&#xff0c;在利用buffer功能实现了通过选点建立一个矩形后&#xff0c;需要将该矩形填充颜色设为空&#xff0c;只留边界。 然而通过正常设置layer的可视化参数并不能实现这一目的。因此只能另辟蹊径&#xff0c;改为定义矢量边界…
阅读更多...
VMware 上安装 CentOS 7 教程 (包含网络设置)

VMware 上安装 CentOS 7 教程 (包含网络设置)

**建议先看一些我安装VMware的教程&#xff0c;有些网络配置需要做一下 1.打开VMware&#xff0c;创建虚拟机 2.勾选自定义&#xff0c;点击下一步 3.点击下一步 4.勾选“稍后安装操作系统”&#xff0c;点击下一步 5.勾选linux&#xff0c;勾选centos7&#xff0c;点击下一步…
阅读更多...
pytorch-训练自定义数据集实战

pytorch-训练自定义数据集实战

目录 1. 步骤2. 加载数据2.1 继承Dataset2.1.1 生成name2label2.1.2 生成image path, label的文件2.1.3 __len__2.1.3 __getitem__2.1.4 数据切分为train、val、test 3. 建立模型4. 训练和测试4. 完整代码 1. 步骤 加载数据创建模型训练和测试迁移学习 2. 加载数据 这里以宝…
阅读更多...
Minos 多主机分布式 docker-compose 集群部署

Minos 多主机分布式 docker-compose 集群部署

参考 docker-compose搭建多主机分布式minio - 会bk的鱼 - 博客园 (cnblogs.com) 【运维】docker-compose安装minio集群-CSDN博客 Minio 是个基于 Golang 编写的开源对象存储套件&#xff0c;虽然轻量&#xff0c;却拥有着不错的性能 中文地址&#xff1a;MinIO | 用于AI的S3 …
阅读更多...
自学JavaScript(放假在家自学第一天)

自学JavaScript(放假在家自学第一天)

目录 JavaScript介绍分为以下几点 1.1 JavaScript 是什么 1.2JavaScript书写位置 1.3 Javascript注释 1.4 Javascript结束符 1.5 Javascript输入输出语法 JavaScript(是什么?) 是一种运行在客户端(浏览器)的编程语言&#xff0c;实现人机交互效果。 2.作用(做什么?)网…
阅读更多...
PCL-基于超体聚类的LCCP点云分割

PCL-基于超体聚类的LCCP点云分割

目录 一、LCCP方法二、代码实现三、实验结果四、总结五、相关链接 一、LCCP方法 LCCP指的是Local Convexity-Constrained Patch&#xff0c;即局部凸约束补丁的意思。LCCP方法的基本思想是在图像中找到局部区域内的凸结构&#xff0c;并将这些结构用于分割图像或提取特征。这种…
阅读更多...
入门 PyQt6 看过来（案例）13~ 制作一个颜色调节器

入门 PyQt6 看过来（案例）13~ 制作一个颜色调节器

本文给大家带来一个利用pyqt制作的颜色调节器&#xff0c;通过拨动滚动条或者旋钮就可以调整rgb三色进行颜色的微调&#xff0c;效果如下&#xff1a; 本文实现的是不同的UI设计&#xff0c;实现的相同的功能&#xff0c;我们先分析以下思路&#xff1a; 首先进行UI页面设计分析…
阅读更多...
SSL/TLS和SSL VPN

SSL/TLS和SSL VPN

1、SSL/TLS SSL安全套接字层&#xff1a;是一种加密协议&#xff0c;用于在网络通信中建立安全连接。它在应用层和传输层&#xff08;TCP/IP&#xff09;之间提供数据加密、服务器身份验证以及信息完整性验证 SSL只保护TCP流量&#xff0c;不保护UDP协议 TLS&#xff1a;传输层…
阅读更多...
VulnHub：cengbox1

VulnHub：cengbox1

靶机下载地址&#xff0c;下载完成后&#xff0c;用VirtualBox打开靶机并修改网络为桥接即可搭建成功。 信息收集 主机发现和端口扫描 扫描攻击机&#xff08;192.168.31.218&#xff09;同网段存活主机确认目标机ip&#xff0c;并对目标机进行全面扫描。 nmap 192.168.31.…
阅读更多...
【VS2019安装+QT配置】

【VS2019安装+QT配置】

【VS2019安装QT配置】 1. 前言2. 下载visual studio20193. visual studio2019安装4. 环境配置4.1 系统环境变量配置4.2 qt插件开发 5. Visual Studio导入QT项目6. 总结 1. 前言 前期安装了qt&#xff0c;发现creator编辑器并不好用&#xff0c;一点都不时髦。在李大师的指导下&…
阅读更多...
[网鼎杯 2020 朱雀组]Nmap（详细解读版）

[网鼎杯 2020 朱雀组]Nmap（详细解读版）

这道题考察nmap的一些用法,以及escapeshellarg和escapeshellcmd两个函数的绕过&#xff0c;可以看这里PHP escapeshellarg()escapeshellcmd() 之殇 (seebug.org) 两种解题方法&#xff1a; 第一种通过nmap的-iL参数读取扫描一个文件到指定文件中第二种是利用nmap的参数写入we…
阅读更多...
昇思25天学习打卡营第1天|快速入门-构建基于MNIST数据集的手写数字识别模型

昇思25天学习打卡营第1天|快速入门-构建基于MNIST数据集的手写数字识别模型

非常感谢华为昇思大模型平台和CSDN邀请体验昇思大模型&#xff01;从今天起&#xff0c;我将以打卡的方式&#xff0c;结合原文搬运和个人思考&#xff0c;分享25天的学习内容与成果。为了提升文章质量和阅读体验&#xff0c;我会将思考部分放在最后&#xff0c;供大家探索讨论…
阅读更多...
java-数据结构与算法-02-数据结构-05-栈

java-数据结构与算法-02-数据结构-05-栈

文章目录 1. 栈1. 概述2. 链表实现3. 数组实现4. 应用 2. 习题E01. 有效的括号-Leetcode 20E02. 后缀表达式求值-Leetcode 120E03. 中缀表达式转后缀E04. 双栈模拟队列-Leetcode 232E05. 单队列模拟栈-Leetcode 225 1. 栈 1. 概述 计算机科学中&#xff0c;stack 是一种线性的…
阅读更多...
[python游戏开发]用Python代码制作中国象棋游戏，适合新手小白练手

[python游戏开发]用Python代码制作中国象棋游戏，适合新手小白练手

Pygame 做的中国象棋&#xff0c;一直以来喜欢下象棋&#xff0c;写了 python 就拿来做一个试试&#xff0c;水平有限&#xff0c;希望源码能帮助大家更好的学习 python。总共分为四个文件&#xff0c;chinachess.py 为主文件&#xff0c;constants.py 数据常量&#xff0c;pie…
阅读更多...
新版海螺影视主题模板M3.1全解密版本多功能苹果CMSv10后台自适应主题

新版海螺影视主题模板M3.1全解密版本多功能苹果CMSv10后台自适应主题

苹果CMS2022新版海螺影视主题M3.1版本&#xff0c;这个主题我挺喜欢的&#xff0c;之前也有朋友给我提供过原版主题&#xff0c;一直想要破解但是后来找了几个SG11解密的大哥都表示解密需要大几百大洋&#xff0c;所以一直被搁置了。这个版本是完全解密的&#xff0c;无需SG11加…
阅读更多...
前端模块化CommonJS、AMD、CMD、ES6

前端模块化CommonJS、AMD、CMD、ES6

在前端开发中&#xff0c;模块化是一种重要的代码组织方式&#xff0c;它有助于将复杂的代码拆分成可管理的小块&#xff0c;提高代码的可维护性和可重用性。CommonJS、AMD&#xff08;异步模块定义&#xff09;和CMD&#xff08;通用模块定义&#xff09;是三种不同的模块规范…
阅读更多...
1、hadoop环境搭建

1、hadoop环境搭建

1、环境配置 ip(/etc/sysconfig/network-scripts) # 网卡1 DEVICEeht0 TYPEEthernet ONBOOTyes NM_CONTROLLEDyes BOOTPROTOstatic IPADDR192.168.59.11 GATEWAY192.168.59.1 NETMASK 255.255.255.0 # 网卡2 DEVICEeht0 TYPEEthernet ONBOOTyes NM_CONTROLLEDyes BOOTPROTOdh…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023