利用C++简单实现顺序表和单链表的示例代码-创新互联

本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容，分享出来供大家参考学习，话不多说，来一起看看详细的介绍：

一、顺序表示例代码：

#include 
#include 
using namespace std;

typedef int Datatype;

class SeqList
{
public:
 SeqList()
  :_array(NULL)
  ,_size(0)
  ,_capacity(0)
 {
 }

 SeqList(const SeqList& s)
 {
  _array = (Datatype*)malloc(s._size*(sizeof(Datatype)));
  memcpy(_array, s._array, s._size*(sizeof(Datatype)));
  _size = _capacity = s._size;
 }

 SeqList& operator=(SeqList& s)
 {
  free(_array);
  Swap(s);
  return *this;
 }

 void Swap(SeqList& s)
 {
  _array = s._array;
  _size = s._size;
  _capacity = s._capacity;
 }

 ~SeqList()
 {
  if (_array)
  {
   free(_array);
   _array = NULL;
   _size = _capacity = 0;
  }
 }

 void Print()
 {
  for (size_t i = 0; i < _size; i++)
  {
   cout << _array[i] << " ";
  }
  cout << endl;
 }

 void CheckCapcacity()
 {
  if (_size == _capacity)
  {
   _capacity = 2 * _capacity + 3;
   _array = (Datatype*)realloc(_array, _capacity*sizeof(Datatype));
   assert(_array);
  }
 }

 //后插
 void PushBack(Datatype x)
 {
  Insert(_size, x);
 }

 //前插
 void PushFront(Datatype x)
 {
  Insert(0, x);
 }

 //删除最后一个
 void PopBack()
 {
  Erase(_size);
 }

 //删除第一个
 void PopFront()
 {
  Erase(0);
 }

 //[]运算符重载
 Datatype& operator[](size_t pos)
 {
  assert(pos < _size);
  return _array[pos];
 }

 //pos位置前插入x
 void Insert(size_t pos, Datatype x)
 {
  assert(pos <= _size);
  CheckCapcacity();
  int end = (int)_size - 1;
  if (pos == 0)
  {
   while (end >= 0)
   {
    _array[end + 1] = _array[end];
    end--;
   }
   _array[0] = x;
  }
  else
  {
   while (end >= (int)pos)
   {
    _array[end + 1] = _array[end];
    end--;
   }
   _array[pos] = x;
  }
  _size++;
 }

 //删除pos位置的元素
 void Erase(size_t pos)
 {
  assert(pos < _size);
  //popfront的实现
  if (_size > 0)
  {
   if (pos == 0)
   {
    int end = 0;
    while (end < (int)_size - 1)
    {
     _array[end] = _array[end + 1];
     end++;
    }
    _size--;
   }
   //popback的实现
   else if (pos == _size)
   {
    _size--;
   }
   //erase
   else
   {
    int end = pos;
    while (end < (int)_size - 1)
    {
     _array[end] = _array[end + 1];
     end++;
    }
    _size--;
   }
  }
  return; 
 }

private:
 Datatype* _array;
 size_t _size;
 size_t _capacity;
};

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。