顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。即线性表采用顺序存储的方式存储就称之为顺序表。在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:欢迎提出任何建议,谢谢!