C++實作簡單順序表

          順序表是在計算機記憶體中以數組的形式儲存的線性表，是指用一組位址連續的存儲單元依次存儲資料元素的線性結構。即線性表采用順序存儲的方式存儲就稱之為順序表。在C語言中，我們通過建立一個結構體的方式來實作了順序表，在C++中可通過建立一個類的形式來建立一個順序表。

直接來看代碼：

#include <iostream>
using namespace std;
#include <assert.h>

typedef int DataType;
class SeqList
{
public:
	// 思考兩種方式的優缺點 
	SeqList(DataType* array, size_t size)//構造函數
		: _array(new DataType[size])
		, _capacity(size)
		, _size(size)
	{
		// 1、循環逐個搬移-缺陷：效率低 正确性 
		for (size_t i = 0; i < size; ++i)
			_array[i] = array[i];

		// 2、優點：效率高--->問題？---可能會出錯 
		//memcpy(_array, array, size*sizeof(array[0])); 
	}

	// 三大big 
	SeqList(const SeqList& s);
	SeqList& operator=(const SeqList& s);//拷貝構造函數
	~SeqList()//析構函數
	{
		if (_array)
		{
			delete[] _array;
			_size = 0;
			_capacity = 0;
		}
	}

	void PushBack(int data);//後增
	void PopBack();//後删
	void Insert(size_t pos, DataType data);//任意位置增
	void Erase(size_t pos);//任意位置删
	size_t Size()const;//求順序表大小
	size_t Capacity()const;//求順序表容量
	bool Empty()const;//判斷順序表是否為空
	DataType& operator[](size_t index);//[]操作符重載
	const DataType& operator[](size_t index)const;

	DataType& Front();// 傳回順序表中的第一個元素 
	const DataType& Front()const; 
	
	DataType& Back();// 傳回順序表中最後一個元素
	const DataType& Back()const;

	void Clear();// 清空順序表中的所有元素 

	// 将順序表中元素個數改變到newSize 
	void ReSize(size_t newSize, const DataType& data = DataType());
	//輸出運算符重載
	friend ostream& operator<<(ostream& _cout, const SeqList& s);

private:
	void _CheckCapacity();
private:
	DataType* _array;
	size_t _size;
	size_t _capacity;
};

//拷貝構造
SeqList::SeqList(const SeqList& s)
{
	if (s._array != _array)
	{
		_array = new DataType[s._capacity];
		_size = s._size;
		_capacity = s._capacity;

		for (size_t i = 0; i < _size; i++)
		{
			_array[i] = s._array[i];
		}
	}
}

//重載=
SeqList& SeqList::operator=(const SeqList& s)
{
	if (s._array != _array)
	{
		_size = s._size;
		_capacity = s._capacity;

		for (size_t i = 0; i < _size; i++)
		{
			_array[i] = s._array[i];
		}
	}
	return *this;
}

//後增
void SeqList::PushBack(int data)
{
	if (_size < _capacity)
	{
		_array[_size] = data;
		_size += 1;
	}

	else
	{
		DataType * temp = new DataType[_capacity + _size];

		for (size_t i = 0; i < _size; i++)
		{
			temp[i] = _array[i];
		}

		temp[_size] = data;
		_capacity += _size;
		_size++;

		delete[] _array;
		_array = temp;
	}
}

//後删
void SeqList::PopBack()
{
	if (_size == 0)
	{
		return;
	}
	else
	{
		_size--;
	}
}

//任意位置增
void SeqList::Insert(size_t pos, DataType data)
{
	if (pos < _size)
	{
		if (_size < _capacity)
		{
			//将pos位置及之後的往後挪一個位置
			for (size_t i = _size; i>=pos; i--)
			{
				_array[i] = _array[i - 1];
			}

			_array[pos] = data;
			_size++;
		}

		else if (_size==_capacity)//增加元素就需要開辟新的空間
		{
			DataType * temp = new DataType[_capacity + _size];
			size_t i = 0;

			for (i = 0; i < _size; i++)//拷貝原來的元素
			{
				temp[i] = _array[i];
			}

			_array[pos] = data;

			delete[] _array;
			_array = temp;
		}
	}
	else
	{
		cout << "輸入位置有誤\n";
	}
}

//任意位置删
void SeqList::Erase(size_t pos)
{
	//将Pos位置的資料覆寫掉（前挪）
	for (size_t i = pos; i < _size; i++)
	{
		_array[i] = _array[i + 1];
	}
	_size--;
}

size_t SeqList::Size()const
{
	return _size;
}

size_t SeqList::Capacity()const
{
	return _capacity;
}

DataType& SeqList::operator[](size_t index)
{
	DataType * temp = _array;
	return temp[index];
}

const DataType& SeqList::operator[](size_t index)const
{
	DataType * temp = _array;
	return temp[index];
}

// 傳回順序表中的第一個元素 
DataType& SeqList::Front()
{
	assert(0 != _size);
	return _array[0];
}

const DataType& SeqList::Front()const
{
	assert(0 != _size);
	return _array[0];
}

// 傳回順序表中最後一個元素 
DataType& SeqList::Back()
{
	assert(0 != _size);
	return _array[_size - 1];
}

const DataType& SeqList::Back()const
{
	assert(0 != _size);
	return _array[_size - 1];
}

// 将順序表中元素個數改變到newSize 
void SeqList::ReSize(size_t newSize, const DataType& data)
{
	if (newSize <= _capacity)
	{
		_size = newSize;
	}
	else
	{
		size_t i = 0;
		DataType * temp = new DataType[newSize];

		for (i = 0; i < _size; i++)
		{
			temp[i] = _array[i];
		}

		for (i = _size; i < newSize; i++)
		{
			temp[i] = data;
		}

		_size = newSize;
		_capacity = _size;
		delete[] _array;
		_array = temp;
	}
}

// 清空順序表中的所有元素 
void SeqList::Clear()
{
	_size = 0;
	_capacity = 0;
}

//判斷順序表是否為空
bool SeqList::Empty() const
{
	if (_size == 0)
		return 1;
	else
		return 0;
}

//對輸出操作符<<重載
ostream& operator<<(ostream& _cout, const SeqList& s)
{
	for (size_t i = 0; i < s._size; i++)
	{
		_cout << s._array[i] << ' ';
	}

	_cout << endl;
	_cout << s._size << endl;
	_cout << s._capacity;
	return _cout;
}

DataType array[] = { 1, 2, 3, 4, 5 };
SeqList List(array,5);

void FunTest1()
{
	cout << List<<endl;

	cout << "後增" << endl;
	List.PushBack(6);
	List.PushBack(7);
	List.PushBack(8);
	cout << List << endl;

	cout << "後删" << endl;
	List.PopBack();
	List.PopBack();
	cout << List<<endl; 
	cout <<  endl;

	cout << "任意位置增、删" << endl;
	List.Insert(2, 7);
	cout << List << endl;
	List.Erase(3);
	cout << List << endl;
}

void FunTest2()
{
	cout << List << endl;

	size_t size = List.Size();
	cout << "size=" <<size << endl;

	size_t capacity = List.Capacity();
	cout << "capacity=" << capacity << endl;

	List.ReSize(8, 9);
	cout << "重置後" << endl;
	cout << List << endl;
}
void FunTest3()
{
	cout << List << endl;

	DataType ret1 = List.Front();
	cout << "first data is:" << ret1 << endl;

	DataType ret2 = List.Back();
	cout << "last data is:" << ret2 << endl;

	cout << List[1] << endl;
}

void FunTest4()
{
	cout << List << endl;

	List.Clear();
	cout << "cleared" << endl;

	bool ret = List.Empty();
	if (ret)
	{
		cout << "EMPTY" << endl;
	}
	else
	{
		cout << "NOT EMPTY" << endl;
	}
}

int main()
{
	FunTest1();//測試後增後删，任意位置增，删
	//FunTest2();//測試求大小、容量，重置容量
	//FunTest3();//測試擷取首位、末位，任意位置元素
	//FunTest4();//測試清空函數及判斷是否為空
	return 0;
}
           

說明：對于主函數裡面調用的測試函數，想要測試哪部分函數功能就将相應的測試函數取消注釋，這樣更有利于觀測其函數功能。

PS：歡迎提出任何建議，謝謝！