模板实现顺序表

                                                           模板实现顺序表

通过模板实现顺序表可以更方便，实例化时可以自动转化成我们需要的类型。

我们一起来看一下代码。

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

template<class T>
class Vector
{
public:
  //
  Vector()
    :_start(0),
    _finish(0),
    _endOfStorage(0)
  {}

  Vector(const T* array, size_t size)
    :_start(new T[size]),
    _finish(_start + size),
    _capacity(_start + size)
  {
    for (size_t i = 0; i < size; i++)
    {
      _start[i] = array[i];
      //*(_finish++) = array[i];
    }
  }

  //拷贝构造函数
  Vector(const Vector &v)
  {
    size_t size = v.Size();
    _start = new T[size];
    for (size_t i = 0; i < size; ++i)
    {
      _start[i] = v._start[i];
    }
    _finish = _start + size;
    _endOfStorage = _finish;
  }

  //赋值运算符的重载
  Vector& operator=(const Vector &s)
  {
    size_t size = s.Size();
    if (this != &s)
    {
      T *tmp = new T[size];
      for (size_t i = 0; i < size; i++)
      {
        tmp[i] = s._start[i];
      }
      delete[] _start;
      _start = tmp;
      _finish = _start + size;
      _endOfStorage = _finish;
    }
    return *this;
  }

  //析构函数
  ~Vector()
  {
    if (_start != NULL)
    {
      delete[] _start;
      _start = NULL;
    }
  }

  ///Modify 
  void PushBack(const T& data)          //尾插
  {
    _CheckCapacity();
    *_finish = data;
    _finish++;
  }

  void PopBack()                         //尾删
  {
    assert(_start < _finish);
    _finish--;
  }

  void Insert(size_t pos, const T& data)  //指定位置插入
  {
    assert(pos <= Size());
    _CheckCapacity();
    for (size_t i = Size(); i >= pos; i--)
    {
      _start[i] = _start[i - 1];
    }
    _start[pos - 1] = data;
    _finish++;
  }

  void Erase(size_t pos)   //指定位置删除
  {
    assert(pos <= Size());
    for (size_t i = pos - 1; i < Size(); i++)
    {
      _start[i] = _start[i + 1];
    }
    _finish--;
  }

  //capacity 
  size_t Size()const          //元素个数
  {
    return _finish - _start;
  }

  size_t Capacity()const     //顺序表容量
  {
    return _endOfStorage - _start;
  }

  bool Empty()const          //判断是否为空
  {
    if (_start == _finish)
    {
      return true;
    }
    return false;
  }

  void Resize(size_t newSize, const T& data = T())  //改变顺序表大小
  {
    size_t oldsize = Size();
    size_t capacity = Capacity();

    if (newSize <= oldsize)
    {
      _finish = _start + newSize;
    }
    else if ((newSize > oldsize) && (newSize <= capacity))
    {
      for (size_t i = oldsize; i < newSize; i++)
      {
        *_finish++ = data;
      }
    }
    else
    {
      T *tmp = new T[newSize];
      for (size_t i = 0; i < oldsize; i++)
        tmp[i] = _start[i];
      for (size_t i = oldsize; i < newSize; i++)
        tmp[i] = data;
      delete[] _start;
      _start = tmp;
      _finish = _start + newSize;
      _endOfStorage = _finish;
    }
  }

  Acess/// 
  T& operator[](size_t index)         //重载访问符[]
  {
    assert(index <= Capacity());
    return _start[index];
  }

  const T& operator[](size_t index)const  //
  {
    assert(index <= Capacity());
    return _start[index];
  }

  T& Front()            //首元素
  {
    return *_start;
  }

  const T& Front()const  //
  {
    return *_start;
  }

  T& Back()              //最后一个元素
  {
    return *(_finish - 1);
  }

  const T& Back()const
  {
    return *(_finish - 1);
  } 

  void Clear()         //清空顺序表
  {
    _finish = _start;
  }

  //输出运算符重载 
  template<class T>
  friend ostream& operator<<(ostream& _cout, const Vector<T>& v)
  {
    for (size_t i = 0; i < v.Size(); i++)
      _cout << v._start[i] << " ";
    cout << endl;
    return _cout;
  }
private:
  void _CheckCapacity()
  {
    size_t size = Size();
    size_t OldCapacity = Capacity();
    size_t NewCapacity = 2 * OldCapacity + 3;
    if (size >= OldCapacity)
    {
      T *tmp = new T[NewCapacity];
      for (size_t i = 0; i < size; i++)
      {
        tmp[i] = _start[i];
      }
      delete[] _start;
      _start = tmp;
      _finish = _start + size;
      _endOfStorage= _start + NewCapacity;
    }
  }

private:
  T* _start;
  T* _finish;
  T* _endOfStorage;
};      

注意：我们进行顺序表的拷贝时，上文用的是for循环，有同学也会用memcpy,但若T为字符串，就是浅拷贝。因此我们最好使用for循环。

来我们测试一下：

void test1()
{
  Vector<int> v1;
  Vector<int> v2;

  v1.PushBack(1);
  v1.PushBack(2);
  v1.PushBack(3);
  v1.PushBack(4);
  v1.PushBack(5);               //v1为1，2，3，4，5

  Vector<int> v3(v1);
  cout << v3;                   //v3为1，2，3，4，5
  v2 = v1;                      //v2为1，2，3，4，5
  v2.PopBack();                 //v2为1，2，3，4

  cout << v1;
  cout << v2;

  v1.Insert(5, 6);              //v1为1，2，3，4，6，5
  cout << v1;

  v1.Erase(1);                  //v1为2，3，4，6，5
  cout << v1;
}      

看一下预想的结果和运行的结果：

void test2()
{
  Vector<int> v1;
  v1.PushBack(1);
  v1.PushBack(2);
  v1.PushBack(3);
  cout << v1;                                  //1,2,3
  cout << v1.Size() << endl;                   //3 3
  cout << v1.Capacity() << endl;
       
  v1.Resize(5, 0);                             
  cout << v1;                                  //1,2,3,0,0
  cout << v1.Size() << endl;                   //5
  cout << v1.Capacity() << endl;               //5

  cout << v1[2] << endl;                       //3
  cout << v1.Front() << endl;                  //1
  cout << v1.Back() << endl;                   //0

  v1.Clear();
  cout << v1.Empty() << endl;                  //1
  cout << v1.Size() << endl;                   //0
  cout << v1.Capacity() << endl;               //5
}      

看一下预想的结果和运行的结果：