数据结构线性表——顺序表

news/2025/2/13 17:39:06/

前言：小伙伴们好久不见，从这篇文章开始，我们就要正式进入数据结构的学习啦。

学习的难度也将逐步上升，希望小伙伴们能够和博主一起坚持，一起加油！！！

目录

一.什么是线性表 

二.什么是顺序表

三.顺序表实现

1.顺序表的定义

2.顺序表初始化

3.顺序表的销毁

四.顺序表的操作

1.顺序表的扩容

2.顺序表的尾插

3.顺序表的打印

 4.顺序表的尾删

 4.顺序表的头插

5.顺序表的头删

6.顺序表的任意插

7.顺序表的任意删

8.顺序表的查找

9.顺序表的修改

五.代码展示

1.Sqlist.h

2.Sqlist.c

3.test.c

六.总结

一.什么是线性表 

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

从逻辑上说，线性表是一个连续的直线。但是从实际物理结构上来说，线性表不一定是连续的，那么根据线性表的连续性，将其分为连续的顺序表和不连续的链表。

今天我们就先来学习连续的线性表——顺序表。

如果小伙伴们已经跟博主一起学习过了通讯录，那么这一块就是小菜一碟哦！

二.什么是顺序表

顺序表是通过使用一段物理地址连续的存储单元依次存储数据元素的线性结构。

那么我们如何理解顺序二字呢？？？

实际上，这里的顺序并不是说我们存放的数据要按升序或者降序的方式存储，毕竟我们存的数据不一定都是数字。

顺序的含义其实是我们在存数据时要一个一个紧挨着的存储，不能间隔存储。

说到这里，小伙伴们应该都能联想到数组，没错，实际上顺序表就是采用数组来存储数据的。

在了解过顺序表的基本结构之后，我们就开始正式的来讲解顺序表该如何实现。

三.顺序表实现

1.顺序表的定义

想定义一个顺序表，就需要先来想想顺序表需要哪些结构元素，首先是一个数组，数组的大小，还要有一个数据来统计我们当前的数据个数。

我们学习过动态内存管理，所以这里我们直接定义一个动态顺序表：

typedef int SLDataType;
//动态顺序表
typedef struct SqList
{SLDataType* data;int size;//数据个数int capacity;//表长
}SL;

定义动态数组，我们就只需要一个头指针。

要注意的是，我们用SLDataType来定义顺序表所存储的数据的类型，方便以后得维护和修改。

2.顺序表初始化

那么在定义好顺序表的基本结构之后，我们要先对其进行初始化，通过封装一个函数：

//初始化顺序表
void SqListInit(SL* ps)
{ps->data = NULL;ps->size = 0;ps->capacity = 0;
}

将头指针置空，并将size和capacity置零。

我们前边学习过，动态开辟的空间使用后要及时释放，所以我们需要封装一个函数来销毁顺序表。

3.顺序表的销毁

//销毁
void SqListDestroy(SL* ps)
{free(ps->data);ps->data = NULL;ps->capacity = ps->size = 0;
}

通过这样三个步骤，我们才算是真正意义上的造出了一个顺序表。

紧接着，我们来讲解顺序表的各种操作。

四.顺序表的操作

对于我们的数据结构这块内容的基本操作，自然是增、删、查、改。

那么我们要特别注意的是对于顺序表的头、尾两个位置的操作。

1.顺序表的扩容

在对顺序表进行各种操作之前，最重要的一点就是要判断这个表当前是否已经占满，如果占满就必须得扩容。

而且小伙伴们似乎发现，我们刚才初始化的时候把顺序表的长度初始化为0，其实就是为了将初始化长度和扩容相结合。

//扩容
void SqlistDilatation(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType tmp = (SLDataType*)realloc(ps->data, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("SqListPushBack->realloc");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}
}

首先进行一个判断，如果当前的数据个数等于顺序表的大小，那么证明已经满了，需要扩容，这时候定义一个新的顺序表长度，注意看这一行：

int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

这里我们用一个三目运算符，它的含义是什么呢？？？

当我们顺序表的长度为0时，也就是刚初始化完还没有大小，那么我们就将它扩容为4个空间，以后没次扩容都是原大小的二倍。 

有了扩容之后，我们就可以安心的进行各种操作了。

2.顺序表的尾插

尾插，顾名思义就是在线性表的数据末尾插入一个数据。

注意是数据的末尾，而不是整个表的末尾。

那么我们该怎么尾插呢？？？

其实很简单，毕竟顺序表本质上就是一个数组，而且我们也有数据的个数size这个变量，初始时size是0，每填入一个数据，size都会指向下一个空白空间，而这个空间，不就是数据的末尾吗？

所以尾插的实现如下：

//尾插
void SqListPushBack(SL* ps, SLDataType x)
{//判断扩容SqlistDilatation(ps);	ps->data[ps->size] = x;	ps->size++;
}

记得要先判断是否需要扩容！！！

那么我们的尾插到底能否实现我们想要的结果呢？？？

想要判断正确与否，我们还得封装一个打印顺序表函数，这样我们才能看到结果。

3.顺序表的打印

打印就很简单了，只需要通过循环来实现即可：

//打印
void SqListPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->data[i]);}
}

接下来我们就来测试尾插是否能够成功：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPrint(s);printf("\n");SqListPushBack(s, 2);SqListPrint(s);printf("\n");SqListPushBack(s, 3); SqListPrint(s);printf("\n");SqListPushBack(s, 4);SqListPrint(s);SqListDestroy(s);
}

 我们封装一个测试函数，先进行初始化，然后每尾插一次，就打印一次并换行，得到结果如下：

确实是从末尾在一个一个的插入，所以我们的尾插并没有错误。

那么既然有插入，就会有删除，接下来我们来讲解尾删。

 4.顺序表的尾删

该怎么尾删呢，既然有了size，那么只需要size--就可以找到末尾的数据，那么该怎么把它删除？

实际上，我们不可能实现真正意义上的删除，因为是数组，我们不可能把整个数组的大小减一。

所以所谓的删除，不过是把原本的数据置0或者置为其他的规定的数字。

那么你有没有想过，我们就非得将数据改变吗？？？

如果我们的size--，我们在遍历数组的时候，是不是就不会遍历到末尾的数据了，虽然这个数据还存在，但是我们下次尾插时，是不是就把它给覆盖了。所以尾删其实特别简单：

//尾删
void SqListPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;
}

唯一要注意的就是判断size是否为0，没数据还删啥呀。

通过测试：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPrint(s);printf("\n");SqListPushBack(s, 2);SqListPrint(s);printf("\n");SqListPushBack(s, 3); SqListPrint(s);printf("\n");SqListPopBack(s);SqListPrint(s);SqListDestroy(s);
}

确实实现了末尾数据的删除。 

 

那么讲完尾部的操作之后，就该轮到头部了，那么头部又该如何操作呢？

 4.顺序表的头插

那么怎么向头部插入数据呢？在数组的开头开一个空间？肯定是不可能的，那么对于我们的顺序表，只有一种操作：那就是整体数据向后挪一位，再将新数据头插进来。

既然要将数据后挪，就肯定还要先判断是否需要扩容。

具体操作如下：

//头插
void SqListPushFront(SL* ps, SLDataType x)
{//判断扩容SqlistDilatation(ps);int end = ps->size - 1;while (end >= 0){ps->data[end + 1] = ps->data[end];end--;}ps->data[0] = x;ps->size++;
}

首先要先找到末尾元素的下标end，然后循环后移，最后头插。

来看测试：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPrint(s);printf("\n");SqListPushBack(s, 2);SqListPrint(s);printf("\n");SqListPushFront(s, 4);SqListPrint(s);printf("\n");SqListPushFront(s, 5);SqListPrint(s);SqListDestroy(s);
}

结果如下：

5.顺序表的头删

头删和头插可以说是反着来的，头插是数据往后挪动，头删则是数据依次往前覆盖。

要注意的是，头删也要判断数据是否为空，没数据还删什么？

//头删
void SqListPopFront(SL* ps)
{assert(ps->size > 0);int begin = 0;while (begin < ps->size - 1){ps->data[begin] = ps->data[begin + 1];begin++;}ps->size--;
}

至于最后一个数据，我们类似于尾删，不用管它，下一次尾插或者头插自然会将其覆盖。

测试如下：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPrint(s);printf("\n");SqListPushBack(s, 2);SqListPrint(s);printf("\n");SqListPushFront(s, 4);SqListPrint(s);printf("\n");SqListPopFront(s);SqListPrint(s);printf("\n");SqListPopFront(s);SqListPrint(s);SqListDestroy(s);
}

结果如下：

那么我们前边讲的都是顺序表固定位置的操作，那么接下来我们就来讲解顺序表任意位置的操作。

6.顺序表的任意插

虽然说是任意位置的插入，但是还是要满足顺序表的条件，只能在0~size的范围内插入。

插入之前，同样需要先判断是否需要扩容。

任意位置的插入其实和头插差不多，头插是把全部的数据向后挪，而任意插只需要挪动我们要插入的位置的后边的数据：

//任意插
void SqListInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//判断扩容SqlistDilatation(ps);int end = ps->size - 1;while (end >= pos){ps->data[end + 1] = ps->data[end];end--;}ps->data[pos] = x;ps->size++;
}

测试如下：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPushBack(s, 2);SqListPushBack(s, 4);SqListPrint(s);printf("\n");SqListInsert(s, 2, 3);SqListPrint(s);SqListDestroy(s);
}

结果如下：

7.顺序表的任意删

任意删的形式则和头删差不多，需要从指定的位置开始，后边的数据依次往前覆盖。

值得注意的是，任意位置插入时，可以在size位置插入，但是任意位置删除时，size处是没有没数据可删的。 

实现如下：

//任意删
void SqListErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos;while (begin < ps->size - 1){ps->data[begin] = ps->data[begin + 1];begin++;}ps->size--;
}

测试如下：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPushBack(s, 2);SqListPushBack(s, 5);SqListPushBack(s, 3);SqListPrint(s);printf("\n");SqListErase(s, 2);SqListPrint(s);SqListDestroy(s);
}

结果如下：

8.顺序表的查找

查找有两种方式，一个是按数据查，一个是按数据的位置下标查。

但是一般情况下我们都是按照数据来查它是否存在，存在则打印其下标位置。

查找其实就是在遍历的基础上找到某个数据，还有一种特殊情况是这个数据有多个，那么我们就同时打印多个下标。

实现如下：

//查找
void SqListFind(SL* ps, SLDataType x)
{assert(ps);int count = 0;for(int i = 0; i < ps->size; i++){if (x == ps->data[i]){count = 1;printf("下标为:%d\n", i);}}if (count == 0){printf("该数据不存在");}
}

这里我们用count来做一个标志，用于判断要找的数据是否存在。

测试如下：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPushBack(s, 2);SqListPushBack(s, 5);SqListPushBack(s, 3);SqListPushBack(s, 3);SqListFind(s, 3);SqListFind(s, 4);SqListDestroy(s);
}

结果如下：

9.顺序表的修改

修改数据一般采用通过数组下标修改的方式，那么前提就是你选择的下标在0~size之内。

实现如下：

//修改
void SqListAmend(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->data[pos] = x;
}

修改就比较简单了，直接找到数组的下标位置修改就行。

测试如下：

void Test(SL* s)
{SqListInit(s);SqListPushBack(s, 1); SqListPushBack(s, 2);SqListPushBack(s, 5);SqListPushBack(s, 3);SqListPrint(s);printf("\n");SqListAmend(s, 2, 3);SqListAmend(s, 3, 4);SqListPrint(s);SqListDestroy(s);
}

结果如下：

五.代码展示

1.Sqlist.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;//动态顺序表
typedef struct SqList
{SLDataType* data;int size;int capacity;
}SL;//接口函数
//初始化
void SqListInit(SL* ps);
//销毁
void SqListDestroy(SL* ps);
//打印
void SqListPrint(SL* ps);
//扩容
void SqlistDilatation(SL* ps);
//尾插
void SqListPushBack(SL* ps, SLDataType x);
//尾删
void SqListPopBack(SL* ps);
//头插
void SqListPushFront(SL* ps, SLDataType x);
//头删
void SqListPopFront(SL* ps);
//任意插
void SqListInsert(SL* ps, int pos, SLDataType x);
//任意删
void SqListErase(SL* ps, int pos);
//查找
void SqListFind(SL* ps, SLDataType x);
//修改
void SqListAmend(SL* ps, int pos, SLDataType x);

2.Sqlist.c

#include "Sqlist.h"
//初始化
void SqListInit(SL* ps)
{assert(ps);ps->data = NULL;ps->size = 0;ps->capacity = 0;
}
//扩容
void SqlistDilatation(SL* ps)
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->data, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("SqListPushBack->realloc");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}
}
//销毁
void SqListDestroy(SL* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->capacity = ps->size = 0;
}
//打印
void SqListPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->data[i]);}
}
//尾插
void SqListPushBack(SL* ps, SLDataType x)
{assert(ps);//判断扩容SqlistDilatation(ps);	ps->data[ps->size] = x;	ps->size++;
}
//尾删
void SqListPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->size--;
}
//头插
void SqListPushFront(SL* ps, SLDataType x)
{assert(ps);//判断扩容SqlistDilatation(ps);int end = ps->size - 1;while (end >= 0){ps->data[end + 1] = ps->data[end];end--;}ps->data[0] = x;ps->size++;
}
//头删
void SqListPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 0;while (begin < ps->size - 1){ps->data[begin] = ps->data[begin + 1];begin++;}ps->size--;
}
//任意插
void SqListInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//判断扩容SqlistDilatation(ps);int end = ps->size - 1;while (end >= pos){ps->data[end + 1] = ps->data[end];end--;}ps->data[pos] = x;ps->size++;
}
//任意删
void SqListErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos;while (begin < ps->size - 1){ps->data[begin] = ps->data[begin + 1];begin++;}ps->size--;
}
//查找
void SqListFind(SL* ps, SLDataType x)
{assert(ps);int count = 0;for(int i = 0; i < ps->size; i++){if (x == ps->data[i]){count = 1;printf("下标为:%d\n", i);}}if (count == 0){printf("该数据不存在");}
}
//修改
void SqListAmend(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->data[pos] = x;
}

3.test.c

#include "Sqlist.h"
void Test(SL* s)
{SqListInit(s);SqListDestroy(s);
}
int main()
{SL s;Test(&s);return 0;
}

有小伙伴们可能会疑惑，为什么顺序表不像通讯录一样搞一个菜单呢？？？

我们实现通讯录，是奔着它的功能去的，所以我们要制造菜单来使用。

但是顺序表我们只需要实现它的各个功能就行，所以只需要掌握每个操作的写法即可。

六.总结

顺序表的讲解到这里就结束啦，当然博主所分享的这个顺序表的操作都是最基本的，更多有用的操作就靠小伙伴们来自己开发啦。

最后不要忘记一键三连哦！！！

我们下期再见！！！


http://www.ppmy.cn/news/1186903.html

相关文章

android wifi和数据网络（以太网切换）出现的问题

android wifi和数据网络（以太网切换）出现的问题

场景1&#xff1a; 在实车上测试车机连接路由器的性能&#xff0c;车机连接着以太网&#xff0c;但是以太网没有网 然后车机通过WIFI连接一个路由器&#xff0c;电脑也连接路由器&#xff0c;突然发现车机通过路由器无法ping通路由器下的电脑&#xff0c;而且也ping不通路由器…
阅读更多...
【Amazon】跨AWS账号资源授权存取访问

【Amazon】跨AWS账号资源授权存取访问

文章目录 一、实验框架图二、实验过程说明三、实验演示过程1、在A账号中创建S3存储桶2、在A账号创建S3存储桶访问策略3、在A账号创建信任开发账号的角色4、在B账号为用户添加内联策略5、在B账号中切换角色&#xff0c;以访问A账号中的S3资源 四、实验总结 一、实验框架图 本次…
阅读更多...
损失函数总结（十）：TripletMarginLoss、TripletMarginWithDistanceLoss

损失函数总结（十）：TripletMarginLoss、TripletMarginWithDistanceLoss

损失函数总结&#xff08;十&#xff09;&#xff1a;TripletMarginLoss、TripletMarginWithDistanceLoss 1 引言2 损失函数2.1 TripletMarginLoss2.2 TripletMarginWithDistanceLoss 3 总结 1 引言 在前面的文章中已经介绍了介绍了一系列损失函数 (L1Loss、MSELoss、BCELoss、…
阅读更多...
fl studio哪个版本好?fl studio21汉化破解版2024免费下载安装图文激活教程

fl studio哪个版本好?fl studio21汉化破解版2024免费下载安装图文激活教程

fl studio哪个版本好?fl studio21汉化破解版2024免费下载安装图文激活教程 fl studio21破解版下载专区由兔八哥爱分享小编精心为大家整理了fl studio软件所有版本合集。其中包含了fl studio21修改版、fl studio 20汉化修改版、fl studio21中文修改版、水果fl studio20完美汉化…
阅读更多...
react路由懒加载lazy直接使用组件标签引发的问题？

react路由懒加载lazy直接使用组件标签引发的问题？

文章 前言错误场景解决方案问题分析后言 前言 ✨他们是天生勇敢的开发者&#xff0c;我们创造bug&#xff0c;传播bug&#xff0c;毫不留情地消灭bug&#xff0c;在这个过程中我们创造了很多bug以供娱乐。 ✨ 这里是前端的一些bug 感兴趣的可以看看前端bug 错误场景 在react18t…
阅读更多...
ios 代码上下文截屏之后导致的图片异常问题

ios 代码上下文截屏之后导致的图片异常问题

业务场景&#xff0c;之前是直接将当前的collectionview截长屏操作&#xff0c;第一次截图会出现黑色部分原因是视图未完全布局&#xff0c;原因是第一次使用了Masonry约束然后再截图的时候进行了frame赋值&#xff0c;可以查看下Masonry约束和frame的冲突&#xff0c;全部修改…
阅读更多...
高效学习工具之Anki新手入门指南（ios端，包括ipad、ihpone设备）————创建、使用、备份、设置参数、相关资料

高效学习工具之Anki新手入门指南（ios端，包括ipad、ihpone设备）————创建、使用、备份、设置参数、相关资料

文章目录 0 背景0.1 闭环学习0.2 什么是anki 1 开始使用1.1 导入1.2 创建空白组1.3 创建卡片1.3.1 利用anki创建卡片的两种方法1.3.2 复习材料分类 1.4 筛选&#xff08;做减法&#xff09;1.5 开启v3算法&#xff0c;设置排程 2 操作卡牌&#xff08;位于卡牌界面中“游览”&a…
阅读更多...
python采集电商jd app商品详情数据（2023-10-30）

python采集电商jd app商品详情数据（2023-10-30）

一、技术要点&#xff1a; 1、cookie可以从手机app端用charles抓包获取&#xff1b; 2、无需安装nodejs&#xff0c;纯python源码&#xff1b; 3、商品详情接口为&#xff1a;functionId "wareBusiness"&#xff1b; 4、clientVersion "10.1.4"同…
阅读更多...
最新文章

Copyright @ 2022~2023