顺序表的基本操作
目录
一.什么是顺序表
二.顺序表的基本操作
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结束&…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...