IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构(三 线性表) -> 正文阅读

[数据结构与算法]数据结构(三 线性表)

看《大话数据结构》所做笔记

线性表:零个或多个数据元素的有限序列

线性表的抽象数据类型定义:线性表的数据对象集合为(a1,a2,…a3),每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素;除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

线性表的顺序存储结构

? 线性表顺序存储结构,这个很常见了,例如:幼儿园,过马路时,一个接一个,按照一定顺序排列

  • 顺序存储的定义

    指的是用一段地址连续的存储单元依次存储线性表的数据元素

  • 顺序存储的方式

    • 顺序存储的三个属性

      • 存储空间的起始位置:index
      • 线性表的最大存储容量:MaxSize
      • 线性表的当前长度:length
    • 数据长度与线性表长度区别

      • 数组的长度:线性表存储空间的长度,一般来说的是不变的(也就是 有不是一般的,动态分配)

      • 线性表的长度:指的是线性表中数据元素的个数,是变化的(插入和删除操作)

        在任意时刻,线性表的长度 都小于等于 数组的长度

    • 地址计算方法

      存储器中的每一存储单元都有自己的编号,这个编号称为地址。

      数组中的编号的地址是从 0 开始的

  • 顺序存储结构的插入和删除

    • 获得元素操作

      就是把数组第i-1下标返回

    • 插入操作

      插入算法的思路

      • 如果插入位置不合理,抛出异常
      • 如果线性表的长度大于等于数组的长度,则抛出异常或动态增加容量
      • 从最后一个元素向前遍历到第i个位置,分别将它们都向后移动一个位置
      • 将要插入元素填入位置i 处
      • 表长度加1
    • 删除操作

      • 如果删除位置不合理,抛出异常
      • 取出删除元素
      • 从删除元素位置开始遍历到最后一个元素位置,分别将它们向前移动一个位置
      • 表长度减1

      思考:插入和删除的时间复杂的

      如果是第一个元素进行插入或删除,则时间复杂度为 O(n)

      根据概率原理,可能性取平均 ,一个元素的插入和删除是 (n-1)/2,时间复杂度还是 O(n)

      在 存(追加),读(不涉及元素的变动)数据时,不管是哪个位置,时间复杂度都是O(1)

      所以,线性表适合存取数据元素

  • 线性表的优缺点

    优点

    • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
    • 可以快速的存取表中任意位置的元素

    缺点

    • 插入和删除移动大量元素
    • 当线性表长度变化较大时,难以确定存储空间的容量
    • 造成存储空间的“碎片”

线性表的链式存储结构

顺序存储结构的不足:最大的缺点就是插入和删除需要移动大量的元素

解决思路: 让每一个元素都知道下一个元素的位置

  • 线性表链式存储结构的定义

    为了表示每个数据元素ai与其直接后继数据元素的ai+1之间的逻辑关系,对数据元素ai来说,除了存储本身的信息之外,还需要存储其直接后继信息(存储其位置)。

    我们把 存储数据元素信息的域称为 数据域把存储直接后继元素位置的域称为 指针域指针域中存储的信息称为指针

    数据域 和 指针域 组成 一个 节点(Node)

    n 个节点组成链表,又称为线性表的链式存储结构,因此每个链表的节点中只包含一个指针域,又称为单链表(有这句话推导 双向链表)

    • 头指针:第一个节点的位置
    • 终点指针:为 NULL,
    • 头节点:有时为了方便对链表进行操作,会在单链表的第一个节点前附设一个节点,称为头节点。头节点的数据域不存储任何信息(也可以存储 线性表长度 等附加信息,头节点的指针域指向第一个节点的指针)
    • 头指针与头节点的异同

    头指针

    • 头指针是指链表指向第一个节点的指针
    • 头指针具有标识作用,所以常以头指针冠以链表的名字
    • 无论链表是否为空,头指针均不为空。头指针式是链表的必要元素

    头节点:

    • 头节点是为了操作的统一和方便而设立的,放在第一个元素节点之前,其数据域一般无意义(也可以存放链表的长度)
    • 有了头节点,对在第一元素节点前插入节点和删除节点,其操作和其他节点就统一了。
    • 头节点不一定是链表的必须要素
  • 单链表的读取

    算法思路:

    • 声明一个节点p指向链表第一个节点,初始化j从1开始
    • 当j < i时,就遍历链表,让p的指针向后移动,不断指向下一节点,j累加1
    • 若干链表末尾p为空,则说明第一个i元素不存在
    • 否则查找成功,返回节点p的数据

    可以看出,最坏情况的时间复杂度 是 O(n)

    其核心思想是工作指针后移,因此不方便使用for循环控制

  • 单链表的插入和删除

    插入算法思路:

    看图即可
    在这里插入图片描述

    删除算法思路:

    看图即可
    在这里插入图片描述

    所以,可以看出插入和删除时间复杂度为 O(1) (顶多三步)

    对于插入或删除数据越频繁的操作,单链表的优势就越明显

单链表结构与顺序存储结构的优缺点

比较存储分配方式时间性能空间性能
顺序存储结构用一段连续的存储单元一次存储存储线性表的数据元素查找:O(1) ,插入和删除:O(n)分配空间困难
链式存储结构用于组任意存储单元存放线性表元素查找:O(n) ,插入和删除:O(1)不需要考虑分配存储空间的问题
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-05 20:27:23  更:2021-07-05 20:28:09 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 9:17:43-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码