线性表

线性表是具有相同特征的数据元素的一个有限序列。

特征：

  • 只有一个开头，一个结尾
  • 元素具有相同特征

顺序存储结构

相当于数组的模式

顺序存储结构存在的问题：

  • 存储空间分配不灵活
  • 运算的空间复杂度高

链式存储结构

在每个元素内存储与它相邻的两个元素的位置

线性表的操作（ADP）

  • 初始化线性表
  • 销毁线性表
  • 清空线性表
  • 判断线性表是否为空
  • 获取表长度
  • 获取表的某个元素
  • 定位元素的位置
  • 获取当前元素的前驱/后驱
  • 插入元素
  • 删除元素
  • 遍历元素

线性表的顺序存储结构表示

顺序存储：

把逻辑上相邻的结构存储到物理上相邻的存储单元

顺序存储的特点：

  • 占用连续的空间，中间不得出现空位置
  • 根据某个元素的位置可以推出其他元素的位置

顺序存储结构的定义：

  • 最大长度
  • 数组长度
  • 元素

顺序存储结构操作方法：

  • 初始化线性表
    1. 分配存储空间，分配失败返回错误
    2. 设置length为0
  • 销毁线性表
    1. 释放存储空间，若数组不存在则返回-1
  • 清空线性表
    1. 设置length为0
  • 判断线性表是否为空
    1. length==0?return true:return false;
  • 获取表长度
    1. 返回length成员
  • 获取表的第i个元素
    1. 判断i是否合理
    2. 返回L.elem[i-1];
  • 定位元素x的位置
    1. for(m,index in L){if(m=x){return index}};return -1;
    2. 平均查找长度就是期望E(x);
  • 插入元素
    1. 判断插入位置是否合法
    2. 判断空间是否已满
    3. 将第n到第i个位置的元素从后到前依次位移来腾出空间（这一步占据了最多的时间）
    4. 将新元素放在第i个位置
    5. 表长加一
  • 删除元素
    1. 判断删除位置是否合法
    2. 将第n到第i个位置的元素从前到后依次位移（这一步占据了最多的时间）有需要可以用一个变量接受被删除的元素，在之后作为返回值
    3. 表长减一
  • 遍历元素