[Day05]程序菜鸟自学C++资料结构演算法 – 阵列Array List实作之二

前言：昨天介绍了如何建立专案、建立空阵列、读取存放资料及修改储存空间，今天要继续实作阵列的其他功能。

编写set()函式修改阵列中的资料。

可以看到阵列的原本第二个资料B已修改成E。

编写insert()函式插入新的资料在阵列之中。

可以看到在阵列的第三个位置中插入F。

接着编写remove()函式移除阵列中的资料

可以看到原本在第三个位置的F被移除

编写pop_back删除最後一个元素。

可以看到在最後一个位置的元素D被移除了

边写remove_front()函式删除第一个元素。

第一个位置的A已成功删除。

编写find()函式查找元素所在的位置。

假设要查找C的位置，结果如下。

那如果阵列有多笔相同的资料，要怎麽查找？
写一个for回圈，在新增一个变数p存取A的位置，每遇到一次A就印出位置一次，直到阵列结束，就可以罗！

今日小结：呼~阵列的实作就先到这边告一段落，其实还有很多应用，但是要全部介绍完恐怕会花上太多篇幅，有机会再跟大家分享。虽然这些实作都算是基础，不过以初学者来说要完全理解也不是甚麽轻松事(包括我(≧д≦ヾ))，虽然程序码看起来很复杂，但只要考清楚阵列在位置上的变动，就可以比较快理解，好了，明天就来介绍阵列的兄弟「链结串列」！

template<typename T> //将资料型态参数化的功能，代号为T
class SqlList {
	T* data; //指针变量
	int capacity, n; //分配空间(整数int)，n表示数据元素的个数，先设为0

public:
	SqlList(int cap = 3) { //创建一个空的SqlList(不包含任何元素)
		data = new T[cap]; //给予数据成员让其初始化 
		if(!data) throw "SqlList内存空间分配失败"; //检查空间是否成功分配{capacity = 0; n = 0; return}
		capacity = cap; n = 0;
	}
	bool get(int i, T& e) { //读取，把数据元素放入引用变量e内
		if (i < 1 || i > n) 
			return false;
		e = data[i - 1]; 
		return true;
    }
	bool set(int i, T e) { //修改，把i资料修改成e
		if (i < 1 || i > n) 
			return false;
		data[i - 1] = e; 
		return true;
	}
	bool push_back(T e) { //编写push_back(放在阵列最尾端)函示来存取阵列中的资料
		if (n==capacity) {
			if (!realloc()) {
				return false;
			}
		 }
		data[n] = e;
		n++;
		return true;
	}
	int size() { //返回当前资料的个数
		return n;
	}
	bool insert(int i, T e) { //在i号位置插入资料e
		if (i < 1 || i > n + 1) return false;
		if (n == capacity) 
			if (!realloc()) return false;
			
		for (int j = n; j >= i; j--) {
			data[j] = data[j - 1];
		}
		data[i - 1] = e;
		n++;
		return true;
	}
	bool remove(int i) { //删除第i号元素
		if (i < 1 || i > n) return false;
		
		for (int j = i+1; j <= n; j++) {
			data[j - 2] = data[j - 1];
		}
		n--;
		return true;
	}
	bool pop_back() {
		if (n == 0) return false;
		n--;
		return true;
	}
	bool remove_front() {
		for (int j = 2; j <= n; j++) {
			data[j - 2] = data[j - 1];
		}
		n--;
		return true;
	}
	int find(int pos,T e) { //查找元素所在的位置，从pos(重新定义)位置开始找
		for (int i = pos; i <= n; i++)
			if (data[i-1] == e) {
				return i;
			}
		return 0;
	}
private: //分配供多空间给阵列
	bool realloc() {
		T* p = new T[2 * capacity];
		if (!p) return false;
		for (int i = 0; i < n; i++) 
			p[i] = data[i];
		delete[] data;
		data = p;
		capacity *= 2;
		return true;
	}
	
};
#include<iostream>
template<typename T>
void print(SqlList<T>& L) { //编写print函示
	T e; //数据元素类型e为T类型
	for (int i = 1; i <= L.size(); i++) {
		L.get(i, e);
		std::cout << e << " ";
	}
	std::cout << std::endl;

}

#include<iostream>
int main() { //编写主程序
	SqlList<char> list; //建立SqlList的变量，数据元素类型设为字元(char)
	char ch;
	if (!list.get(1, ch))std::cout << "没有找到 \n"; //箭头方向"<<"是一个运算子。
	else std::cout << ch << std::endl;  //endl就是这一行到这边结束换下一行(只能输出，不能输入)。
	list.push_back('A'); print(list);
	list.push_back('B'); print(list);
	list.push_back('C'); print(list);
	list.push_back('D'); print(list);
	list.set(2, 'E'); print(list);
	list.insert(3, 'F'); print(list);
	list.remove(3); print(list);
	list.pop_back(); print(list);
	list.remove_front(); print(list);

	int i = list.find(1, 'C');
	if (i >= 0) std::cout << "查找成功，位置是：" << i << std::endl;

	list.insert(2, 'A'); 
	list.push_back('A'); print(list);

	
	for (int p = 1; p < list.size();) {
		int i = list.find(p, 'A');
		if (i >= 0) std::cout << "查找成功，位置是：" << i << std::endl;
		p = i + 1;
	}
	
}