数据结构之顺序表

🕗 发布于 2024-04-21 10:23 数据结构

片头

嗨! 小伙伴们,大家好! 哈哈,今天我们来一起学习顺序表,本篇超级详细,一定可以教会你!

一、线性表

1.1是线性表呢？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。常见的线性表：顺序表、链表、栈、队列、字符串......

线性表在逻辑上是线性结构,就像一串珠子穿在一根绳上。但是线性表在物理结构上不一定是连续的,线性表以数组的形式存储时和以链式结构存储时在物理内存上的布局是不一样的。

线性表以数组的形式存储时在内存中是连续的，而线性表以链式结构存储时在内存中不一定连续。

二、顺序表

2.1 顺序表的定义

线性表的顺序存储又称为顺序表，顺序表是用一段地址连续的存储单元来依次存储数据元素的线性结构，从而使得逻辑上相邻的两个元素在物理位置上也相邻，也就是说我们可以通过下标来依次访问结构中的内容。平时我们使用的数组也是顺序表的一种实现方式。

2.2 顺序表的种类

顺序表一般可以分为：（1）静态顺序表：使用定长数组存储元素

我们先来试一下创建一个静态顺序表

#define N 10
typedef int ElemType;

typedef struct SeqList {
ElemType arr[N];//定长数组
int size;//有效数据个数
}SL;

我们可以看到,静态顺序表中定义了一个定长数组,也就是说数组一旦开辟就无法再更改大小了。

所以静态顺序表只适用于已知需要存储多少数据的场景，如果定长数组过大，就会浪费空间，如果过小，又不够用。所以一般情况下，我们都使用动态顺序表，可以根据需要来动态分配空间，接下来我们认识一下动态顺序表。

（2）动态顺序表：使用动态开辟的数组存储

typedef int ElemType;

typedef struct SeqList {
ElemType* arr;//指向动态数组开辟的空间
int capacity;//开辟空间的容量大小
int size;    //有效数据个数
}SL;

动态顺序表中存储数据的空间需要我们进行动态内存开辟，以上便是动态顺序表的结构。

2.3 顺序表的增删改查接口实现

接下来我们一步一步来实现顺序表的增删改查接口，当然此处使用的是动态顺序表。

本次演示的是vs2019,我们先创建一个新项目,并新建头文件"SeqList.h"和两个源文件"SeqList.c" 和"test.c",它们的作用分别是:

SeqList.h	顺序表的定义,头文件的引用和接口函数的声明
SeqList.c	具体实现顺序表里定义的接口/方法
test.c	测试各个函数

首先我们展示"SeqList.h"的完整代码,不要忘了在两个源文件中引用"SeqList.h"

#pragma once//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//静态顺序表
//#define N 10
//typedef struct SeqList {
//ElemType arr[N];//定长数组
//int size;//有效数据个数
//}SL;

//动态顺序表
typedef int ElemType;//如果要修改存储的数据类型可直接在此修改
typedef struct SeqList {
ElemType* arr;//指向动态数组开辟的空间
int capacity;//开辟空间的容量大小
int size;    //有效数据个数
}SL;

//顺序表的增删改查接口
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL* ps);

//检查顺序表的容量,如果满了,进行扩容
void SLCheckCapacity(SL* ps);

//顺序表的尾插
void SLPushBack(SL* ps, ElemType x);
//顺序表的头插
void SLPushFront(SL* ps, ElemType x);
//顺序表的尾删
void SLPopBack(SL* ps);
//顺序表的头删
void SLPopFront(SL* ps);

//顺序表指定位置插入数据
void SLInsert(SL* ps, int pos, ElemType x);
//顺序表删除指定位置的数据
void SLErase(SL* ps,int pos);
//顺序表中查找目标值
int SLFind(SL* ps, ElemType x);

接下来,我们逐一的实现各个接口函数,每一步都详细讲解,必须让你学会

(1)顺序表初始化

//顺序表初始化
void SLInit(SL* ps) {
assert(ps); //断言,防止传入空指针
ps->arr = NULL; //初始化动态数组为空
ps->capacity = 0;//初始化动态数组的空间容量为0
ps->size = 0; //初始化有效元素个数为0
}

(2)检查顺序表的容量,如果为空或者满了,进行增容

//扩容
void SLCheckCapacity(SL* ps) {
assert(ps);//断言,防止传入空指针
if (ps->capacity == ps->size) //如果容量为空或者有效数据个数等于空间容量大小则已满,扩容
{
//定义一个新变量来表示顺序表的空间容量,如果当前容量为空,则给顺序表的容量开辟4个空间,如果当前容量非空,则开辟原来空间的2倍
//创建一个临时变量来存储新空间的地址,防止开辟失败
int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
if (temp == NULL) //防止空间开辟失败
{
perror("realloc fail!\n");
exit(1);
}
ps->arr = temp;//将临时指针变量中存放的新空间地址赋给arr
ps->capacity = newCapacity;//空间容量更新
}
}

(3)顺序表的尾插

//顺序表的尾插
void SLPushBack(SL* ps, ElemType x) {
assert(ps);//断言,防止传入空指针
//空间不足,扩容
SLCheckCapacity(ps);//如果容量为空或者已满,则扩容
//空间足够,填充数据
ps->arr[ps->size] = x;//在数组arr中的下标为size的地方插入数据x
ps->size++;  //size指向下一个位置
}

测试一下:


int main() {
SL sl;//定义一个顺序表sl
SLInit(&sl);//将顺序表sl初始化
SLPushBack(&sl, 1); //将"1"尾插到顺序表中
SLPushBack(&sl, 2); //将"2"尾插到顺序表中
SLPushBack(&sl, 3); //将"3"尾插到顺序表中
SLPushBack(&sl, 4); //将"4"尾插到顺序表中
SLPrint(&sl);//打印顺序表

return 0;
}

运行结果为:

1 2 3 4

(4)顺序表的头插

在顺序表的第一个位置(下标为0处)插入新元素"5"

//顺序表的头插
void SLPushFront(SL* ps, ElemType x) {
assert(ps);//断言,防止传入空指针
SLCheckCapacity(ps);//如果容量为空或者已满则扩容
for (int i = ps->size-1; i >= 0; i--) //从后到前,通过循环将所有数据向后移动
{
ps->arr[i + 1] = ps->arr[i];
//最后一次循环:  ps->arr[1] = ps->arr[0];
}
ps->arr[0] = x;//将头部插入新数据
ps->size++;   //size指向下一个位置
}

测试一下:

int main() {
SL sl;//定义一个顺序表sl
SLInit(&sl);//将顺序表sl初始化
SLPushBack(&sl, 1); //将"1"尾插到顺序表中
SLPushBack(&sl, 2); //将"2"尾插到顺序表中
SLPushBack(&sl, 3); //将"3"尾插到顺序表中
SLPushBack(&sl, 4); //将"4"尾插到顺序表中
SLPrint(&sl);//打印顺序表

SLPushFront(&sl, 5);//将"5"头插到顺序表中
SLPrint(&sl);

return 0;
}

运行结果为:

1 2 3 4

5 1 2 3 4

(5) 顺序表尾删

//顺序表尾删
void SLPopBack(SL* ps) {
assert(ps);//断言,防止传入空指针
assert(ps->size);//断言,防止数组中元素个数已经为空,却还在执行删除
ps->size--; //通过更新size把尾部数据覆盖即可
}

测试一下:

int main() {
SL sl;//定义一个顺序表sl
SLInit(&sl);//将顺序表sl初始化
SLPushBack(&sl, 1); //将"1"尾插到顺序表中
SLPushBack(&sl, 2); //将"2"尾插到顺序表中
SLPushBack(&sl, 3); //将"3"尾插到顺序表中
SLPushBack(&sl, 4); //将"4"尾插到顺序表中
SLPrint(&sl);//打印顺序表

SLPopBack(&sl);//将最后一个元素"4"删除
SLPrint(&sl);//打印顺序表

return 0;
}

运行结果为:

1 2 3 4

1 2 3

(6) 顺序表头删

//顺序表头删
void SLPopFront(SL* ps) {
assert(ps);//断言,防止传入空指针
assert(ps->size);//断言,防止有效数据为空却还在执行删除操作

for (int i = 1; i < ps->size; i++)//从前往后,通过循环将所有数据向前移动,把头数据覆盖
{
ps->arr[i - 1] = ps->arr[i];
//最后一次: ps->arr[size-2] = ps->arr[size-1];
}
ps->size--;//size更新
}

测试一下:

int main() {
SL sl;//定义一个顺序表sl
SLInit(&sl);//将顺序表sl初始化
SLPushBack(&sl, 1); //将"1"尾插到顺序表中
SLPushBack(&sl, 2); //将"2"尾插到顺序表中
SLPushBack(&sl, 3); //将"3"尾插到顺序表中
SLPushBack(&sl, 4); //将"4"尾插到顺序表中
SLPrint(&sl);//打印顺序表

SLPopFront(&sl);//将第一个元素"1"删除
SLPrint(&sl);//打印顺序表
return 0;
}

运行结果:

1 2 3 4

2 3 4

(7) 顺序表中查找目标值

//顺序表中查找目标值
int SLFind(SL* ps, ElemType x) {
assert(ps);//断言,防止传入空指针
for (int i = 0; i < ps->size; i++) //遍历顺序表
{
if (ps->arr[i] == x) {
return i;//找到了,返回下标
}
}
return -1;//没有找到,返回-1
}

测试一下:

int main() {
SL sl;//定义一个顺序表sl
SLInit(&sl);//将顺序表sl初始化
SLPushBack(&sl, 1); //将"1"尾插到顺序表中
SLPushBack(&sl, 2); //将"2"尾插到顺序表中
SLPushBack(&sl, 3); //将"3"尾插到顺序表中
SLPushBack(&sl, 4); //将"4"尾插到顺序表中
SLPrint(&sl);//打印顺序表

int ret = SLFind(&sl, 2);//在顺序表中寻找"2"
if (ret == -1) {
printf("对不起,没有找到!\n");
}
else {
printf("找到了,下标为: %d\n", ret);
}
return 0;
}

运行结果:

1 2 3 4

找到了,下标为: 1

(8)顺序表指定位置插入数据

//在指定位置插入数据
void SLInsert(SL* ps, int pos, ElemType x) {
assert(ps);//断言,防止传入空指针
assert(pos >= 0 && pos <= ps->size);//断言,防止pos超出有效数据范围
SLCheckCapacity(ps);//如果空间已满则扩容

for (int i = ps->size-1; i >= pos; i--) //把pos之后的数据向后移动
{
ps->arr[i + 1] = ps->arr[i];
//最后一次: ps->arr[pos+1] = ps->arr[pos];
}
ps->arr[pos] = x;//在pos处插入数据
ps->size++; //size更新
}

测试一下:

int main() {
SL sl;//定义一个顺序表sl
SLInit(&sl);//将顺序表sl初始化
SLPushBack(&sl, 1); //将"1"尾插到顺序表中
SLPushBack(&sl, 2); //将"2"尾插到顺序表中
SLPushBack(&sl, 3); //将"3"尾插到顺序表中
SLPushBack(&sl, 4); //将"4"尾插到顺序表中
SLPrint(&sl);//打印顺序表

SLInsert(&sl, 2, 100);//在下标为2的位置插入"100"
SLPrint(&sl);//打印顺序表
return 0;
}

运行结果为:

1 2 3 4

1 2 100 3 4

(9)顺序表删除指定位置的数据

//删除指定位置的数据
void SLErase(SL* ps, int pos) {
assert(ps);//断言,防止传入空指针
assert(pos >= 0 && pos < ps->size);//断言,防止pos超出有效数据范围

for (int i = pos; i < ps->size-1; i++)//将pos之后的数据向前移动,覆盖pos处的数据
{
ps->arr[i] = ps->arr[i+1];
//最后一次: ps->arr[size-2] = ps->arr[size-1];
}
ps->size--;//size更新
}

测试一下:


int main() {
SL sl;//定义一个顺序表sl
SLInit(&sl);//将顺序表sl初始化
SLPushBack(&sl, 1); //将"1"尾插到顺序表中
SLPushBack(&sl, 2); //将"2"尾插到顺序表中
SLPushBack(&sl, 3); //将"3"尾插到顺序表中
SLPushBack(&sl, 4); //将"4"尾插到顺序表中
SLPrint(&sl);//打印顺序表

SLErase(&sl, 1);//删除下标为1的元素
SLPrint(&sl);//打印顺序表
return 0;
}

运行结果为:

1 2 3 4

1 3 4

(10) 顺序表的销毁

//顺序表的销毁
void SLDestroy(SL* ps) {
assert(ps);//断言,防止传入空指针
if (ps->arr) {//如果动态数组arr非空,就把arr释放
free(ps->arr);
ps->arr = NULL;//置空,避免野指针
}
ps->capacity = 0;//空间容量为0
ps->size = 0;//有效数据为0
}

(11)打印顺序表

//打印顺序表
void SLPrint(SL* ps) {
assert(ps);//断言,防止传入空指针
for (int i = 0; i < ps->size; i++) //遍历顺序表
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}

片尾

我们今天学习了什么是顺序表以及如何实现顺序表,希望看完这篇文章能对友友们有所帮助 ! ! !

求点赞收藏加关注 ! ! !

谢谢大家 ! ! !

原文地址：https://blog.csdn.net/qq_74336191/article/details/138007058

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：移植speexdsp到OpenHarmony标准系统④
下一篇：【C语言】指针详解（五）

【脑机接口】脑机接口性能的电压波形的尖峰分类和阈值比较
目标。对于皮质内脑机接口(bmi)，动作电位电压波形通常被分类以分离出单个神经元。如果这些神经元包含独立调节这一过程可以提高BMI的表现。然而，sorting行动电位(“尖峰”)需要高采样率，并且计算
阅读更多2024-09-20
与谷歌旗下自动驾驶公司扩大合作后，Uber股票值得买入吗？
在第二季度强劲的业绩和战略合作伙伴关系的推动下，Uber的股价最近出现了反弹，这表明该公司的股价仍有上涨空间，尤其是Uber在自动驾驶领域还在继续创新，以及还在持续的扩大其广告业务，目前该业务已经可以
阅读更多2024-09-20
IntelliJ IDEA 创建 Java 项目指南
通过以上步骤，我们成功地在 IntelliJ IDEA 中创建了一个新的 Java 项目，并编写和运行了第一个 Java 程序。如果想为你的代码添加测试，可以右键点击类名，选择 `Create New
阅读更多2024-09-20
jenkins声明式流水线语法详解
最基本的语法包含。
阅读更多2024-09-20
【原创】java+springboot+mysql高校社团网系统设计与实现
使用java+springboot+mysql开发的高校社团网，系统包含管理员、学生角色，功能如下：管理员：登录系统；首页；用户管理；社团分类管理；社团信息管理（社团审核）；系统留言；系统公告；友链管
阅读更多2024-09-20
Unity 设计模式之结构型模式 -【适配器模式】【桥接模式】【组合模式】
设计模式是指在软件开发中为解决常见问题而总结出的一套可复用的解决方案。这些模式是经过长期实践证明有效的编程经验总结，并可以在不同的项目中复用。设计模式并不是代码片段，而是对常见问题的抽象解决方案，它提
阅读更多2024-09-20
萌啦数据行业数据在哪看，萌啦ozon行业数据怎么看
在跨境电商的浪潮中，数据已成为商家决策的重要基石。萌啦Ozon数据行业分析板块，作为连接商家与市场动态的桥梁，为商家提供了丰富的行业洞察与精准的市场指导。本文将带您深入探索萌啦Ozon数据行业分析板块
阅读更多2024-09-20
班主任群发成绩教程，宝藏工具来减负
家长们呀，都特别关心自己孩子的成绩，考试一结束就像潮水般涌来询问成绩。老师也是人啊，忙完这些工作，都没有自己的时间了。各种表格要填写，学生的信息表、考勤表、成绩统计表等等，每一项都容不得半点马虎。而且
阅读更多2024-09-20
微服务架构中的负载均衡与服务注册中心(Nacos)
通过合理使用负载均衡和注册中心，我们可以构建一个更加健壮、可扩展的微服务架构。这不仅提高了系统的可用性，还大大增强了运维的灵活性。在实际业务中，要根据具体的场景选择合适的策略，并持续优化以应对不断变化
阅读更多2024-09-20
基于Java的题库管理系统设计与实现（springboot vue）
摘要现今教育教学领域对于高效、便捷的题库管理系统的需求日益增长。本文以Java为基础，采用SpringBoot和Vue构建前后端分离的技术架构，结合MySQL数据库，设计与实现了一套题库管理系统。该系
阅读更多2024-09-20

数据结构之顺序表

片头

一、线性表

1.1是线性表呢？

二、顺序表

2.1 顺序表的定义

2.2 顺序表的种类

2.3 顺序表的增删改查接口实现

(1)顺序表初始化

(2)检查顺序表的容量,如果为空或者满了,进行增容

(3)顺序表的尾插

(4)顺序表的头插

(5) 顺序表尾删

(6) 顺序表头删

(7) 顺序表中查找目标值

(8)顺序表指定位置插入数据

(9)顺序表删除指定位置的数据

(10) 顺序表的销毁

(11)打印顺序表

片尾

相关文章