前言
数据结构入门 — 顺序表详解
关注博主,后期持续更新系列文章
文章末尾有源码*****感谢观看,希望对你有所帮助*****
文章目录
- 前言
- 一、顺序表
- 1. 顺序表是什么
- 2. 优缺点
- 二、概念及结构
- 1. 静态顺序表
- 2. 动态顺序表
- 三、顺序表接口实现(代码演示)
- 1. 动态存储结构
- 2. 顺序表打印
- 3. 顺序表初始化
- 4. 检查空间大小
- 5. 增删查改接口
- 6. 顺序表销毁
- 四、所有文件代码
- 1. Gitee链接
- 总结
一、顺序表
1. 顺序表是什么
顺序表是连续存储的
顺序表是一种线性表的数据结构,它的数据元素按照一定次序依次存储在计算机存储器中,使用连续的存储空间来存储。顺序表中每个数据元素的位置都有一个序号,这个序号也称为元素在顺序表中的下标。顺序表的特点是:元素的逻辑顺序与物理顺序相同,支持随机访问,插入和删除元素的时间复杂度为O(n),查找元素的时间复杂度为O(1)。
2. 优缺点
优点
优点是访问速度快,因为它的元素在内存中是连续存储的,可以直接通过下标访问,而且不需要额外的空间来存储指向下一个节点的指针。缺点
缺点是插入和删除元素的时间复杂度为O(n),因为需要移动其他元素的位置,而且不利于动态扩展容量。
二、概念及结构
元素的类型、元素的个数、数组的大小和数组的指针
顺序表的实现需要预留一段连续的存储空间来存储所有的元素,目前常见的实现方式是使用数组来实现顺序表。数组的地址是连续的,因此可以通过数组下标进行快速访问元素。为了实现顺序表,需要定义一个数据结构,包含元素的类型、元素的个数、数组的大小和数组的指针等信息。
1. 静态顺序表
静态顺序表是一种使用连续存储空间实现的线性表结构,其特点是在创建表时就需要预先分配好固定长度的存储空间,表长也就固定了下来,不能动态扩展或缩小。
在静态顺序表中,数据元素按照顺序依次存放,每个元素都占用相同的存储空间,而且元素在内存中的地址也是连续的。
2. 动态顺序表
动态顺序表是一种线性表的实现方式,它在静态顺序表的基础上,将存储空间由固定长度改为动态分配。
当动态顺序表中存放的元素个数达到当前存储空间的上限时,可以重新申请更大的空间来存放更多的元素,因此动态顺序表的长度是可变的。动态顺序表的实现通常采用数组形式,通过realloc函数来动态分配空间。
三、顺序表接口实现(代码演示)
1. 动态存储结构
即定义顺序表的结构。由动态开辟的数组、有效数据个数和容量空间的大小组成
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a; // 指向动态开辟的数组
int size; // 有效数据个数
int capacity; // 容量空间的大小
}SL;
2. 顺序表打印
使用循环,将顺序表遍历一遍,进行打印
//打印顺序表
void SLPrint(SL* pc)
{
assert(pc);
int i = 0;
for (i = 0; i < pc->size; i++)
{
printf("%d ", pc->a[i]);
}
printf("\n");
}
3. 顺序表初始化
在顺便表初始化时,先用malloc
开辟4个空间,如果开启失败报错并返回
//初始化顺序表
void SLInit(SL *pc)
{
assert(pc);
//开启内存
pc->a=(SLDataType*)malloc(sizeof(SLDataType) * 4);
//检查是否开辟成功
if (pc->a==NULL)
{
perror("SLInit");
//return;
exit(-1);
}
pc->capacity = 4;
pc->size = 0;
}
4. 检查空间大小
检查空间,当顺序表内的数据等于初始化开辟的空间时,再开辟4个空间(用realloc
开辟乘2的空间)
//检查内存容量
void SLCheckCapacity(SL* pc)
{
assert(pc);
if (pc->size == pc->capacity)
{
SLDataType*tem = (SLDataType*)realloc(pc->a, sizeof(SLDataType)*2*pc->capacity); //要乘以2
if (tem == NULL)
{
perror("SLCheckCapacity");
exit(-1);
}
pc->a = tem;
pc->capacity *= 2;
}
}
5. 增删查改接口
以增删查改顺序依次编排
头插:
头插,即在顺序表头部进行插入数值,在SLCheckCapacity
检查空间是否充足后,进行插入数值
//头插
void SLPushFront(SL* pc,SLDataType x)
{
assert(pc);
SLCheckCapacity(pc);
int end = pc->size - 1;
while (end >=0)
{
pc->a[end + 1] = pc->a[end];
--end;
}
pc->a[0] = x;
pc->size++;
}
尾插:
尾插,即找到顺序表的尾,下标为pc->size的位置插入数值
//尾插
void SLPushBack(SL* pc, SLDataType x)
{
assert(pc);
SLCheckCapacity(pc);
pc->a[pc->size] = x;
pc->size++;
}
头删:
头删,将后面的数值依次向前覆盖。覆盖时要注意顺序,将在前的先覆盖,防止数组丢失,然后将顺序表的size(数据个数减一)
//头删
void SLPopFront(SL* pc)
{
assert(pc);
int start = 1;
while (start < pc->size)
{
pc->a[start] = pc->a[start + 1];
++start;
}
pc->size--;
}
尾删:
尾删,即将有效数据减一,直接将pc所指向的size减一
//尾删
void SLPopBack(SL* pc)
{
assert(pc->size > 0);
pc->size--;
}
查找:
查找方法有很多种,这里使用暴力查找,将顺序表遍历一遍,找到要找的元素并返回下标
//查找数字位置
int SLFind(SL* pc, SLDataType x)
{
int i = 0;
for (i = 0; i < pc->size; i++)
{
if (pc->a[i] == x)
{
return i;
}
}
return -1;
}
指定位置插入
这里配合查找函数使用,找到要找的数值的下标,进入下列函数,将pos之后的值依次下向后移动,在pos位置插入数值
// 在pos位置插入x
void SLInsert(SL* pc, int pos, SLDataType x)
{
assert(pc);
assert(pos >= 0 && pos <= pc->size);
SLCheckCapacity(pc);
int end = pc->size - 1;
while (end >= pos)
{
pc->a[end + 1] = pc->a[end];
--end;
}
pc->a[pos] = x;
pc->size++;
}
指定位置删除
这里配合查找函数使用,找到要找的数值的下标,进入下列函数,将pos位置后的数值依次向前覆盖
// 删除pos位置的值
void SLErase(SL* pc, int pos)
{
assert(pc);
assert(pos >= 0 && pos < pc->size);
int start = pos+ 1;
while (start < pc->size)
{
pc->a[start - 1] = pc->a[start];
++start;
}
pc->size--;
}
更改指定位置
这里配合查找函数使用,找到要找的数值的下标,进入下列函数,将pos位置的值进行修改
//更改制定位置的数字
void SLModify(SL* pc, int pos, SLDataType x)
{
assert(pc);
assert(pos >= 0 && pos < pc->size);
pc->a[pos] = x;
}
6. 顺序表销毁
顺序表进行销毁,将开辟的数值空间进行释放,并置为空(NULL)将空间和数据个数置为0 ,这样顺序表就销毁完成
//销毁释放内存
void SLDestroy(SL* pc)
{
assert(pc);
free(pc->a);
pc->a=NULL;
pc->capacity = 0;
pc->size=0;
}
四、所有文件代码
1. Gitee链接
***查看所有代码***
点击右边蓝色文字 DuckBro Gitee 代码仓库
总结
顺序表是一种线性表,它的重点是:
- 物理结构:顺序表的数据元素在内存中是连续存放的,即使用一段连续的存储空间来存储线性表的元素。
- 逻辑结构:顺序表是一种线性表,它的元素在逻辑上是依次排列的。
- 数据操作:顺序表支持基本的数据操作,包括插入、删除、查找等操作。其中,插入和删除操作需要移动大量元素,时间复杂度较高,而查找操作可以通过使用二分查找等算法来提高效率。
- 容量管理:顺序表的容量是由数组的长度来决定的。如果数组长度不够,顺序表需要进行扩容操作,如果数组长度过长,会浪费内存空间。
- 性能特点:由于顺序表的数据元素在内存中是连续存放的,所以顺序表具有快速的随机访问能力,但插入、删除操作较为耗时。因此,适合于需要随机访问元素,但不频繁进行插入、删除操作的场景。顺序表
如这篇博客对大家有帮助的话,希望 三连 支持一下 !!! 如果有错误感谢大佬的斧正 如有 其他见解发到评论区,一起学习 一起进步。