[数据结构与算法]线性表的应用 —— 顺序表

线性表的应用 —— 顺序表

【线性表】

线性表是由n （n ≥0）个相同类型的数据元素组成的有限序列，它是最基本、最常用的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第1个元素，每个元素都有唯一的直接前驱；除了最后一个元素，每个元素都有唯一的直接后继。

线性表有两种存储方式：顺序存储和链式存储。
采用顺序存储的线性表被称为顺序表，采用链式存储的线性表被称为链表。

【顺序表】

顺序表是顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。在顺序存储方式中，元素存储是连续的，中间不允许有空，可以快速定位某个元素，所以插入、删除时需要移动大量元素。
根据分配空间方法的不同，顺序表可以分为静态分配和动态分配两种。

【静态分配】

在顺序表中，最简单的方法是使用一个定长数组data[]存储数据，最大空间为Maxsize，用length记录实际的元素个数，即顺序表的长度。这种用定长数组存储的方法被称为静态分配。

当采用静态分配的方法时，定长数组需要预先分配一段固定大小的连续空间，但是在运算过程中进行合并、插入等操作容易超过预分配的空间长度，并出现溢出。
可以采用动态分配的方法解决溢出问题。

【动态分配】

在程序运行过程中，根据需要动态分配一段连续的空间（大小为Maxsize），用elem记录该空间的基地址（首地址），用length记录实际的元素个数，即顺序表的长度。

采用动态分配方法时，在运算过程中如果发生溢出，则可以另外开辟一块更大的存储空间，用来替换原来的存储空间，从而达到扩充存储空间的目的。

顺序表的动态分配结构体定义：

【插入】

在顺序表中的第i 个位置之前插入一个元素e ，需要从最后一个元素开始，后移一位……直到把第i 个元素也后移一位，然后把e 放入第i 个位置

算法步骤：

1. 判断插入位置i 是否合法(1 ≤ i ≤ L.length + 1)，可以在第1个元素之前插入，也可以在第L.length + 1 个元素之前插入。
2. 判断顺序表的存储空间是否已满。
3. 将第L.length 至 第 i 个元素依次向后移动一个位置，空出第 i 个位置
4. 将要插入的新元素 e 放入 第 i 个位置
5. 顺序表长度 + 1，插入成功后返回 true。

[举个栗子]

在顺序表中的第5个位置之前插入一个元素9。

移动元素。从最后一个元素(下标：L.length - 1)开始后移 一位，移动过程：

插入元素。这个时候第 5 个位置就空出来了，将要插入的元素 9 放入第 5 个位置，表长 + 1。

[算法代码]

bool ListInsert_Sq(SqList &L , int i , int e){
	if(i < 1 || i > L.length + 1){
		return false; //i 值不合法
	}
	if(L.length == Maxsize){
		return false; //存储空间已满
	}
	for(int j = L.length - 1; j >= i - 1; j--){
		L.elem[j + 1] = L.elem[j]; // 从最后一个元素开始后移，直到第i个元素后移
	}
	L.elem[i - 1] = e; // 将新元素e 放入第 i 个位置
	L.length ++ ;// 表长 + 1
	return true; // 插入成功
}

[算法分析]

假设每个位置插入的概率均等，则顺序表中插入元素算法的平均时间复杂度为O (n)。

【删除】

在顺序表中删除第i 个元素时，需要把该元素暂存到变量e 中，然后从第i +1个元素开始前移……直到把第n 个元素也前移一位，即可完成删除操作。

[算法步骤]

1. 判断删除位置 i 是否合法(1 ≤ i ≤ L.length)
2. 将欲删除的元素保留在 e 中。
3. 将第 i + 1 至 第 n 个元素依次向前移动一个位置。
4. 表长 - 1，若删除成功 则返回 true。

[举个栗子：从顺序表中删除第5个元素]

移动元素。首先将待删除元素2暂存到变量e 中，以后可能有用，如果不暂存，则将被覆盖。然后从第6个元素开始前移一位。

表长 - 1。

[算法代码]

bool ListDelete_Sq(SqList &L , int i ,int &e){
	if(i < 1 || i > L.length){
		return false;   // i 值不合法
	}
	e = L.elem[i - 1];  //将欲删除的元素保留在e中
	for(int j = 1; j <= L.length - 1; j++){
		L.elem[j - 1] = L.elem[j];  //被删除元素之后的元素前移
	}
	L.length --;  //表长 - 1
	return true;
}

[算法分析]

假设每个元素删除的概率均等，则顺序表中删除元素算法的平均时间复杂度为O (n)。

【顺序表的优缺点】

• 优点
  操作简单，存储密度高，可以随机存取，只需O(1)的时间就可以取出第i 个元素。
• 缺点
  需要预先分配最大空间，最大空间数估计过大或过小都会造成空间浪费或溢出。进行插入和删除操作时需要移动大量元素。