数据结构与算法 --- 2.线性表

线性表的概念

• 线性表简称表，是零个或多个元素的有穷序列，通常可 以表示成 k0，k1, ...，kn-1(n ≥ 1)

  • 表目:线性表中的元素(可包含多个数据项，记录)
  • 索引(下标):i 称为表目 ki 的“索引”或“下标”
  • 表的长度:线性表中所含元素的个数 n
  • 空表:长度为零的线性表 ( n = 0 )

• 线性表特点:

  • 操作灵活，其长度可以增长、缩短
  • 有一个唯一的开始结点，它没有前驱，有一个唯一的直接后继
  • 一个唯一的终止结点，它有一个唯一的直接前驱，而没有后继
  • 其它的结点皆称为 内部结点，每一个内部结点都有且仅有一个唯一的直 接有前驱，也有一个唯一的直接后继
  • 均匀性:虽然不同线性表的数据元素可以是各种各样 的，但对于同一线性表的各数据元素必定具有相同的 数据类型和长度
  • 有序性:各数据元素在线性表中都有自己的位置，且 数据元素之间的相对位置是线性的

• 按复杂程度划分

  • 简单的:线性表、栈、队列、散列表
  • 高级的:广义表、多维数组、文件......

• 按访问方式划分

  • 直接访问型 (direct access)
  • 顺序访问型 (sequential access)
  • 目录索引型 (directory access)

• 按操作划分

  • 线性表

    • 所有表目都是同一类型结点的线性表
    • 不限制操作形式
    • 根据存储的不同分为:顺序表，链表

  • 栈 (LIFO, Last In First Out)

    • 插入和删除操作都限制在表的同一端进行

  • 队列 (FIFO, First In First Out)

    • 插入操作在表的一端， 删除操作在另一端

线性表包括三个方面，线性表的逻辑结构，线性表的存储结构，线性表运算

• 线性表逻辑结构主要属性包括

  • 线性表的长度
  • 表头 (head)
  • 表尾 (tail)
  • 当前位置 (current position)

• 线性表的存储结构

  • 顺序表
    • 按索引值从小到大存放在一片相邻的连续区域
    • 紧凑结构，存储密度为 1
  • 链表
    • 单链表
    • 双链表
    • 循环链表

• 线性表的运算

  • 建立线性表
  • 清除线性表
  • 插入一个新元素
  • 删除某个元素
  • 修改某个元素
  • 排序
  • 检索

顺序表

也称向量，采用定长的一维数组存储结构

• 主要特性
  • 元素的类型相同
  • 元素顺序地存储在连续存储空间中，每一个元素有唯一
    的索引值
  • 使用常数作为向量长度

读写其元素很方便 ，通过下标即可指定位置,只要确定了首地址，顺序表中任意数据元素都可以随机 存取

• 在顺序表中每个位置上插入和删除元素的 概率相同时间代价为O(n)

链表(linked list)

通过指针把它的一串存储结点链接成一个链,存储结点由两部分组成:数据域 + 指针域(后继地址)

• 链表根据链接方式和指针多寡分类
  • 单链 时间复杂度O(n) 查找复杂度O(n)+插入复杂度O(1)
  • 双链 为弥补单链表的不足,而产生双链表. 单链表的 next 字段仅仅指向后继结点，不能有效地找
    到前驱, 反之亦然 增加一个指向前驱的指针
  • 循环链. 将单链表或者双链表的头尾结点链接起来，就是一个循 环链表 不增加额外存储花销，却给不少操作带来了方便,从循环表中任一结点出发，都能访问到表中其他结点

线性表实现方法的比较

• 顺序表的主要优点

  • 没有使用指针，不用花费额外开销
  • 线性表元素的读访问非常简洁便利

• 链表的主要优点

  • 无需事先了解线性表的长度
  • 允许线性表的长度动态变化
  • 能够适应经常插入删除内部元素的情况

总结:顺序表是存储静态数据的不二选择,链表是存储动态变化数据的良方

• 顺序表

  • 插入、删除运算时间代价 O(n)，查找则可常数时间完成
  • 预先申请固定长度的连续空间
  • 如果整个数组元素很满，则没有结构性存储开销

• 链表

  • 插入、删除运算时间代价 O(1)，但找第i个元素运算时间
    代价 O(n)
  • 存储利用指针，动态地按照需要为表中新的元素分配存
    储空间
  • 每个元素都有结构性存储开销

应用场合的选择

• 顺序表不适用的场合

  • 经常插入删除时，不宜使用顺序表
  • 线性表的最大长度也是一个重要因素

• 链表不适用的场合

  • 当读操作比插入删除操作频率大时，不应选择链表
  • 当指针的存储开销，和整个结点内容所占空间相比其 比例较大时，应该慎重选择