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

数据结构：顺序表的奥秘

news 来源：原创 2024/5/17 14:49:57

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🐻‍❄个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🕊系列专栏：零基础学习C语言----- 数据结构的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————————————

🎉文章简介：

🎉本篇文章对   用C语言实现顺序表 学习的相关知识进行分享！🎉

如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉

目录

一.顺序表的概念及存储结构

1.1储存结构

二.顺序表的实现

一.功能函数的实现

1.初始化函数

2.顺序表的销毁

3.顺序表的打印

4.扩容函数

5.尾插函数

6.尾删函数

7.头插函数

8.头删函数

9.插入函数

10.删除函数

11.查找函数

12.修改函数

三.总代码

四.顺序表的性能分析

一.顺序表的概念及存储结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表可以分为静态顺序表和动态顺序表。

1.1储存结构

静态顺序表：使用定长数组存储元素；

动态顺序表：数组的大小是根据存储的数据个数，如果满了就动态开辟出来的，相对而言不会造成空间的浪费；

二.顺序表的实现

静态顺序表 只适用于确定知道需要存多少数据的场景；

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。例如：如果数组的大小定为200，却只储存了几十个数据，和动态的顺序表相比，空间浪费更大；所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

一.功能函数的实现（含图解）

1.初始化函数

功能：对结构体内成员进行初始化操作；

代码实现：

void InitList(SL* s)
{assert(s);        //断言，防止传入空指针s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);  if (s->a == NULL)   //这里最开始开辟四个存储数据类型的大小{perror("malloc fail");exit(-1);}s->size = 0;            //存储的有效数据个数为0s->capacity = 4;       //空间置成4
}

2.顺序表的销毁

功能：对动态开辟的空间进行销毁，空间释放

代码实现：

void DestoryList(SL* s)
{assert(s);free(s->a);       //释放动态开辟的空间s->a = NULL;      //置空s->capacity = s->size = 0;
}

3.顺序表的打印

代码实现：

void SListPrintf(SL* s)
{assert(s);if (s->size < 0)     //如果没有数据，则直接返回{return;}for (int i = 0; i < s->size; i++){printf("%d ", s->a[i]);       //遍历依次打印}printf("\n");        //打印完换行
}

4.扩容函数

功能：检查是否需要扩容

代码实现：

void CheckCapacity(SL* s)
{assert(s);if (s->capacity == s->size)    //相等则说明空间已经满了{SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity);  //二倍扩容if (tmp == NULL)    {perror("realloc fail");exit(-1);}s->a = tmp;s->capacity *= 2;}
}

5.尾插函数

功能：在顺序表最后插入一个数据

代码实现：

void PushBack(SL* s, SLDateType n)
{assert(s);CheckCapacity(s);  //检查空间是否满s->a[s->size] = n;    //直接插入到数组最后s->size++;       //有效数据个数++
}

6.尾删函数

功能: 删除顺序表的最后一个数据

代码实现：

void PopBack(SL* s)
{assert(s);assert(s->size > 0);     //当数组中有效数据个数为0时，不能再删除s->size--;         //数据个数--}

7.头插函数

功能：在顺序表最前面插入一个数据

代码实现：

void PushFront(SL* s, SLDateType n)
{assert(s);CheckCapacity(s);    //检查扩容int end = s->size;    while (end>0) {s->a[end] = s->a[end - 1];   //挪动数据end--;}s->a[0] = n;         s->size++;
}

图解：

性能分析：头插一个数据，首先需要将全部数据一次往后挪一个位置，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

8.头删函数

功能：删除表中第一个元素

代码实现：

void Popfront(SL* s)
{assert(s);assert(s->size > 0);   //size为0时，不能再删除for (int i = 0; i < s->size; i++){s->a[i] = s->a[i+1];      //向前挪动数据}s->size--;
}

图解：

性能分析：头删一个数据，首先需要将全部数据一次往前挪一个位置，将第一个元素覆盖掉，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

9.插入函数

功能：在某个位置插入一个数据

代码实现：


void SListInsert(SL* s, int pos, SLDateType n)
{assert(s);assert(pos >= 0 && pos <= s->size);    //判断pos合法int end = s->size;int begin = pos;while (begin < end){s->a[end] = s->a[end - 1];   //挪动数据end--;}s->a[pos] = n;       //修改数据s->size++;
}

图解：

性能分析：中间插入一个数据和头插差不多，首先需要将该位置后面的全部数据依次往后挪一个位置，将该位置空出来，再将该数据插入，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

10.删除函数

功能：删除数组中任何位置的数据

代码实现：

void SListErase(SL* s, int pos)
{assert(s);assert(pos >= 0 && pos < s->size);    //pos范围合法判断int cur = pos;while (cur < s->size){s->a[cur] = s->a[cur+1];    //挪动位置cur++;}s->size--;}

图解：

性能分析：删除一个数据与头删差不多，首先需要待删数据位置后面全部数据依次往前挪一个位置，将待删元素覆盖掉，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

11.查找函数

功能：查找顺序表中某个数据，返回下标

代码实现：

int SListFind(SL* s,SLDateType n)
{assert(s);for (int i = 0; i < s->size; i++)    //遍历寻找{if (s->a[i] == n)     //找到了返回下标{ return i;}}printf("顺序表中无该数据\n");   exit(-1);}

性能分析：将数组中的数据遍历一遍；时间复杂度：O(N)

空间复杂度：O(1)

12.修改函数

功能：修改数组中某个数据

代码实现：

void SListModify(SL* s, int pos,SLDateType n)
{assert(s);assert(pos >= 0 && pos < s->size);s->a[pos] = n;     //直接通过下标访问修改
}

三.总代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDateType;struct SeqList
{SLDateType* a;      //指向一个数组的指针int size;           //记录数据个数int capacity;       //记录容量，如果与数据个数相等就扩容
};typedef struct SeqList SL;void InitList(SL* s);void SListPrintf(SL* s);void PushBack(SL* s, SLDateType n);
void PushFront(SL* s, SLDateType n);
void PopBack(SL* s);
void Popfront(SL* s);int SListFind(SL* s,SLDateType n);void SListModify(SL* s, int pos, SLDateType n);
void SListErase(SL* s, int pos);
void SListInsert(SL* s, int pos, SLDateType n);void DestoryList(SL* s);


#include"SeqList.h"void InitList(SL* s)
{assert(s);        //断言，防止传入空指针s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);  if (s->a == NULL)   //这里最开始开辟四个存储数据类型的大小{perror("malloc fail");exit(-1);}s->size = 0;            //存储的有效数据个数为0s->capacity = 4;       //空间置成4
}void SListPrintf(SL* s)
{assert(s);if (s->size < 0)     //如果没有数据，则直接返回{return;}for (int i = 0; i < s->size; i++){printf("%d ", s->a[i]);       //遍历依次打印}printf("\n");        //打印完换行
}void CheckCapacity(SL* s)
{assert(s);if (s->capacity == s->size)    //相等则说明空间已经满了{SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity);  //二倍扩容if (tmp == NULL)    {perror("realloc fail");exit(-1);}s->a = tmp;s->capacity *= 2;}
}void PushBack(SL* s, SLDateType n)
{assert(s);CheckCapacity(s);  //检查空间是否满s->a[s->size] = n;    //直接插入到数组最后s->size++;       //有效数据个数++
}void PushFront(SL* s, SLDateType n)
{assert(s);CheckCapacity(s);    //检查扩容int end = s->size;    while (end>0) {s->a[end] = s->a[end - 1];   //挪动数据end--;}s->a[0] = n;         s->size++;
}void PopBack(SL* s)
{assert(s);assert(s->size > 0);     //当数组中有效数据个数为0时，不能再删除s->size--;         //数据个数--}void Popfront(SL* s)
{assert(s);assert(s->size > 0);   //size为0时，不能再删除for (int i = 0; i < s->size; i++){s->a[i] = s->a[i+1];      //向前挪动数据}s->size--;
}int SListFind(SL* s,SLDateType n)
{assert(s);for (int i = 0; i < s->size; i++)    //遍历寻找{if (s->a[i] == n)     //找到了返回下标{ return i;}}printf("顺序表中无该数据\n");   exit(-1);
}void SListModify(SL* s, int pos,SLDateType n)
{assert(s);assert(pos >= 0 && pos < s->size);s->a[pos] = n;     //直接通过下标访问修改
}void SListErase(SL* s, int pos)
{assert(s);assert(pos >= 0 && pos < s->size);    //pos范围合法判断int cur = pos;while (cur < s->size){s->a[cur] = s->a[cur+1];    //挪动位置cur++;}s->size--;}void SListInsert(SL* s, int pos, SLDateType n)
{assert(s);assert(pos >= 0 && pos <= s->size);    //判断pos合法int end = s->size;int begin = pos;while (begin < end){s->a[end] = s->a[end - 1];   //挪动数据end--;}s->a[pos] = n;       //修改数据s->size++;
}void DestoryList(SL* s)
{assert(s);free(s->a);       //释放动态开辟的空间s->a = NULL;      //置空s->capacity = s->size = 0;
}

四.顺序表的性能分析

问题：


1. 中间/头部的插入删除，时间复杂度为O(N);
2. 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗;
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间;

思考：如何解决以上问题呢？

下一章链表结构就可以解决这个问题；

相关文章：

  • pgrouting学习记录
  • 【图像拼接/视频拼接】论文精读：Efficient Video Stitching Based on Fast Structure Deformation
  • 8套成熟在用的三级医院信息化系统源码，HIS、LIS、PACS、智慧导诊、线上预约挂号支付系统源码
  • mongo基本使用
  • 已解决ResponseEntityException的Spring MVC异常响应实体异常的正确解决方法，亲测有效！！！
  • Vue.js 实用技巧：深入理解 Vue.mixin
  • ICVQUANTUMCHINA报告：《2024全球量子精密测量产业发展展望》
  • [本地跑项目总是要权限校验输密码]Error: EACCES: permission denied
  • 宝塔php站点设置伪静态规则 访问 a.com 时候跳转到 a.com/b.html
  • 【数据结构】初识
  • 2024第二次培训：win11系统下使用nginx、JDK、mysql搭建基于vue2、java前后端分离的web应用运行环境
  • 前端实现一个绕圆心转动的功能
  • javascript中字符串处理，常用的方法汇总
  • Java ElasticSearch面试题
  • 文心一言 VS 讯飞星火 VS chatgpt （209）-- 算法导论15.4 6题
  • python3.6+scrapy+mysql 爬虫实战
  • Android 初级面试者拾遗（前台界面篇）之 Activity 和 Fragment
  • CSS相对定位
  • express如何解决request entity too large问题
  • Java面向对象及其三大特征
  • JS进阶 - JS 、JS-Web-API与DOM、BOM
  • MySQL的数据类型
  • 闭包--闭包作用之保存(一)
  • 多线程事务回滚
  • 记一次删除Git记录中的大文件的过程
  • 小程序01:wepy框架整合iview webapp UI
  • 一起参Ember.js讨论、问答社区。
  • 1.Ext JS 建立web开发工程
  • 阿里云ACE认证之理解CDN技术
  • ​低代码平台的核心价值与优势
  • ​无人机石油管道巡检方案新亮点：灵活准确又高效
  • ​油烟净化器电源安全，保障健康餐饮生活
  • #git 撤消对文件的更改
  • #pragma预处理命令
  • #多叉树深度遍历_结合深度学习的视频编码方法--帧内预测
  • （￥1011）－（一千零一拾一元整）输出
  • （二）JAVA使用POI操作excel
  • (三)模仿学习-Action数据的模仿
  • （已解决）什么是vue导航守卫
  • (转)C#调用WebService 基础
  • (转)拼包函数及网络封包的异常处理(含代码)
  • .Mobi域名介绍
  • .MyFile@waifu.club.wis.mkp勒索病毒数据怎么处理|数据解密恢复
  • .NET C#版本和.NET版本以及VS版本的对应关系
  • .NET core 自定义过滤器 Filter 实现webapi RestFul 统一接口数据返回格式
  • .NetCore项目nginx发布
  • .NET业务框架的构建
  • @property python知乎_Python3基础之：property
  • @Valid和@NotNull字段校验使用
  • @vue/cli 3.x+引入jQuery
  • [ vulhub漏洞复现篇 ] JBOSS AS 4.x以下反序列化远程代码执行漏洞CVE-2017-7504
  • [ 云计算 | Azure 实践 ] 在 Azure 门户中创建 VM 虚拟机并进行验证
  • [100天算法】-每个元音包含偶数次的最长子字符串（day 53）
  • [AI]ChatGPT4 与 ChatGPT3.5 区别有多大
  • [BUG]Datax写入数据到psql报不能序列化特殊字符