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;
}