当前位置： 首页 > news >正文

【数据结构】顺序表

news 2025/1/16 17:48:27


🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

目录

  • 🐼前言
  • 🐼线性表
  • 🐼顺序表
    • 🐼 初始化
    • 🐼尾插
      • 🐼增容
    • 🐼 展示顺序表
    • 🐼 头插
    • 🐼 尾删
    • 🐼 头删
    • 🐼查找指定元素
    • 🐼在指定位置之前插入数据
    • 🐼删除指定位置
    • 🐼销毁顺序表
  • 🐼全部源码
  • 🐼文末

🐼前言

在上一节我们实现了通讯录，如果感兴趣的小伙伴，可以阅读我的上一篇文章:
通讯录，这一节要更客观的认识它的底层逻辑结构:顺序表

🐼线性表

首先我们来介绍线性表，线性表是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

🐼顺序表

顺序表是线性表的一种

顺序表是一段物理上的连续存储单元存储数据的线性结构，一般用数组存储，顺序表分为两种，静态顺序表和动态顺序表，定义如下:

typedef int SLDataType;
//静态顺序表
#define MAX_SIZE 100
typedef struct SeqList
{SLDataType data[MAX_SIZE];int size;//顺序表中有效元素的个数
}SL;//动态顺序表
typedef struct SeqList
{SLDataType* data;int size;//顺序表中有效元素的个数int capacity;//容量大小
}SL;

静态顺序表顾名思义，数组的个数是固定的。静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。
动态顺序表在静态循序表的基础上，又增加了一个结构体变量capacity
当capacity == size 时，我们增容，从而实现了动态的功能。
动态顺序表缺陷：频繁增容，可能会有多个内存碎片，造成内存泄露。
相比于静态顺序表的数据流失，动态顺序表显然更好，所以我们用动态顺序表来实现顺序表

在顺序表的实现中，我们要手动实现顺序表的初始化，销毁顺序表，打印，尾插，头插，尾删，头删，在指定位置之前插入数据，查找指定位置数据，以及删除指定位置的数据现在我们来一一实现。

🐼 初始化

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

🌻代码解析

上述代码我们对ps指向的data数组开辟的那块内存空间置空，并将顺序表有效的数据元素和容量大小置为0。

🐼尾插

尾插的逻辑很简单，在arr中插入有效元素，并让size++，但是，在插入数据时，是否有空间让我们尾插呢?所以我们首先要检查是否有空间来支持我们插入，如果有空间，则直接尾插，没有空间，让操作系统申请空间以便于让我们尾插
所以我们在插入元素之前，首先要检查是否需要增容，要增容，那我们增容，不增容，执行尾插操作
这里我们封装一个函数CheakCapacity()来检查是否需要增容。

🐼增容

void CheakCapacity(SL* pc)
{//判断是否是要增容if (pc->size == pc->capacity){//增容int newcapacity = pc->capacity == 0 ? 4 : 2 * pc->capacity;SLDataType* tmp =(SLDataType*) realloc(pc->data,newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("CheakCapacity()::fail");exit(1);}pc->data = tmp;pc->capacity = newcapacity;}
}

🌻代码解析

我们用pc->size和pc->capacity是否相等判断是否需要增容，如果需要增容，我们用realloc()函数来增容，将realloc的申请的空间先放在临时变量tmp中，增容的大小以2倍的方式增容，最后更新data和capacity.
时间复杂度为O(1),空间复杂度为O(1),只创建有效个变量
注意：以二倍方式增容是比较科学的，概率论为基础，既不会浪费太多空间，也不会频繁增容。

尾插代码

//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//等价于assert(ps != NULL)//检查是否需要增容CheakCapacity(ps);ps->data[ps->size++] = x;
}

🌻代码解析

在尾插前，我们要先检查是否需要增容，然后更细数组中的内容和下标size
时间复杂度为O(1),空间复杂度为O(1),只创建有效个变量
如图:
在这里插入图片描述

🍀 测试结果:
在这里插入图片描述

🐼 展示顺序表

//展示顺序表
void SLDisplay(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->data[i]);}printf("\n");
}

🌻代码解析

为了更直观的展示顺序表，我们通过有效元素的个数，一一打印出顺序表中的有效数据。
时间复杂度为O(N),只遍历一次顺序表，空间复杂度为O(1),只创建有效个变量

🐼 头插

//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//检查是否需要增容CheakCapacity(ps);//将size-1个数据整体向后移动一位for (int i = ps->size - 1; i >=0; i--){ps->data[i + 1] = ps->data[i];}//将下标为0的位置空出来ps->data[0] = x;ps->size++;
}

🌻代码解析

头插与尾插相同，在插入过程中首先都需要先检查是否需要增容，然后将第0个下标之后的元素整体向后移动一位，
将下标为0的位置空出来，插入元素，完成头插操作
时间复杂度为O(N),只遍历一次顺序表，空间复杂度为O(1),只创建有效个变量
画图解析:
在这里插入图片描述

🍀 测试结果:
在这里插入图片描述

🐼 尾删

// 尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);//将有效元素的个数减一ps->data[ps->size--];
}

🌻代码解析

尾删代码很简单，要保证要删除的元素不为空并且ps不为空的前提下，我们只需要让有效元素减一，最后一个元素对于其他功能都是无作用的，当进行下一个操作时，会覆盖掉最后一个元素，从而达到了尾删的目的。
时间复杂度为O(1),空间复杂度为O(1),只创建有效个变量

🍀 测试结果:
在这里插入图片描述

🐼 头删

// 头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);//整体数据往前挪动一位for (int i = 1; i <= ps->size - 1; i++){ps->data[i - 1] = ps->data[i];}ps->size--;
}

🌻代码解析

头删也是要保证删除的顺序表不为空，然后整体向前挪动一位，覆盖掉前面数据，完成一次头删操作，最后更新size的值
时间复杂度为O(N),只遍历一次顺序表，空间复杂度为O(1),只创建有效个变量
🍀 测试结果:
在这里插入图片描述

🐼查找指定元素

//查找指定元素
int SLFind(SL* ps, SLDataType x)
{assert(ps);int i = ps->size;//保存有效元素的个数while (i--){if (ps->data[i] == x)//找到返回下标return i;}//返回无效下标return -1;
}

🌻代码解析

为了不改变size的值，用i从后往前遍历顺序表，如果找到了该数据，返回下标，没有找到返回无效下标。
时间复杂度为O(N),只遍历一次顺序表，空间复杂度为O(1),只创建有效个变量

🍀 测试结果:
在这里插入图片描述

🐼在指定位置之前插入数据

//在指定位置之前插入数据
void Insert(SL* ps, SLDataType pos, SLDataType x)
{assert(ps);assert(ps->size >= pos && pos>=0);//空间足够才能插入数据CheakCapacity(ps);//将pos后的数据整体挪动向后一位for (int i = ps->size - 1; i >=pos; i--){ps->data[i + 1] = ps->data[i];}//插入数据ps->data[pos] = x;ps->size++;
}

🌻代码解析

要保证插入的位置是<=size的，等于pos = size时，相当于尾插,pos等于0，相当于头插。在插入前要检查是否有空间插入。插入过程先将将pos后的数据整体挪动向后一位，空出下标为pos的位置，插入数据。
时间复杂度为O(N),只遍历一次顺序表，空间复杂度为O(1),只创建有效个变量
画图分析:
在这里插入图片描述

🍀 测试结果:

在2前面插入数据:

在这里插入图片描述

🐼删除指定位置

/删除指定位置数据
void Erase(SL* ps, SLDataType pos)
{assert(ps);//有元素才能删assert(ps->size >= pos && pos >= 0);//将pos后的位置整体向前挪动一位for (int i = pos; i < ps->size-1; i++){ps->data[i] = ps->data[i + 1];}ps->size--;
}

🌻代码解析

要删除的元素下标是要存在的，用assert来暴力解决限制，在删除时将pos后的位置整体向前挪动一位，实现覆盖pos，最后，更新size的值，完成删除操作
时间复杂度为O(N),只遍历一次顺序表，空间复杂度为O(1),只创建有效个变量
画图解析:
在这里插入图片描述

🍀 测试结果:
在这里插入图片描述

🐼销毁顺序表

//销毁顺序表
void Destroy(SL* ps)
{assert(ps);//指向空间存在销毁if (ps->data){free(ps->data);}ps->data = NULL;ps->size = ps->capacity = 0;
}

🌻代码解析

释放ps指向的那块空间，并将成员变量capacity和size置为0

🐼全部源码

SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
//静态顺序表
//#define MAX_SIZE 100
//typedef struct SeqList
//{
//	SLDataType data[MAX_SIZE];
//	int size;//顺序表中有效元素的个数
//}SL;
// //动态顺序表
typedef struct SeqList
{SLDataType* data;int size;//顺序表中有效元素的个数int capacity;//容量大小
}SL;//顺序表的初始化
void SLInit(SL* ps);//展示顺序表
void SLDisplay(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//头插
void SLPushFront(SL* ps, SLDataType x);// 尾删
void SLPopBack(SL * ps);// 头删
void SLPopFront(SL* ps);//查找指定元素
int SLFind(SL* ps, SLDataType x);//在指定位置之前插入数据
void Insert(SL* ps, SLDataType pos, SLDataType x);//删除指定位置数据
void Erase(SL* ps, SLDataType pos);//销毁顺序表
void Destroy(SL* ps);

SeqList.c

#define  _CRT_SECURE_NO_WARNINGS
#include "SqList.h"//顺序表的初始化
void SLInit(SL* ps)
{ps->data = NULL;ps->capacity = ps->size = 0;
}void CheakCapacity(SL* pc)
{if (pc->size == pc->capacity){//增容int newcapacity = pc->capacity == 0 ? 4 : 2 * pc->capacity;SLDataType* tmp =(SLDataType*) realloc(pc->data,newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("CheakCapacity()::fail");exit(1);}pc->data = tmp;pc->capacity = newcapacity;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//等价于assert(ps != NULL)//检查是否需要增容CheakCapacity(ps);ps->data[ps->size++] = x;
}//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//检查是否需要增容CheakCapacity(ps);//将size-1个数据整体向后移动一位for (int i = ps->size - 1; i >=0; i--){ps->data[i + 1] = ps->data[i];}//将下标为0的位置空出来ps->data[0] = x;ps->size++;
}//展示顺序表
void SLDisplay(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->data[i]);}printf("\n");
}// 尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);//将有效元素的个数减一ps->data[ps->size--];
}// 头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);//整体数据往前挪动一位for (int i = 1; i <= ps->size - 1; i++){ps->data[i - 1] = ps->data[i];}ps->size--;
}//查找指定元素
int SLFind(SL* ps, SLDataType x)
{assert(ps);int i = ps->size;//保存有效元素的个数while (i--){if (ps->data[i] == x)//找到返回下标return i;}//返回无效下标return -1;
}//在指定位置之前插入数据
void Insert(SL* ps, SLDataType pos, SLDataType x)
{assert(ps);assert(ps->size >= pos && pos>=0);//空间足够才能插入数据CheakCapacity(ps);//将pos后的数据整体挪动向后一位for (int i = ps->size - 1; i >=pos; i--){ps->data[i + 1] = ps->data[i];}//插入数据ps->data[pos] = x;ps->size++;
}//删除指定位置数据
void Erase(SL* ps, SLDataType pos)
{assert(ps);//有元素才能删assert(ps->size >= pos && pos >= 0);//将pos后的位置整体向前挪动一位for (int i = pos; i < ps->size-1; i++){ps->data[i] = ps->data[i + 1];}ps->size--;
}//销毁顺序表
void Destroy(SL* ps)
{assert(ps);//指向空间存在销毁if (ps->data){free(ps->data);}ps->data = NULL;ps->size = ps->capacity = 0;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS
#include "SqList.h"void Test01()
{SL sl;SLInit(&sl);/*SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);*/SLPushFront(&sl, 1);SLPushFront(&sl, 2);SLPushFront(&sl, 3);SLPushFront(&sl, 4);SLDisplay(&sl);/*SLDisplay(&sl);SLPopBack(&sl);SLDisplay(&sl);SLPopBack(&sl);SLDisplay(&sl);SLPopBack(&sl);SLDisplay(&sl);SLPopBack(&sl);SLDisplay(&sl);*//*SLPopFront(&sl);SLDisplay(&sl);SLPopFront(&sl);SLDisplay(&sl);SLPopFront(&sl);SLDisplay(&sl);SLPopFront(&sl);SLDisplay(&sl);*/int ret = SLFind(&sl, 3);/*if (ret != -1)printf("找到了\n");elseprintf("没找到\n");*///Insert(&sl, ret, 66);Erase(&sl, ret);SLDisplay(&sl);
}
int main()
{Test01();
}

🐼文末

感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力 ⛅️🌈 ☀️


http://www.mrgr.cn/news/47003.html

相关文章：

  • OpenCV的对比度受限的自适应直方图均衡化算法
  • ansible 检查目录大小
  • [笔记] 使用 Jenkins 实现 CI/CD ：从 GitLab 拉取 Java 项目并部署至 Windows Server
  • Unity 人体切片三维可视化，可任意裁切切割。查看不同断层的图像。
  • 【Java】-- 利用 jar 命令将配置文件添加到 jar 中
  • PL/SQL语言的数据库交互
  • 推理实现new操作符
  • AI绘画Stable Diffusion XL优化终极指南！
  • CSS 命名规范及 BEM 在前端开发中的实践
  • 《网络基础之 HTML 与 CSS 基础 —— 网页的基本结构解析》
  • 力扣1~10题
  • acme.sh在nginx环境配置，ssl证书测试
  • HCIE的含金量都是被吹出来的？
  • 洗衣店订单管理：Spring Boot技术革新
  • [实用工具]Docker安装nextcloud实现私有云服务和onlyoffice
  • 【工具】前端js数字金额转中文大写金额
  • JAVA中的线程控制
  • 画质修复怎么弄？这4个恢复照片清晰度的修复工具快收藏
  • vue3学习记录-watch
  • 智慧水利（数字孪生流域）建设方案
  • 从不同的细节察觉人的性格
  • A股热了，但黄金周实体经济的统计数字却有点凉
  • 地理空间数据共享资源，爱好者进
  • PELCO-D协议简介
  • python 实现双向A*算法
  • vue3实现登录获取token并自动刷新token进行JWT认证