数据结构(一)------顺序表

文章目录

  • 前言
  • 一、什么是顺序表
  • 二、实现顺序表
  • 1.静态顺序表
  • 2.动态顺序表

  • 总结


前言

制作不易!三连支持一下呗!!!

从今天起我们将会进入数据结构的学习!

我们先来了解

什么是数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。

一般数据结构有很多种,一般来说,按照数据的逻辑结构对其进行简单的分类,包括线性结构和非线性结构两类。

线性表在逻辑结构上是连续的,但在物理结构上不一定是连续的!

今天我们就来学习一下线性表之一的顺序表!


一、什么是顺序表

顺序表是最简单的一种数据结构,它底层采用的是我们之前学过的数组,它在逻辑结构(数据之间的关系)上是连续的,在物理结构上也是连续的(因为数组中的数据在内存中是连续存放的)。

但是顺序表又不能等同于数组,它其实是在数组的基础上进行封装,通过增,删,查,改等接口来对数据进行操作。

顺序表根据大小是否是固定的又分为

1.静态顺序表

2.动态顺序表

二、顺序表的实现

1.静态顺序表

底层使用的是固定大小的数组

比如:

#include<stdio.h>
typedef int Seqtype;//如果我们后续要更改存储的数据的类型,这样重定义可以方便我们一键替换
#define Seqtype_MAX 100//方便我们后续修改顺序表的大小
typedef struct SeqList
{
	Seqtype arr[100];//存放100个整型类型的数据
	int size;//记录有效数据(也就是已经保存的数据)的个数
}SL;//使结构体类型更加简洁

这里着重解释一下为什么只创建一个数组来存放数据还不够,我们还需要一个size来记录有效数据的个数:

这是因为当我们在后续实现一些增,删,查,改等接口时难免会遍历已保存的数据,这样size就可以方便我们知道每次需要遍历多少个数据。 

由于静态顺序表有大小是固定的这样的弊端,因此我们更加喜欢使用动态顺序表!

二.动态顺序表

想要实现动态顺序表就要用到我们之前介绍过的动态内存管理的方式(malloc,calloc,realloc),通过realloc函数的特点,在我们空间大小不够的情况下扩容。

实现方式如下:

#include<stdio.h>
typedef int Seqtype;//如果我们后续要更改存储的数据的类型,这样重定义可以方便我们一键替换
typedef struct SeqList
{
	Seqtype* arr;
	int capacity;//记录当前顺序表的容量
	int size;//记录有效数据(也就是已经保存的数据)的个数
}SL;//使结构体类型更加简洁

我们通过指针的方式来遍历整个数组,也通过动态开辟的方式来申请空间。

1. 顺序表的初始化与销毁

创建好一个顺序表,,类比创建变量,我们首先要做的第一步就是初始化这个顺序表。我们可以通过一个接口函数来完成这个功能:

<1>.顺序表的初始化
#include<stdio.h>
#include<assert.h>
void SLInit(SL* ps)
{
    assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

这里我们只强调为什么我们要传址调用,而不能传值调用:

我们在这里是想要初始化这个顺序表,也就是要对顺序表中的内容进行修改,如果我们采用传值调用的方式,形参只是实参的临时拷贝,对形参的修改是不会影响实参的,也就是说实参是并没有被初始化的!因此,我们这里传一个地址过去,通过指针的方式来对顺序表进行初始化(修改)。

<2>. 顺序表的销毁

当我们会初始化顺序表后,销毁顺序表其实也大差不差:

#include<stdio.h>
#include<assert.h>
void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

同样的道理我们这里还是要传址调用!

2.扩容 

动态顺序表最大的特点就是当空间不够时,可以自动开辟更多的空间以存放数据。

扩容的原理也有很多,比如:

1.每次扩容一个元素大小的空间

原则就是每当我们空间不足时,使用realloc函数来增加一个元素的空间。

这种方式有它的优点:不会一次扩容过度,造成空间的浪费。

弊端:每次只扩大一个元素的空间,这样会造成需要频繁的扩容,那样就会频繁的调用这个接口函数,造成程序的运行效率低下!

2.每次扩容固定大小的空间

优点:可以做到不会频繁扩容

弊端:可能会导致一次性扩容过度,造成空间的浪费

可以看出前两种方式是两个极端!

3.成倍数的扩容(强烈推荐)

每次扩容为原来的容量的固定倍数的大小的空间,我们通常会使用1.5倍或2倍(倍数不宜过大,会导致空间的浪费)

这种方式平衡了前两种方式的弊端,既不会过度扩容,也不会特别造成空间的浪费,是一种中性的方法。

说完扩容的原则,我们接下来实现扩容的功能:

在后面插入,删除数据的接口中可能会存在空间不足需要扩容的情况,所以我们单独将扩容拿出来,实现一个扩容的接口。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)//判断是否需要扩容
	{
		int newcapacity = ps->capacity == 0 ? 2 : 2*ps->capacity;
		Seqtype* tmp = (Seqtype*)realloc(ps->arr, newcapacity * sizeof(Seqtype));
		//刚开始ps->arr是NULL,realloc会直接开辟新空间,作用相当于malloc
		//注意单位是字节,要*类型的大小
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);//直接终止程序,比return 1更加暴力
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

这里我们再实现一个打印顺序表的接口,方便我们进行调试观察代码是否有误

void SLPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}

非常简单!

3.头插和尾插 

<1>.尾插

尾插顾名思义就是在之前的数据的末尾插入新的数据。

当我们插入数据时就会遇到两种情况:

1.空间足够,直接插入

根据上图可以看出ps->size就是我们要插入的位置的下标 

2.空间不足时

这种情况我们需要先扩容,再插入

代码实现如下:

void SLPushBack(SL* ps, Seqtype x)
{
	assert(ps);
	SLCheckCapacity(ps);//判断是否要扩容
	ps->arr[ps->size++] = x;//注意:不用忘了将ps->size++。
}

<2>.头插

将每次要插入的数据放到数组下标为0的起始位置,同样分为两种情况:

1.空间足够

假如我们要插入100

最后应该是将之前的元素往后挪动,再加100插入到头部,最后ps->size++ 

2.空间不足

对于空间不足的情况,同尾插一样,我们需要先扩容再插入。

下面我们实现代码:

void SLPushFront(SL* ps, Seqtype x)
{
	assert(ps);
	SLCheckCapacity(ps);//判断是否要扩容
	int i = 0;
	for (i = ps->size; i >0; i--)//边界条件:ps->arr[1]=ps->arr[0]
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

4.头删和尾删 

<1>.尾删

尾删的思想与尾插相似,也是从之前数据的末尾删掉一个数据(这里无需判断是否空间足够,因为肯定足够!),代码实现十分简单:

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//确保顺序表中有元素,否则不执行
	ps->size--;
}

可能有些老铁会想先将要删除的元素置为0,再将ps->size--。其实这样是不太合理的,因为我们存入的数据也可能为0,这样无法判断0是删除的数据还是插入进来的数据。而且我们也没必要那样做,因为我们直接将 ps->size--,这样我们遍历顺序表时本就无法再查询到被删除的数据了!

<2>.头删

当我们进行一次头删操作,顺序表将变成这样:

可以看出后面的元素整体向前挪动一位,并且ps->size--。 

代码实现如下:

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);//确保顺序表中有元素,否则不执行
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)//边界位置判断:ps->arr[0]=ps->arr[1]
		                              //还有ps->arr[ps->size-2]=ps->arr[ps->size-1]
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//注意不要丢掉
}

5.指定位置插入和删除 

<1>.指定位置插入

同样的,指定位置插入数据也要先判断是否需要扩容,原理同上,这里不再过多赘述。

因为需要用户自己指定插入的位置,所以我们还需要一个参数pos来确定插入位置的下标。

数据插入后的顺序表应该是这样的:

可以看出,需要将pos位置及以后的数据整体向后挪动1个单位!!!

void SLInsert(SL* ps, Seqtype x,int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//判断pos的合法性
	SLCheckCapacity(ps);//判断是否要扩容
	int i = 0;
	for (i = ps->size - 1; i >= pos;i--)//边界条件判断:ps->arr[pos+1] = ps->arr[pos]
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[pos] = x;
	ps->size ++ ;
}

特别的,pos=ps->size时就相当于尾插,当pos=0时相当于头插!!! 

 <2>.指定位置删除

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//检验pos的合法性
	assert(ps->size);//确保顺序表中有元素
	int i = 0;
	for (i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//不要忘记
}

 特别的,pos=ps->size-1时就相当于尾删,当pos=0时相当于头删!!! 

6.查找 

思路很简单,就是遍历整个顺序表

int SLFind(SL* ps, Seqtype x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了,返回下标
		}
	}
	return -1;//找不到,返回-1
}


总结

以上就是本节的所有内容

下面将整个顺序表的所有代码放到这里

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int Seqtype;//如果我们后续要更改存储的数据的类型,这样重定义可以方便我们一键替换
typedef struct SeqList
{
	Seqtype* arr;
	int capacity;//记录当前顺序表的容量
	int size;//记录有效数据(也就是已经保存的数据)的个数
}SL;//使结构体类型更加简洁
void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)//判断是否需要扩容
	{
		int newcapacity = ps->capacity == 0 ? 2 : 2*ps->capacity;
		Seqtype* tmp = (Seqtype*)realloc(ps->arr, newcapacity * sizeof(Seqtype));
		//刚开始ps->arr是NULL,realloc会直接开辟新空间,作用相当于malloc
		//注意单位是字节,要*类型的大小
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);//直接终止程序,比return 1更加暴力
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}
void SLPushBack(SL* ps, Seqtype x)
{
	assert(ps);
	SLCheckCapacity(ps);//判断是否要扩容
	ps->arr[ps->size++] = x;//注意:不用忘了将ps->size++。
}
void SLPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}
void SLPushFront(SL* ps, Seqtype x)
{
	assert(ps);
	SLCheckCapacity(ps);//判断是否要扩容
	int i = 0;
	for (i = ps->size; i >0; i--)//边界条件:ps->arr[1]=ps->arr[0]
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//确保顺序表中有元素,否则不执行
	ps->size--;
}
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);//确保顺序表中有元素,否则不执行
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)//边界位置判断:ps->arr[0]=ps->arr[1]
		                              //还有ps->arr[ps->size-2]=ps->arr[ps->size-1]
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//注意不要丢掉
}
void SLInsert(SL* ps, Seqtype x,int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//判断pos的合法性
	SLCheckCapacity(ps);//判断是否要扩容
	int i = 0;
	for (i = ps->size - 1; i >= pos;i--)//边界条件判断:ps->arr[pos+1] = ps->arr[pos]
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[pos] = x;
	ps->size ++ ;
}
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//检验pos的合法性
	assert(ps->size);//确保顺序表中有元素
	int i = 0;
	for (i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//不要忘记
}
int SLFind(SL* ps, Seqtype x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了,返回下标
		}
	}
	return -1;//找不到,返回-1
}

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

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

相关文章

喜报|「云原生数据库PolarDB」、「阿里云瑶池一站式数据管理平台」揽获“2023技术卓越奖”

日前&#xff0c;国内知名IT垂直媒体&技术社区IT168公布2023年“技术卓越奖”评选结果&#xff0c;经由行业CIO/CTO大咖、技术专家及IT媒体三方的联合严格评审&#xff0c;阿里云瑶池数据库揽获两项大奖&#xff1a;云原生数据库PolarDB荣获“2023年度技术卓越奖”&#xf…

分布式ID(3):雪花算法生成ID之UidGenerator(百度开源的分布式唯一ID生成器)

1 UidGenerator官方地址 UidGenerator源码地址: https://github.com/baidu/uid-generator UidGenerator官方说明文档地址: https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md 这边只做简单介绍,详细说明请看官方说明文档。 2 Snowflake算法 Snowfl…

VMware中CentOS 7解决网络问题

问题描述 在 VMware 中使用 CentOS 7 中使用 ping www.baidu.com 测试网络是否能正常连接。 出现了未知的名称和服务的问题&#xff1a; 解决方案一 在服务中检查 VMware NAT Service 是否开启 解决方案二 在控制面板中的网络适配器里检查 解决方案三 检查VMware中的网络适…

SpringBoot常见错误

SpringBoot常见错误 1、SpringBoot启动时报错 错误: 找不到或无法加载主类 com.xxx.xxx.Application springboot启动时报错错误&#xff1a;找不到或无法加载主类 com.xxx.xxx.Application。 解决方法就是打开idea的控制台&#xff0c;输入以下三行命令&#xff1a; mvn cl…

遗传算法求解基于移动边缘计算的任务卸载与资源调度优化(提供MATLAB代码)

一、优化模型介绍 移动边缘计算的任务卸载与资源调度优化原理是通过利用配备计算资源的移动无人机来为本地资源有限的移动用户提供计算卸载机会&#xff0c;以减轻用户设备的计算负担并提高计算性能。具体原理如下&#xff1a; 任务卸载&#xff1a;移动边缘计算系统将用户的计…

SV-7042C 标准TCP协议网络有源音柱

SV-7042C 标准TCP协议网络有源音柱 一、描述 SV-7042C是深圳锐科达电子有限公司的一款壁挂式网络有源音柱&#xff0c;具有10/100M以太网接口&#xff0c;可将网络音源通过自带的功放和喇叭输出播放&#xff0c;其采用防水设计&#xff0c;功率可以从20W到40W。SV-7042C作为网…

小土堆pytorch学习笔记003 | 下载数据集dataset 及报错处理

目录 1、下载数据集 2、展示数据集里面的内容 3、DataLoader 的使用 例子&#xff1a; 结果展示&#xff1a; 1、下载数据集 # 数据集import torchvisiontrain_set torchvision.datasets.CIFAR10(root"./test10_dataset", trainTrue, downloadTrue) test_set …

深入了解Redis:选择适用于你的场景的持久化方案

自然语言处理的发展 文章目录 自然语言处理的发展强烈推荐前言&#xff1a;Redis提供了几种主要的持久化方案&#xff1a;RDB快照持久化&#xff1a;工作原理&#xff1a; AOF日志文件持久化&#xff1a;混合持久化&#xff1a; 总结强烈推荐专栏集锦写在最后 强烈推荐 前些天…

第五篇:express路由路径方式(字符串,字符串模式,和正则)

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 &#x1f4d8; 引言&#xff1a; &#x1f4…

JVM篇----第十篇

系列文章目录 文章目录 系列文章目录前言一、JAVA 强引用二、JAVA软引用三、JAVA弱引用四、JAVA虚引用五、分代收集算法前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧…

CVPR——Latex模版下载

CVPR官网 -> AuthorGuidelines 链接&#xff1a;AuthorGuidelines

备战蓝桥杯---数据结构与STL应用(基础3)

今天我们主要介绍的是pair,string,set,map pair:我们可以把它当作一个结构体&#xff1a; void solve(){pair<int int> a;//创建amake_pair(1,2);//添加元素cout<<a.first<<endl<<a.second<<endl;}//输出 当然&#xff0c;它也可以嵌套&#…

Qt/C++音视频开发64-共享解码线程/重复利用解码/极低CPU占用/画面同步/进度同步

一、前言 共享解码线程主要是为了降低CPU占用&#xff0c;重复利用解码&#xff0c;毕竟在一个监控系统中&#xff0c;很可能打开了同一个地址&#xff0c;需要在多个不同的窗口中播放&#xff0c;形成多屏渲染的效果&#xff0c;做到真正的完全的画面同步&#xff0c;在主解码…

60、Flink CDC 入门介绍及Streaming ELT示例(同步Mysql数据库数据到Elasticsearch)-完整版

Flink 系列文章 一、Flink 专栏 Flink 专栏系统介绍某一知识点&#xff0c;并辅以具体的示例进行说明。 1、Flink 部署系列 本部分介绍Flink的部署、配置相关基础内容。 2、Flink基础系列 本部分介绍Flink 的基础部分&#xff0c;比如术语、架构、编程模型、编程指南、基本的…

Java项目:基于SSM框架实现的企业员工岗前培训管理系统(ssm+B/S架构+源码+数据库+毕业论文)

一、项目简介 本项目是一套ssm821基于ssm框架实现的企业员工岗前培训管理系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格…

智能巡检系统:企业管理创新的一个新方向

智能巡检系统是一个重要的工具&#xff0c;它可以帮助企业实现更高效、更准确和更安全的管理。在谈论智能巡检时&#xff0c;我们主要关注的是以下几个方面的创新和改进。 数据处理能力&#xff1a;智能巡检系统通过云端处理技术&#xff0c;可以实现大规模数据的快速处理和分析…

接口参数校验之路径变量:@PathVariable(二):多个路径变量校验

一、引言 在上一篇文章《接口参数校验之路径变量&#xff1a;PathVariable》中&#xff0c;我们深入探讨了Spring MVC框架中的一个重要特性——路径变量的使用和校验。文章详细阐述了如何通过PathVariable注解从请求URL中提取路径变量&#xff0c;并对单个路径变量进行合法性校…

贝锐蒲公英全新网页认证,保障企业访客无线网络安全

随着企业规模的不断扩大、人员的增长、无线终端数量/类型的增加&#xff0c;传统WiFi无线网络会暴露出越来越多的问题&#xff0c;导致无线网络管理困难。 比如&#xff1a;采用弱密码、安全防护不到位的默认设置、员工缺乏信息安全意识、未经授人员权访问无线网络…… 这些问…

Kafka(九)跨集群数据镜像

目录 1 跨集群镜像的应用场景1.1 区域集群和中心集群1.2 高可用(HA)和灾备(DR)1.3 监管与合规1.4 云迁移1.5 聚合边缘集群的数据 2 多集群架构2.1 星型架构2.2 双活架构2.2 主备架构2.2.1 如何实现Kafka集群的故障转移2.2.1.1 故障转移包括的内容1. 灾难恢复计划2. 非计划内的故…

使用SQL来操作DataFrame?我们给pandas找了个新搭子

对有一定SQL基础的人来说&#xff0c;pandas中的查询会有点繁琐。 在这篇文章&#xff0c;我们将给Pandas找个搭子&#xff0c;在用SQL方便的地方&#xff0c;我们用SQL&#xff1b;在用原生查询方便的地方&#xff0c;我们就用原生查询。 这个搭子会是谁呢&#xff1f; data…