线性表

  1. 定义:线性表简称表,包含零个或多个元素的有序序列
  2. 属性
    • 表目 == 记录
    • 索引 == 下标
  3. 二元组B = (K,R) , K = {a0,a1,a2,…an-1} R = {r}
    具有反对称性 , a1是a2的(直接)前驱,a2是a1的(直接)后继
  4. 特点
    • 均匀性: 元素类型相同
    • 有序性
  5. 线性结构分类
    • 简单:线性表、栈、队列、散列表
    • 难:广义表,多维数组、文件
  6. 访问方式
    • 直接访问
    • 间接访问
    • 目录访问
  7. (线性)表的三个方面
    • 逻辑结构
    • 存储结构
    • 运算

线性表的逻辑结构

  1. 属性:长度、表头、表尾、位置
  2. 有存储结构可分为
    • 顺序表(是由数组实现的)
    • 链表
  3. 按操作可分为
    • 队列
  4. 按运算
    清除操作、插入操作、删除操作等

顺序表

  1. 亦称向量,由数组实现
  2. 特性
    • 元素相同
    • 顺序、连续储存
    • 元素地址公式 Loc(i) = Loc(i0) + c * i 其中 (c = sizeof(ELEM));
  3. 顺序表插入与删除的算法分析
    • 插入移动次数: n - i
    • 删除移动次数:n - i - 1
未完待续

谢谢访问