数据结构--顺序表

目录

1.顺序表

1.1顺序表的概念及结构

线性表

 2、顺序表分类

2.1顺序表和数组的区别

静态顺序表

动态顺序表

3.顺序表的实现

 3.1初始化

随后便可对顺序表初始化

3.2插入数据

尾插

头插

 在指定位置插入数据

顺序表的查找

头删、尾删及指定位置删除

实现代码：

1.顺序表

1.1顺序表的概念及结构

线性表

线性表（ linear list ）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
案例：蔬菜分为绿叶类、⽠类、菌菇类。

 2、顺序表分类

2.1顺序表和数组的区别

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝

  • 静态顺序表

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

概念：使用定长数组存放元素

缺陷：空间给少了不够⽤，给多了造成空间浪费

  • 动态顺序表

struct SeqList
{
    int *arr;
    int size;//有效的数据个数
    int capacity;//空间大小
};

因为数组并不是定长的，可根据实际数据大小进行动态申请空间，随着数据的增加，也可进行动态增容。

3.顺序表的实现

分成三个文件实现：

SeqList.h

SeqList.c

test.c

 3.1初始化

首先在SeqList.h创建好顺序表的结构

typedef int SLDataType;//顺序表存放的类型可能是int 也可能是char，
所有重新起个名字，方便以后更改
//动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

随后便可对顺序表初始化

void SLlnit(SL* ps)//顺序表初始化
{
	ps->arr = NULL;
	ps->size = ps->capacity=0;
}

3.2插入数据

在插入数据之前首先要判断空间是否为0，空间是否足够，

若不够，一次应增容多少？

通常来说增容是成倍的增长，一般是2倍或3倍

因此，创建一个函数SLCheckCapacity专门实现增容，每次插入数据之前需调用一次函数

void SLCheckCapacity(SL* ps)
{
	//插入数据之前先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间-->增容realloc
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//三目表达式 判断capacity是否为0 是：赋值为4 否：赋值为2 * ps->capacity
		//增容通常来说是成倍数的增加，一般是2或3倍
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序，不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

尾插

在数据的尾部插入数据

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	//防止ps可能为NULL
	assert(ps);//等价于assert(ps!=NULL);

	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

头插

在数据的头部插入数据；

插入数据之前把原有数据全部向后移动一位

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//先让顺序表中已有的数据整体往后挪动一位
	for (int i = ps->size; i > 0; i--)//数组下标不会为-1
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//头插
	ps->size++;
}

 在指定位置插入数据

创建一个变量pos存放指定位置，然后把pos之后的数据整体往后移动一位，在pos位置插入所需要的数据即可。

//在指定位置之前插入数据
void SLlnsert(SL* ps, int pos, SLDataType x)//pos：指定的位置 x：插入的数据
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	//插入数据：空间够不够
	SLCheckCapacity(ps);
	//让pos及之后的数据整体往后挪动一位
	for (int i = ps->size; i > pos; i--)//从后往前挪动
	{
		ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos] 最后下标为pos位置为空
	}
	ps->arr[pos] = x;//在pos位置插入数据
	ps->size++;
}

顺序表的查找

//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//没有找到
	return -1;
}

头删、尾删及指定位置删除

与插入数据原理一样，只需在所需的位置删除数据即可

实现代码：

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构

//#define N 100

静态顺序表
//struct SeqList
//{
//	int arr[N];
//	int size;//有效数据个数
//};

typedef int SLDataType;//顺序表存放的类型可能是int 也可能是char，所有重新起个名字，方便以后更改
//动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

//顺序表初始化
void SLlnit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLprint(SL s);

//头部插入删除/尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//指定位置之前插入/删除数据
void SLlnsert(SL* ps,int pos,SLDataType x );
void SLErase(SL* ps, int pos);

//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"
void SLlnit(SL* ps)//顺序表初始化
{
	ps->arr = NULL;
	ps->size = ps->capacity=0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)//等价于 if(ps->!=NULL)
	{
		free(ps-> arr);//释放空间
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps)
{
	//插入数据之前先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间-->增容realloc
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//三目表达式 判断capacity是否为0 是：赋值为4 否：赋值为2 * ps->capacity
		//增容通常来说是成倍数的增加，一般是2或3倍
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序，不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	//防止ps可能为NULL
	assert(ps);//等价于assert(ps!=NULL);

	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//先让顺序表中已有的数据整体往后挪动一位
	for (int i = ps->size; i > 0; i--)//数组下标不会为-1
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//头插
	ps->size++;
}
//打印顺序表
void SLprint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

//尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	--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];
	}
	ps->size--;//删除
}
//在指定位置之前插入数据
void SLlnsert(SL* ps, int pos, SLDataType x)//pos：指定的位置 x：插入的数据
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	//插入数据：空间够不够
	SLCheckCapacity(ps);
	//让pos及之后的数据整体往后挪动一位
	for (int i = ps->size; i > pos; i--)//从后往前挪动
	{
		ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos] 最后下标为pos位置为空
	}
	ps->arr[pos] = x;//在pos位置插入数据
	ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//pos位置后的数据全部往前挪动一位
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//没有找到
	return -1;
}

test.c

#include<SeqList.h>
void SLTest01()//测试
{
	SL sl;
	//初始化
	SLlnit(&sl);
	//尾插
	SLPushBack(&sl, 1);

	//打印顺序表
	SLprint(sl);
	//头插
	SLPushFront(&sl,1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);

	SLprint(sl);

	SLPopBack(&sl);
	SLprint(sl);

	//测试指定位置之前插入数据
	SLlnsert(&sl, 3, 90);
	SLprint(sl);
	//删除指定位置的数据
	SLErase(&sl, 4);
	SLprint(sl);

	int a=SLFind(&sl, 40);
	if (a >= 0)
	{
		printf("找到了，下标是：%d\n", a);
	}
	else
	{
		printf("没找到\n");
	}
	SLDestroy(&sl);

}
int main()
{
    SLTest01();
    return 0;
}

感谢观看，再见

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

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

相关文章

pycharm找不到conda可执行文件解决办法

pycharm找不到conda可执行文件解决办法

解决办法 1、第一种 按照以下步骤&#xff0c;找到condabin文件下面&#xff0c;conda.bat 文件&#xff0c;把路径给复制下来&#xff0c;粘贴到 Conda 可执行文件&#xff0c;即可。 然后再点击加载环境&#xff0c;我这里是已经汉化了 pycharm &#xff0c;如何汉化&…
阅读更多...
P451 try-Catch异常处理

P451 try-Catch异常处理

//基本使用演示代码 public static void main(String[] args) { int num1 10; int num2 0; try { int res num1 / num2; }catch (Exception e) { System.out.println(e.getMessage()); } } public class TryCatchDetail { public static void main(String[] args) { //1. 如…
阅读更多...
信息安全与多媒体基础知识

信息安全与多媒体基础知识

阅读更多...
Excel工作簿/表的合并/拆分全集（一文通关）

Excel工作簿/表的合并/拆分全集（一文通关）

概述 在工作中&#xff0c;我们常会用到到Excel拆分/合并为多个工作表/簿&#xff0c;如全国的订单表&#xff0c;需要根据省份列拆分下发至对应的省、各省份数据需要汇总、...... 应该如何操作呢&#xff1f; 1. 传统方法&#xff08;借助透视表、Power Query编辑器、VBA实现…
阅读更多...
【启程Golang之旅】运算符与流程控制讲解

【启程Golang之旅】运算符与流程控制讲解

欢迎来到Golang的世界&#xff01;在当今快节奏的软件开发领域&#xff0c;选择一种高效、简洁的编程语言至关重要。而在这方面&#xff0c;Golang&#xff08;又称Go&#xff09;无疑是一个备受瞩目的选择。在本文中&#xff0c;带领您探索Golang的世界&#xff0c;一步步地了…
阅读更多...
java -spring 15 配置类 ConfigurationClassPostProcessor

java -spring 15 配置类 ConfigurationClassPostProcessor

01Spring中定义的配置类 ConfigurationClassPostProcessor是一个BeanFactory的后置处理器&#xff0c;因此它的主要功能是参与BeanFactory的建造&#xff0c;在这个类中&#xff0c;会解析加了Configuration的配置类&#xff0c;还会解析ComponentScan、ComponentScans注解扫描…
阅读更多...
【全开源】知识库文档系统源码（ThinkPHP+FastAdmin）

【全开源】知识库文档系统源码（ThinkPHP+FastAdmin）

知识库文档系统源码&#xff1a;构建智慧知识库的基石 引言 在当今信息爆炸的时代&#xff0c;知识的有效管理和利用对于企业和个人来说至关重要。知识库文档系统源码正是为了满足这一需求而诞生的&#xff0c;它提供了一个高效、便捷的平台&#xff0c;帮助用户构建、管理、…
阅读更多...
全金属狂潮！金银铜齐飞

全金属狂潮！金银铜齐飞

在纽约铜史诗级逼空的影响下&#xff0c;全球金属市场迎来了一波“全金属狂潮”。 全金属狂潮 本周&#xff0c;纽约、上海交易所铜价纷纷创下新高。周五&#xff0c;伦敦金属交易所的铜价也录得2.8%涨幅&#xff0c;逼近2022年3月的历史最高点。 与此同时&#xff0c;白银价…
阅读更多...
Ardupilot开源代码之Rover上路 - 后续3

Ardupilot开源代码之Rover上路 - 后续3

Ardupilot开源代码之Rover上路 - 后续3 1. 源由2. 深度配置2.1 编码器2.2 WS2812B LED灯带2.3 4GLTE超视距2.3.1 摄像头2.3.2 QGC OSD虚拟遥控2.3.3 QGC外接JoyStick遥控 2.4 伴机电脑供电 3. 实测效果4. 遗留&后续4.1 设置倒车按钮4.2 MP无法连接ESP82664.3 高精度编码器问…
阅读更多...
FFMPEG 解码过程初步学习

FFMPEG 解码过程初步学习

1. 视频文件解码过程 解码过程 步骤如下&#xff1a; 视频文件&#xff08;封装格式&#xff0c;MP4/FLV/AVI 等&#xff09;获取视频格式信息等解复用为Stream 流&#xff0c; 准备解码用的Codec将Stream 流 使用解码器解为Raw 格式针 1.1 音视频格式填充&#xff1a; int…
阅读更多...
神秘山洞惊现AI绘画至宝Stable Diffusion残卷

神秘山洞惊现AI绘画至宝Stable Diffusion残卷

最近听到不少大宗门纷纷发声&#xff1a;随着AI神器的现世“程序员职业将不复存在”&#xff0c;“设计图将要失业”。 至此&#xff0c;不少修士开始担忧起来&#xff0c;现出世的AI神器会不会取代掉我辈修士。 其实&#xff0c;至女娲天神创造人类以来&#xff0c;在这漫漫…
阅读更多...
接口测试流程详解

接口测试流程详解

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 在讲接口测试流程之前&#xff0c;首先需要给大家申明下&#xff1a;接口测试对于测试人员而言&a…
阅读更多...
STM32H743的FDCAN使用方法（1）：STM32CubeMX初始化代码生成

STM32H743的FDCAN使用方法（1）：STM32CubeMX初始化代码生成

0 工具准备 1.STM32CubeMX1 前言 本文介绍基于STM32CubeMX&#xff0c;使用stm32h743xi的对FDCAN2进行配置的方法。 2 初始化代码生成 2.1 选择FDCAN引脚 本例选择PB5、PB6作为FDCAN2的RX、TX引脚。 2.2 选择FDCAN时钟源 本例选择PLL2Q作为FDCAN时钟源&#xff0c;频率…
阅读更多...
深度学习中的优化算法二（Pytorch 19）

深度学习中的优化算法二（Pytorch 19）

一 梯度下降 尽管梯度下降&#xff08;gradient descent&#xff09;很少直接用于深度学习&#xff0c;但了解它是理解下一节 随机梯度下降算法 的关键。例如&#xff0c;由于学习率过大&#xff0c;优化问题可能会发散&#xff0c;这种现象早已在梯度下降中出现。同样地&…
阅读更多...
YOLOV10实时端到端目标检测

YOLOV10实时端到端目标检测

代码地址&#xff1a;GitHub - THU-MIG/yolov10: YOLOv10: Real-Time End-to-End Object Detection 论文地址&#xff1a;https://arxiv.org/pdf/2405.14458 本文介绍了YOLO系列目标检测器在实时和高效方面的优势&#xff0c;但是仍然存在一些缺陷&#xff0c;包括依赖非极大值…
阅读更多...
Linux修炼之路之冯系结构，操作系统

Linux修炼之路之冯系结构，操作系统

目录 一&#xff1a;冯诺依曼体系结构 1.五大组件 2.存储器存在的意义 3.几个问题 二&#xff1a;操作系统 接下来的日子会顺顺利利&#xff0c;万事胜意&#xff0c;生活明朗-----------林辞忧 一&#xff1a;冯诺依曼体系结构 我们当代的计算机的基本构成都是由冯诺依曼…
阅读更多...
【Tools】微服务工程中的通用功能模块抽取

【Tools】微服务工程中的通用功能模块抽取

Catalog 通用功能模块抽取一、需求二、步骤三、细节 通用功能模块抽取 一、需求 在微服务工程中&#xff0c;可能有一些工具类、实体类是多个微服务通用的&#xff0c;如果在每个微服务中都复制粘贴这些工具类&#xff0c;会产生很多重复性的代码&#xff0c;对开发来说也很繁…
阅读更多...
git revert 和 git reset

git revert 和 git reset

文章目录 工作区 暂存区 本地仓库 远程仓库需求&#xff1a;已推送到远程仓库&#xff0c;想要撤销操作git revert &#xff08;添加新的提交来“反做”之前的更改&#xff0c;云端会残留上次的提交记录&#xff09;git reset&#xff08;相当于覆盖上次的提交&#xff09;1.--…
阅读更多...
Convolutional Occupancy Networks【ECCV】

Convolutional Occupancy Networks【ECCV】

论文&#xff1a;https://arxiv.org/pdf/2003.04618 代码&#xff1a;GitHub - autonomousvision/convolutional_occupancy_networks: [ECCV20] Convolutional Occupancy Networks 图 1&#xff1a;卷积占据网络。传统的隐式模型 (a) 由于其全连接网络结构&#xff0c;表现能力…
阅读更多...
自回归模型（二）：具有自回归误差的回归

自回归模型（二）：具有自回归误差的回归

让我们考虑一个问题&#xff0c;其中我们有一个y变量和多个x变量&#xff0c;它们都被测量为时间序列。举个例子&#xff0c;我们可以将y设定为高速公路上每月的事故数量&#xff0c;而x则表示每月在高速公路上的交通量&#xff0c;观测时间为连续的120个月。一个多元&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023