文章目录
📑前言
什么是数据结构？我们为什么要学数据结构？数据结构中的顺序表长什么样子？它是怎么运用？
本期我们将对这些一一讲解,彻底明白数据结构的重要性，以及顺序表是一种什么的数据结构。
🌤️数据结构的重要性
☁️什么是数据结构？
数据结构指的是计算机中组织和存储数据的方式。它涉及到数据的组织、管理和操作，以便能够高效地访问和处理数据。
☁️数据结构能干嘛？
数据结构可以用来解决各种计算问题，它提供了不同的数据类型和操作，使得我们可以有效地存储和操作数据。通过选择合适的数据结构，我们可以提高算法的效率，减少时间和空间的消耗。
☁️数据结构有多重要？
它是算法设计和优化的基础，对于解决实际问题和提高计算机程序的性能至关重要。良好的数据结构设计可以提高程序的可读性、可维护性和可扩展性，同时也能够减少资源的消耗和提高程序的执行效率。
🌤️顺序表的概念与结构
☁️顺序表的概念
顺序表是一种线性表的存储结构，它将元素顺序地存储在一块连续的内存空间中。顺序表中的元素在内存中的物理地址是连续的，通过元素在内存中的相对位置来表示元素之间的逻辑关系。
☁️顺序表的结构
顺序表由两部分组成：数据存储区和长度信息。数据存储区是一块连续的内存空间，用来存储顺序表中的元素。长度信息记录了顺序表中元素的个数。
☁️顺序表图例
🌤️动态顺序表的实现
☁️顺序表所需要的接口
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个数据空间。
🌤️全篇总结
经过上述一系列的代码和文字讲解，我们了解了数据结构的基本概念，而顺序表作为一种数据结构，它的特性和其独特的特点也是非常鲜明。
☁️ 好了，由于篇幅有限,本章是只介绍了比较简单的一种数据结构——顺序表，后序还会有更多不同的数据结构会分享给大家。
看到这里了还不给博主留个：
👍 点赞🌟收藏 ⭐️ 关注！
💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
