线性表 - 数组

线性表

---

1. 数组

#ifndef __ARRAYLIST_H__
#define __ARRAYLIST_H__
#include <ostream> // ostream
#include <cstring> // memset

template <class T>
class ArrayList {
private:
	T* __array;

	size_t __capacity;

	size_t cur;

	const static size_t DEFAULT_LENGTH;
	/**
	 * 使用特定值n分配内存
	 * @param n 初始元素的个数
	 * @return ArrayList对象的引用
	 */
	ArrayList& create(size_t n);
	/**
	 * 使用默认值分配内存
	 * @return ArrayList对象的引用
	 */
	ArrayList& recreate();
	/**
	 * i<->j
	 * @param i
	 * @param j
	 */
	void swap(int i, int j);

public:
	/**
	 * 初始化(使用默认值)
	 *
	 */
	ArrayList();

	/**
	 * 初始化
	 *
	 * @param n 初始化元素的个数
	 */
	ArrayList(size_t n);
	/**
	 * 获取当前已经使用的数组大小
	 *
	 * @return cur
	 */
	size_t size();
	/**
	 * 获取分配的数组最大长度
	 *
	 * @return __capacity
	 */
	size_t capacity();
	/**
	 * 获取元素对应的下标(从前到后)
	 * @param t 待查找的元素
	 * @return 元素对应的下标, 或者-1(表示没有找到)
	 */
	long long indexOf(const T& t);
	/**
	 * 获取元素对应的下标(从后到前)
	 * @param t 待查找的元素
	 * @return 元素对应的下标, 或者-1(表示没有找到)
	 */
	long long lastIndexOf(const T& t);
	/**
	 * 获取下标对应的元素
	 * @param i 下标
	 * @throws Index out of length
	 * @return 如果没报错: 下标对应的元素
	 */
	T& at(size_t i);
	/**
	 * 添加新元素
	 *
	 * @param t 待添加的元素
	 */
	void add(const T& t);
	/**
	 * 插入元素
	 *
	 * @param i 待插入的下标
	 * @param t 待插入的元素
	 */
	void insert(size_t i, const T& t);
	/**
	 * 删除指定元素
	 *
	 * @param i 待删的元素的下标
	 * @throws Exception : Index out of range
	 * @return 被删除的元素
	 */
	T remove(size_t);
	/**
	 * 判断是否为空(没有元素)
	 * @return true如果为空, 否则false
	 */
	bool empty();
	/**
	 * 释放内存&指针置空
	 */
	~ArrayList();

	/**
	 * 对每一个元素做func操作
	 *
	 * @param func 消费函数
	 */
	void forEach(void (*func)(T));

	/**
	 * 判断是否相同
	 * @param al 需要判断的数组
	 * @return true 相同, 否则false
	 */
	bool equals(ArrayList<T>& al);
	/**
	 * 反转数组
	 */
	void reverse();
	/**
	 * 部分反转数组
	 * @param i 开始下标(包括)
	 * @param j 结束下标(包括)
	 */
	void reverse(int i, int j);

	friend bool operator==(ArrayList<T>& al1, ArrayList<T>& al2);

	friend bool operator!=(ArrayList<T>& al1, ArrayList<T>& al2);

	/**
	 * 将数组元素输出到标准流
	 * @param os 标准输出流对象
	 * @param al 数组对象
	 * @return 标准输出流对象
	 */
	template <class U>
	friend std::ostream& operator<<(std::ostream& os, const ArrayList<U>& al);
	/**
	 * 将数组元素输出到标准流
	 * @param os 标准输出流对象
	 * @param al 数组对象的指针
	 * @return 标准输出流对象
	 */
	template <class U>
	friend std::ostream& operator<<(std::ostream& os, const ArrayList<U>* al);
};

template <class T>
const size_t ArrayList<T>::DEFAULT_LENGTH = 8;

template <class T>
ArrayList<T>& ArrayList<T>::create(size_t n) {
	__capacity = n;
	cur = 0;
	__array = new T[n];
	memset(__array, 0, n * sizeof(T));
	return *this;
}

template <class T>
ArrayList<T>& ArrayList<T>::recreate() {
	T* a = new T[__capacity * 2];
	memset(a, 0, __capacity * 2 * sizeof(T));
	for (size_t i = 0, l = __capacity; i < l; i++) {
		a[i] = __array[i];
	}
	__capacity *= 2;
	delete[] __array;
	__array = a;
	return *this;
}
template <class T>
void ArrayList<T>::swap(int i, int j) {
	T tmp = this->__array[i];
	this->__array[i] = this->__array[j];
	this->__array[j] = tmp;
}

template <class T>
ArrayList<T>::ArrayList() {
	create(DEFAULT_LENGTH); // 不接收
}

template <class T>
ArrayList<T>::ArrayList(size_t n) {
	create(n);
}

template <class T>
size_t ArrayList<T>::size() {
	return cur;
}

template <class T>
size_t ArrayList<T>::capacity() {
	return __capacity;
}

template <class T>
long long ArrayList<T>::indexOf(const T& t) {
	for (size_t i = 0; i < cur; i++) {
		if (__array[i] == t)
			return i;
	}
	return -1ll;
}

template <class T>
long long ArrayList<T>::lastIndexOf(const T& t) {
	for (long long i = cur - 1; i >= 0; i--) {
		if (__array[i] == t)
			return i;
	}
	return -1ll;
}

template <class T>
T& ArrayList<T>::at(size_t i) {
	if (i >= __capacity || i < 0)
		throw "Exception : Index out of range!";
	return __array[i];
}

template <class T>
void ArrayList<T>::add(const T& t) {
	if (cur == __capacity)
		recreate();
	__array[cur++] = t;
}

template <class T>
void ArrayList<T>::insert(size_t i, const T& t) {
	if (cur >= __capacity)
		recreate();
	for (size_t k = cur; k > i; k--) {
		__array[k] = __array[k - 1];
	}
	__array[i] = t;
	cur++;
}

template <class T>
T ArrayList<T>::remove(size_t i) {
	if (i >= __capacity || i < 0)
		throw "Exception : Index out of range :(";
	T t = move(__array[i]); // 不能返回引用
	for (size_t k = i; k < cur - 1; k++) {
		__array[k] = __array[k + 1];
	}
	--cur;
	return t;
}

template <class T>
bool ArrayList<T>::empty() {
	return cur == 0 ? true : false;
}

template <class T>
ArrayList<T>::~ArrayList() {
	delete[] __array; // 还可以调用?
	__array = nullptr;
}

template <class T>
void ArrayList<T>::forEach(void (*func)(T)) {
	for (size_t i = 0; i < cur; i++) {
		func(__array[i]);
	}
}
template <class T>
bool ArrayList<T>::equals(ArrayList<T>& al) {
	if (this->cur != al.size())
		return false;
	for (size_t i = 0; i < this->cur; i++) {
		if (__array[i] != al.at(i))
			return false;
	}
	return true;
}
template <class T>
void ArrayList<T>::reverse() {
	reverse(0, cur);
}

template <class T>
void ArrayList<T>::reverse(int i, int j) {
	if (i >= j)
		return;
	swap(i, j);
	reverse(++i, --j);
}


template <class U>
std::ostream& operator<<(std::ostream& os, const ArrayList<U>& l) {
	if (l.__array != nullptr)
		for (size_t i = 0; i < l.cur; i++) {
			os << *(l.__array + i) << " ";
		}
	else
		os << "null ";
	return os;
}

template <class U>
std::ostream& operator<<(std::ostream& os, const ArrayList<U>* l) {
	if (l->__array != nullptr)
		for (size_t i = 0; i < l->cur; i++) {
			os << *(l->__array + i) << " ";
		}
	else
		os << "null ";
	return os;
}
#endif

2. 数组测试代码

#include <iostream>
#include "ArrayList.h"

using namespace std;

ArrayList<string>* al = nullptr;
ArrayList<string> al1;

void init() {
	al = new ArrayList<string>();
	cout << al->empty() << "\n";
	al->add("Hello");
	al->add("Tang");
	al->add("Quanwei");
	al->add(".");
	al->add("How's");
	al->add("everything");
	al->add("going");
	al->add("?");
	al->add(" :) ");
}
void testEquals() {
	al1.add("Hello");
	al1.add("Tang");
	al1.add("Quanwei");
	al1.add(".");
	al1.add("How's");
	al1.add("everything");
	al1.add("going");
	al1.add("?");
	al1.add(" :) ");
	cout << "al==al1 " << al->equals(al1) << "\n";
	al1.remove(1);
	cout << "al==al1 " << al->equals(al1) << "\n";
}
int main() {
	init();
	testEquals();
	cout << "forEach:\n";
	auto func = [](string x) -> void { cout << x << " "; };
	al->forEach(func);
	cout << "\n";
	cout << al << "\n";
	al->insert(0, "Hi");
	cout << al << "\n";
	al->insert(al->size() - 1, "Hi");
	cout << al << "\n";
	al->insert(al->size(), "Hi");
	cout << al << "\n";
	cout << al->indexOf("Hi") << "\n";
	cout << al->indexOf("Quanwei") << "\n";
	cout << al->lastIndexOf("Quanwei") << "\n";
	cout << al->lastIndexOf("Quanwe") << "\n";
	cout << al << "\n";
	try {
		cout << al->at(3) << "\n";
		cout << al->at(100) << "\n";
	}
	catch (const char* e) {
		cerr << e << '\n';
	}
	try {
		cout << "remove: " << al->remove(1) << '\n';
		cout << "remove: " << al->remove(2) << '\n';
		cout << "remove: " << al->remove(3) << '\n';
		cout << "remove: " << al->remove(103) << '\n';
	}
	catch (const char* e) {
		cerr << e << '\n';
	}
	cout << al << "\n";
	al->~ArrayList();
	cout << al << "\n";

	auto al1 = new ArrayList<int>();
	cout << al1;
	cout << "\n";
	cout << al << "\n";
	al->reverse();
	cout << al << "\n";


	return 0;
}