数据结构（1） 线性表-数组实现

线性表是最简单的数据结构，一般有数组实现和链式描述两种，数组实现可以用基础数组，也可以用vector等结构来实现。

数组本身限制是很多的，必须提前设置好数据类型和长度。

type arrayName [ arraySize ];//基础数组结构
double balance[10];//定义一个一维数组
double balance[5] = {1000.0, 2.0, 3.4, 7.0, 50.0};//在定义时一并赋值

//数组长度不能为变量，必须使用const
const int n = 3;
int a[n] = { 1,2,3 };
std::cout << a[0] << std::endl;

使用new方法实现动态数组，这是数组实现线性表的基础

int *psome = new int[10];
psome[0]=0;
psome[1]=1;
delete [] psome ;//创立动态数组一定要记得删除

有了动态数组的实现方法，我们就可以再进一步写出更改数组长度的函数

//shuzu.cpp
using namespace std;
template<class T>
void changeLength1D(T*& a, int oldLength, int newLength) {
	T* temp = new T[newLength];
	int number = fmin(oldLength, newLength);
	copy(a, a + number, temp);
	delete[]a;
	a = temp;
}
//shuzu.h
template<class T>
void changeLength1D(T*&, int, int);
//main.cpp
#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
using namespace std;
int main()
{   
	int* a = new int[5]{1,2,3,4,5};//必须是动态数组
	changeLength1D(a, 5, 3);
}

这段代码使用模板类以应对不同的变量类型，实现了一定的通用性。除此之外函数在接受参数时使用了引用的技巧， T*& a 的含义时获得指针的引用，a是一个指针，如果不通过引用，我们只能更改a指向的变量的数值，不能改变a的指向，这样就没法在后面删除a指向的数组再令a指向temp指向的数组了。通过指针的指针也能实现同样的效果。

template<class T>
void changeLength1D(T** a, int oldLength, int newLength) {
	T* temp = new T[newLength];
	int number = fmin(oldLength, newLength);
	copy(*a, *a + number, temp);
	delete[]*a;
	*a = temp;
}
int main()
{   
	int* a = new int[5]{1,2,3,4,5};
	changeLength1D(&a, 5, 3);
}

有了变长函数我们就可以开始定义arraylist类了

template<class T>
class arrayList {
public:
	arrayList(int initialcapacity = 10);
	arrayList(const arrayList<T>&);
	~arrayList(){delete []element;}
	bool empty() const { return listSize == 0; }
	int size() const { return listSize; }
	T& get(int theIndex) const;
	void arrayList<T>::erase(int);
	void arrayList<T>::insert(int, const T&);
protected:
	T* element;
	int arrayLength;
	int listSize;
};

构造函数：两个构造函数通过函数重载实现创建和复制功能

template<class T>
arrayList<T>::arrayList(int initialCapacity) {
	arrayLength = initialCapacity;
	element = new T[arrayLength];
	listSize = 0;
}

template<class T>
arrayList<T>::arrayList(const arrayList<T>& theList) {//使用引用来避免复制提高效率，const避免不小心修改
	arrayLength = theList.arrayLength;
	element = new T[arrayLength];
	listSize = theList.listSize;
	copy(theList.element, theList.element + listSize, element);
}

查找和获取指定位置的元素都很简单，删除和插入稍微复杂一些。删除需要把删除后的元素向左移，插入不仅要平移，还得提前判断一下长度够不够了。

template<class T>
void arrayList<T>::erase(int theIndex) {
	copy(element + theIndex + 1, element + listSize, element + theIndex);
	element[--listSize].~T();
}

template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement) {
	if (listSize == arrayLength) {
		changeLength1D(element, arrayLength, 2 * arrayLength);
		arrayLength *= 2;
	}
	copy_backward(element + theIndex, element + listSize, element + listSize + 1);//必须从最后一个开始平移
	element[theIndex] = theElement;
}

其他一些函数比如输出啊，检查啊啥的就不写了~