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

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

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

线性表的抽象数据类型定义：线性表的数据对象集合为（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) (顶多三步)

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

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