【从零开始拿捏数据结构】顺序表是什么？它有什么样的特性？结构到底是什么样的？-Toy模板网

这篇具有很好参考价值的文章主要介绍了【从零开始拿捏数据结构】顺序表是什么？它有什么样的特性？结构到底是什么样的？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【从零开始拿捏数据结构】顺序表是什么？它有什么样的特性？结构到底是什么样的？,数据结构探索,数据结构

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

📑前言

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

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

🌤️数据结构的重要性

【从零开始拿捏数据结构】顺序表是什么？它有什么样的特性？结构到底是什么样的？,数据结构探索,数据结构

☁️什么是数据结构？

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

☁️数据结构能干嘛？

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

☁️数据结构有多重要？

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

🌤️顺序表的概念与结构

☁️顺序表的概念

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

☁️顺序表的结构

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

☁️顺序表图例

【从零开始拿捏数据结构】顺序表是什么？它有什么样的特性？结构到底是什么样的？,数据结构探索,数据结构

🌤️动态顺序表的实现

☁️顺序表所需要的接口

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;
}

☁️顺序表的特点

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

☁️顺序表的劣势

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

🌤️全篇总结

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

☁️ 好了，由于篇幅有限,本章是只介绍了比较简单的一种数据结构——顺序表，后序还会有更多不同的数据结构会分享给大家。
看到这里希望给博主留个：👍点赞🌟收藏⭐️关注！
有问题可以评论或者私信呢秒回哦。
【从零开始拿捏数据结构】顺序表是什么？它有什么样的特性？结构到底是什么样的？,数据结构探索,数据结构文章来源地址https://www.toymoban.com/news/detail-715776.html