数据结构初阶之顺序表（C语言实现）

在这里插入图片描述

数据结构初阶之线性表（C语言实现）

  • 🍏前言：
  • 🍏顺序表和数组的区别
  • 🍏动态顺序表的模拟实现
    • 🍀动态顺序表的基本结构设计
    • 🍀动态顺序表的各种功能模拟实现
      • 🐲 初始化（init）
      • 🐲 头插、头删
        • 🚙 头插
        • 🚙 头删
      • 🐲 尾插、尾删
        • 🚙 尾插
        • 🚙 尾删
      • 🐲 计算动态顺序表的大小（size接口）
      • 🐲 动态顺序表在特定位置插入（insert）
      • 🐲 动态顺序表在特定位置删除（erase）
      • 🐲 动态顺序表的查找
      • 🐲 修改某个位置的值
      • 🐲 动态顺序表的销毁
  • ⭕️ 总结

🍏前言：

顺序表是数据结构里面很基础的一类，它是线性表的一种，其它线性表还有链表、栈和队列等，今天来和博主一起学习关于顺序表的知识吧。

🍏顺序表和数组的区别

顺序表，它分为两类：动态顺序表和静态顺序表，这两个表的区别就是前者的空间不固定，是支持扩容的，后者的空间是固定的，但是两者的共同点是空间都是连续的，动态顺序表的底层是动态数组，而静态顺序表的底层是数组。

  • 很明显我们经常用到的数据结构就是动态的顺序表，因为静态的顺序表空间固定，没什么实际的价值。
  • 还有一个区别就是，动态顺序表是基于动态数组的，但是它作为一个数据结构，提供了很多动态数组没有直接提供的功能，像增、删、查、改、创建和销毁、以及计算数组的大小这些基本的功能。

在这里插入图片描述

🍏动态顺序表的模拟实现

🍀动态顺序表的基本结构设计

#define DataTypeVector int
typedef struct my_vector
{
	int* a;//储存数据
	size_t size;//顺序表的数据大小
	size_t capacity;//顺序表的空间大小
}mv;

各种接口：

//初始化

mv* Init();

//头插
void push_front(mv* mv1, DataTypeVector x);

//头删
void pop_front(mv* mv1);

//尾插
void push_back(mv* mv1, DataTypeVector x);

//尾删
void pop_back(mv* mv1);

//插入--在某个位置之前
void insert(mv* mv1,size_t positon, DataTypeVector x);

//删除某个位置的元素
void erase(mv* mv1,size_t position);

//查找某个值，并返回它出现的位置,没有找到，返回-1；
int find(mv* mv1, DataTypeVector x);

//计算动态顺序表的大小
size_t Size(mv* mv1);

//销毁动态顺序表
void Destroy(mv** mv1);

//修改某个位置的值
void Modify(mv* mv1, size_t position, DataTypeVector x);

🍀动态顺序表的各种功能模拟实现

🐲 初始化（init）

返回值版本：

//初始化动态顺序表
//返回值版本
mv* Init()
{
	mv* mv1 = (mv*)malloc(sizeof(mv));
	if (mv1 == NULL)
	{
		printf("malloc Falied\n");
		exit(-1);
	}
	mv1->a = NULL;
	mv1->capacity = 0;
	mv1->size = 0;
	return mv1;
}

二级指针版本：

//二级指针版本，不带返回值
void Init(mv** mv1)
{
	assert(mv1);
	(*mv1) = (mv*)malloc(sizeof(mv));
	if ((*mv1) == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	(*mv1)->a = NULL;
	(*mv1)->capacity = NULL;
	(*mv1)->size = NULL;
}

🐲 头插、头删

🚙 头插
//头插
void push_front(mv* mv1, DataTypeVector x)
{
	assert(mv1 != NULL);
	if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
	{
		(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
		DataTypeVector* tmp = NULL;
		tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		mv1->a = tmp;
	}

	//将所有值后移
	for (size_t i = mv1->size; i > 0; --i)
	{
		mv1->a[i] = mv1->a[i-1];
	}

	mv1->a[0] = x;
	++mv1->size;
}

在这里插入图片描述

🚙 头删
//头删
void pop_front(mv* mv1)
{
	assert(mv1 != NULL);
	assert(mv1->size > 0);

	//将后面的值依次覆盖前面的值
	for (size_t i = 0; i < mv1->size-1; ++i)
	{
		mv1->a[i] = mv1->a[i + 1];
	}

	--mv1->size;//别忘了数组的大小要减减
}

在这里插入图片描述

🐲 尾插、尾删

🚙 尾插
//尾插
void push_back(mv* mv1, DataTypeVector x)
{
	assert(mv1 != NULL);

	if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
	{
		(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
		DataTypeVector* tmp = NULL;
		tmp = (DataTypeVector*)realloc(mv1->a,sizeof(DataTypeVector) * mv1->capacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		mv1->a = tmp;
	}
	mv1->a[mv1->size] = x;
	++mv1->size;
}

在这里插入图片描述

🚙 尾删
//尾删
void pop_back(mv* mv1)
{
	assert(mv1);
	assert(mv1->size > 0);
	--mv1->size;
}

在这里插入图片描述

🐲 计算动态顺序表的大小（size接口）

//计算动态线性表的大小
size_t Size(mv* mv1)
{
	assert(mv1);
	return mv1->size;
}

在这里插入图片描述

🐲 动态顺序表在特定位置插入（insert）

这里我们仿照C++STL库，只实现了在pos位置之前插入。
在这里插入图片描述

//插入--在某个位置之前
//插入--在某个位置之前
void insert(mv* mv1, size_t position,DataTypeVector x)
{
	assert(mv1 != NULL);
	assert(position < mv1->size);

	if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
	{
		(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
		DataTypeVector* tmp = NULL;
		tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
		if (tmp == NULL)
		{
			printf("calloc failed\n");
			exit(-1);
		}
		mv1->a = tmp;
	}

	//从下标size开始，把数据都往后挪动.
	
		for (size_t i = mv1->size; i > position; --i)
		{
			mv1->a[i] = mv1->a[i-1];
		}
	
	
	//最后把下标position位置赋值为x
	mv1->a[position] = x;
	//别忘了size
	++mv1->size;
}

在这里插入图片描述

🐲 动态顺序表在特定位置删除（erase）

//删除某个位置的元素
void erase(mv* mv1, size_t position)
{
	assert(mv1 != NULL);
	assert(position < mv1->size);

	for (size_t i = position; i < mv1->size-1; ++i)
	{
		mv1->a[i] = mv1->a[i + 1];
	}

	--mv1->size;
}

在这里插入图片描述

🐲 动态顺序表的查找

//查找某个值，并返回它出现的位置,没有找到，返回-1；
int find(mv* mv1,DataTypeVector x)
{
	assert(mv1 != NULL);

	for (size_t i = 0; i < mv1->size; ++i)
	{
		if (x == mv1->a[i])//找到直接返回下标i
			return i;
	}

	return -1;//没有找到返回-1
}

这里顺序表不一定是有序的，所以不能使用二分查找。

🐲 修改某个位置的值

void Modify(mv* mv1,size_t position,DataTypeVector x)
{
	assert(mv1);
	assert(position < mv1->size);

	mv1->a[position] = x;
}

🐲 动态顺序表的销毁

动态顺序表的底层就是动态数组，它是堆上开辟的，通常遵循一下原则：
1. 由谁申请就由谁释放。 这是一个约定俗成的说法，指的是谁（程序员）申请的内存，需要自己负责去释放，避免出现内存泄漏。
2.只能一次释放整个动态数组，而不能只释放一部分
只要我们遵循这两个原则，然后再对顺序表类型的成员进行置空和置零，就实现了动态线顺序表的销毁。

//销毁动态顺序表
void Destroy(mv** mv1)
{
	assert(mv1 != NULL);
	(*mv1)->capacity = (*mv1)->size = 0;
	free((*mv1)->a);//先销毁顺序表里面的成员
	(*mv1)->a = NULL;
	free(*mv1);//销毁整个顺序表
	*mv1 = NULL;
}

⭕️ 总结

关于《数据结构初阶之顺序表（C语言实现）》这篇文章就讲解到这儿，感谢大家的支持，欢迎大家留言交流以及批评指正。接下来将为大家带来一篇《不一样的C语言之easyx库的使用》，敬请期待吧。下面是本篇博客的思维导图希望对您有所帮助。

在这里插入图片描述

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

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

相关文章

兔子目标检测数据集VOC格式3900张

兔子目标检测数据集VOC格式3900张

兔子是一类可爱的哺乳动物&#xff0c;拥有圆润的脸庞和长长的耳朵&#xff0c;身体轻盈柔软。它们通常是以温和和友善的形象出现在人们的视野中&#xff0c;因此常常成为童话故事和卡通形象中的角色。 兔子是草食性动物&#xff0c;主要以各种草本植物为食&#xff0c;包括草…
阅读更多...
【八】【C语言\动态规划】1567. 乘积为正数的最长子数组长度、413. 等差数列划分、978. 最长湍流子数组，三道题目深度解析

【八】【C语言\动态规划】1567. 乘积为正数的最长子数组长度、413. 等差数列划分、978. 最长湍流子数组，三道题目深度解析

动态规划 动态规划就像是解决问题的一种策略&#xff0c;它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题&#xff0c;并将每个小问题的解保存起来。这样&#xff0c;当我们需要解决原始问题的时候&#xff0c;我们就可以直接利…
阅读更多...
git 学习 之一个规范的 commit 如何写

git 学习 之一个规范的 commit 如何写

最好的话做一件完整的事情就提交一次
阅读更多...
状态管理概述

状态管理概述

ArkTS UI的状态管理到这里就叙述完了&#xff0c;现在做一个概述&#xff0c;也可以认为是一个总结。 在声明式UI编程框架中&#xff0c;UI是程序状态的运行结果&#xff0c;用户构建了一个UI模型&#xff0c;其中应用的运行时的状态是参数。当参数改变时&#xff0c;UI作为返回…
阅读更多...
Vue（一）：Vue 入门与 Vue 指令

Vue（一）：Vue 入门与 Vue 指令

Vue 01. Vue 快速上手 1.1 Vue 的基本概念 用于 构建用户界面 的 渐进性 框架 构建用户界面&#xff1a;基于数据去渲染用户看到的界面渐进式&#xff1a;不需要学习全部的语法就能完成一些功能&#xff0c;学习是循序渐进的框架&#xff1a;一套完整的项目解决方案&#x…
阅读更多...
探索Apache Commons Imaging处理图像

探索Apache Commons Imaging处理图像

第1章&#xff1a;引言 大家好&#xff0c;我是小黑&#xff0c;咱们今天来聊聊图像处理。在这个数字化日益增长的时代&#xff0c;图像处理已经成为了一个不可或缺的技能。不论是社交媒体上的照片编辑&#xff0c;还是专业领域的图像分析&#xff0c;图像处理无处不在。而作为…
阅读更多...
JavaSE50题：26. （数组练习题）使奇数位于偶数之前

JavaSE50题：26. （数组练习题）使奇数位于偶数之前

概述 调整数组顺序使得奇数位于偶数之前&#xff0c;调整之后&#xff0c;不关心大小顺序。 如数组&#xff1a;{1,2,3,4,5,6} 调整后可能是&#xff1a;{1&#xff0c;5&#xff0c;3&#xff0c;4&#xff0c;2&#xff0c;6} 方法 定义 left 和 right&#xff0c;二者分别…
阅读更多...
位运算|比特位计数、汉明距离

位运算|比特位计数、汉明距离

位运算|比特位计数、汉明距离 338 比特位计数 /** 比特位计数法一&#xff1a;Brian Kernighan 算法的原理是&#xff1a;对于任意整数 x&#xff0c;令 xx & (x−1)&#xff0c;该运算将 x 的二进制表示的最后一个 1 变成 0。因此&#xff0c;对 x 重复该操作&#xff0…
阅读更多...
中职网络安全Web2003-2——Web渗透测试

中职网络安全Web2003-2——Web渗透测试

需要环境或换&#xff0c;有问题可以私信我或加Q 1.通过URL访问http://靶机IP/1&#xff0c;对该页面进行渗透测试&#xff0c;将完成后返回的结果内容作为Flag值提交&#xff1b; FLAGflag{htmlcode} 2.通过URL访问http://靶机IP/2&#xff0c;对该页面进行渗透测试&#xff…
阅读更多...
数字钥匙进入3.0时代，他们要做智能汽车时代的「微信」

数字钥匙进入3.0时代，他们要做智能汽车时代的「微信」

“假设用我们的即时通讯的工具来说&#xff0c;我们想造一个微信&#xff0c;我们希望跟更多的主机厂拥抱融合&#xff0c;而不是造一个飞信。” 11月24日&#xff0c;在银基科技承办的第三届数字钥匙及生态大会期间&#xff0c;银基科技CEO单宏寅尝试向到场的媒体&#xff0c…
阅读更多...
Flink Kafka[输入/输出] Connector

Flink Kafka[输入/输出] Connector

本章重点介绍生产环境中最常用到的Flink kafka connector。使用Flink的同学&#xff0c;一定会很熟悉kafka&#xff0c;它是一个分布式的、分区的、多副本的、 支持高吞吐的、发布订阅消息系统。生产环境环境中也经常会跟kafka进行一些数据的交换&#xff0c;比如利用kafka con…
阅读更多...
代码随想录刷题题Day24

代码随想录刷题题Day24

刷题的第二十四天&#xff0c;希望自己能够不断坚持下去&#xff0c;迎来蜕变。&#x1f600;&#x1f600;&#x1f600; 刷题语言&#xff1a;C Day24 任务 ● 491.递增子序列 ● 46.全排列 ● 47.全排列 II 1 递增子序列 491.递增子序列 思路&#xff1a; 本题求自增子序…
阅读更多...
Translation翻译插件

Translation翻译插件

Translation插件是为IntelliJ IDEA开发的&#xff0c;因此只能在IntelliJ IDEA中使用。但是&#xff0c;如果你需要在其他软件中进行翻译&#xff0c;可以考虑使用其他的翻译工具或服务。例如&#xff0c;一些在线翻译网站&#xff08;如Google翻译、百度翻译等&#xff09;提供…
阅读更多...
由浅入深走进Python异步编程【协程与yield】（含代码实例讲解 || 迭代器、生成器、协程、yield from）

由浅入深走进Python异步编程【协程与yield】（含代码实例讲解 || 迭代器、生成器、协程、yield from）

写在前面 从底层到第三方库&#xff0c;全面讲解python的异步编程。这节讲述的是python异步编程的底层原理第一节&#xff0c;详细了解需要配合下一节观看哦。纯干货&#xff0c;无概念&#xff0c;代码实例讲解。 本系列有6章左右&#xff0c;点击头像或者专栏查看更多内容&…
阅读更多...
C++学习实践（一）高频面试问题总结（附详细答案）

C++学习实践（一）高频面试问题总结（附详细答案）

文章目录 一、基础常见面试题1、数组和链表区别2、深拷贝和浅拷贝相关问题的区别3、a和a区别4、c内存模型5、四种强制转换和应用场景 二、指针相关1、指针和引用的区别2、函数指针和指针函数3、传指针、引用和值4、常量指针和指针常量5、野指针6、智能指针的用法 三、关键字作用…
阅读更多...
YOLOv8可视化：引入多种可视化CAM方法，为科研保驾护航

YOLOv8可视化：引入多种可视化CAM方法，为科研保驾护航

💡💡💡本文内容：调用pytorch下的CAM可视化库，支持十多种可视化方法，打开“黑盒”，让YOLOv8变得相对可解释性 收录 YOLOv8原创自研 https://blog.csdn.net/m0_63774211/category_12511737.html?spm=1001.2014.3001.5482 💡💡💡全网独家首发创新（原创），适…
阅读更多...
桥接模式-举例

桥接模式-举例

概叙&#xff1a;桥接模式用一种巧妙的方式处理多层继承存在的问题&#xff0c; 用抽象关联取代了传统的多层继承&#xff0c; 将类之间的静态继承关系转换为动态的对象组合关系&#xff0c; 使得系统更加灵活&#xff0c;并易于扩展&#xff0c; 同时有效控制了系统中类的个数…
阅读更多...
企业如何购买腾讯云服务器?(详细指南)

企业如何购买腾讯云服务器?(详细指南)

腾讯云服务器购买流程直接在官方秒杀活动上购买比较划算&#xff0c;在云服务器CVM或轻量应用服务器页面自定义购买价格比较贵&#xff0c;但是自定义购买云服务器CPU内存带宽配置选择范围广&#xff0c;活动上购买只能选择固定的活动机&#xff0c;选择范围窄&#xff0c;但是…
阅读更多...
专题四：前缀和

专题四：前缀和

前缀和 一.一维前缀和(模板)&#xff1a;1.思路一&#xff1a;暴力解法2.思路二&#xff1a;前缀和思路 二. 二维前缀和(模板)&#xff1a;1.思路一&#xff1a;构造前缀和数组 三.寻找数组的中心下标&#xff1a;1.思路一&#xff1a;前缀和 四.除自身以外数组的乘积&#xff…
阅读更多...
php最常出现的错误

php最常出现的错误

目录 1. E_WARNING&#xff1a;为 foreach &#xff08;&#xff09;提供的参数无效 2. PDOException&#xff1a;拒绝SQLSTATEHY000连接 3.错误使用empty函数 1. E_WARNING&#xff1a;为 foreach &#xff08;&#xff09;提供的参数无效 PHP foreach构造在PHP 4中引入&am…
阅读更多...
最新文章

Copyright @ 2022~2023