動态擴容數組（C++）

以下代碼均在VS2017下調試通過

//sort.h 快排，用于數組内元素排序
#pragma once
#include<iostream>
using namespace std;
//快速排序的内部子表劃分
template<typename T>
void partition(T* &array, int s, int t, T &cutpoint)
{
	T x = array[s];
	int i = s, j = t;
	while (i != j)
	{
		while (i < j && array[j] > x)
			j--;
		if (i < j)
		{
			array[i] = array[j];
			i++;
		}
		while (i < j && array[i] < x)
			i++;
		if (i < j)
		{
			array[j] = array[i];
			j--;
		}
	}
	array[i] = x;
	cutpoint = i;
}
//快速排序
template<typename T>
void quick_sort(T* &array, int s, int t)
{
	int i;
	if (s < t)
	{
		partition(array, s, t, i = 0);
		quick_sort(array, s, i - 1);
		quick_sort(array, i + 1, t);
	}
}

//Array.h  動态擴容數組類（模闆）
#pragma once
#include<iostream>
#include<cmath>
#include"Sort.h"
using namespace std;



//動态擴容數組
template <class T>
class Array
{
private:
	int size;
	int maxsize;
public:
	T*  element;
public:
	Array(int maxsize_=3)
	{
		size = 0;
		maxsize = maxsize_;
		element = new T[maxsize];
	}
	~Array()
	{
		delete[]element;
	}
	
	int & operator[](int loc)
	{
		int i;
		i = this->element[loc];
		return i;
	}
	int get_size() { return size; }
	int get_maxsize() { return maxsize; }
	void resize();
	void append(T t);							//增
	void remove(int loc);						//删
	void revise(int loc, T t);					//改
	T	 get_element(int loc);					//查
	void concat(Array<T>* array1, Array<T>* array2, Array<T>* &array3);	//合并兩個數組						
};

template<class T>
void Array<T>::resize()
{
	if (size >= maxsize)
	{
		T* newarr;
		int new_maxsize = ceil(maxsize + maxsize / 2);
		newarr = new T[new_maxsize];
		for (int i = 0; i < maxsize; i++)
		{
			newarr[i] = element[i];
		}
		delete[]element;
		element = newarr;
		maxsize = new_maxsize;
	}
}

template<class T>
void Array<T>::append(T t)
{
	if (size >= maxsize)
		resize();
	element[size++] = t;
}

template<class T>
void Array<T>::remove(int loc)
{
	if (loc >= size)
	{
		cout << "Error, out of array valid range!";
		return;
	}
	else
	{
		if (loc = size - 1)
		{
			size--;
		}
		else
		{
			for (int i = loc; i < size - 1; i++)
			{
				element[i] = element[i++];
			}
			size--;
		}
	}
}

template<class T>
void Array<T>::revise(int loc, T t)
{
	if (loc >= size)
	{
		cout << "Error, out of array valid range!";
		return;
	}
	else
	{
		element[loc] = t;
	}
}

template<class T>
T Array<T>::get_element(int loc)
{
	if (loc >= size)
	{
		cout << "Error, out of array valid range!";
		return -1;
	}
	else
	{
		return element[loc];
	}
}

template<class T>
void Array<T>::concat(Array<T>* array1, Array<T>* array2, Array<T>* &array3)
{
	int m = array1->get_size(), n = array2->get_size();
	if (m == 0 && n == 0)
		return;	//如果都為空，則任意傳回一個
	quick_sort(array1->element, 0, m - 1);
	quick_sort(array2->element, 0, n - 1);
	if (m == 0)
		array3 = array2;
	if (n == 0)
		array3 = array1;
	int i = 0, j = 0;
	while(i < m && j < n)
	{
		if (array1->get_element(i) >= array2->get_element(j))
		{
			array3->append(array2->get_element(j));
			j++;
		}
		else
		{
			array3->append(array1->get_element(i));
			i++;
		}
	}
	while (i < m)
	{
		array3->append(array1->get_element(i));
		i++;
	}
	while(j<n)
	{
		array3->append(array2->get_element(j));
		j++;
	}
	//return array3;
}

//main.h 主函數所在檔案
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<ctime>
#include"Sort.h"
#include"Array.h"
using namespace std;


int main()
{
	Array<int> *array = new Array<int>(3);

	//初始指派
	srand((unsigned)time(NULL));
	for(int i=0 ; i < 10 ; i++)
	{
		array->append(rand() % 100);
	}
	for (int i = 0; i < 10; i++)
	{
		cout << (*array)[i]<< "\t";
	}


	cout << endl<<"修改後:" << endl;
	array->revise(0, 100);
	for (int i = 0; i < 10; i++)
	{
		cout << (*array)[i] << "\t";
	}

	cout << endl << "删除後" << endl;
	array->remove(9);
	for (int i = 0; i < 9; i++)
	{
		cout << (*array)[i] << "\t";
	}


	Array<int>* array2 = new Array<int>(5);
	array2->append(10);
	array2->append(100);
	array2->append(1000);
	array2->append(33);
	Array<int> *array3=new Array<int>(10);


	cout <<endl<< "合并後:" << endl;
	array3->concat(array2, array, array3);
	cout << endl;
	for (int i = 0; i < array3->get_size(); i++)
	{
		cout << (*array3)[i] << "\t";
	}


	delete array;
	delete array2;
	delete array3;
	system("pause");
	return 0;
}