【数据结构】二、线性表:6.顺序表和链表的对比不同(从数据结构三要素讨论:逻辑结构、物理结构(存储结构)、数据运算(基本操作))

news/2024/4/16 14:58:39/文章来源:https://blog.csdn.net/weixin_51350847/article/details/136516977

文章目录

      • 6.对比:顺序表&链表
        • 6.1逻辑结构
        • 6.2物理结构(存储结构)
          • 6.2.1顺序表
          • 6.2.2链表
        • 6.3数据运算(基本操作)
          • 6.3.1初始化
          • 6.3.2销毁表
          • 6.3.3插入、删除
          • 6.3.4查找

6.对比:顺序表&链表

6.1逻辑结构

顺序表和链表都是线性结构。

6.2物理结构(存储结构)
6.2.1顺序表

顺序存储

请添加图片描述

优点:

  1. 使用顺序存储,每个数据元素大小相同,所以可以随机访问,即可以在O(1)时间内找到第i个元素。
  2. 存储密度高,每个节点只存储数据元素。

缺点:

  1. 拓展容量不方便,使用大片连续的空间,即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高。
  2. 插入、删除操作不方便,需要移动大量元素
6.2.2链表

链式存储

请添加图片描述

优点:

  1. 离散分配空间,分配方便,改变容量方便。
  2. 单链表的节点是通过指针来连接的,因此在插入、删除节点时不需要移动其他节点,只需要修改指针的指向即可。

缺点:

  1. 由于链表每个节点只存储了指向下一个节点的指针,只能顺序存储,不可随机存储,所以访问节点时需要从头指针开始依次遍历访问,直到找到需要的节点,或者到达链表的结尾。
  2. 存储密度低,每个结点除了存储数据元素,还存储了指针。
6.3数据运算(基本操作)

6个基本操作:创销增删改查

顺序表链表
数据弹性(可扩容)
增、删
查找
6.3.1初始化

顺序表:

需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源。

  • 静态分配:静态数组,容量不可以改变。
  • 动态分配:动态数组(malloc、free):容量可改变,但需要移动大量元素,时间代价高。

链表:

只需分配一个头结点(也可以不要头结点,只声明一个头指针),之后方便拓展。

6.3.2销毁表

顺序表:

  1. 修改Length = 0
  2. 释放空间
    • 静态分配:静态数组,系统自动回收空间。
    • 动态分配:动态数组(malloc、 free),需要手动free。

链表:

依次删除各个结点(free)。

6.3.3插入、删除

顺序表:

插入/删除元素要将后续元素都后移/前移。

时间复杂度O(n),时间开销主要来自移动元素

链表:

插入/删除元素只需修改指针即可。

时间复杂度O(n),时间开销主要来自查找目标元素

若元素占用空间很大,那么移动元素花费的时间要比查找元素花费是时间代价更大。

6.3.4查找

顺序表:

按位查找:使用顺序存储,每个数据元素大小相同,所以可以随机访问,即可以在**O(1)**时间内找到第i个元素。

按值查找:O(n)。若表内元素有序,可在 O(log_2n) 时间内找到。

链表:

按位查找:由于单链表每个节点只存储了指向下一个节点的指针,只能顺序存储,不可随机存储,所以访问节点时需要从头指针开始依次遍历访问,直到找到需要的节点O(n)。

按值查找:只能遍历O(n)

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

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

相关文章

管理技巧 | 提升团队效能:如何与下属进行有效沟通

本文节选霍格沃兹测试开发学社沟通管理公开课- 某外企PMO Angelia老师的分享 在日常的管理工作中,沟通作为一项基础而关键的技能,往往决定了团队的协作效率和目标达成率。作为一个曾经从基层员工一路成长为管理者的Angelia老师,深知沟通的艺术…

jmap-各种option参数说明

基本情况 jmap(JVM Memory Map):作用一方面是获取dump文件(堆转储快照文件,二进制文件),它还可以获取目标Java进程的内存相关信息,包括Java堆各区域的使用情况、堆中对象的统计信息…

国家妇女节放假是法定的假日

在这个充满活力和希望的春天,我们迎来了一个特殊的节日——国家妇女节。这是一个属于所有女性的节日,是一个庆祝女性成就、关爱女性权益的时刻。在这个特殊的日子里,我们不禁要问:国家妇女节放假是法定假日吗?让我们一…

ChatGPT数据分析应用——漏斗分析

ChatGPT数据分析应用——漏斗分析 ​ 漏斗分析在数据分析中也比较常用,主要是用于发现各个转化流程中哪个环节有问题。接下来我们让ChatGPT解释这个方法的概念并提供相应的案例。发送如下内容给ChatGPT。 ​ ChatGPT收到上述内容后,返回如下结果。 漏斗…

MutationObserver详解

1.基于之前Chrome游览器插件开发的过程中,会遇到在插件控制台打印被安游览器页面的元素,一直未解决。后来找到了解决了办法可以使用MutationObserver;使用MutationObserver这个可以在被安游览器页面直接打印页面元素等等,可能你会…

【电路笔记】-RC网络-时间常数

时间常数 文章目录 时间常数1、概述2、RC 电路的时间常数3、示例14、示例25、RC瞬态放电曲线6、示例37、总结Tau τ \tau τ 是 RC 电路在阶跃变化输入条件下从一种稳态条件变为另一种稳态条件所需的时间常数。 1、概述 Tau,符号 τ \tau τ,是电气和电子计算中使用的希腊字…

【翻译】零信任架构准则(五)Don‘t trust any network

将监控重点放在用户,设备和服务上 全面监控必不可少,因为设备和服务更容易受到网络攻击。在零信任架构中,随着设备,服务和用户行为的持续评估,我们的监控策略很可能发生改变。我们应该持续进行监控,并将用…

基于uniapp cli项目开发的老项目,运行报错path.replace is not a function

项目:基于uniapp cli的微信小程序老项目 问题:git拉取代码,npm安装包时就报错; cnpm能安装成功包,运行报错 三种方法尝试解决: 更改代码,typeof pathstring的话,才走path.replace…

wpf prism左侧抽屉式菜单

1.首先引入包MaterialDesignColors和MaterialDesignThemes 2.主页面布局 左侧菜单显示在窗体外&#xff0c;点击左上角菜单图标通过简单的动画呈现出来 3.左侧窗体外菜单 <Grid x:Name"GridMenu" Width"150" HorizontalAlignment"Left" Ma…

1.2_2 OSI参考模型

文章目录 1.2_2 OSI参考模型一、概述&#xff08;一&#xff09;ISO/OSI参考模型是怎么来的&#xff1f;&#xff08;二&#xff09;ISO/OSI参考模型&#xff08;三&#xff09;ISO/OSI参考模型解释通信过程 二、各层功能及协议&#xff08;一&#xff09;应用层&#xff08;第…

备份 ChatGPT 的聊天纪录

备份 ChatGPT 的聊天纪录 ChatGPT 在前阵子发生了不少次对话纪录消失的情况&#xff0c;让许多用户觉得困扰不已&#xff0c;也担心自己想留存的聊天记录消失不见。 好消息是&#xff0c;OpenAI 在 2023 年 4 月 11 日推出了 ChatGPT 聊天记录备份功能&#xff0c;无论是免费…

java基础-io

文章目录 IO常见面试题java中io流分为几种BIO,NIO,AIO有什么区别 IO分类字符流-字节流-缓冲区字节流、字符流和转换流之间的关系字节字符得区别缓冲区 同步阻塞IO/BIO同步非阻塞IO/NIOjava NIO由几个核心部门&#xff1a;缓存Buffers&#xff1b;通道Channels&#xff1b;选择器…

项目建设计划书-word

【项目建设计划书-word】 项目描述&#xff08;项目目标&#xff0c;客户需求情况&#xff0c;项目交付清单&#xff0c;验收标准和交付期限&#xff0c;服务及约束&#xff09;项目组织&#xff08;项目组人员架构&#xff0c;职责分工&#xff0c;人员投入安排及时间点安排&…

气相白炭黑外资垄断格局被打破 国内本土企业数量增加

气相白炭黑外资垄断格局被打破 国内本土企业数量增加 气相白炭黑又名气相二氧化硅&#xff0c;是一种无毒、无味、无嗅&#xff0c;无污染的非金属氧化物&#xff0c;主要由硅的卤化物在氢氧火焰中高温水解生成的带有表面羟基和吸附水的无定形的纳米级颗粒。气相白炭黑主要用于…

测试一下 Anthropic 宣称超过 GPT-4 的 Claude 3 Opus

测试一下 Anthropic 宣称超过 GPT-4 的 Claude 3 Opus 0. 引言1. 测试 Claude 3 Opus 0. 引言 今天测试一下 Anthropic 发布的 Claude 3 Opus。 3月4日&#xff0c;Anthropic 宣布推出 Claude 3 型号系列&#xff0c;该系列在广泛的认知任务中树立了新的行业基准。该系列包括…

【NR 定位】3GPP NR Positioning 5G定位标准解读(三)

目录 前言 5 NG-RAN UE定位架构 5.1 架构 5.2 UE定位操作 5.3 NG-RAN定位操作 5.3.1 通用NG-RAN定位操作 5.3.2 OTDOA定位支持 5.3.3 广播辅助信息支持 5.3.4 NR RAT相关定位支持 5.4 NG-RAN中与UE定位相关的元素功能描述 5.4.1 用户设备&#xff08;UE&#xff09; …

c++ 中const

对于基础类型直接赋值 void test01(){const int data10;cout<<"data"<<data<<endl;int * p (int*)&data;*p 1000;cout<<"*p"<<*p<<endl;cout<<"after data"<<data; } c中&#xff0c;对于…

洛谷 P1731 [NOI1999] 生日蛋糕

题目 题目链接 自己没看题解写的&#xff0c;摸石头过河&#xff0c;解释一下 首先&#xff0c;输入输出都是正整数。先搞定输入&#xff0c;再判断条件&#xff0c;如果无解&#xff0c;输出0&#xff0c;否则输出蛋糕外表面面积Q&#xff08;这里用全局变量&#xff0c;开l…

【愚公系列】2024年02月 《网络安全应急管理与技术实践》 013-网络安全应急技术与实践(Web层-XSS钓鱼攻击)

🏆 作者简介,愚公搬代码 🏆《头衔》:华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,CSDN商业化专家,阿里云专家博主,阿里云签约作者,腾讯云优秀博主,腾讯云内容共创官,掘金优秀博主,51CTO博客专家等。 🏆《近期荣誉》:2022…

全志D1s裸机开发之体验第一个程序

体验第一个程序 2.1 编译烧录运行 2.1.1 编译 先进入源码目录&#xff0c;打开 Git Bash&#xff0c;如下图操作&#xff1a; 然后在 Git Bash 中执行 make 命令&#xff0c;可以生成 benos_payload.bin 文件&#xff0c;如下图所示&#xff1a; 2.1.2 烧录运行 使用 2 条 …