线性表的顺序存储
线性表的基本概念
- 线性表（Linear List）：由同类型数据元素构成有序序列的线性结构。
- 表中元素个数称为线性表的长度。
- 线性表没有元素（长度为0）时，称为空表。
- 表的起始位置称为表头。
- 表的结束位置称为表尾。
线性表的抽象数据类型描述
线性表的抽象数据类型描述
- 类型名称：线性表
- 数据对象集：线性表是n（>=0）个元素构成的有序序列（a1,a2,...,an），其中a1是表的第一个元素，也叫表头；an（n是下标）是表的最后一个元素（表尾）；a[i+1]称为a[i]的直接后继，a[i-1]称为a[i]的直接前驱。
- 操作集
- List MakeEmpth()：初始化一个空线性表L
- ElementType FindKth(int K,List L)：根据位序K，返回相应的元素
- int Find(ElementType X,List L)：在线性表L中查找X的第一次出现位置
- void Insert(ElementType X,int i,List L)：在位序i前插入一个新元素X
- void Delete(int i,List L)：删除指定位序i的元素
- int Length(List L)：返回线性表L的长度n
线性表的顺序存储实现
线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。
为什么需要Last？因为线性表的运算有插入和删除，因此表的长度是动态可变的，但由于当前线性表中实际元素个数不等于数组长度，所以需要用一个变量来记录当前线性表中最后一个元素在数组中 的位置（即下标），所以Last就是这个变量。那么线性表为空时Last=-1，线性表的当前表长为Last+1（因为Last是下标所以加1）。
主要操作实现
1. 初始化（建立空的顺序表）
首先动态分配表结构所需要的存储空间；
然后将Last置为-1，表示表中没有元素；
2. 查找
- 平均比较次数
查找成功的平均比较次数为(n+1)/2，最好的情况是1次就查找到，最坏的情况是最后一个数才是需要查找的即需要查找n次，求平均值就是平均比较次数。 - 时间复杂度：O(n)
- 查找的思路
顺序存储的线性表中，查找主要是指在线性表中查找与给定值X相等的数据元素。由于线性表的元素都存储在数组Data中，所以实际上是在数组里的顺序进行查找：从第一个元素起依次和X比较，直到找到一个与X相等的数据元素，返回它在顺序表中的存储下标；或者查遍整个表都没有与之相等的元素，则返回错误信息ERROR。
3. 插入
- 平均比较次数
在线性表顺序存储中的插入，平均移动次数为n/2，最好的情况就是插入到最后一个位置，一次都不需要移动，即移动次数为0，最坏的情况是插入到第一个位置，需要将所有项都向后移动，即需要移动次数为n，所以平均移动次数为n/2。 - 时间复杂度：O(n)
- 插入的思路
顺序表的插入就是在表的第i个位置上插入一个值为X的新元素，插入后使原长度为n的数组元素序列变为长度为n+1的序列。但插入位序为1时，表示插入到序列的最前端；为n+1时，表示插入到序列最后。所以思路是：将第i个位序后的所有元素都顺序向后移动，为新元素让出位置，然后将X置入空出的第i个位序，组合修改Last指针（相当于修改表长），使之仍然指向最后一个元素。注意：在向顺序表插入时需要将先检查表是否满了，在表满的情况下不能插入，否则产生溢出错误；要检查插入位序的合法性，这里i指的是元素序号而非数组中的下标，有效范围是1<=i<=n+1，n这是原表长；也需要注意数据的移动次序和方向。
4. 删除
- 平均比较次数
在线性表顺序存储中的删除，平均移动次数为(n-1)/2，最好的情况就是删除最后一项，即不需要向前移动位置，即移动次数为0，最坏的情况就是删除第一项，需要将第一项后面的所有项都向前移动，即需要移动n-1次，所以平均移动次数为(n-1)/2。 - 时间复杂度：O(n)
- 删除的思路
顺序表的删除运算是指将表中位序为i（1<=i<=n，n指的是表长度）从线性表中去掉，删除后使原表长为n的数组元素序列变成长度为n-1的数组序列。所以思路是：将要删除位序之后的元素向前移动，a[i]元素被a[i+1]覆盖（这里i指的是下标）；接着修改Last指针（相当于修改表长）使之仍然指向最后一个元素。注意：（1）检查要删除位序的合法性，要删除位序为i的元素，i的取值范围是1<-i<=n，否则该元素不存在；（2）但表为空时不能作删除，因为表空时Last的值为-1，条件（i<1||i>Last+1）也包括了对表空的检查；（3）删除指定位序为i的元素后，该数据已经不存在，如果需要使用，可先取出来，然后再做删除。
Java代码实现
/**
* 线性表顺序存储常用操作集实现
*
* @author lck100
*/
public class MyLinearList {
private Integer[] list;// 顺序表的存储空间
private int last;// 顺序表的最后一个元素的位置
private final int MAXSIZE;// 顺序表的最大长度
private MyLinearList(int maxSize) {
list = new Integer[maxSize];
this.last = -1;// 表示线性表为空
this.MAXSIZE = maxSize;// 线性表的最大长度
}
/**
* 根据给定的值X在线性表中查找指定元素，如果找到则返回其下标，否则返回-1
*
* @param value 要查询的指定值
* @return 如果找到返回其在表中的位置（下标），否则返回-1
*/
private int find(int value) {
int i = 0;
// 在表中循环遍历指定值是否与表中某项匹配，如果匹配则得到下标i
while (i <= last && list[i] != value) {
i++;
}
if (i > last) {
// 如果没有找到，返回-1
return -1;
} else {
// 如果找到，返回的是存储位置，下标
return i;
}
}
/**
* 根据给定的位序i和值newValue插入到表中
*
* @param newValue 需要插入的值
* @param i 给定的位序（不是下标）
* @throws Exception 抛出异常
*/
private void insert(int newValue, int i) throws Exception {
// 首先判断表空间是否已满
if (last == MAXSIZE - 1) {
throw new Exception("表空间已满，不可再插入！");
}
// 判断插入位序是否合法
if (i < 1 || i > last + 2) {
throw new Exception("位置不合法!");
}
// 将位序i之后的元素向后移动
for (int j = last; j >= i - 1; j--) {
list[j + 1] = list[j];
}
// 将值插入到表中
list[i - 1] = newValue;
// 修改last，使其仍然指向最后一个位置
last++;
}
/**
* 根据给定的位序删除表中的元素
*
* @param i 给定的位序（不是下标）
* @throws Exception 抛出异常
*/
private void delete(int i) throws Exception {
// 判断表是否为空，如果为空就不能进行删除
if (last == -1) {
throw new Exception("表为空，不能删除！");
}
// 判断删除位序是否合法
if (i < 1 || i > last + 1) {
throw new Exception("不存在第" + i + "个元素");
}
// 将要删除的元素位序之后的元素向前移动一位
for (int j = i; j <= last; j++) {
list[j - 1] = list[j];
}
// 将last减1，指向最后一个元素
last--;
}
/**
* 打印线性表中的所有数据
*/
private void print() {
for (int i = 0; i <= last; i++) {
System.out.print(list[i] + "\t");
}
System.out.println();
}
public static void main(String[] args) throws Exception {
MyLinearList linearList = new MyLinearList(10);
linearList.insert(22, 1);
linearList.insert(33, 2);
linearList.insert(44, 3);
linearList.print();
linearList.delete(2);
linearList.print();
linearList.delete(2);
linearList.print();
linearList.insert(55, 2);
linearList.print();
int i = linearList.find(55);
System.out.println(i);
linearList.insert(66, 1);
linearList.print();
linearList.insert(77, 1);
linearList.print();
}
}
控制台打印结果如下：
关于插入和删除的图解析：
