线性表

线性表1

• 线性表的定义
  • 线性表（list）：由零个或多个数据元素组成的有限序列，也称为有序表
    • 序列：先来后到
    • 第一个无前驱，最后一个无后继

• 抽象数据类型

  • 一组性质相同的值的集合以及定义在此集合上的一些操作的总称

• C语言中数据类型可分为两类

  • 原子类型
  • 可以不再分解的基本类型，如整型、浮点、字符
  • 结构类型
  • 若干个类型组合而成

• 抽象数据类型标准格式
  • ADT 抽象数据类型名
  • DATA 数据元素之间逻辑关系的定义
  • Operation 操作
  • endADT

线性表2

• 定义
  • ADT
    • 线性表（List）
  • Data
    • 数据对象集合为{a1,a2,…,an} 每个元素为DataType
    • 除最后一个元素都有后继 除第一个元素都有前驱
  • Operation
    • InitList(*L):建立空表
    • ListEmpty(L):判断是否为空
    • ClearList(*L):清空线性表
    • GetElem(L,i,*e):返回第i个位置的元素给e
    • LocateElem(L,e):查找和e相等的元素，有则返回位置，没有则返回0
    • ListInsert(*L,i,e):第i个位置插入新元素e
    • ListDelete(*L,i,e):删除第i个位置的元素，用e返回其值
    • ListLength(L):返回L的元素个数

线性表3

• 线性表的物理存储结构
  • 顺序存储结构
    • 连续的存储单元依次存储数据元素
    • 预留一定空间
    • 封装需要三个属性
      • 存储空间的起始位置
      • 线性表的最大存储容量
      • 线性表的当期长度
    • 第i个数据元素位置可随时推算出:$LOC(ai) = LOC(a1) + (i-1)*c$
    • 用c表示每个数据元素所占大小
    • 存储时间性能为$O(1)$,称为随机存储结构
    • 获得元素操作
      • 只需要返回第i-1下标的值就可以
      • Status是一个整型，返回0代表ERROR，返回1代表OK
    • 插入元素操作
      • 检查表是否满了
      • 检查i是否在范围内