线性表

作者: Yix1a | 来源:发表于2017-08-15 18:11 被阅读8次

线性表的定义

零个或多个数据元素的有限序列。

a(i-1)是ai的直接前驱元素，a（i+1）是ai的直接后继元素
当线性表元素的个数为0时，称为空表
线性表的顺序存储结构
- 顺序存储定义
  线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
- 数据长度和线性表长度的区别
  - 数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不会变的。
  - 任意时刻，线性表的长度应该小于等于数组的长度。
- 地址计算方法
  公式 ai= a1 + (i-1)*c
  c是规定的存储单元。
顺序存储结构的插入和删除
- 获得元素操作

图片.png

插入操作

图片.png

删除操作

图片.png

线性表顺序存储结构的优缺点
- 优点
  无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
  可以快速地存取表中任一位置的元素
- 缺点
  插入和删除操作需要移动大量元素
  当线性表长度变化较大时，难以确定存储空间的容量
  造成存储空间的碎片

线性表的链式存储结构
- 顺序存储结构不足的解决办法
  链表
- 线性表链式存储结构定义
  为了表示每个数据元素ai与其直接后继元素a（i+1）之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息，我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域，指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）
  n个结点链结成一个链表，即线性表的链式存储结构，因为此链表的每个结点中包含一个指针域，所以叫做单链表。
  - 我们把链表第一个结点的存储位置叫做头指针。
  - 最后一直指针是NULL
  - 第一结点是头结点。
- 头指针与头结点的异同
  - 头指针
    头指针是指链表指向第一个结点（实际上是第二个，因为还有头结点）的指针，若链表有头结点，则是指向头结点的指针。
    头指针具有标识作用，所以常用头指针冠以链表的名字
    无论链表是否为空，头指针均不为空。头指针是链表的必要元素
  - 头结点
    头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义。
    有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
    头结点不一定是链表必须要素
单链表的读取

图片.png

单链表的插入和删除
- 单链表的插入

图片.png

单链表的删除

图片.png

对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。
单链表的整表创建
- 头插入

图片.png

尾插法

图片.png

单链表的整表删除

图片.png

单链表结构与顺序结构优缺点
- 存储分配方式
  - 顺序结构用一段连续的存储单元依次存储线性表的数据元素
  - 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
- 时间性能
  - 查找
    - 顺存储结构O(1)
    - 单链表O(n)
  - 插入和删除
    - 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
    - 单链表在线出某位置指针后，插入和删除时间为O(1)
  - 空间性能
    - 顺序存储结构需要预分配存储空间，分大了，浪费，分小易溢出。
    - 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
静态链表