线性表之顺序表解析

1. 顺序表是在计算机内存中以数组的形式保存的线性表。

2. 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表

3. 优点：存取速度高效，通过下标来直接存储

缺点：插入和删除比较慢

4. 基本操作：

5. 具体的代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;
#include
#include
typedef int DataType;

class SeqList
{
public:
	SeqList()
		:_a(NULL), _size(0), _capacity(0)
	{}
	SeqList(const SeqList& s)
		:_a(new DataType[s._capacity])
		, _size(s._size)
		, _capacity(s._capacity)
	{
		memcpy(_a, s._a, sizeof(DataType)*_size);
	}
	SeqList& operator=(SeqList s)
	{
		if (this != &s)
		{
			Swap(s);
		}
		return *this;
	}
	~SeqList()
	{
		delete[]_a;
		_size = _capacity = 0;
	}

	void Swap(SeqList& s)
	{
  swap(_a,s._a);
  swap(_size,s._size);
  swap(_capacity,s._capacity);
	}
	void PushBack(DataType x)
	{
		Insert(_size, x);
	}
	void PopBack()
	{
		Erase(_size);
	}
	void PushFront(DataType x)
	{
		Insert(0, x);
	}
	void PopFront()
	{
		Erase(0);
	}
	void Insert(size_t pos, DataType x)//在pos位前面插入数据x
	{
		assert(pos <= _size);
		if (_size >= _capacity)
		{
			_capacity = 2 * _capacity + 3;
			_size++;
			DataType *tmp = new DataType[_capacity];//扩容开空间
			for (size_t i = 0; i < pos; ++i)//将数据复制到新空间
				tmp[i] = _a[i];
			tmp[pos] = x;
			for (size_t i = pos + 1; i < _size; ++i)
				tmp[i] = _a[i - 1];

			delete[]_a;
			_a = tmp;
		}
		else
		{
			_size++;
			for (size_t i = _size - 1; i > pos; --i)
			{
				_a[i] = _a[i - 1];
			}
			_a[pos] = x;
		}
	}
	void Erase(size_t pos)
	{
		assert(_size&&pos <= _size);
		--_size;
		for (size_t i = pos; i < _size; ++i)
			_a[i] = _a[i + 1];
	}
	DataType& operator[](size_t pos)
	{
		assert(pos < _size);
		return _a[pos];
	}
	void Print()
	{
		for (size_t i = 0; i < _size; ++i)
			cout << _a[i] << " ";
		cout << endl;
	}
private:
	DataType* _a;
	size_t _size;
	size_t _capacity;
};
int main()
{
	SeqList s1;
	s1.PushFront(1);
	s1.PushFront(2);
	s1.PushFront(3);
	s1.PushFront(4);
	s1.Print();
	s1.Insert(1, 10);
	s1.Print();

	system("pause");
	return 0;
}