线性表

这是一篇关于线性表的思维导图，包括：定义和特点、线性表的类型定义(基本操作)、线性表的顺序表示和实现线性表的链式、表示和实现顺序表和链表的比较。

线性表

• 定义和特点
  • 定义
    • 线性表：有n(n≥0)个数据特性相同的元素构成的有限序列
    • 空表：线性表中元素的个数n(n≥0)定义为线性表的长度，当n=0时称之为空表
  • 特点
    • 1.存在唯一的一个被称作"第一个"的数据元素；
    • 2.存在唯一的一个被称作"最后一个"的数据元素；
    • 3.除第一个元素之外结构中的每个数据元素均只有一个前驱；
    • 4.除最后一个元素之外，结构中的每个数据元素均只有一个后继。
• 线性表的类型定义(基本操作)
  • InitList(&L) (构造一个空的线性表L)
  • DestoryList(&L) (销毁线性表L)
  • ClearList(&L) (将L重置为空表)
  • ListEmpty(L) (若L为空表，则返回true，否则返回false)
  • ListLength(L) (返回L中数据元素的个数)
  • GetElem(L,i,&e)
    • 初始条件：L存在，且1≤i≤ListLength(L)
    • 用e返回L中第i个数据元素的值
  • locateElem(L,e) (返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在，则返回值为0)
  • PriorElem(L,cur_e,&pre_e) (若cur_e是L的数据元素，且不是最后一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义)
  • NextElem(L,cur_e,&next_e) (若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义)
  • ListInsert(&L,i,e)
    • 初始条件：L存在，且1≤i≤ListLength(L)+1
    • 在L中第i个位置之前插入新的数据元素e，L的长度加1
  • TraverseList(L) (对线性表L进行遍历，在遍历过程中对L的每个节点访问一次)
• 线性表的顺序表示和实现
  • 顺序表示
    • 定义：用一组地址连续的存储单元依次存储线性表的数据元素
    • 特点：逻辑上相邻的数据元素，其物理位置也是相邻的
    • 存储结构：只要确定了存储线性表的起始位置，线性表中仁义数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的数据结构（通常用数组来描述）
  • 基本操作的实现
    • 初始化：构造一个空的顺序表；
    • 取值：根据指定的位置序号i，获取顺序表中第i个数据元素的值；
    • 查找：根据指定的元素e，查找顺序表中第1个值与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0；
    • 插入：在表的第i个位置插入一个新的数据元素e，使长度为n的线性表变成长度为n+1的线性表；
    • 删除：将表的第i个元素删去，使长度为n的线性表变成长度为n-1的线性表；
• 线性表的链式表示和实现
  • 单链表的定义和表示
    • 特点：用一组任意的存储单元存储线性表的数据元素
    • 节点：除了存储数据元素ai本身的信息之外，还需存储一个指示其直接后继的信息
    • 域
      • 数据域：存储数据元素信息的域
      • 指针域：存储直接后继存储位置的域;其中存储的信息称作指针或链
    • 头节点：在单链表的第一个节点之前附设一个节点
    • 增加头节点的作用
      • 便于首元节点的处理
      • 便于空表和非空表的统一处理
  • 循环链表
  • 双向链表
• 顺序表和链表的比较
  • 空间性能
    • 存储空间的分配
      • 顺序表的存储空间必须预先分配，元素个数有一定限制，易造成存储空间浪费或空间溢出现象
      • 链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制
    • 存储密度的大小
      • 不考虑顺序表中的空闲区，顺序表的存储空间利用率为1
      • 单链表的仅为0.5
  • 时间性能
    • 存取元素的效率
      • 顺序表是随机存取结构
      • 链表是一种顺序存取结构
    • 插入和删除操作的效率
      • 链表在确定插入和删除的位置后，无需移动数据，只需要修改指针，时间复杂度为O(1)
      • 顺序表进行插入和删除时，平均要移动表中近一半的节点，时间复杂度为O(n)
• 以下基本操作基于 线性表L已存在