数组

数组基础

  从概念上说，数组就是把数据码成一排进行存放。

int main()
{
	int arr[10];
	for (int i = 0; i < 10; i++) {
		arr[i] = i;
	}

	int* arr2 = new int[10];
	for (size_t index = 0; index < 10; index++) {
		arr2[index] = index;
	}

	delete[] arr2;

	int scores[] = { 100,99,98 };

	for (auto score : scores) {
		cout << score << endl;
	}

	scores[1] = 66;

	for (size_t i = 0; i < sizeof(scores) / sizeof(scores[0]); i++) {
		cout << scores[i] << endl;
	}
	
	return 0;
}

  数组最重要的就是就是它的索引。索引可以有语义，也可以没有语义。数组最大的优点就是可以快速查询，直接用数组下标就可以找到元素，因此数组最好应用于“索引有语义”的情况，通俗的说就是我们最好知道我们要查什么。但也要注意并非所有有语义的索引都适用于数组，比如当我们要存储人员信息，索引是身份证号的话，需要为索引信息开辟大量的空间。

自己封装数组

  使用原生的数组会有很多限制，比如数组开辟了连续的空间，但只有很少的空间存储了信息，如果索引没有语义，那么那些没有信息的空间如何表示呢？还有如何向数组添加元素，如何删除元素等等。所以我们需要编写自己的动态数组类。

//动态数组，支持增删改查
template<typename T>
class Array
{
public:
	//构造函数传入数组容量capacity构造array
	Array(int capacity)
	{
		m_nCapacity = capacity;
		m_nSize = 0;
		m_arrData = new T[m_nCapacity];
	}

	//默认构造函数,默认容量为10
	Array()
	{
		m_nSize = 0;
		m_nCapacity = 10;
		m_arrData = new T[10];
	}

	~Array()
	{
		if (m_arrData) {
			delete[] m_arrData;
			m_arrData = nullptr;
		}
		m_nSize = 0;
	}

public:
	int GetSize() { return m_nSize; }
	int GetCapacity() { return m_nCapacity; }
	bool IsEmpty() { return m_nSize == 0; }

	//向指定的位置添加元素
	void Add(int index, T e)
	{
		assert(index >=0 && index <=m_nSize);

		//动态扩容，添加元素时如果size当前元素已经占满内存空间，则容量翻倍
		//此处使用翻倍策略，而不是加上一个常数
		//如果只是简单加一个固定常数，这个常数不好确定
		//很容易出现当前Capacity小但加了一个很大的常数，或当前Capacity很大却加了一个很小的常数
		//造成效率低或资源浪费
		if (m_nSize == m_nCapacity)
			Resize(2 * m_nCapacity);

		//index开始后面的元素全部后移
		for (int i = m_nSize - 1; i >= index; i--) {
			m_arrData[i + 1] = m_arrData[i];
		}
		m_arrData[index] = e;
		m_nSize++;
	}

	void AddLast(T e)
	{
		Add(m_nSize, e);
	}

	void AddFirst(T e)
	{
		Add(0, e);
	}

	//获取index位置的元素
	T Get(int index)
	{
		assert(index >= 0 && index < m_nSize);
		return m_arrData[index];
	}

	//更新数组元素
	void Set(int index, T e)
	{
		assert(index >= 0 && index < m_nSize);
		m_arrData[index] = e;
	}

	//判断数组中是否存在元素e
	bool Contains(T e)
	{
		for (int i = 0; i < m_nSize; i++) {
			if (m_arrData[i] == e)
				return true;
		}
		return false;
	}

	//查找元素，找到时返回索引，否则返回-1
	int Find(T e)
	{
		for (int i = 0; i < m_nSize; i++) {
			if (m_arrData[i] == e)
				return i;
		}
		return -1;
	}

	//删除index位置的元素，返回删除的元素
	T Remove(int index)
	{
		assert(index >= 0 && index < m_nSize);
		T ret = m_arrData[index];
		for (int i = index + 1; i < m_nSize; i++) {
			m_arrData[i - 1] = m_arrData[i];
		}
		m_nSize--;
		//m_arrData[m_nSize] = NULL; //这句可以不加，主要是为了清空垃圾值

		//动态缩减空间
		if (m_nSize == m_nCapacity / 2)
			Resize(m_nCapacity / 2);
		return ret;
	}

	int RemoveFirst()
	{
		return Remove(0);
	}

	int RemoveLast()
	{
		return Remove(m_nSize - 1);
	}

	//删除指定元素
	void RemoveElement(T e)
	{
		int index = Find(e);
		if (index != -1)
			Remove(index);
	}

	void Print()
	{
		assert(m_nSize > 0);
		cout << "Array:size=" << m_nSize << ",capacity=" << m_nCapacity << endl;
		cout << "[";
		for (int i = 0; i < m_nSize; i++)
		{
			cout << m_arrData[i];
			if (i != m_nSize - 1)
				cout << ",";
		}
		cout << "]" << endl;
	}

private:
	//扩容函数私有，不允许外部扩容
	void Resize(int newCapacity)
	{
		T* newData = new T[newCapacity];

		//先把旧数据拷贝过来
		for (int i = 0; i < m_nSize; i++) {
			newData[i] = m_arrData[i];
		}

		m_arrData = newData;
		m_nCapacity = newCapacity;
		newData = nullptr;
		delete[] newData;
	}
private:
	int m_nSize;	//实际存储的元素格式
	int m_nCapacity;	//数组空间最多可以装多少元素
	T* m_arrData;
};


int main()
{
	//Array myArr = 5;
	Array<int> *myArr = new Array<int>(3);
	myArr->AddLast(2);
	myArr->AddLast(3);
	myArr->AddFirst(1);
	myArr->Print();

	myArr->AddFirst(10);
	myArr->Print();

	myArr->RemoveFirst();
	myArr->Print();

	auto tmp1 = myArr->Get(1);

	bool b1 = myArr->Contains(6);
	myArr->Set(2, 6);
	b1 = myArr->Contains(6);

	if (myArr) {
		delete myArr;
		myArr = nullptr;
	}

	return 0;
}

时间复杂度分析