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

【数据结构】线性表与顺序表

news 来源：原创 2024/9/20 10:49:50

  •  🚩 WRITE IN FRONT 🚩       

  • 🔎 介绍："謓泽"正在路上朝着"攻城狮"方向"前进四" 🔎
  • 🏅 荣誉：2021|2022年度博客之星物联网与嵌入式开发TOP5|TOP4、2021|2222年获评百大博主、华为云享专家、阿里云专家博主、掘金优秀创作者、腾讯云年度进取作者、全网粉丝量8w+、个人社区人数累计5w+、全网访问量100w+ 🏅
  • 🆔 本文章内容由 謓泽 原创 如需相关转载请提前告知博主 ⚠
  • 📑 创作时间：2022 年 12 月 04 日 📅
  • 📝 个人主页：謓泽的博客 📃
  • 📣 专栏系列：数据结构_謓泽的博客-CSDN博客📃
  • 🙌 Gitee：謓泽 (wsxsx) - Gitee.com ⭐️
  • 🎁 点赞👍+ 收藏⭐️+ 留言📝​

  • ✉️ 我们并非登上我们所选择的舞台，演出并非我们所选择的剧本 📩

前言 

概述⇢数据结构🐟算法真的很难对于刚接触的新手来说，所以希望在学习这个知识点的小伙伴们以及博主自己都可以坚持下来。

⛳来和博主一起干了这碗🐓汤。

所谓困难，其实是自己的本事不够；很多纠结的事情，当我们做出决定并迈出第一步的时候，最困难的那部分其实就已经完成了。

线性表

概述⇢线性表是数据结构相对来说入门的数据结构，线性主要就是呈现出"线性"，算了这样说也不太明白。直接用图形表示法会更加明显，带大家理解所谓的线性。

说明⇢像上述的形式通常我们在数组当中会经常的去使用也是线性结构。

正题⇢线性表(linear list) 是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，也是必须要牢牢掌握的。

常见的顺序表
1.顺序表
2.链表
3.栈
4.队列

注意⇢包括我们常用的数组(array)以及字符串(str)也是属于顺序表的。

顺序表实现

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

顺序表分类

⑴静态顺序表:使用定长的数组进行存储。

⑵动态顺序表:使用动态开辟的数组进行存储。

⒈示例－静态顺序表

概述⇢示例代码①会使用静态顺序表来实现相关的内容并且用结构体类型的方式来进行代码的示例，里面会设计到C语言当中比较高级的语法。如果你看起来觉得一头雾水的话，建议还是再去学习下C语言吧♬

1.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void TestSeqList1()
{unsigned int i = 0;SL sl;//这里传递地址,是因为形参实际上是实参的临时拷贝。如果不传递地址的话,形参的函数出了作用域就会被销毁。所以,我们就需要用地址传递,使得它们的地址空间是一样的,这样形参就会实例话,相当于也改变了实参。SeqListInit(&sl);for (i = 0; i < PB_MAX; i++){SeqListPushBack(&sl, i);}
}int main(void)
{TestSeqList1();return 0;
}

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void SeqListInit(SL* ps)
{//对于结构体数组初始化可以用memset() - 内存填充块进行初始化操作。memset(ps->a, 0, sizeof(int) * MAX_SIZE);ps->Size = 0;
}void SeqListPushBack(SL* ps, int x)  //顺序表
{if (ps->Size >= MAX_SIZE){printf("SeqList is Full\n");return;}else{ps->a[ps->Size] = x;ps->Size++;printf("%d.SeqList is ok-%p\n",x,&(ps->a[ps->Size]));}
}void SeqListPushFront(SL* ps, int y) 
{}void SeqListPopBack(SL* ps)			
{}void SeqListPopFront(SL* ps)		 
{}

3.SeqList.h

#ifndef __SEQLIST_H
#define __SEQLIST_H#include <stdio.h>
#include <string.h>#define MAX_SIZE 10
#define PB_MAX   10typedef struct
{int a[MAX_SIZE];int Size;
}SL;extern void SeqListInit(SL* ps);			//增删查改等接口extern void SeqListPushBack(SL* ps, int x); //顺序表
extern void SeqListPushFront(SL* ps, int y);
extern void SeqListPopBack(SL* ps);			
extern void SeqListPopFront(SL* ps);		#endif

说明⇢静态的顺序表在实际情况下是有缺陷的。

1.它数组大小是固定死的，我们是需要根据情况对数组下标进行相对应的修改，不方便。

2.浪费空间，假设要存储10个字节。而你数组存放了1000个字节的单位，这样就会浪费内存空间。

总结⇢静态的顺序表不推荐使用!

⒉示例－动态顺序表✨

概述⇢好!接下来用动态顺序表的方式来实现。如果你对于动态存储比较模糊的话，推荐你看下博主写的这篇博客相信会对你有所帮助的。

🔗malloc链接－【C语言】动态内存开辟的使用『malloc』

🔗项目参考内容 【C语言】通讯录《动态内存版本》

1.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void TestSeqList1(s)
{unsigned int i = 0;SL sl;//这里传递地址,是因为形参实际上是实参的临时拷贝。如果不传递地址的话,形参的函数出了作用域就会被销毁。所以,我们就需要用地址传递,使得它们的地址空间是一样的,这样形参就会实例话,相当于也改变了实参。SeqListInit(&sl);for (i = 0; i < PB_MAX; i++){SeqListPushInsert(&sl, i);//插入}printf("插入:");SeqListprint(&sl);		      //打印printf("\n");printf("插入->头插:");SeqListPushFront(&sl, 5);SeqListprint(&sl);		      //打印printf("\n");printf("插入->头插->尾删:");SeqListPopBack(&sl);SeqListprint(&sl);		      //打印printf("\n");printf("插入->头插->尾删->头删:");SeqListPopFront(&sl);SeqListprint(&sl);		      //打印printf("\n");printf("插入->头插->尾删->头删->尾插:");SeqListPushBack(&sl, 6);SeqListprint(&sl);		      //打印printf("\n");printf("插入->头插->尾删->头删->尾插->初始化:");SeqListInitClearZero(&sl);SeqListprint(&sl);		      //打印printf("\n");
}int main(void)
{TestSeqList1();return 0;
}

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void SeqListInit(SL* ps)
{ps->a = NULL;ps->Size = 0;ps->capacity = 0;
}void SeqListCheckCape(SL* ps)			//检查空间,如果满了,进行增容。
{//扩容一般2倍进行,可以用relloc()进行内存填充if (ps->Size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SQDateType* tmp = (SQDateType*)realloc(ps->a, sizeof(SQDateType) * newcapacity);//如果tmp是空指针的话,说明扩容失败。if (tmp == NULL){perror("realloc fail");exit(-1); //除了exit(0)其他参数均代表程序异常退出。}else{ps->a = tmp;ps->capacity = newcapacity;}}
}void SeqListPushInsert(SL* ps, int x)    //插入
{//扩容一般2倍进行,可以用relloc()进行内存填充SeqListCheckCape(ps);ps->a[ps->Size] = x;ps->Size++; 
}void SeqListPushFront(SL* ps, int y)    //头插
{SeqListCheckCape(ps);for (int end = ps->Size - 1; end >= 0; end--){ps->a[end + 1] = ps->a[end];}ps->a[0] = y;ps->Size++;
}void SeqListPopFront(SL* ps)            //头删
{assert(ps->Size > 0);int starts = 1;while (starts < ps->Size){ps->a[starts - 1] = ps->a[starts];starts++;}ps->Size--;
}void SeqListPopBack(SL* ps)			   //尾删
{assert(ps->Size > 0);//断言,当Size大于0的时候断言失败,当Size小于等于0的时候断言成功。ps->Size--;
}void SeqListPushBack(SL* ps, int z)    //尾插
{assert(ps->Size >= 0);ps->a[ps->Size++] = z;
}void SeqListInitClearZero(SL* ps)          //初始化清0
{int i = 0;for (i = 0; i < ps->Size; i++){ps->a[i] = 0;}
}void SeqListprint(SL* ps)			   //打印
{for (int i = 0; i < ps->Size; i++){printf("%d ", ps->a[i]);}
}

🕹说明⇢有很多小伙伴可能会在第十七行有所疑问？为什么realloc()的返回值是新的整形指针，而不能直接是 ps->a 这个是因为"relloc"可能返回null指针赋值给"ps->a"(后者将作为参数传递给"relloc"将导致原始内存块会被泄露，这是一个很不安全的做法。

3.SeqList.h

#ifndef __SEQLIST_H
#define __SEQLIST_H#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>#define PB_MAX   5typedef int SQDateType;//增强程序的可维护性typedef struct
{SQDateType* a;int Size;		//有效数据个数int capacity;	//容量
}SL;extern void SeqListInit(SL* ps);			 //增删查改等接口初始化√
extern void SeqListCheckCape(SL* ps);		 //检查空间,如果满了,进行增容√
extern void SeqListPushInsert(SL* ps, int x);//插入√
extern void SeqListPushFront(SL* ps, int y); //头插√
extern void SeqListPopFront(SL* ps);		 //头删√
extern void SeqListPopBack(SL* ps);			 //尾删√ 
extern void SeqListPushBack(SL* ps, int z);  //尾插√
extern void SeqListInitClearZero(SL* ps);    //初始化0√
extern void SeqListprint(SL* ps);			 //打印√#endif

运行结果↙

说明⇢相对于静态顺序表来说无疑用动态顺序表是更加好的选择。

总结⇢动态的顺序表可以更好的去帮助我们解决问题!

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Ubuntu22.04使用NVM安装多版本Node.js和版本切换
  • RedisTemplate、StringRedisTemplate、序列化器配置
  • Django REST Framework(十四)路由Routes
  • 二十四、【机器学习】【非监督学习】- 高斯混合模型 (Gaussian Mixture Models, GMM)
  • 深入理解 Redis 的使用与监控
  • 移动UI：排行榜单页面如何设计，从这五点入手，附示例。
  • 【DP】01背包
  • Linux嵌入书学习—数据结构——栈（seqstak）
  • 鸿蒙（HarmonyOS）下拉选择控件
  • CSS实现表格无限轮播
  • Kafka基础概念
  • @NotNull、@NotEmpty 和 @NotBlank 区别
  • 【leetcode 详解】生成特殊数字的最少操作【中等】(C++思路精析)
  • C#中实现Web API的签名验证
  • 24种设计模式介绍与6大设计原则（电子版教程）
  • CentOS从零开始部署Nodejs项目
  • express如何解决request entity too large问题
  • Java知识点总结（JDBC-连接步骤及CRUD）
  • Laravel Telescope：优雅的应用调试工具
  • LintCode 31. partitionArray 数组划分
  • Making An Indicator With Pure CSS
  • Redash本地开发环境搭建
  • spark本地环境的搭建到运行第一个spark程序
  • Vue--数据传输
  • Windows Containers 大冒险: 容器网络
  • 网络应用优化——时延与带宽
  • 微服务框架lagom
  • 用 Swift 编写面向协议的视图
  • 原生Ajax
  • 找一份好的前端工作，起点很重要
  • “十年磨一剑”--有赞的HBase平台实践和应用之路 ...
  • Prometheus VS InfluxDB
  • 数据可视化之下发图实践
  • ​​​【收录 Hello 算法】10.4 哈希优化策略
  • ​2020 年大前端技术趋势解读
  • #14vue3生成表单并跳转到外部地址的方式
  • #FPGA（基础知识）
  • #数据结构 笔记三
  • (1)bark-ml
  • (过滤器)Filter和(监听器)listener
  • （没学懂，待填坑）【动态规划】数位动态规划
  • （七）Activiti-modeler中文支持
  • （四）c52学习之旅-流水LED灯
  • （五）MySQL的备份及恢复
  • (转)h264中avc和flv数据的解析
  • （转）原始图像数据和PDF中的图像数据
  • (轉貼) UML中文FAQ (OO) (UML)
  • (自适应手机端)行业协会机构网站模板
  • .net core 的缓存方案
  • .NET开源项目介绍及资源推荐：数据持久层
  • .NET开源项目介绍及资源推荐：数据持久层 （微软MVP写作）
  • .net快速开发框架源码分享
  • /3GB和/USERVA开关
  • @NotNull、@NotEmpty 和 @NotBlank 区别
  • [AIGC] Redis基础命令集详细介绍