在哪做网站建设,百度售后服务电话,做家装施工的网站,东营雪亮工程app下载二维码前言
数据结构入门 — 顺序表详解 博客主页链接#xff1a;https://blog.csdn.net/m0_74014525 关注博主#xff0c;后期持续更新系列文章 文章末尾有源码 *****感谢观看#xff0c;希望对你有所帮助***** 文章目录 前言一、顺序表1. 顺序表是什么2. 优缺点 二、概念及结构…前言
数据结构入门 — 顺序表详解 博客主页链接https://blog.csdn.net/m0_74014525 关注博主后期持续更新系列文章 文章末尾有源码 *****感谢观看希望对你有所帮助***** 文章目录 前言一、顺序表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-aNULL){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); //要乘以2if (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-aNULL;pc-capacity 0;pc-size0;
} 四、所有文件代码
1. Gitee链接
***查看所有代码*** 点击右边蓝色文字 DuckBro Gitee 代码仓库 总结
顺序表是一种线性表它的重点是 物理结构顺序表的数据元素在内存中是连续存放的即使用一段连续的存储空间来存储线性表的元素。 逻辑结构顺序表是一种线性表它的元素在逻辑上是依次排列的。 数据操作顺序表支持基本的数据操作包括插入、删除、查找等操作。其中插入和删除操作需要移动大量元素时间复杂度较高而查找操作可以通过使用二分查找等算法来提高效率。 容量管理顺序表的容量是由数组的长度来决定的。如果数组长度不够顺序表需要进行扩容操作如果数组长度过长会浪费内存空间。 性能特点由于顺序表的数据元素在内存中是连续存放的所以顺序表具有快速的随机访问能力但插入、删除操作较为耗时。因此适合于需要随机访问元素但不频繁进行插入、删除操作的场景。顺序表 如这篇博客对大家有帮助的话希望 三连 支持一下 如果有错误感谢大佬的斧正 如有 其他见解发到评论区一起学习 一起进步。
