【数据结构】 顺序表详解!(源码+解析)

这篇具有很好参考价值的文章主要介绍了【数据结构】 顺序表详解!(源码+解析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】 顺序表详解!(源码+解析),数据结构探索,数据结构,c语言,开发语言

🎥 屿小夏 : 个人主页
🔥个人专栏 : 数据结构解析
🌄 莫道桑榆晚,为霞尚满天!

📑前言

​ 什么是数据结构?我们为什么要学数据结构?数据结构中的顺序表长什么样子?它是怎么运用?

​ 本期我们将对这些一一讲解,彻底明白数据结构的重要性,以及顺序表是一种什么的数据结构。

🌤️数据结构的重要性

【数据结构】 顺序表详解!(源码+解析),数据结构探索,数据结构,c语言,开发语言

☁️什么是数据结构?

​ 数据结构指的是计算机中组织和存储数据的方式。它涉及到数据的组织、管理和操作,以便能够高效地访问和处理数据。

☁️数据结构能干嘛?

​ 数据结构可以用来解决各种计算问题,它提供了不同的数据类型和操作,使得我们可以有效地存储和操作数据。通过选择合适的数据结构,我们可以提高算法的效率,减少时间和空间的消耗。

☁️数据结构有多重要?

​ 它是算法设计和优化的基础,对于解决实际问题和提高计算机程序的性能至关重要。良好的数据结构设计可以提高程序的可读性、可维护性和可扩展性,同时也能够减少资源的消耗和提高程序的执行效率。

🌤️顺序表的概念与结构

☁️顺序表的概念

​ 顺序表是一种线性表的存储结构,它将元素顺序地存储在一块连续的内存空间中。顺序表中的元素在内存中的物理地址是连续的,通过元素在内存中的相对位置来表示元素之间的逻辑关系。

☁️顺序表的结构

​ 顺序表由两部分组成:数据存储区和长度信息。数据存储区是一块连续的内存空间,用来存储顺序表中的元素。长度信息记录了顺序表中元素的个数。

☁️顺序表图例

【数据结构】 顺序表详解!(源码+解析),数据结构探索,数据结构,c语言,开发语言

🌤️动态顺序表的实现

☁️顺序表所需要的接口

typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* array;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;
//增删查改
void SLInit(SL* ps);//初始化
void SLdestroy(SL* ps);//销毁
//打印
void SLprint(SL* ps);
//检查空间
void Inspect(SL* ps);
//尾插尾删
void SLpushBack(SL* ps, SLDatatype x);
void SLpopback(SL* ps);
//头插头删
void SLpushFront(SL*ps, SLDatatype x);
void SLpopFront(SL*ps);
//查找数据下标
int  SLFind(SL* ps, SLDatatype x);
//在pox位置插入x
void SLInsert(SL* ps, int pox,SLDatatype x);
//删除pox位置的值
void SLErase(SL* ps, int pox);
//修改pox位置的值
void SLModify(SL* ps, int pox, SLDatatype x);

☁️顺序表的初始化

对顺序表进行初始化,使表的开始大小可以存储4个有效元素。

void SLInit(SL* ps)
{
	assert(ps);
	ps->array = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (ps->array == NULL)
	{
		perror("malloc failde");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

☁️顺序表的空间检查

若是表中的元素个数已满,则进行扩容,扩容的后大小是原顺序表的2倍。

void Inspect(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(ps->array, ps->capacity * 2 * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->array = tmp;
		ps->capacity *= 2;
	}
}

☁️顺序表的打印

打印顺序表中所有的元素。

void SLprint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->array[i]);
	}
	printf("\n");
}

☁️顺序表的尾部插入

在顺序表的末尾插入元素。

void SLpushBack(SL* ps, SLDatatype x)
{
	assert(ps);
	Inspect(ps);
	ps->array[ps->size] = x;
	ps->size++;
}

☁️顺序表的尾部删除

将顺序表最后一个元素删除。

void SLpopback(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

☁️顺序表的头部插入

在顺序表的头部,表中首元素的前面插入新的元素,这时就需要将旧数据都往后挪一位。

void SLpushFront(SL* ps, SLDatatype x)
{
	assert(ps);
	Inspect(ps);
	int len = ps->size - 1;
	while (len >= 0)
	{
		ps->array[len + 1] = ps->array[len];
		len--;
	}
	ps->array[0] = x;
	ps->size++;
}

☁️顺序表的头部删除

将头部的首元素删除。

//头删
void SLpopFront(SL* ps)
{
	assert(ps);
	int left = 1;
	while (left < ps->size)
	{
		ps->array[left - 1] = ps->array[left];
		left++;
	}
	ps->size--;
}

☁️顺序表查找数据下标

这一步是为了在指定的位置进行增删改查。

int  SLFind(SL* ps, SLDatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

☁️顺序表指定位置插入元素

查找到要插入的位置下标,将元素插入。

void SLInsert(SL* ps, int pox, SLDatatype x)
{
	assert(ps);
	assert(pox >= 0 && pox <= ps->size);
	Inspect(ps);
	int end = ps->size - 1;
	while (end >= pox)
	{
		ps->array[end + 1] = ps->array[end];
		end--;
	}
	ps->array[pox] = x;
	ps->size++;
}

☁️顺序表指定位置元素删除

查找到要删除的位置下标,将元素删除。

void SLErase(SL* ps, int pox)
{
	assert(ps);
	assert(pox >= 0 && pox < ps->size);
	int begin = pox + 1;
	while (begin < ps->size)
	{
		ps->array[begin - 1] = ps->array[begin];
		begin++;
	}
	ps->size--;
}

☁️顺序表修改指定位置的值

查找到要修改的值的位置下标,将旧的元素改为新的值。

void SLModify(SL* ps, int pox, SLDatatype x)
{
	assert(ps);
	assert(pox >= 0 && pox < ps->size);
	ps->array[pox] = x;
}

☁️顺序表的销毁

顺序表使用完后,可以进行释放空间的操作。

void SLdestroy(SL* ps)
{
	assert(ps);
	free(ps->array);
	ps->array = NULL;
	ps->size = ps->capacity = 0;
}

☁️顺序表的特点

  1. 内存连续:顺序表的元素在内存中是连续存储的,可以通过下标直接访问元素。
  2. 随机访问:由于元素在内存中的物理地址是连续的,可以通过下标快速定位和访问元素。
  3. 插入和删除操作效率低:在顺序表中插入或删除元素时,需要移动其他元素的位置,导致操作效率较低。

☁️顺序表的劣势

  1. 中间/头部的插入删除,时间复杂度为O(N)
  2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

🌤️全篇总结

​ 经过上述一系列的代码和文字讲解,我们了解了数据结构的基本概念,而顺序表作为一种数据结构,它的特性和其独特的特点也是非常鲜明。

☁️ 好了,由于篇幅有限,本章是只介绍了比较简单的一种数据结构——顺序表,后序还会有更多不同的数据结构会分享给大家。
看到这里希望给博主留个:👍点赞🌟收藏⭐️关注!
有问题可以评论或者私信呢秒回哦。
【数据结构】 顺序表详解!(源码+解析),数据结构探索,数据结构,c语言,开发语言文章来源地址https://www.toymoban.com/news/detail-741820.html

到了这里,关于【数据结构】 顺序表详解!(源码+解析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 探索顺序表:数据结构中的秩序之美(c语言实现常见功能接口)

    在我们的数据结构探索中,我们已经探讨时间复杂度、空间复杂度。大家可以移步到我的上篇文章: 打开数据结构大门:深入理解时间与空间复杂度 今天,我们将深入研究另一个重要的主题——顺序表 全部的源代码大家可以去我github主页进行浏览:Nerosts/just-a-try: 学习c语言

    2024年02月03日
    浏览(55)
  • 深入解析顺序表:揭开数据结构的奥秘,掌握顺序表的精髓

    💓 博客主页:江池俊的博客 ⏩ 收录专栏:数据结构探索 👉专栏推荐:✅C语言初阶之路 ✅C语言进阶之路 💻代码仓库:江池俊的代码仓库 🔥编译环境: Visual Studio 2022 🎉欢迎大家点赞👍评论📝收藏⭐ 【维基百科】 线性表 (英语:Linear List)是由n(n≥0)个数据元素(

    2024年02月09日
    浏览(50)
  • 【数据结构】顺序表:与时俱进的结构解析与创新应用

      欢迎来到白刘的领域     Miracle_86.-CSDN博客           系列专栏     数据结构与算法 先赞后看,已成习惯    创作不易,多多支持! 目录 一、数据结构的概念 二、顺序表(Sequence List) 2.1 线性表的概念以及结构 2.2 顺序表分类 2.2.1 顺序表和数组的区别 2.2.2 顺序表的分类

    2024年04月23日
    浏览(29)
  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

    顺序表 ,全名 顺序存储结构 ,是线性表的一种。通过《什么是线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对数据的物理存储结构也有要求。 顺序表存储数据时,会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(41)
  • 数据结构:顺序表详解

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

    2024年02月14日
    浏览(35)
  • 【数据结构】顺序表详解

    当我们写完通讯录后,顺序表肯定难不倒你,跟着小张一起来学习顺序表吧! 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就

    2024年02月10日
    浏览(47)
  • 【数据结构】——顺序表详解

    大家好!当我们学习了动态内存管理后,就可以写一个管理数据的顺序表了!!! 顺序表的理解: 线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。 顺序表是在计算机内存

    2024年02月08日
    浏览(49)
  • 数据结构(一):顺序表详解

    在正式介绍顺序表之前,我们有必要先了解一个名词:线性表。 线性表: 线性表是,具有n个相同特性的数据元素的有限序列。常见的线性表:顺序表、链表、栈、队列、数组、字符串... 线性表在逻辑上是线性结构,但在物理结构上并不一定是连续的。 1. 顺序表概念 顺序表

    2024年02月13日
    浏览(39)
  • 数据结构之顺序表详解

    hello,大家好,今天的内容是关于顺序表的,其实之前也发过文章,但是那个时候水平还是差了一点,有些地方不是很详细,这次会把每个点都讲清楚,也当给自己在复习一遍。 顺序表在本质上就是数组,顺序表是连续的,我们的数组在内存上也是连续存储的,所以我们可以

    2024年02月06日
    浏览(40)
  • 数据结构入门 — 顺序表详解

    数据结构入门 — 顺序表详解 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 顺序表是连续存储的 顺序表是一种线性表的数据结构,它的数据元素按照一定次序依次存储在计算机存储器中,使

    2024年02月11日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包