顺序表的基本操作
目录
一.什么是顺序表
二.顺序表的基本操作
1.初始化
2.增容
3.尾插
4.头插
5.尾删
6.头删
7.指定位置插入
8.指定位置删除
9.打印
10.查找
11.销毁
一.什么是顺序表
#define MAX 100
typedef int SLDataType;//对类型重定义,方便适应不同的数据类型
struct SeqList
{SLDataType a[MAX];//定长数组int size; //当前数据个数
};
动态顺序表:
typedef int SLDataType;//对类型重定义,方便适应不同的数据类型
typedef struct SeqList
{SLDataType *a;//定义指针指向动态开辟的空间int size; //当前存储的数据个数int capacity; //数据最大个数
}SL;
一般我们不太经常使用静态顺序表,因为实际需求往往空间都是不定的,因此我们只讨论动态顺序表
顺序表的本质还是对数组进行操作,只是和数组有所不同的是,顺序表的数据是连续存放的
二.顺序表的基本操作
一般地,我们都是用结构体定义顺序表,对顺序表的基本操作分为初始化,插入,删除,打印,查找,增容等操作,下面我们就来学习一下这些基本操作
1.初始化
顺序表的初始化我们只需要讲指针置为空指针,然后将当前数据元素个数和最大数据元素个数置为0,到插入时我们便会动态开辟空间给指针a
void SLInit(SL * ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用ps->a = NULL;//置为空指针ps->size = 0;//初始化为0ps->capacity = 0;
}
2.增容
当当前数据元素个数等于最大数据元素个数时,说明空间已满,此时则需要我们进行扩容,而扩容需要我们利用的动态内存管理函数开辟空间,我们选择的是realloc函数,打开cpp网站查看该函数有关信息
realloc函数的的两个参数分别为空间的地址和扩容后的空间大小,返回值是指向扩容后空间的地址,返回值void*,因此我们需要将其强制类型转换为我们需要的类型
当realloc函数的第一个指针为空指针时,其作用相当于malloc,第一次增容,由于我们初始化时给了最大容量capacity为0,因此需要给capacity赋一个初始值4,后面再扩容时则最大容量翻倍
第一次调用realloc函数时,由于我们初始化时将指针a赋为空指针,故第一次调用realloc函数作用和malloc函数相当,后面再次调用则实现扩容功能
void SLCheckCapacity(SL* ps)
{assert(ps);断言是否为空指针,如传入空指针则报错,防止函数被误用if (ps->size == ps->capacity)//判断当前数据个数是否到达最大值,是则增容{int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次给值为4,后面则翻倍SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间if (tmp == NULL)//判断是否开辟成功,如果返回空指针说明开辟失败则报错,否则将空间的地址付给a指针{perror("realloc fail");return;}ps->a = tmp;ps->capacity = newCapacity;//最大容量更新为扩容之后的容量}
}
3.尾插
尾插先判断空间是否已满,若空间已满,则需要扩容,然后再直接从尾部插入,后将数据个数加1即可
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用SLCheckCapacity(ps);//检查是否需要增容ps->a[ps->size] = x;//在尾部插入值ps->size++; //数据个数加1
}
4.头插
头插也需要判断空间是否已满,若空间已满,则需要扩容,然后再从头部插入,插入过程:先将顺序表里面已有的每一个元素往后挪动一个位置,相当于头部就腾出了一个“空位”,然后我们将需要插入的元素放到这个“空位”即可,后将数据元素加1
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用SLCheckCapacity(ps);//检查是否需要增容int end = ps->size - 1;while (end >= 0)//从尾部依次挪动元素{ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;//将值赋给第一个元素ps->size++; //数据个数加1
}
5.尾删
尾删需要先判断当前顺序表是否有元素,没有元素则直接报错,如果有元素,我们只需要将数据个数减1即达到删除效果,而不需要对最后一个元素进行操作,后续操作直接将它覆盖就行
void SLPopBack(SL* ps)
{assert(ps->size > 0);//判断当前是否有元素ps->size--;//直接将数据个数减1即可
}
6.头删
头删也需要先判断当前顺序表是否有元素,没有元素则直接报错,如果有元素,则删除的过程为:以我们排队打饭为例,当队伍的最前面一个人打完饭,后面的每一个人就都会往前一个位置,此时删除元素也是一样,从第二个位置开始到最后一个元素每个元素都依次往前挪动一个元素即可,后将数据个数减1
void SLPopFront(SL* ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用assert(ps->size > 0);//判断当前是否有元素int begin = 0;while (begin < ps->size - 1)//从尾部一次挪动元素{ps->a[begin] = ps->a[begin+1];begin++;}ps->size--;//数据个数减1
}
7.指定位置插入
指定位置我们需要先判断指定位置是否合法,如果小于0或者大于最大元素个数则直接报错,再判断是否需要增容,然后从指定位置开始到最后一个元素每个元素依次往后挪动一个位置,然后再将所插入的元素放到指定位置即可,后将数据元素个数加1
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用assert(pos >= 0 && pos<=ps->size);//判断给定的位置是否合法SLCheckCapacity(ps);//检查是否需要增容int end = ps->size - 1;while (end >= pos)//从尾部依次挪动元素,直到到达给定位置{ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;//将值赋给指定位置ps->size++;//数据个数加1
}
8.指定位置删除
指定位置删除野需要先判断给定位置是否合法,不合法则直接报错,然后从指定位置到最后一个元素依次往前挪动一个位置即可,后将数据元素减1
void SLErase(SL* ps, int pos)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用assert(pos >= 0 && pos < ps->size);//判断给定的位置是否合法int begin = pos;while (begin < ps->size - 1)//从指定位置依次挪动元素,直到到达尾部的前一个元素{ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;//数据个数减1
}
9.打印
打印只需要定义一个循环变量,以下标的形式遍历顺序表打印即可
void SLPrint(SL* ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用int i = 0;for (i = 0; i < ps->size; i++)//依次遍历打印顺序表即可{printf("%d ", ps->a[i]);}
}
10.查找
查找也是遍历顺序表,将每一个元素与查找的元素比较,若相等则返回元素下标,若遍历完没有找到元素,则返回-1,证明找不到该元素
int SLFind(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用int i = 0;for (i = 0; i < ps->size; i++)//遍历数组,比较是否相等,相等则返回元素下标{if (ps->a[i] == x)return i;}return -1;//如果遍历没有找到该元素,则返回-1
}
11.销毁
由于我们前面开辟空间是利用动态内存管理函数realloc开辟的,而该函数开辟的空间是由程序员自行开辟的,空间位于堆上,使用完空间后需要我们手动销毁,否则会导致内存泄露
销毁空间我们需要用到free函数,我们打开cpp网站查看该函数有关信息
freea函数的参数是一个指针,即所需要销毁的空间的地址,我们销毁顺序表只需要将指针a传给free函数即可,后讲指针a赋为空指针,防止其成为野指针
void SLDestroy(SL* ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用if (ps->a){free(ps->a);//释放a指针指向的空间ps->a = NULL;//将a指针置为空,防止其成为野指针ps->size = ps->capacity = 0;//当前数据元素个数和最大数据元素个数全置为0}
}
可以看到,上面的基本操作都是有相应的接口函数,我们只需要调用相应的函数即可实现顺序表的一些基本操作
上面所有的接口函数都用到了assert函数,且都位于函数体开头,assert函数称之为断言函数,当表达式为真是继续执行,当表达式为假时则直接报错,而这种报错可以让我们快速了解错误出在什么地方
我们打开cpp网站查看该函数有关信息
上面的所有接口函数调用assert函数,传的参数时指针a,当指针a为空指针时则直接报错,可以防止函数被误用而导致一些未知的错误
上面就是顺序表的一些基本操作,以下是全部代码:
SeqList.c
#include"SeqList.h"
void SLCheckCapacity(SL* ps)
{assert(ps);断言是否为空指针,如传入空指针则报错,防止函数被误用if (ps->size == ps->capacity)//判断当前数据个数是否到达最大值,是则增容{int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次给值为4,后面则翻倍SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间if (tmp == NULL)//判断是否开辟成功,如果返回空指针说明开辟失败则报错,否则将空间的地址付给a指针{perror("realloc fail");return;}ps->a = tmp;ps->capacity = newCapacity;//最大容量更新为扩容之后的容量}
}
void SLInit(SL * ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用ps->a = NULL;//置为空指针ps->size = 0;//初始化为0ps->capacity = 0;
}
void SLDestroy(SL* ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用if (ps->a){free(ps->a);//释放a指针指向的空间ps->a = NULL;//将a指针置为空,防止其成为野指针ps->size = ps->capacity = 0;//当前数据元素个数和最大数据元素个数全置为0}
}
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用SLCheckCapacity(ps);//检查是否需要增容ps->a[ps->size] = x;//在尾部插入值ps->size++; //数据个数加1
}
void SLPrint(SL* ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用int i = 0;for (i = 0; i < ps->size; i++)//依次遍历打印顺序表即可{printf("%d ", ps->a[i]);}
}
void SLPopBack(SL* ps)
{assert(ps->size > 0);//判断当前是否有元素ps->size--;//直接将数据个数减1即可
}
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用SLCheckCapacity(ps);//检查是否需要增容int end = ps->size - 1;while (end >= 0)//从尾部依次挪动元素{ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;//将值赋给第一个元素ps->size++; //数据个数加1
}
void SLPopFront(SL* ps)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用assert(ps->size > 0);//判断当前是否有元素int begin = 0;while (begin < ps->size - 1)//从尾部一次挪动元素{ps->a[begin] = ps->a[begin+1];begin++;}ps->size--;//数据个数减1
}
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用assert(pos >= 0 && pos<=ps->size);//判断给定的位置是否合法SLCheckCapacity(ps);//检查是否需要增容int end = ps->size - 1;while (end >= pos)//从尾部依次挪动元素,直到到达给定位置{ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;//将值赋给指定位置ps->size++;//数据个数加1
}
void SLErase(SL* ps, int pos)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用assert(pos >= 0 && pos < ps->size);//判断给定的位置是否合法int begin = pos;while (begin < ps->size - 1)//从指定位置依次挪动元素,直到到达尾部的前一个元素{ps->a[begin] = ps->a[begin + 1];begin++;}ps->size--;//数据个数减1
}
int SLFind(SL* ps, SLDataType x)
{assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用int i = 0;for (i = 0; i < ps->size; i++)//遍历数组,比较是否相等,相等则返回元素下标{if (ps->a[i] == x)return i;}return -1;//如果遍历没有找到该元素,则返回-1
}
SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDataType;//对类型重定义,方便适应不同的数据类型
typedef struct SeqList
{SLDataType *a;//定义指针指向动态开辟的空间int size; //当前存储的数据个数int capacity; //数据最大个数
}SL;
void SLCheckCapacity(SL *ps);
void SLInit(SL * ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);void SLPushBack(SL * ps, SLDataType x);
void SLPopBack(SL * ps);void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);void SLInsert(SL* ps,int pos, SLDataType x);
void SLErase(SL* ps, int pos);int SLFind(SL* ps, SLDataType x);
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void TestSeqList()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPushFront(&sl, 0);SLInsert(&sl, 2, 9);SLErase(&sl, 2);int pos = SLFind(&sl, 5);if (pos != -1)SLErase(&sl, pos);SLPrint(&sl);SLDestroy(&sl);
}
int main()
{TestSeqList();return 0;
}
输出结果:
好啦,顺序表我们就先学到这里,如果喜欢我的文章,欢迎动动手指一键三连~
相关文章:

顺序表的基本操作
目录 一.什么是顺序表 二.顺序表的基本操作 1.初始化 2.增容 3.尾插 4.头插 5.尾删 6.头删 7.指定位置插入 8.指定位置删除 9.打印 10.查找 11.销毁 一.什么是顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组…...

设计模式——创建型模型——单列模式(8种实现)
前言: 👏作者简介:我是笑霸final,一名热爱技术的在校学生。 📝个人主页:个人主页1 || 笑霸final的主页2 📕系列专栏:计算机基础专栏 📧如果文章知识点有错误的地方&#…...
【软考中级】软件设计师笔记
计算机系统的性能一般包括两个方面:一方面是它的可用性,也就是计算机系统能正常工作的时间,其指标可以是能够持续工作的时间长度,也可以是在一段时间内,能正常工作的时间所占的百分比 另一方面是处理能力,又…...
包教包会的ES6
自学参考:http://es6.ruanyifeng.com/ 一、ECMAScript 6 简介 ECMAScript 6.0(以下简称 ES6)是 JavaScript 语言的下一代标准,已经在 2015 年 6 月正式发布了。它的目标,是使得 JavaScript 语言可以用来编写复杂的大…...

python学习——【第四弹】
前言 上一篇文章 python学习——【第三弹】 中学习了python中的流程控制语句,这篇文章我们接着学习python中的序列。先给大家介绍不可变序列 字符串和可变序列 列表,下一篇文章接着补充元组,集合和字典。 序列 指的是一块可以存放多个值的…...

Web3中文|无聊猿Otherside元宇宙启动第二次旅行
3月9日消息,无聊猿Bored Ape Yacht Club母公司Yuga Labs公布了其Otherside元宇宙游戏平台第二次测试的最新细节。Yuga Labs公司称,“第二次旅行”将于3月25日举行,由四位Otherside团队长带领完成近两小时的游戏故事。本次旅行对Otherdeed NFT…...
SpringCloud-7_OpenFeign服务调用
OpenFeign介绍OpenFeign是什么1.OpenFeign是个声明式WebService客户端,使用OpenFeign让编写Web Service客户端更简单2.它的使用方法是定义一个服务接口然后在上面添加注解3.OpenFeign也支持可拔插式的编码器和解码器4.Spring Cloud对OpenFeign进行了封装使其支持了S…...
解决docker容器之间网络互通
docker容器之间相互访问 1.查看当前的网络 Copy [roothost ~]# docker network ls NETWORK ID NAME DRIVER SCOPE 3dd4643bb158 bridge bridge local 748b765aca52 host host …...
测试微服务:快速入门指南
在过去几年中,应用程序已经发展到拥有数百万用户并产生大量数据。使用这些应用程序的人期望快速响应和 24/7 可用性。为了使应用程序快速可用,它们必须快速响应增加的负载。 一种方法是使用微服务架构,因为在单体应用程序中,主要…...

MySQL Show Profile分析
6 Show Profile分析(重点) Show Profile是mysql提供可以用来分析当前会话中语句执行的资源消耗情况。可以用于SQL的调优的测量 官网文档 默认情况下,参数处于关闭状态,并保存最近15次的运行结果 分析步骤: 1、是否…...

基于Docker快速搭建蜜罐Dionaea(30)
实验目的 1. 快速搭建Dionaea蜜罐 2. 使用Nmap扫描测试Dionaea蜜罐预备知识1. 初步认识Dionaea dionaea,中文的意思即捕蝇草,是否形容蜜罐很形象?dionaea是nepenthes(猪笼草)的发展和后续,更加容易被部署和…...
WP_Query 的所有参数及其讲解和实用案例
WP_Query 是 WordPress 提供的一个强大的查询工具,用于获取与当前页面或文章相关的内容。下面是 WP_Query 的所有参数及其讲解:author: 查询特定作者的文章。可以是作者 ID、作者登录名或作者昵称。实用案例:查询作者为 "John Smith&quo…...
100个网络运维工作者必须知道的小知识!(上)
1)什么是链接? 链接是指两个设备之间的连接。它包括用于一个设备能够与另一个设备通信的电缆类型和协议。 2)OSI参考模型的层次是什么? 有7个OSI层:物理层,数据链路层,网络层,传输…...

Python如何获取大量电影影评,做可视化演示
前言 《保你平安》今天上映诶,有朋友看过吗,咋样啊 这是我最近比较想看的电影了,不过不知道这影评怎么样,上周末的点映应该是有蛮多人看的吧,可以采集采集评论看过的朋友发出来的评论,分析分析 这周刚好…...

【C语言】详讲qsort库函数
qsort函数介绍具体作用qsort函数是一种用于对不同类型数据进行快速排序的函数,排序算法有很多最常用的冒泡排序法仅仅只能对整形进行排序,qsort不同,排序类型不受限制,qsort函数的底层原理是一种快速排序.基本构造qsort( void* arr, int sz, int sizeof, cmp_code);…...

SEO技术风口来了|SEO能否抓住全球约93%的网络用户?
开篇词作者/出品人 | 美洽 SEO 流量专家 白桦为什么要做一个 SEO 专栏?在一部分人眼中,SEO(搜索引擎优化)已经是老掉牙的玩意儿,在这个信息爆炸的年代,它似乎已经无法承担吸引流量的主要作用。但ÿ…...

mxnet版本与numpy,requests等都不兼容问题
简介 跟着李沐学AI时遇到的mxnet环境问题。 问题 使用pip install mxnet时会重新安装相匹配的numpy和requests,而这新安装的这两个版本不满足d2l所需的版本。 然后报错: ERROR: pips dependency resolver does not currently take into account all …...

逆向分析——壳
你脑海中的壳是什么 壳在自然界是动物的保护壳,软件同样有保护壳,为了防止破解 也许大海给贝壳下的定义是珍珠,也许时间给煤炭下的定义是钻石 ——沙与沫 壳的由来 在DOS时代,壳一般指的是磁盘加密软件中的一段加密程序 后来发展…...

为 Argo CD 应用程序指定多个来源
在 Argo CD 2.6 中引入多源功能之前,Argo CD 仅限于管理来自 单个 Git 或 Helm 存储库 的应用程序。用户必须将每个应用程序作为 Argo CD 中的单个实体进行管理,即使资源存储在多个存储库中也是如此。借助多源功能,现在可以创建一个 Argo CD 应用程序,指定存储在多个存储库…...
verilog specify语法
specify block用来描述从源点(source:input/inout port)到终点(destination:output/inout port)的路径延时(path delay),由specify开始,到endspecify结束&…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...

Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...

push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...