C++实现顺序表

#include<iostream>
using namespace std;

typedef int DataType;

class SeqList
{
public:
   SeqList()
       :_array(NULL)
       , _size(0)
       , _capacity(0)
   {
       cout << "SeqList()" << endl;
   }

SeqList(DataType* array, size_t size)
       :_array(new DataType[size])
       , _size(size)
       , _capacity(size)
   {
       cout << "SeqList()" << endl;
       memcpy(_array, array, sizeof(DataType)*size);
   }

~SeqList()
   {
       if (_array)
       {
           delete[] _array;
           _array = NULL; //?

_size = 0;
           _capacity = 0;
       }
       cout << "~SeqList()" << endl;
   }

SeqList(const SeqList& s)
       :_array(NULL)
       , _size(0)
       , _capacity(0)
   {
       SeqList tmp(s._array, s._size);
       tmp.Swap(*this);
   }

SeqList& operator=(SeqList s)
{
s.Swap(*this);

return *this;
}

public:
   void Print()
   {
       for (int i = 0; i < _size; ++i)
       {
           cout << _array[i] << " ";
       }

cout << endl;
}

void PushBack(const DataType& x)
{
_CheckCapacity(_size + 1);

_array[_size++] = x;
}

void PopBack()
   {
       _size--;
   }
   void PushFront(const DataType& x)
   {
       _CheckCapacity(_size + 1);
       _size++;
       for (int i = _size; i >= 0; i--)
       {
           _array[i] = _array[i-1];
       }
       _array[0] = x;
   }
   void PopFront()
   {
       for (int i = 1; i < _size; ++i)
       {
           _array[i - 1] = _array[i];
       }
       _size--;
   }

void Insert(size_t pos, const DataType& x)
   {
       for (int i = _size; i >= pos; --i)
       {
           _array[i+1] = _array[i];
       }
       _array[pos] = x;
       ++_size;
   }
   int Find(const DataType& x)
   {
       for (int i = 0; i < _size; ++i)
       {
           if (_array[i] == x)
               return i;
       }
       printf("没有这个数！");
       return 0;
   }
   void Erase(size_t pos)
   {
       for (int i = pos; i < _size; ++i)
       {
           _array[i] = _array[i + 1];
       }
       _size--;
   }

DataType& operator[](size_t index)
   {
       assert(_array);
       assert(index < _size);

return _array[index];
}

size_t Size()
   {
       return _size;
   }

size_t Capacity()
   {
       return _capacity;
   }

void Reserve(size_t size)
   {
       _CheckCapacity(size);
   }

void Clear()
   {
       _size = 0;
   }

void Swap(SeqList& s)
   {
       std::swap(_array, s._array);
       std::swap(_size, s._size);
       std::swap(_capacity, s._capacity);
   }

// 怎么样是释放空间??

private:
   void _CheckCapacity(size_t size)
   {
       if (size > _capacity)
       {
           _capacity = size > 2 * _capacity ? size : 2 * _capacity;

DataType* tmp = new DataType[_capacity];
memcpy(tmp, _array, sizeof(DataType)*_size);
delete[] _array;

_array = tmp;
}
}

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

void Test1()
{
   int array[5] = { 0, 1, 2, 3, 4 };
   SeqList s1(array, 5);
   s1.Print();

s1.PushBack(5);
s1.PushBack(6);
s1.Print();

s1.Clear();
s1.Print();
cout << s1.Capacity() << endl;

{
       SeqList tmp;
       tmp.Swap(s1);
   }

cout << s1.Capacity() << endl;

//SeqList s2(s1);
}

void Test2()
{
   int array[5] = { 0, 1, 2, 3, 4 };
   SeqList s1(array, 5);
   s1.Print();

SeqList s2(s1);
s2.Print();

SeqList s3;

s3 = s1;
s3.Print();
}

void Test3()
{
   int array[5] = { 0, 1, 2, 3, 4 };
   SeqList s1(array, 5);
   s1.Print();

秒客网

C++实现顺序表

相关文章