02.数据结构介绍顺序表、链表简述+对比

目录

一、什么是数据结构

二、线性表

三、顺序表

四、链表

五、顺序表和链表的区别


一、什么是数据结构

        数据结构是由“数据”和“结构”两个词组合而来。

        数据:常见的数值1、2、3......,网页里的文字图片信息等都是数据。

        结构:组织数据的方式。例如对数据的增删改查等方法。

        总结:1)能够存储数据(如顺序表,链表等结构)

                   2)存储的数据能够方便进行增删改查等操作。

二、线性表

        线性表(linear list)是n个具有相同特性的数据元素的有限序列(相同特性指都为整型int、字符型char或其它类型)。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串...

        线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

 三、顺序表

1).顺序表概念及结构

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储,在数组上完成数据的增删改查。一般见到的顺序表都是在结构体中定义的数组,只是比普通数组多了增删改查等一些其他功能函数。

顺序表一般可以分为:

        ①. 静态顺序表:使用定长数组存储元素。(即数组大小一旦确定就不能改变)。可能导致有时空间开大了,造成空间浪费;或者空间开小了,空间不够用。

#define N 7
typedef int SLDataType;
typedef int SeqList
{SLDataType a[N];	//定长数组,N的值一开始就确定了size_t size;
}SeqList;

        ②. 动态顺序表:使用realloc动态开辟的数组存储,数组大小可以改变,每次增容2倍。


typedef int SLDataType
typedef struct SeqList
{SLDataType* a;		//指向动态开辟的数组size_t size;		//有效数据个数size_t capicity;	//容量空间的大小
}SeqList;

2).动态顺序表接口:(接口实现见下一篇博客)

//顺序表初始化
//检查空间,如果满了,进行增容
//顺序表尾插
//顺序表头插
//顺序表尾删
//顺序表头删
//顺序表查找
//顺序表在指定位置插入
//顺序表删除指定位置的值
//顺序表的销毁
//顺序表的打印

四、链表

1)链表的概念及结构

        数据元素是由指针链接实现的。每次增加数据都要申请空间。

typedef int SLTDateType
typedef struct SListNode
{SLTDateType data;          //存储数据struct SListNode* next;    //next指针,指向下一个数据节点
}SListNode;

链表的结构如下,head为链表的头节点(头节点可有可无),是一个指针,指向链表的第一个元素,每个链表节点中的next指针指向下一个节点的地址,每个节点通过上一个节点的next指针链接。

2).链表的分类

        ①.单向或者双向,双向链表中有两个指针,一个指向前一个节点的地址,一个指向后一个节点的地址。

        ②.带头节点,或者不带头节点 。

        ③.循环或者非循环。

                循环:最后一个节点的next指向第一个节点。

                非循环:最后一个节点的next指向NULL。

3).链表的实现(单链表)(具体实现见下下篇博客)

typedef int SLTDateType
typedef struct SListNode
{SLTDateType data;          //存储数据struct SListNode* next;    //next指针,指向下一个数据节点
}SListNode;//动态申请一个节点
//单链表打印
//单链表尾插
//单链表头插
//单链表尾删
//单链表头删
//单链表查找
//单链表在指定位置之后插入
//单链表在指定位置之后删除

五、顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1)不支持:O(N)
任意位置插入或者删除元素可能需要搬移元素,效率低O(N)只需修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/453754.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【从零开始的LeetCode-算法】3184. 构成整天的下标对数目 I

给你一个整数数组 hours&#xff0c;表示以 小时 为单位的时间&#xff0c;返回一个整数&#xff0c;表示满足 i < j 且 hours[i] hours[j] 构成 整天 的下标对 i, j 的数目。 整天 定义为时间持续时间是 24 小时的 整数倍 。 例如&#xff0c;1 天是 24 小时&#xff0c…

leetcode动态规划(九)-0-1背包理论基础

题目 背包问题主要有以下几种分类&#xff0c;对于面试来说掌握0-1背包和完全背包足够&#xff0c;多重背包和分组背包是竞赛级别的题目&#xff0c;面试就无需准备 题目&#xff1a; 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xff0c;得到的价…

C# SM2 加签、验签工具

目录 效果 项目 代码 下载 效果 项目 代码 using Org.BouncyCastle.Crypto.Parameters; using Org.BouncyCastle.Crypto.Signers; using Org.BouncyCastle.Asn1.GM; using System; using System.Text; using System.Windows.Forms; using Org.BouncyCastle.Asn1.X9; using…

element plus e-table表格中使用多选,当翻页时已选中的数据丢失

摘要&#xff1a; 点击第一页选中两个&#xff0c;再选择第二页&#xff0c;选中&#xff0c;回到第一页&#xff0c;之前选中的要保留&#xff01; element ui table 解决办法&#xff1a; :row-key“getRowKeys” &#xff08;写在el-table中&#xff09; methods中声明 ge…

Spring Boot项目中怎么设置内容安全策略Content Security Policy

内容安全策略&#xff08;CSP&#xff0c;Content Security Policy&#xff09; 是一种用于防止跨站点脚本攻击&#xff08;XSS&#xff09;和数据注入攻击的安全策略。它通过指定允许加载的资源类型&#xff08;如脚本、样式表、图像等&#xff09;和其来源&#xff0c;来减少…

Python爬虫之小白入门保姆级教程,带7个爬虫小案例(附源码)!

以下是一份 Python 爬虫入门保姆级教程&#xff1a; 一、准备工作 安装 Python 前往 Python 官方网站&#xff08;https://www.python.org/&#xff09;下载适合你操作系统的 Python 版本并安装。安装过程中可以勾选“Add Python to PATH”以便在命令行中方便地调用 Python。 …

初识git · 有关模型

目录 前言&#xff1a; 有关开发模型 前言&#xff1a; 其实文章更新到这里的时候&#xff0c;我们已经学习了可以满足我们日常生活中的基本需求的指令了&#xff0c;但是为什么要更新本篇文章呢&#xff1f;是因为实际生活中我们对于开发工作&#xff0c;运维工作&#xff…

ubuntu查看系统版本命令

查看系统版本指令 在 Ubuntu 操作系统中&#xff0c;您可以使用多个命令来查看系统版本。以下是一些常用的命令&#xff1a; lsb_release -a 这个命令会显示详细的 Ubuntu 版本信息&#xff0c;包括发行版名称、版本号、代号等。lsb_release -acat /etc/os-release 这个命令会显…

基于SSM的的水电管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

5G工业路由器智能电网部署实录:一天内解决供电、网络

凌晨4:13,我被手机震动惊醒。变电站值班人员发来紧急消息:昨晚部署的SR800突然离线。我立即查看了STAR Device Manager平台,确认是设备A37号在3:47分失去连接。(key-iot.com/iotlist/sr800-3.html) 6:30到达变电站。检查SR800状态,发现是供电问题导致设备重启。这个老旧变电站…

pytorch训练和使用resnet

pytorch训练和使用resnet 使用 CIFAR-10数据集 训练 resnet resnet-train.py import torch import torchvision import torchvision.transforms as transforms import torch.nn as nn import torch.optim as optim# 在CIFAR-10数据集中 # 训练集&#xff1a;包含50000张图像…

电影院订票选座小程序ssm+论文源码调试讲解

第2章 开发环境与技术 电影院订票选座小程序的编码实现需要搭建一定的环境和使用相应的技术&#xff0c;接下来的内容就是对电影院订票选座小程序用到的技术和工具进行介绍。 2.1 MYSQL数据库 本课题所开发的应用程序在数据操作方面是不可预知的&#xff0c;是经常变动的&…

处理文件上传和进度条的显示(进度条随文件上传进度值变化)

成品效果图&#xff1a; 解决问题&#xff1a;上传文件过大时&#xff0c;等待时间过长&#xff0c;但是进度条却不会动&#xff0c;只会在上传完成之后才会显示上传完成 上传文件的upload.component.html <nz-modal [(nzVisible)]"isVisible" [nzTitle]"文…

python包以及异常、模块、包的综合案例(较难)

1.自定义包 python中模块是一个文件&#xff0c;而包就是一个文件夹 有这个_init_.py就是python包&#xff0c;没有就是简单的文件夹 包的作用&#xff1a;当我们的模块越来越多时&#xff0c;包可以帮助我们管理这些模块&#xff0c;包的作用就是包含多个模块&#xff0c;但包…

【命令操作】信创终端系统上timedatectl命令详解 _ 统信 _ 麒麟 _ 方德

原文链接&#xff1a;【命令操作】信创终端系统上timedatectl命令详解 | 统信 | 麒麟 | 方德 Hello&#xff0c;大家好啊&#xff01;今天给大家带来一篇关于如何在信创终端系统上使用timedatectl命令的详细介绍。timedatectl 是Linux系统中非常实用的时间管理工具&#xff0c;…

学习写作--polyGCL.md

POLYGCL: GRAPH CONTRASTIVE LEARNING VIA LEARNABLE SPECTRAL POLYNOMIAL filters 这篇工作的摘要和引言写的特别好&#xff08;不愧是ICLR spotlight&#xff09; 摘要 第一步&#xff0c;设定背景 Recently, Graph Contrastive Learning (GCL) has achieved significantl…

使用Flask实现本机的模型部署

前言 模型部署是指将大模型运行在专属的计算资源上&#xff0c;使模型在独立的运行环境中高效、可靠地运行&#xff0c;并为业务应用提供推理服务。其目标是将机器学习模型应用于实际业务中&#xff0c;使最终用户或系统能够利用模型的输出&#xff0c;从而发挥其作用。 一、设…

12 django管理系统 - 注册与登录 - 登录

为了演示方便&#xff0c;我就直接使用models里的Admin来演示&#xff0c;不再创建用户模型了。 ok&#xff0c;先做基础配置 首先是在base.html中&#xff0c;新增登录和注册的入口 <ul class"nav navbar-nav navbar-right"><li><a href"/ac…

黑马软件测试第一篇_Linux

Linux 操作系统 说明: 所有硬件设备组装完成后的第⼀一层软件, 能够使⽤用户使⽤用硬件设备的软件 即为操作系统 常见分类 桌⾯面操作系统: Windows/macOS/Linux移动端操作系统: Android(安卓)/iOS(苹果)服务器器操作系统: Linux/Windows Server嵌⼊入式操作系统: Android(底…

linux线程 | 同步与互斥 | 线程池以及知识点补充

前言&#xff1a;本节内容是linux的线程的相关知识。本篇首先会实现一个简易的线程池&#xff0c; 然后再将线程池利用单例的懒汉模式改编一下。 然后再谈一些小的知识点&#xff0c;比如自旋锁&#xff0c; 读者写者问题等等。 那么&#xff0c; 现在开始我们的学习吧。 ps:本…