[C++知识库]学习笔记——顺序表（C++表述）

在学学生，可能存在不足与错误地方，如有发现还请批评指正。

顺序表定义——什么是顺序表

顺序表是利用连续的物理存储单元依次存储相同数据类型的有限序列。简称表。
顺序表长度即是数据元素的个数。

顺序表实现——类的声明

template<class T>
class SeqList {
protected: 
	T* head; 	//指向数组头元素
	int length; 	//数组当前长度
	int max_length; 	//最大表长度
public: 
	SeqList(); 	//创建一个空的顺序表
	virtual ~SeqList(); 	//析构函数
	T* reSetLength(); 	//设置新的数组大小。当位置不足时默认加10
public: 
	bool empty(); 	//表是否为空
	bool full(); 	//表是否满
	bool add(const T& element); 	//添加元素
	bool insert(const int index, const T& element);//插入元素至index
	T* find(const int index); 	//查找对应下标数据
	int find(const T& element); 	//查找与element数据一致的位置
	bool remove(const int index); 	//删除对应下标的位置
}; 

方法实现

构造函数

我们可以发现，在顺序表属性当中，我们发现有一个指向一维数组的指针head变量.
所以我们得到一个思路：
使用一维数组实现顺序表，表中元素（表项）会占用一段连续的存储空间。这样子所得到的表中表项的逻辑顺序与物理顺序一致。

由于日后顺序表所需要存储的存储空间未知，采取动态分配将有利于优化空间使用，不足时可以扩充空间。

template<class T>
SeqList<T>::SeqList() {
	head = new T[100];  	//创建动态数组
	length = 0; 	//当前长度为0
	max_length = 100; 	//最大长度为100
}

添加元素

我们创建了一个顺序表，我需要向这个顺序表添加元素。我们添加一个元素的思维是判断是否有空的位置，没有就扩充空间。

template<class T>
bool SeqList<T>::add(const T& element) {
	if(head == nullptr) {
		head = new T[100]; 
		length = 0; max_length = 100; 
	}
	if(full() == true) {
		T* temp = reSetLength(); 	//扩充空间
		if(temp == nullptr) { 	//扩充失败
			return false; 
		}
	}
	head[length] = element; //添加元素
	length++; 
	return true; 
}

设置表大小

当表空间满了的时候，对空间进行扩充，以方便后面可以方便添加数据。

template<class T>
T* SeqList<T>::reSetLength() {
	int i = 0; 
	T* temp = new T[max_length + 10]; 	//创建新的数组
	if(temp == nullptr) {
		return nullptr; 	//如果创建新数组失败，返回空
	}
	for(i = 0; i < max_length; i++) {
		temp[i] = head[i]; 	//移动数据至新的数组
	}
	delete[] head; 	//删除原来数组
	max_length += 10; 	//设置最大长度
	return temp; 
}

插入元素

插入元素是一个很重要的方法。这里基于给定元素下标将新元素插于此元素后。

template<class T>
bool SeqList<T>::insert(const int index, const T& element) {
	index--; //传入的下标是“自然下标”，即第一、二个元素，而不是数组下标
	if(index < 0 || index >= max_length) {
		return false; 
	}
	else {
		if(full() == true) {
			T* temp = reSetLength(); 	//扩充空间
			if(temp == nullptr) {
				return false; 
			}
		}
		int i = length - 1; 	//指向最后的一个元素 
		for(i = length - 1; i >= index; i--) { 	//移动index以及之后的元素
			head[i + 1] = head[i]; 
		}
		head[index] = element; 	//添加元素
		length++; 
		return true; 
	}
}

删除元素

删除元素只需要将需要删除的对应 index 下标后的元素依次往前移即可。

template<class T>
bool SeqList<T>::remove(const int index) {
	index--;
	if(index < 0 || index >= max_length) { 	//判断下标是否合法
		return false; 
	}
	int i = index; 
	for(i = index; i < length; i++) { 	//移动index后面的元素
		head[i] = head[i + 1]; 
	}
	length--; 
	return true; 
}

查找元素

查找元素只需一一对比即可，当然你也可以添加一个重载，使表项与样本间进行某些特殊的比较。

virtual int find(T&, bool (*comparator)(const T&, const T&)); 
//含比较函数的find方法

template<class T>
T* SeqList<T>::find(const int index) {
	index--; 
	if(index < 0 || index >= max_length) {
		return nullptr; 
	}
	return head + index; 
}

template<class T>
int SeqList<T>::find(const T& element) {
	int i = 0; 
	for(i = 0; i < length; i++) {
		if(element == head[i]) {
			return i; 	//找到了返回下标
		}
	}
	return -1; 	//没找到与样本一致的表项，返回-1
}

检查是否为空

当当前数组没有任何元素时，即顺序表中属性 length 等于0或者 head 属性指向 nullptr.

template<class T>
bool SeqList<T>::empty() {
	if(head == nullptr || length == 0) {
		return true; 
	}
	else {
		return false; 
	}
}

检查是否为满

以初始化表容量为100为例子，当已经装满时，full()方法应该返回为true，未满或者 head 指向nullptr时，方法返回false.

template<class T>
bool SeqList<T>::full() {
	if(head == nullptr || length >= max_length) {
		return true; 
	}
	else {
		return false; 
	}
}

析构函数

template<class T>
SeqList<T>::~SeqList() {
	if(head != nullptr) {
		delete[] head; 
	}
}

插入与删除两个方法的分析

关于插入

在插入算法中，我们采用的是将需要插入的元素插入至 index 位置，所以对具有 $n$ 个 表项的顺序表，再插入一个就是具有$n+1$个表项假设每个表项被插入的概率等价。
有每个元素被插入位置的概率
$p_i=\frac{1}{n+1}$
对插入相应位置，每一项需要移动的次数为
$E_i=n?i+1$
所以**数学期望（平均移动次数）**为：
$E_{(}ins)={\Sigma }_{i=1}^n(p_i{E}_i)=\frac{n}{2}$
所以，插入平均移动次数为$\frac{n}{2}$，平均时间复杂度为 $O(n)$.

关于删除

在删除算法中，我们采用的是将需要删除的元素之后的元素不断向前移动一位，所以对具有 $n$ 个 表项的顺序表，假设每个表项被删除的概率等价。
有每个元素被删除的概率
$p_i=\frac{1}{n}$
对删除相应位置，需要移动
$E_i=n?i$
所以**数学期望（平均移动次数）**为：
$E_{(}ins)={\Sigma }_{i=1}^n(p_i{E}_i)=\frac{n?1}{2}$
所以，插入平均移动次数为$\frac{n?1}{2}$，平均时间复杂度为 $O(n)$.

顺序表的特点

1. 特点1：数据元素类型相同。顺序表中的数据元素类型同一。
2. 特点2：数据元素个数有限。在顺序表中数据元素个数具有有穷性。
3. 特点3：数据元素具有顺序。在线性表中除最后一个元素外，其他元素只有一个后继；除第一个元素外，其他元素只有一个前驱。
4. 特点4：存储利用率高。由于顺序表使用了一维数组实现，占用了连续的内存，无需额外内存来存储逻辑信息。
5. 特点5：存取速度快。可以很方便的随机访问任一结点（表项）。

顺序表的优与劣

优点

1. 存储利用率高。由于顺序表使用了一维数组实现，占用了连续的内存，无需额外内存来存储逻辑信息。
2. 存取速度快。可以很方便的随机访问任一结点（表项）。

缺点

1. 插入与删除不方便。插删操作平均需要移动一半的元素，插删麻烦，不适合运用于插删操作频繁的数据结构。
2. 难以应对空间变化较大的情况。若原先就采用静态分配的方法，若需要再次扩充空间时就无法完成；若使用远低于原先分配的内存时又会造成内存的浪费；若采用动态分配的方法管理内存，一旦需要更大的内存空间时，又需要花一定时间迁移数据，时间开销大。