数据结构顺序表的初始化，头插，尾插，头删，尾删，指定位置删除，指定位置插入，查找，销毁（详解）

目录

  • 前言
  • 顺序表的介绍
  • 静态顺序表
  • 动态顺序表
  • 一.顺序表的初始化
  • 二.销毁
  • 扩容顺序表
  • 打印顺序表
  • 三.头插
  • 四.尾插
  • 五.头删
  • 六.尾删
  • 七.指定位置之前（包括指定位置）的插入
  • 八.指定位置数据的删除
  • 九.查找
  • 全部的代码实现
  • 总结

前言

数据结构是什么？
数据结构是两个词的集合
数据：是一系列的在杂乱无章的数据的集合
结构：是有条理，清晰的集合（例如目录）
数据结构就是一些有条理数据的集合
数据结构是计算机存储和组织数据的方式

顺序表的介绍

顺序表是线性表的一种
那么顺序表和线性表到底是什么呢？

线性表：具有相同特性的数据结构的集合
例如：蔬菜：黄瓜，白菜，莲藕
相同特性：蔬菜
顺序表的底层是数组，但是在数组的基础上有增删查改等方法，就变成了数据结构

线性表有物理结构和逻辑结构

线性表：
物理结构：不一定是连续的
逻辑结构：一定是连续的

物理结构：例如数组的下标一定是连续的
在这里插入图片描述

逻辑结构：例如商店门口排队的人，人排队的位置不一定是一条直线，但是在逻辑上是一条直线
在这里插入图片描述

顺序表的物理结构一定是连续的，
逻辑结构也一定是连续的
因为顺序表的底层是数组，数组的物理结构和逻辑结构一定是连续的

顺序表需要的基础有：
动态内存管理
指针
结构体

写顺序表先创建三个文件
一个测试文件（.c）:测试顺序表的方法
一个顺序表的头文件（.h）：顺序表的结构，声明顺序表的方法
一个顺序表的源文件（.c）：实现顺序表的方法

静态顺序表

#define N 100
//100可以用N代替，后续可以方便修改数据

struct SeqList
{
   int arr[N];//定长的数组
   int size；//顺序表当前有效的数据个数
};

数组给大了，空间浪费
数组给小了，空间不够
静态顺序表的缺点还是比较多的

动态顺序表

struct SeqList
{
  int* arr;//指向顺序表的指针
  int size;//顺序表中有效数据个数
  int capacity;//顺序表的空间大小
};

动态顺序表可以动态增加顺序表的大小（动态增容）
防止了空间的大量浪费
也防止了空间的不足
所以下面我们来实现动态顺序表

一.顺序表的初始化

//SeqList.c
#include"SeqList.h"

//初始化顺序表
void SLInit(SL* ps)
{
	ps->arr = NULL;//将数组置为NULL
	ps->size = 0;//有效数据为0
	ps->capacity = 0;//空间大小为0
}

二.销毁

//SeqList.c
//销毁顺序表
void SLDestroy(SL* ps)
{
	//如果顺序表不为空，说明arr中还有动态申请的空间
	//要把动态申请的空间free掉
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	//顺序表不用了，置为NULL
	ps->size = ps->capacity = 0;
	//销毁完有效元素和空间为0
}

扩容顺序表

后面需要使用到，所以提前说
在这里插入图片描述

所以要用realloc增容，而不是malloc

//二倍或三倍地扩容
//扩容顺序表
void SLCheck(SL* ps)
{
	assert(ps);
	if(ps->capacity == ps->size)
	//看看空间够不够
	{
		//三目操作符判断给4个空间，还是直接增容2倍
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		DataType* tmp = realloc(ps->arr, sizeof(DataType) * NewCapacity);
		//用新的指针接收，防止增容失败
		if (tmp == NULL)
		{
			perror("realloc");
			return;//增容失败，提前返回
		}
		//增容成功
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
}

打印顺序表

//打印顺序表
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
	//打印一行就换行
}

三.头插

在这里插入图片描述

//头插
void SLPushFront(SL* ps,DataType x)
{
	assert(ps);
	SLCheck(ps);
	//增容
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i-1];
		//最后一次: = 1 ,arr[1] = arr[0]
	}
	ps->arr[0] = x;
	// 0下标的位置，放入插入的元素
	(ps->size)++;
	//插入一个数据，有效元素加一
}

四.尾插

在这里插入图片描述

//尾插
void SLPushBack(SL* ps,DataType x)
{
	assert(ps);
	SLCheck(ps);
    //判断空间够不够
	ps->arr[ps->size] = x;
	// == arr[size] = x
	(ps->size)++;
	//插入了一个元素
}

五.头删

在这里插入图片描述

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//顺序表不能为空
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
		// arr[size-2] = arr[size-1]
	}
	(ps->size)--;
	//删除一个元素，有效元素少一个
}

六.尾删

在这里插入图片描述

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	//指向顺序表的指针不能为空指针
	//为NULL，停止运行
	//不为NULL，继续运行
	assert(ps->size);
	//顺序表不能为空
	(ps->size)--;
	//删除一个元素，有效元素少一个
}

七.指定位置之前（包括指定位置）的插入

在这里插入图片描述

//指定位置之前插入元素
//pop:下标
//x:要插入的元素
void SLInsert(SL* ps, int pop, DataType x)
{
	assert(ps);
	assert(pop >= 0 && pop <= ps->size);
	// pop == size就是尾插
	// pop < size 在中间插入
	// pop == 0 头插
	SLCheck(ps);
	for (int i = ps->size; i > pop; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		// arr[pop+1] = arr[pop]
	}
	ps->arr[pop] = x;
	(ps->size)++;
}

八.指定位置数据的删除

在这里插入图片描述

//指定位置之前的删除
void SLEarse(SL* ps, int pop)
{
	assert(ps);
	assert(pop >= 0 && pop < ps->size);
	
	for(int i = pop;i < ps->size - 1;i++)
	{
		ps->arr[i] = ps->arr[i+1];
		//arr[size-2] = arr[size-1]
	}
	(ps->size)--;
	//删除一个元素，有效元素减一
}

九.查找

//查找
int SLCheck1(SL* ps, DataType x)
// x是要找的数据
{
	assert(ps);
	assert(ps->size > 0);
	//至少有一个元素才能够查找

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
			//找到了，返回下标
		}
	}
	return -1;
}

全部的代码实现

// test.c文件

#define _CRT_SECURE_NO_WARNINGS

#include"SeqList.h"

void SLtest()
{
	SL sl;
	SLInit(&sl);//传址调用
	//不能使用传值调用，因为这里sl并没有值
	//传址调用，改变指针指向的内容，给指向内容初始化
	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPrint(sl);//2 1
	//SLPushBack(&sl, 12);
	//SLPopFront(&sl);
	//SLPopBack(&sl);
	//SLInsert(&sl, 2, 10);
	//SLEarse(&sl, 1);
	int find = SLCheck1(&sl, 2);
	if (find < 0)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了，下标是:%d\n", find);
	}
	SLPrint(sl);
	SLDestroy(&sl);
}
int main()
{
	SLtest();

	return 0;
}

// SeqList.h文件

#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int DataType;//顺序表可以使用多种数据类型

typedef struct SeqList
{
	DataType* arr;
	int size;//有效数据
	int capacity;//空间大小
}SL;//将struct SeqList 改名为SL，更为方便简洁

void SLInit(SL* p);//初始化

void SLDestroy(SL* sl);//销毁

void SLPushFront(SL* sl,DataType x);//头插

void SLPrint(SL sl);//打印顺序表

void SLPushBack(SL* sl, DataType x);//尾插

void SLPopFront(SL* sl);//头删

void SLPopBack(SL* sl);//尾删

void SLInsert(SL* sl,int pop,DataType x);//指定位置之前的插入

void SLEarse(SL* sl, int pop);//指定位置之前的删除

int SLCheck1(SL* sl, DataType x);//查找

// SeqList.c文件


#define _CRT_SECURE_NO_WARNINGS

#include"SeqList.h"

//初始化顺序表
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;//有效数据为0
	ps->capacity = 0;//空间大小为0
}

//销毁顺序表
void SLDestroy(SL* ps)
{
	//如果顺序表不为空，说明arr中还有动态申请的空间
	//要把动态申请的空间free掉
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	//顺序表不用了，置为NULL
	ps->size = ps->capacity = 0;
	//销毁完有效元素和空间为0
}

//二倍或三倍地扩容
//扩容顺序表
void SLCheck(SL* ps)
{
	assert(ps);
	if(ps->capacity == ps->size)
	//看看空间够不够
	{
		//三目操作符判断给4个空间，还是直接增容2倍
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		DataType* tmp = realloc(ps->arr, sizeof(DataType) * NewCapacity);
		//用新的指针接收，防止增容失败
		if (tmp == NULL)
		{
			perror("realloc");
			return;//增容失败，提前返回
		}
		//增容成功
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
}
//头插
void SLPushFront(SL* ps,DataType x)
{
	assert(ps);
	SLCheck(ps);
	//增容
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i-1];
		//最后一次: = 1 ,arr[1] = arr[0]
	}
	ps->arr[0] = x;
	// 0下标的位置，放入插入的元素
	(ps->size)++;
	//插入一个数据，有效元素加一
}

//打印顺序表
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

//尾插
void SLPushBack(SL* ps,DataType x)
{
	assert(ps);
	SLCheck(ps);
    //判断空间够不够
	ps->arr[ps->size] = x;
	// == arr[size] = x
	(ps->size)++;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//顺序表不能为空
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
		// arr[size-2] = arr[size-1]
	}
	(ps->size)--;
	//删除一个元素，有效元素少一个
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	//指向顺序表的指针不能为空指针
	//为NULL，停止运行
	//不为NULL，继续运行
	assert(ps->size);
	//顺序表不能为空
	(ps->size)--;
	//删除一个元素，有效元素少一个
}

//指定位置之前插入元素
//pop:下标
//x:要插入的元素
void SLInsert(SL* ps, int pop, DataType x)
{
	assert(ps);
	assert(pop >= 0 && pop <= ps->size);
	// pop == size就是尾插
	// pop < size 在中间插入
	// pop == 0 头插
	SLCheck(ps);
	for (int i = ps->size; i > pop; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		// arr[pop+1] = arr[pop]
	}
	ps->arr[pop] = x;
	(ps->size)++;
}

//指定位置之前的删除
void SLEarse(SL* ps, int pop)
{
	assert(ps);
	assert(pop >= 0 && pop < ps->size);
	
	for(int i = pop;i < ps->size - 1;i++)
	{
		ps->arr[i] = ps->arr[i+1];
		//arr[size-2] = arr[size-1]
	}
	(ps->size)--;
	//删除一个元素，有效元素减一
}

//查找
int SLCheck1(SL* ps, DataType x)
{
	assert(ps);
	assert(ps->size > 0);
	//至少有一个元素才能够查找

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
			//找到了，返回下标
		}
	}
	return -1;
}

总结

总的来说顺序表的实现还是比较简单的
主要难的地方就是扩容，for循环的结束条件要想一下

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

碘浊度法与红外相机联用测定食品中维生素C

碘浊度法与红外相机联用测定食品中维生素C

&#x1f31e;欢迎来到看论文的世界 &#x1f308;博客主页&#xff1a;卿云阁 &#x1f48c;欢迎关注&#x1f389;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f31f;本文由卿云阁原创&#xff01; &#x1f4c6;首发时间&#xff1a;&#x1f339;2024年4月6日&…
阅读更多...
1.微服务

1.微服务

一、微服务是什么 微服务是一种架构风格&#xff0c;即&#xff0c;一个应用应该是一组小型服务&#xff0c;每个服务器只负责一种服务&#xff0c;服务之间可以通过 HTTP 的方式进行互通。每一个功能元素最终都是一个可独立替换和独立升级的软件单元。 可以说&#xff0c;微…
阅读更多...
网络编程套接字应用分享【Linux C/C++ 】【UDP应用 | TCP应用 | TCP线程池小项目】

网络编程套接字应用分享【Linux C/C++ 】【UDP应用 | TCP应用 | TCP线程池小项目】

目录 前提知识 1. 理解源ip&#xff0c;目的ip和Macip 2. 端口号 3. 初识TCP&#xff0c;UDP协议 4. 网络字节序 5. socket 编程 sockaddr类型 一&#xff0c;基于udp协议编程 1. socket——创建套接字 2. bind——将套接字强绑定 3. recvfrom——接受数据 4. s…
阅读更多...
c++11的重要特性2

c++11的重要特性2

可变参数模板在3中。 目录 ​编辑 1、统一的列表初始化&#xff1a; std::initializer_list&#xff1a; std::initializer_list是什么类型&#xff1a; std::initializer_list使用场景&#xff1a; 让模拟实现的vector也支持{}初始化和赋值 2、声明 auto decltype nul…
阅读更多...
「每日跟读」英语常用句型公式 第4篇

「每日跟读」英语常用句型公式 第4篇

「每日跟读」英语常用句型公式 第4篇 1. I’ve decided to ____ 我决定要____了 I’ve decided to take a vacation (我决定要去度假) I’ve decided to change my lifestyle (我决定要改变我的生活方式) I’ve decided to adopt a dog (我决定要收养一条狗了) I’ve dec…
阅读更多...
【深度学习环境配置】一文弄懂cuda，cudnn，NVIDIA Driver version，cudatoolkit的关系

【深度学习环境配置】一文弄懂cuda，cudnn，NVIDIA Driver version，cudatoolkit的关系

【深度学习环境配置】一文弄懂cuda&#xff0c;cuDNN&#xff0c;NVIDIA Driver version&#xff0c;cudatoolkit的关系 NVIDIA Driver version&#xff08;NVIDIA驱动程序&#xff09;CUDAcuDNNcudatoolkit深度学习环境配置顺序 今天突然发现配置的环境有些问题&#xff0c;意…
阅读更多...
使用阿里云试用Elasticsearch学习：2.6 深入搜索——控制相关度

使用阿里云试用Elasticsearch学习：2.6 深入搜索——控制相关度

处理结构化数据&#xff08;比如&#xff1a;时间、数字、字符串、枚举&#xff09;的数据库&#xff0c;只需检查文档&#xff08;或关系数据库里的行&#xff09;是否与查询匹配。 布尔的是/非匹配是全文搜索的基础&#xff0c;但不止如此&#xff0c;我们还要知道每个文档与…
阅读更多...
java日志框架简介

java日志框架简介

文章目录 概要常用日志框架常见框架有以下&#xff1a;slf4j StaticLoggerBinder绑定过程&#xff08;slf4j-api-1.7.32 &#xff09;JCL 运行时动态查找过程&#xff1a;&#xff08;commons-logging-1.2&#xff09;使用桥接修改具体日志实现 一行日志的打印过程开源框架日志…
阅读更多...
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

本文涉及的知识点 图论 分类讨论 本题同解 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 LeetCode3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中&#xff0c;存在编号从 1 到 n 的房屋&#xff0c;由 n 条街道相连。对所有 …
阅读更多...
服务效率飙升！2024最新Zoho Desk功能解析

服务效率飙升！2024最新Zoho Desk功能解析

2024年&#xff0c;立足于服务经济浪潮&#xff0c;如何为您的客户提供优质服务&#xff0c;高效解决客户工单&#xff0c;赢得客户美誉度&#xff0c;是当下各行企业的着力点。 在企业中&#xff0c;与客户发生最直接接触的就是客户服务部门。规范化客服部门业务流程&#xf…
阅读更多...
【JavaWeb】Day36.MySQL概述——数据库设计-DDL（三）

【JavaWeb】Day36.MySQL概述——数据库设计-DDL（三）

查询 关于表结构的查询操作&#xff0c;工作中一般都是直接基于图形化界面操作。 1.查询当前数据库所有表 2.查看指定表结构 3.查询指定表的建表语句 注意&#xff1a;23版的点击导航中的转到DDL 修改 关于表结构的修改操作&#xff0c;一般也是直接基于图形化界面操作。 添…
阅读更多...
LeetCode---127双周赛

LeetCode---127双周赛

题目列表 3095. 或值至少 K 的最短子数组 I 3096. 得到更多分数的最少关卡数目 3097. 或值至少为 K 的最短子数组 II 3098. 求出所有子序列的能量和 一、或值至少k的最短子数组I&II 暴力的做法大家都会&#xff0c;这里就不说了&#xff0c;下面我们来看看如何进行优化…
阅读更多...
彩虹易支付接口配置

彩虹易支付接口配置

支付通道配置 基本概念 彩虹易支付系统有强大的支付接口扩展能力&#xff0c;首先需要明白以下几个概念。 支付方式&#xff1a; 支付方式用于定义发起支付的调用值&#xff08;在前台开发文档里面显示&#xff09;与支付方式名称。目前系统自带6种支付方式&#xff0c;它们的…
阅读更多...
腾讯云最新活动及优惠券领取指南

腾讯云最新活动及优惠券领取指南

随着云计算技术的不断发展和普及&#xff0c;越来越多的企业和个人选择将业务迁移到云端。腾讯云作为国内领先的云计算服务提供商&#xff0c;经常推出各种优惠活动&#xff0c;以帮助用户降低成本、提高效率。本文将为大家详细介绍腾讯云的最新活动及优惠券领取指南&#xff0…
阅读更多...
猫头虎分享已解决Bug || **Error (通用错误)** 全景剖析

猫头虎分享已解决Bug || **Error (通用错误)** 全景剖析

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
数学杂谈之一：数学的形态

数学杂谈之一：数学的形态

数学杂谈之一&#xff1a;数学的形态 数学的形态可以根据不同的角度和视角进行分类和描述。下面是从数学的发展和应用的不同角度进行的分类&#xff1a; 原始形态&#xff1a;原始形态是指数学的发展和应用起源的形态。它涉及到数学的理论构建、证明和发现过程&#xff0c;是数…
阅读更多...
目标追踪StrongSORT——基于DeepSORT重大升级提高多目标跟踪的准确性和鲁棒性

目标追踪StrongSORT——基于DeepSORT重大升级提高多目标跟踪的准确性和鲁棒性

1、概述 1.1 DeepSORT DeepSORT算法是在SORT基础上发展起来的一种多目标跟踪算法。SORT算法结合了目标检测器和跟踪器&#xff0c;其中跟踪器的核心是卡尔曼滤波和匈牙利算法。卡尔曼滤波用于预测目标在下一帧的位置和状态&#xff0c;而匈牙利算法则用于将预测状态与实际检测…
阅读更多...
【Linux】Linux C 编程

【Linux】Linux C 编程

在 Windows 下编程首先就是安装对应的 IDE &#xff0c;然后在 IDE 里面进行代码编写和编译&#xff0c;但是在 Linux 下&#xff0c;这两个部分是分开的&#xff0c;比如我们可以使用 vim 编辑器编写代码&#xff0c;然后用 gcc 编译器编译代码。Ubuntu 下有一些可以进行编程的…
阅读更多...
Azkaban集群模式部署详细教程

Azkaban集群模式部署详细教程

序言 Azkaban是一个用于工作流程调度和任务调度的开源工具&#xff0c;它可以帮助用户轻松地管理和监控复杂的工作流程。Azkaban的架构设计旨在提供高度可扩展性和可靠性&#xff0c;同时保持易用性和灵活性。 Azkaban的架构可以分为三个主要组件:Executor、Web Server和db数据…
阅读更多...
Python-VBA编程500例-033(入门级)

Python-VBA编程500例-033(入门级)

角色定位(Role Positioning)在编程中的实际应用场景主要体现在以下几个方面&#xff1a; 1、权限管理&#xff1a;在开发企业级应用或复杂的系统时&#xff0c;角色定位用于定义和管理用户的权限。例如&#xff0c;一个系统可能有管理员、普通用户、访客等不同角色&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023