数据结构:顺序表 模拟实现及详解

目录

一、线性表

二、顺序表

2.1顺序表的概念及结构

2.1.1静态顺序表

2.2.2动态顺序表

2.2动态顺序表接口实现


一、线性表

  线性表( linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串...
  线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,
线性表在物理上存储时,通常以数组和链式结构的形式存储。

99f65998588745c3b51575878c970406.png

二、顺序表

2.1顺序表的概念及结构

  顺序表是用一段 物理地址连续的存储单元依次连续存储数据元素的线性结构,一般情况下采用 数组
储。在数组上完成数据的增删查改。
顺序表一般分为 静态顺序表动态顺序表

2.1.1静态顺序表

  这里的静态一般是指顺序表的长度是定长,及数组的大小是固定的。

424dd80310514333a003ce1bc42023b2.png

//静态顺序表
#define N 1000
typedef int SLDataType;

struct SeqList
{
	SLDataType a[N];
	int size;
};

此处创建一个顺序表SeqList,其包含两个成员,定长数组array和记录array及顺序表中有效数据的个数size。

2.2.2动态顺序表

764b110ca9bb406d9d70a3ffeed8b95c.png

  相比于静态顺序表,动态顺序表就显得更灵活和方便,静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空 间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间 大小,所以下面我们实现动态顺序表。

2.2动态顺序表接口实现

  静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空
间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间
大小,所以下面我们实现动态顺序表的以下接口。
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟的数组
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间,如果满了,进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);
void SLInit(SL* ps)
{
	assert(ps);

	ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
	if (ps->a == NULL)
	{
		perror("malloc failed");
		exit(-1);
		//return;
	}

	ps->size = 0;
	ps->capacity = 4;
}

void SLDestroy(SL* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void SLPrint(SL* ps)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SLCheckCapacity(SL* ps)
{
	assert(ps);

	// 满了要扩容
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}
}


void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);

	/*SLCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;*/
	SLInsert(ps, ps->size, x);//更好的复用代码
}

void SLPopBack(SL* ps)
{
	assert(ps);

	// 温柔的检查
	//if (ps->size == 0)
		//return;

	// 暴力的检查
	//assert(ps->size > 0);

	ps->a[ps->size - 1] = 0;
	//ps->size--;

	SLErase(ps, 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++;

	SLInsert(ps, 0, x);
}

void SLPopFront(SL* ps)
{
	assert(ps);

	/*assert(ps->size > 0);

	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;*/
	SLErase(ps, 0);
}

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

// 在pos位置插入x
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++;
}

// 删除pos位置的值
void SLErase(SL* ps, int pos)
{
	assert(ps);

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

	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;
}

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);

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

	ps->a[pos] = x;
}

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

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

相关文章

如何使用iPhone或iPad上的二维码共享Wi-Fi密码?这里有详细步骤

你有没有想过在不泄露网络密码的情况下与客人共享你的家庭或工作Wi-Fi?你肯定不是第一个这样想的人,我们很高兴地通知你,多亏了以下这个的变通方法,你现在可以使用iPhone或iPad做到这一点。 通常,如果你想让其他人访问网络,你需要共享你的Wi-Fi密码。苹果通过引入与任何…

Jetpack Compose -> 分包 自定义Composable

前言 上一章我们讲解了 Compose 基础UI 和 Modifier 关键字&#xff0c;本章主要讲解 Compose 分包以及自定义 Composable&#xff1b; Compose 如何分包 我们在使用 Button 控件的时候&#xff0c;发现如果我们想给按钮设置文本的时候&#xff0c;Button 函数并没有直接提供…

读书笔记-《数据结构与算法》-摘要8[桶排序]

桶排序和归并排序有那么点点类似&#xff0c;也使用了归并的思想。大致步骤如下&#xff1a; 设置一个定量的数组当作空桶。Divide - 从待排序数组中取出元素&#xff0c;将元素按照一定的规则塞进对应的桶子去。对每个非空桶进行排序&#xff0c;通常可在塞元素入桶时进行插入…

C#中ArrayList运行机制及其涉及的装箱拆箱

C#中ArrayList运行机制及其涉及的装箱拆箱 1.1 基本用法1.1.1 属性1.1.2 方法 1.2 内部实现1.3 装箱1.4 拆箱1.5 object对象的相等性比较1.6 总结1.7 其他简单结构类 1.1 基本用法 命名空间&#xff1a; using System.Collections; 1.1.1 属性 Capacity&#xff1a;获取或设…

【代码随想录10】20. 有效的括号 1047. 删除字符串中的所有相邻重复项 150. 逆波兰表达式求值

目录 20. 有效的括号题目描述参考代码 1047. 删除字符串中的所有相邻重复项题目描述参考代码 150. 逆波兰表达式求值题目描述参考代码 20. 有效的括号 题目描述 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;…

语音模块学习——LSYT201B模组(深圳雷龙科技)

目录 引子 处理器 外设 音频 蓝牙 模组展示 引子 关注我的老粉们应该知道我之前用过语音模块做东西&#xff0c;那个比较贵要50多。 今天这个淘宝20元左右比那个便宜&#xff0c;之前那个内核是51的&#xff0c;一个8位机。 后面我做东西的时候语音模块可能会换成这个&…

【51单片机】动态数码管

0、前言 参考&#xff1a; 普中51单片机开发攻略–A2.pdf 1、数码管介绍 上一章我们主要是介绍一位数码管的内部结构及控制原理。下面我们再来介 绍下多位数码管及动态显示原理的相关知识。 1.1 多位数码管简介 2、74HC245 和 74HC138 芯片介绍 2.1 74HC245 芯片简介 2.2 7…

Flink入门教程

使用flink时需要提前准备好scala环境 一、创建maven项目 二、添加pom依赖 <properties><scala.version>2.11.12</scala.version></properties><dependency><groupId>org.scala-lang</groupId><artifactId>scala-library<…

探索指针的奇妙世界,程序中的魔法箭头(上)

目录 一.指针是什么二.指针和指针类型1.指针加减整数2.指针的解引用 三.野指针1.野指针形成的原因&#xff08;1&#xff09;指针未初始化指针越界访问 2.如何规避野指针&#xff08;1&#xff09;指针初始化&#xff08;2&#xff09;小心指针越界&#xff08;3&#xff09;指…

用Python实现Excel中的Vlookup功能

目录 一、引言 二、准备工作 三、实现Vlookup功能 1、导入pandas库 2、准备数据 3、实现Vlookup功能 4、处理结果 5、保存结果 四、完整代码示例 五、注意事项 六、总结 一、引言 在Excel中&#xff0c;Vlookup是一个非常实用的函数&#xff0c;它可以帮助我们在表…

014-信息打点-JS架构框架识别泄漏提取API接口枚举FUZZ爬虫插件项目

014-信息打点-JS架构&框架识别&泄漏提取&API接口枚举&FUZZ爬虫&插件项目 #知识点&#xff1a; 1、JS前端架构-识别&分析 2、JS前端架构-开发框架分析 3、JS前端架构-打包器分析 4、JS前端架构-提取&FUZZ 解决&#xff1a; 1、如何从表现中的JS提取…

1.11马原

同一性是事物存在和发展的前提&#xff0c;一方的发展以另一方的发展为条件 同一性使矛盾双方相互吸收有利于自身的因素&#xff0c;在相互作用中各自得到发展 是事物发展根本规律&#xff0c;唯物辩证法的实质和核心 揭示了事物普遍联系的根本内容和变化发展的内在动力 是贯…

VIM工程的编译 / VI的快捷键记录

文章目录 VIM工程的编译 / VI的快捷键记录概述笔记工程的编译工程的编译 - 命令行vim工程的编译 - GUI版vim备注VIM的帮助文件位置VIM官方教程vim 常用快捷键启动vi时, 指定要编辑哪个文件正常模式光标的移动退出不保存 退出保存只保存不退出另存到指定文件移动到行首移动到行尾…

Java面试汇总——jvm篇

目录 JVM的组成&#xff1a; 1、JVM 概述(⭐⭐⭐⭐) 1.1 JVM是什么&#xff1f; 1.2 JVM由哪些部分组成&#xff0c;运行流程是什么&#xff1f; 2、什么是程序计数器&#xff1f;(⭐⭐⭐⭐) 3、介绍一下Java的堆(⭐⭐⭐⭐) 4、虚拟机栈(⭐⭐⭐⭐) 4.1 什么是虚拟机栈&…

【开源】基于JAVA语言的软件学院思政案例库系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统管理员2.2 普通教师 三、系统展示四、核心代码4.1 查询思政案例4.2 审核思政案例4.3 查询思政课程4.4 思政案例点赞4.5 新增思政案例评语 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的软件学…

2024最新:optee系统开发精讲 - 课程介绍

&#xff08;本课程中如有涉及代码或硬件架构&#xff0c;则对应的版本号&#xff1a;TF-A 2.80&#xff0c;optee 3.20, Linux Kernel 6.3&#xff0c;armv8.79.0的aarch64&#xff09; &#xff08;注意&#xff1a; 该课程没有PPT&#xff0c;该课程是对照代码讲解的&#x…

六、Netty核心模块组件

目录 6.1 BootStrap&#xff0c;ServerBootStrap6.2 Future&#xff0c;ChannelFuture6.3 Channel6.4 Selector6.5 ChannelHandler 以及其实现类6.6 Pipeline 和 ChannelPipeline6.7 ChannelHandlerContext6.8 ChannelOption6.9 EventLoopGroup和其实现类 NioEventLoopGroup6.1…

力扣 第 122 场双周赛 解题报告 | 珂学家 | 脑筋急转弯 + 滑窗反悔堆

前言 整体评价 倒开差点崩盘&#xff0c;T4这个反悔堆写吐了&#xff0c;T3往众数上去猜了&#xff0c;幸好case良心。 T1. 将数组分成最小总代价的子数组 I 思路: 取 nums[1:] 的最小2个值 可以部分排序&#xff0c;这样更快捷 class Solution {public int minimumCost(in…

WorkPlus:构建高效协作的企业即时通讯解决方案

在现代企业中&#xff0c;高效沟通是实现协作和改善工作效率的关键。而企业即时通讯工具成为了推进沟通的利器。作为一款高质量的企业即时通讯解决方案&#xff0c;WorkPlus以其卓越的性能和独特的功能&#xff0c;助力企业构建高效协作的新格局。 为什么选择WorkPlus作为企业即…

一文读懂「RAG,Retrieval-Augmented Generation」检索增强生成

Retrieval-Augmented Generation&#xff08;RAG&#xff09;作为机器学习和自然语言处理领域的一大创新&#xff0c;不仅代表了技术的进步&#xff0c;更在实际应用中展示了其惊人的潜力。 RAG结合了检索&#xff08;Retrieval&#xff09;和生成&#xff08;Generation&#…