顺序表详解（SeqList）

本文使用C语言进行顺序表的代码实现。

博主将使用代码和相关知识相结合的方式进行讲解，简单易懂，懵懂的大学生一听就会~

顺序表是一种线性表的存储结构，它将数据元素存储在一段连续的存储空间中，每个元素占据一个存储单元，并按照逻辑顺序依次存放。顺序表可以采用数组来实现，通过数组的下标来表示元素在顺序表中的位置，从而实现对元素的快速访问和操作。

一、顺序表的定义

线性表是一种基本的数据结构，它是由一组相同类型的数据元素组成的有序序列。线性表的特点是元素之间的关系是线性的，即每个元素都有一个唯一的索引（也称为位置），并且可以通过索引访问元素。

线性表有两种常见的实现方式：顺序表和链表。顺序表是使用一组连续的内存空间来存储元素，而链表则是使用一组离散的内存空间来存储元素，并通过指针将它们连接起来。

本文讲解顺序表的代码实现。

二、顺序表的实现

我们使用多文件的方法来进行顺序表的实现。

  • SeqList.h用存放需要使用的头文件及声明函数
  • SeqList.c用来实现对于顺序表的操作函数
  • test用来进行顺序表的功能测试和使用

1.顺序表的初始化

//结构体创建
typedef int SQDataType;typedef struct SeqList
{SQDataType* a;int size;     // 有效数据的个数int capacity; // 容量
}SL;//顺序表初始化
void SeqListInit(SL* ps)
{ps->a = NULL;ps->size = 0;ps->capacity = 0;
}

首先创建一个结构体用来存放一个指针a，数据个数和顺序表的容量。

2.设置修改检查函数

//作为每次增添时的检查函数，如果顺序表的存储满了就进行扩容
void SeqListCheckCapacity(SL* ps)
{// 满了就要扩容if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}else{ps->a = tmp;ps->capacity = newcapacity;}}
}

 该函数用于检查顺序表（a）是否大小足够进行添加数据，如果大小为0那么将空间设置为4，如果不够用即用realloc扩容到原大小的二倍。，之后再对相关数值进行修改。

3.从头部插入数据

void SeqListPushFront(SL* ps, SQDataType x)
{SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;}

头插的方法相当于是将整个顺序表向后挪动一位，最后将第一个位置空下然后插入数据。但是挪动的顺序是从后往前挪动，如果是从前往后的话就会将数据覆盖，从而无法正常插入。

4.从尾部插入数据

void SeqListPushBack(SL* ps, SQDataType x)
{SeqListCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;}

尾插就是直接向顺序表最后添加数据。

5.指定位置插入数据

void SeqListInsert(SL* ps, int pos, SQDataType x)
{assert(pos <= ps->size);SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}//将pos位置及之后全部向后移动一位，然后再pos位置上插入xps->a[pos] = x;ps->size++;
}

关于assert断言相关知识如果想深入学习可以点击这段话跳转至博主的另一篇博客~

首先使用assert断言进行一个条件判断，确保插入的位置合法。之后的移动数据位置的操作和头插的方法类似，将pos位置和之后的数据全部向后移动一个位置，然后再在pos这个下标的位置上添加数据。

6.从头部删除数据

void SeqListPopFront(SL* ps)
{assert(ps->size > 0);int start = 1;while (start < ps->size){ps->a[start - 1] = ps->a[start];++start;}ps->size--;
}

代码实现的操作就是将第一个位置上的位置进行覆盖，用第一个之后的数据逐一将前面一个的数据进行覆盖，从而达到删除第一个数据的效果。最后将size进行修改。

7.从尾部删除数据

void SeqListPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;
}

直接将顺序表的size进行-1就可以实现删除最后一个数据的操作。

8.指定位置删除数据

void SeqListErase(SL* ps, int pos)
{assert(pos < ps->size);int start = pos + 1;while (start < ps->size){ps->a[start - 1] = ps->a[start];++start;}ps->size--;
}

操作与头删类似，先设置start的数值为要删除的那个下标，然后将start之后的数据依次向前挪动覆盖数据实现在该指定位置的数据删除。

9.指定位置修改数据

void SeqListModity(SL* ps, int pos, SQDataType x)
{assert(pos < ps->size);ps->a[pos] = x;
}

修改数据的操作十分简单，找到该位置的下标然后进行修改即可完成操作。

10.查找数据

int SeqListFind(SL* ps, SQDataType x)
{for (int i = 0; i < ps->size; ++i){if (ps->a[i] == x){return i;}}return -1;
}

遍历顺序表，逐个进行对比，与要查找的数据相同时返回该数据位置的下标，未找到返回-1.

三、整体程序代码展现

因为指定位置插入数据的函数和指定位置删除数据的函数可以完成头插尾插，头删尾删的操作，所以在程序中直接使用这两个插入方法进行头尾的操作减少了代码量。

在test.c中通过简单的菜单和分支操作可以对顺序表进行简单的操作。

SeqList.h

#pragma once#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#include <assert.h>// 增强程序可维护性
typedef int SQDataType;
// 动态的
typedef struct SeqList
{SQDataType* a;int size;     // 有效数据的个数int capacity; // 容量
}SL;//typedef struct SeqList SL;// 增删查改等接口函数
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestory(SL* ps);// 头插 尾插 头删 尾删
void SeqListPushBack(SL* ps, SQDataType x);
void SeqListPushFront(SL* ps, SQDataType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);
void SeqListInsert(SL* ps, int pos, SQDataType x);
void SeqListErase(SL* ps, int pos);int SeqListFind(SL* ps, SQDataType x);
void SeqListModity(SL* ps, int pos, SQDataType x);

SeqList.c

#include "SeqList.h"// 增删查改等接口函数//初始化数组
void SeqListInit(SL* ps)
{ps->a = NULL;ps->size = 0;ps->capacity = 0;
}//清除内存
void SeqListDestory(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}//作为每次增添时的检查函数，如果顺序表的存储满了就进行扩容
void SeqListCheckCapacity(SL* ps)
{// 满了就要扩容if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}else{ps->a = tmp;ps->capacity = newcapacity;}}
}// 头插 尾插 头删 尾删
void SeqListPushBack(SL* ps, SQDataType x)
{/*SeqListCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;*/SeqListInsert(ps, ps->size, x);
}void SeqListPushFront(SL* ps, SQDataType x)
{//SeqListCheckCapacity(ps);1、初始条件2、结束条件3、迭代过程//int end = ps->size - 1;//while (end >= 0)//{//	ps->a[end + 1] = ps->a[end];//	--end;//}//ps->a[0] = x;//ps->size++;SeqListInsert(ps, 0, x);}void SeqListPopBack(SL* ps)
{//assert(ps->size > 0);ps->a[ps->size - 1] = 0;//ps->size--;SeqListErase(ps, ps->size - 1);
}void SeqListPopFront(SL* ps)
{assert(ps->size > 0);/*int start = 1;while (start < ps->size){ps->a[start - 1] = ps->a[start];++start;}ps->size--;*/SeqListErase(ps, 0);
}void SeqListInsert(SL* ps, int pos, SQDataType x)
{assert(pos <= ps->size);SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}//将pos位置及之后全部向后移动一位，然后再pos位置上插入xps->a[pos] = x;ps->size++;
}void SeqListErase(SL* ps, int pos)
{assert(pos < ps->size);int start = pos + 1;while (start < ps->size){ps->a[start - 1] = ps->a[start];++start;}ps->size--;
}int SeqListFind(SL* ps, SQDataType x)
{for (int i = 0; i < ps->size; ++i){if (ps->a[i] == x){return i;}}return -1;
}//修改pos位置上的值为x
void SeqListModity(SL* ps, int pos, SQDataType x)
{assert(pos < ps->size);ps->a[pos] = x;
}void SeqListPrint(SL* ps)
{for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}

test.c

#include "SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);SeqListPushBack(&sl, 9);SeqListPushBack(&sl, 10);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPushBack(&sl, 11);SeqListPrint(&sl);SeqListDestory(&sl);
}void TestSeqList2()
{SL sl;SeqListInit(&sl);SeqListPushFront(&sl, 1);SeqListPushFront(&sl, 2);SeqListPushFront(&sl, 3);SeqListPushFront(&sl, 4);SeqListPushFront(&sl, 5);SeqListPushFront(&sl, 6);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);SeqListDestory(&sl);
}void TestSeqList3()
{SL sl;SeqListInit(&sl);SeqListPushFront(&sl, 1);SeqListPushFront(&sl, 2);SeqListPushFront(&sl, 3);SeqListPushFront(&sl, 4);SeqListPushFront(&sl, 5);SeqListPushFront(&sl, 6);SeqListPrint(&sl);SeqListInsert(&sl, 1, 20);SeqListPrint(&sl);SeqListErase(&sl, 1);SeqListPrint(&sl);SeqListDestory(&sl);
}void menu()
{printf("**********************************************\n");printf("1.尾插数据， 2.头插数据\n");printf("3.尾删数据， 4.头删数据\n");printf("5.打印数据，-1.退出\n");printf("**********************************************\n");printf("请输入你操作选项:");
}int main()
{SL s;SeqListInit(&s);int option = 0;int x = 0;while (option != -1){menu();scanf("%d", &option);switch (option){case 1:printf("请输入你要插入的数据，以-1结束\n");do {scanf("%d", &x);if (x != -1){SeqListPushBack(&s, x);}} while (x != -1);break;case 2:break;case 3:break;case 4:break;case 5:SeqListPrint(&s);break;default:break;}}SeqListDestory(&s);return 0;
}

那么本篇博客到此就结束了，如果可以帮助到你是博主的荣幸！

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

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

相关文章

Java入门-可重入锁

Java入门-可重入锁

可重入锁 什么是可重入锁? 当线程获取某个锁后&#xff0c;还可以继续获取它&#xff0c;可以递归调用&#xff0c;而不会发生死锁&#xff1b; 可重入锁案例 程序可重入加锁 A.class,没有发生死锁。 sychronized锁 package com.wnhz.lock.reentrant;public class Sychroniz…
阅读更多...
【Linux】git操作 - gitee

【Linux】git操作 - gitee

1.使用 git 命令行 安装 git yum install git 2.使用gitee 注册账户 工作台 - Gitee.com 进入gitee&#xff0c;根据提示注册并登录 新建仓库 仓库名称仓库简介初始换仓库 3.Linux-git操作 进入仓库&#xff0c;选择“克隆/下载” 复制下面的两行命令进行git配置 然后将仓库clo…
阅读更多...
搜索中关于稀疏检索和稠密向量检索的召回效果比较

搜索中关于稀疏检索和稠密向量检索的召回效果比较

不同检索方式说明 最近在做搜索召回提升相关的研究工作。对比了稀疏检索和稠密向量检索的效果。其中使用的搜索引擎为elasticsearch8.x版本。稀疏检索包括BM25的检索方式&#xff0c;以及es官方在8.8之后版本提供的稀疏向量模型的方式。稠密向量检索&#xff0c;是指借助机器学…
阅读更多...
基于springboot实现的音乐网站

基于springboot实现的音乐网站

一、系统架构 前端&#xff1a;html | js | css | bootstrap 后端&#xff1a;springboot | mybatis 环境&#xff1a;jdk1.8 | mysql | maven 二、 代码及数据库 三、功能介绍 01. 登录页 02. 用户注册 03. 首页 04. 喜欢 05. 查询
阅读更多...
1902_野火FreeRTOS教程内核在STM32中用到的2个中断PENDSV和SYSTICK

1902_野火FreeRTOS教程内核在STM32中用到的2个中断PENDSV和SYSTICK

1902_野火FreeRTOS教程内核在STM32中用到的2个中断PENDSV和SYSTICK 全部学习汇总&#xff1a; g_FreeRTOS: FreeRTOS学习笔记 (gitee.com) 上面是涉及到的源代码&#xff0c;而这次需要分析的就是78、79行的两个中断。首先&#xff0c;需要确认NVIC_SYSPRI2寄存器的作用。 进一…
阅读更多...
【dc-dc】世微AP5125 外置MOS 5-100V 8A平均电流型LED降压恒流驱动器 SOT23-6

【dc-dc】世微AP5125 外置MOS 5-100V 8A平均电流型LED降压恒流驱动器 SOT23-6

产品描述 AP5125 是一款外围电路简单的 Buck 型平均电流检测模式的 LED 恒流驱动器&#xff0c;适用于 8-100V 电压范围的非隔离式大功率恒流 LED 驱动领域。芯片采用固定频率 140kHz 的 PWM 工作模式&#xff0c; 利用平均电流检测模式&#xff0c;因此具有优异的负载调整 率特…
阅读更多...
SICTF round#3 web

SICTF round#3 web

1.100&#xff05;_upload url可以进行文件包含&#xff0c;但是flag被过滤 看一下源码 <?phpif(isset($_FILES[upfile])){$uploaddir uploads/;$uploadfile $uploaddir . basename($_FILES[upfile][name]);$ext pathinfo($_FILES[upfile][name],PATHINFO_EXTENSION);$t…
阅读更多...
Linux程序性能分析60秒+

Linux程序性能分析60秒+

Linux性能分析大师Brendan Gregg有一篇非常著名的博客&#xff0c;介绍在性能分析开始的60秒内&#xff0c;利用标准的Linux命令行工具&#xff0c;执行一次充分的性能检查&#xff0c;获得系统资源利用率和进程运行情况的整体概念&#xff0c;查看是否存在异常、评估饱和度。本…
阅读更多...
【数据结构】二叉树的三种遍历

【数据结构】二叉树的三种遍历

目录 一、数据结构 二、二叉树 三、如何遍历二叉树 一、数据结构 数据结构是计算机科学中用于组织和存储数据的方式。它定义了数据元素之间的关系以及对数据元素的操作。常见的数据结构包括数组、链表、栈、队列、树、图等。 数组是一种线性数据结构&#xff0c;它使用连续…
阅读更多...
com.alibaba.fastjson.JSONException: toJSON error的原因

com.alibaba.fastjson.JSONException: toJSON error的原因

问题&#xff1a; 导出接口报错&#xff0c;显示json格式化异常 发现问题&#xff1a; 第一个参数为HttpResponse,转换成json的时候报错 修改方法&#xff1a; 1.调换两个参数的位置 2.在aop判断里边 把ServletAPI过滤掉 Before("excudeWebController()")pub…
阅读更多...
苍穹外卖学习-----2024/02/21

苍穹外卖学习-----2024/02/21

1.新增员工 /*** 处理SQL异常* param sqlIntegrityConstraintViolationException* return*/ExceptionHandlerpublic Result exceptionHandler(SQLIntegrityConstraintViolationException sqlIntegrityConstraintViolationException){//String message sqlIntegrityConstraintV…
阅读更多...
String字符串，FastJson常用操作方法

String字符串，FastJson常用操作方法

JSON字符串操作 1、创建配置环境 # 引入测试包testImplementation group: org.springframework.boot, name: spring-boot-starter-test, version: 2.2.6.RELEASE # 创建测试类RunWith(SpringRunner.class)SpringBootTestpublic class JsonTest {Testpublic void test(){Syste…
阅读更多...
第100讲：MHA+Atlas实现MySQL主从复制读写分离分布式集群

第100讲：MHA+Atlas实现MySQL主从复制读写分离分布式集群

文章目录 1.Atlas读写分离简介2.搭建MHA高可用MySQL主从复制集群3.部署配置Atlas读写分离中间件3.1.安装Atlas读写分离中间件3.2.配置读写分离3.3.启动Atlas读写分离 4.读写分离集群测试5.生产环境中创建一个用户通过Atlas使用6.Atlas通过管理接口实现在线管理7.Atlas自动分表 …
阅读更多...
Linux下解压tar.xz文件的命令

Linux下解压tar.xz文件的命令

tar -c: 建立压缩档案-x&#xff1a;解压-t&#xff1a;查看内容-r&#xff1a;向压缩归档文件末尾追加文件-u&#xff1a;更新原压缩包中的文件 ------------------------------------------ 这五个是独立的命令&#xff0c;压缩解压都要用到其中一个&#xff0c;可以和别的…
阅读更多...
【 Maven 】花式玩法之多模块项目

【 Maven 】花式玩法之多模块项目

目录 一、认识Maven多模块项目 二、maven如何定义项目的发布策略 2.1 版本管理 2.2 构建配置 2.3 部署和发布 2.4 依赖管理 2.5 发布流程 三、使用Jenkins持续集成Maven项目 四、总结 如果你有一个多模块项目&#xff0c;并且想将这些模块发布到不同的仓库或目标位置&…
阅读更多...
拿捏c语言指针（下）

拿捏c语言指针（下）

前言 此篇讲解的主要是函数与指针的那些事~ 书接上回 拿捏c语言指针&#xff08;上&#xff09;和 拿捏c语言指针&#xff08;中&#xff09; ​​​​​​没有看的小伙伴要抓紧喽~ 欢迎关注​​个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#x…
阅读更多...
Cache-M语言 通用工具类

Cache-M语言 通用工具类

链接&#xff1a;M语言通用工具类
阅读更多...
MySQL错误-this is incompatible with sql_mode=only_full_group_by完美解决方案

MySQL错误-this is incompatible with sql_mode=only_full_group_by完美解决方案

项目场景 有时候&#xff0c;遇到数据库重复数据&#xff0c;需要将数据进行分组&#xff0c;并取出其中一条来展示&#xff0c;这时就需要用到group by语句。 但是&#xff0c;如果mysql是高版本&#xff0c;当执行group by时&#xff0c;select的字段不属于group by的字段的…
阅读更多...
设计模式——观察者模式

设计模式——观察者模式

定义&#xff1a; 定义一种一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;其所有依赖者都会收到通知并自动更新。 作用&#xff1a; 定义对象间的一种一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;所有依赖于它的对象都得到通…
阅读更多...
MySQL 基础知识（十）之 MySQL 架构

MySQL 基础知识（十）之 MySQL 架构

目录 1 MySQL 架构说明 2 连接层 3 核心业务层 3.1 查询缓存 3.2 解析器 3.3 优化器 3.4 执行器 4 存储引擎层 5 参考文档 1 MySQL 架构说明 下图是 MySQL 5.7 及其之前版本的逻辑架构示意图 MySQL 架构大致可分为以下三层&#xff1a; 连接层&#xff1a;负责跟客户…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023