顺序表（数据结构与算法）

news/2024/5/20 5:47:46 标签: 数据结构, 顺序表

请添加图片描述
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 无人扶我青云志 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 我自踏雪之山巅🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍋顺序表

🍌顺序表的定义

顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

在这里插入图片描述

线性表：线性表是最基本、最简单、也是最常用的一种数据结构。大部分线性表除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。而又一些小部分,比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点

🍌顺序表的结构

🍍静态顺序表

静态顺序表就是以一定长度的数组来存储元素

//静态存储
#define  N  5
typedef int SLDetatype ;
typedef struct SeqList
{
	SLDetatype a[N] ;//有限空间的数组
	int size ;//有效的数据个数
}SeqList;

在这里插入图片描述

🍍动态顺序表

动态顺序表使用动态开辟的数组来存储元素

//动态存储
typedef  int SLDetatype ;
typedef struct SeqList
{
	SLDetatype *a ;   //指向动态开辟的数组
	int size ;       //有效的数据个数
	int capicity ;   //空间的容量
}SeqList;

在这里插入图片描述

🍌顺序表接口的实现（增删查改）

🍍其它接口

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

typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int capacity;
	int size;
}SeqList;

🍍顺序表初始化

void SeqListInit(SeqList* ps)
{
	ps->a = NULL;            
	//在初始情况我们可以直接置空
	//当然也可以创建空间，看自己习惯
	ps->capacity = ps->size = 0;
}

🍍检查空间是否增容（空间满了就增容）

void CheckCapacity(SeqList* ps)
{
	assert(ps);
	//在两个相等时，空间可能会满，还可能空间为0，这是因为我们在初始化没有创建空间导致
	if (ps->capacity == ps->size)
	{
		if (ps->capacity == 0)
			ps->capacity = 2;
		else
			ps->capacity *= 2;
		int newcapacity = ps->capacity;
		//在扩容时，我们都是利用realloc,创建空间利用malloc
		SLDatatype* cur = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * newcapacity);
		if (cur == NULL)
		{
			perror("realloc   faild");
			exit(-1);
		}
		ps->a = cur;
		ps->capacity = newcapacity;
	}
}

大家如果对于malloc和realloc以及空间的创建的用法有些遗忘，可以看我这篇博客：动态内存管理（这是一个链接，有需要的朋友可以直接点进去）

🍍顺序表尾插

void SeqListPushBack(SeqList* ps, SLDatatype x)
{
	assert(ps);
	CheckCapacity(ps);  //需要检查空间是否满或者空
	ps->a[ps->size] = x;
	(ps->size)++;
}

在这里插入图片描述

🍍顺序表尾删

//顺序表尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);  //检查数据个数是否为0，如果为0就不执行，反之亦然
	(ps->size)--;
}

在这里插入图片描述

🍍顺序表头插

// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDatatype x)
{
	assert(ps);
	CheckCapacity(ps);//判断空间是否满还是空
	//注意头插要分两种情况
	//第一种是数组里没有元素，此时头插就是相当于尾插
	//第二种是数组里有元素，这时就先把整体元素往后移动一位
	if (ps->size - 1 == 0)
	{
		ps->a[ps->size -1] = x;
		(ps->size)++;
	}
	else
	{
		int end = ps->size - 1;
		while (end >= 0)
		{
			ps->a[end + 1] = ps->a[end];
			end--;
		}
		ps->a[0] = x;
		(ps->size)++;
	}
}

注意：
注意头插要分两种情况
（1）第一种是数组里没有元素，此时头插就是相当于尾插
（2）第二种是数组里有元素，这时就先把整体元素往后移动一位

在这里插入图片描述

🍍顺序表头删

// 顺序表头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//注意头删要分两种情况
	//第一种是数组里没有元素，此时头删就是相当于尾删
	//第二种是数组里有元素，这时就需要把除了第一个元素外的所有元素往前移动一位，把原来的第一位元素覆盖
	if (ps->size - 1 == 0)
	{
		(ps->size)--;
	}
	else
	{
		int end = 0;
		while (end < ps->size - 1)
		{
			ps->a[end] = ps->a[end + 1];
			end++;
		}
		(ps->size)--;
	}
}

注意:
注意头删要分两种情况
（1）第一种是数组里没有元素，此时头删就是相当于尾删
（2）第二种是数组里有元素，这时就需要把除了第一个元素外的所有元素往前移动一位，把原来的第一位元素覆盖

在这里插入图片描述

🍍顺序表查找

// 顺序表查找
int SeqListFind(SeqList* ps, SLDatatype x)
{
	assert(ps);
	int i = 0;
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return 1;
	}
	return -1;
}

🍍顺序表在pos位置插入x

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int i = 0;
	for (i = pos - 1; i < ps->size - 1; i++)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos-1] = x;
	(ps->size)++;
}

注意:pos必须在0到ps->size之间

在这里插入图片描述

🍍顺序表删除pos位置的值

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	int i = 0;
	for (i = pos - 1; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	(ps->size)--;
}

注意：pos必须在0到ps->size之间

🍍顺序表修改pos位置的值

//顺序表修改pos位置的值
void SeqModify(SeqList* ps, int pos, SLDatatype x)
{
	assert(ps);

	assert(pos >= 0 && pos < ps->size);

	ps->a[pos - 1] = x;
}

🍍顺序表销毁

// 顺序表销毁
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

🍍顺序表打印

// 顺序表打印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

🍌顺序表整体代码的实现

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

typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int capacity;
	int size;
}SeqList;

//顺序表初始化
void SeqListInit(SeqList* ps)
{
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//检查空间，如果满了就增容
void CheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		if (ps->capacity == 0)
			ps->capacity = 2;
		else
			ps->capacity *= 2;
		int newcapacity = ps->capacity;
		SLDatatype* cur = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * newcapacity);
		if (cur == NULL)
		{
			perror("realloc   faild");
			exit(-1);
		}
		ps->a = cur;
		ps->capacity = newcapacity;
	}
}

//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDatatype x)
{
	assert(ps);
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	(ps->size)++;
}

//顺序表尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	(ps->size)--;
}

// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDatatype x)
{
	assert(ps);
	CheckCapacity(ps);
	if (ps->size == 0)
	{
		ps->a[ps->size] = x;
		(ps->size)++;
	}
	else
	{
		int end = ps->size - 1;
		while (end >= 0)
		{
			ps->a[end + 1] = ps->a[end];
			end--;
		}
		ps->a[0] = x;
		(ps->size)++;
	}
}

// 顺序表头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	if (ps->size - 1 == 0)
	{
		(ps->size)--;
	}
	else
	{
		int end = 0;
		while (end < ps->size - 1)
		{
			ps->a[end] = ps->a[end + 1];
			end++;
		}
		(ps->size)--;
	}
}

// 顺序表查找
int SeqListFind(SeqList* ps, SLDatatype x)
{
	assert(ps);
	int i = 0;
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return 1;
	}
	return -1;
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int i = 0;
	for (i = pos - 1; i < ps->size - 1; i++)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos-1] = x;
	(ps->size)++;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	int i = 0;
	for (i = pos - 1; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	(ps->size)--;
}

// 顺序表销毁
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

// 顺序表打印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}


//顺序表修改pos位置的值
void SeqModify(SeqList* ps, int pos, SLDatatype x)
{
	assert(ps);

	assert(pos >= 0 && pos < ps->size);

	ps->a[pos - 1] = x;
}

void test1()
{
	SeqList cur;
	SeqListInit(&cur);
	SeqListPushBack(&cur, 500);//尾插
	SeqListPushBack(&cur, 400);//尾插
	SeqListPushBack(&cur, 300);//尾插
	SeqListPrint(&cur);

	SeqListPopBack(&cur);//尾删
	SeqListPrint(&cur);

	SeqListPushFront(&cur, 100);//头插
	SeqListPushFront(&cur, 200);//头插
	SeqListPushFront(&cur, 600);//头插
	SeqListPrint(&cur);

	SeqListPopFront(&cur); //头删
	SeqListPrint(&cur);

	if (SeqListFind(&cur,200) == 1)//元素查找
		printf("找到了\n");
	else
	{
		printf("没有找到\n");
	}

	SeqListInsert(&cur, 3, 999);//在pos位置插入x
	SeqListPrint(&cur);

	SeqListErase(&cur, 3);//删除pos位置的值
	SeqListPrint(&cur);

	SeqModify(&cur, 3, 666); //修改pos位置的值
	SeqListPrint(&cur);
}

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

请添加图片描述


http://www.niftyadmin.cn/n/5191662.html

相关文章

抖音直播间涨粉助手，其开发流程与需要的技术和代码分享

抖音直播间涨粉助手，其开发流程与需要的技术和代码分享

先来看实操成果&#xff0c;↑↑需要的同学可看我名字↖↖↖↖↖&#xff0c;或评论888无偿分享 一、直播间涨人气的15种方法 直播间的人气就像水池中的水&#xff0c;想要有源源不断的流量&#xff0c;就要想办法把水龙头的水流开到最大&#xff0c;也就是要增加直播间曝光率&…
阅读更多...
通信原理板块——奇偶监督码、方阵码、恒比码、正反码

通信原理板块——奇偶监督码、方阵码、恒比码、正反码

微信公众号上线&#xff0c;搜索公众号小灰灰的FPGA,关注可获取相关源码&#xff0c;定期更新有关FPGA的项目以及开源项目源码&#xff0c;包括但不限于各类检测芯片驱动、低速接口驱动、高速接口驱动、数据信号处理、图像处理以及AXI总线等 1、奇偶监督码(parity check) 奇偶…
阅读更多...
目标检测标注工具AutoDistill

目标检测标注工具AutoDistill

引言 在快速发展的机器学习领域&#xff0c;有一个方面一直保持不变&#xff1a;繁琐和耗时的数据标注任务。无论是用于图像分类、目标检测还是语义分割&#xff0c;长期以来人工标记的数据集一直是监督学习的基础。 然而&#xff0c;由于一个创新性的工具 AutoDistill&#x…
阅读更多...
使用maven命令打包依赖

使用maven命令打包依赖

1、maven仓库地址 阿里云地址&#xff1a;https://developer.aliyun.com/mvn/search 中央仓库地址&#xff1a;https://mvnrepository.com/ 2、下载方式 在地址栏中输入要搜索的依赖 选择需要的版本 &#xff08;1&#xff09;直接复制 &#xff08;2&#xff09;pom下载 …
阅读更多...
简朴博客系统测试报告

简朴博客系统测试报告

文章目录 一. 项目简介二. 测试概要三. 测试环境四. 测试执行概况及功能测试1. 手工测试1.1 手动测试用例编写1.2 执行的部分测试用例 2. 自动化测试Selenium2.1 编写测试用例2.2 自动化测试代码 3. 测试结果 五. 发现的问题 一. 项目简介 简朴博客系统是采用前后端分离的方式…
阅读更多...
国科大数据挖掘期末复习——聚类分析

国科大数据挖掘期末复习——聚类分析

聚类分析 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。由聚类所生 成的簇是一组数据对象的集合&#xff0c;这些对象与同一个簇中的对象彼此相似&#xff0c;与其他簇中的对象相异。 聚类属于无监督学习&#xff08;unsupervised learning&…
阅读更多...
FreeRtos 任务切换深入分析

FreeRtos 任务切换深入分析

一、背景知识&#xff1a; 1、任务切换包含三个基本流程&#xff1a;保护现场、更新TCB、恢复现场并跳转 2、freertos的任务切换是在xPortPendSVHandler 中断函数中完成的 3、中断函数在调用之前&#xff0c;硬件已经保存了r0,r1,r2,r3,r12,r14(LR),r15(pc)&#xff0c;恢复…
阅读更多...
SpringCloud FeignClient声明式服务调用采坑记录（A调用服务B/C，B/C重启后必须重启A后才能成功调用配置项）

SpringCloud FeignClient声明式服务调用采坑记录（A调用服务B/C，B/C重启后必须重启A后才能成功调用配置项）

SpringCloud FeignClient声明式服务调用&#xff08;A调用服务B/C&#xff0c;B/C重启后必须重启A后才能成功调用配置项采坑记录&#xff09; 1. 报错&#xff08;info级别的警告信息&#xff09;2. 原因&#xff1a;使用了默认了cache负载均衡&#xff0c;或者禁用了ribbonLoa…
阅读更多...
最新文章

Copyright @ 2022~2023