[C++]实现顺序表和单链表

顺序表:

#include <assert.h>
#include <iostream>
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);
 }



 //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++;
 }


 void Erase(size_t pos)
 {
  assert(pos < _size);

  if (_size > 0)
  {
   if (pos == 0)
   {
    int end = 0;
    while (end < (int)_size - 1)
    {
     _array[end] = _array[end + 1];
     end++;
    }
    _size--;
   }

   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;
};

单链表

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

typedef int DataType;

struct SListNode
{
 SListNode* _next;
 DataType _data;

 SListNode(DataType x)
  :_data(x)
  , _next(NULL)
 {}
};

typedef SListNode Node;

class SList
{
public:
 SList()
  :_head(NULL)
  , _tail(NULL)
 {}

 SList(const SList& s)
  :_head(NULL)
  ,_tail(NULL)
 {
  Copy(s);
 }

 SList& operator=(const SList& s)
 {
  Destroy();
  Copy(s);
  return *this;
 }

 ~SList()
 {
  Destroy();
 }


 void Copy(const SList& s)
 {
  Node* cur = s._head;
  while (cur)
  {
   PushBack(cur->_data);
   cur = cur->_next;
  }
 }

 void Destroy()
 {
  Node* cur = _head;
  while (_head != NULL)
  {
   cur = _head;
   _head = cur->_next;
   delete cur;
  }
  _head = _tail = NULL;
 }

 void PushBack(DataType x)
 {
  if ((_head == NULL)&&(_tail == NULL))
  {
   _head = _tail = new Node(x);
  }
  else
  {
   _tail->_next = new Node(x);
   _tail = _tail->_next;
  }
 }

 void PopBack()
 {
  if (_head == NULL)
  {
   return;
  }
  else if (_head ->_next == NULL)
  {
   delete _head;
   _head = _tail = NULL;
  }
  else
  {
   Node* tmp = _head;
   while (tmp->_next->_next != NULL)
   {
    tmp = tmp->_next;
   }
   _tail = tmp;
   tmp->_next = NULL;
  }  
 }

 void PushFront(DataType x)
 {
  if ((_head == NULL) && (_tail == NULL))
  {
   _head = _tail = new Node(x);
  }
  else
  {
   Node* tmp = new Node(x);
   tmp->_next = _head;
   _head = tmp;
  }
 }

 void PopFront()
 {
  if (_head == NULL)
  {
   return;
  }
  Node* cur = _head;
  _head = _head->_next;
  delete cur;
 }

 Node* Find(DataType x)
 {
  Node* tmp = _head;
  while (tmp)
  {
   if (tmp->_data == x)
    return tmp;
   tmp = tmp->_next;
  }
  return NULL;
 }

 // 插入一个节点在pos的前面
 void Insert(Node* pos, DataType x)
 {
  assert(pos);
  if (pos == 0)
  {
   PushFront(x);
  }
  else
  {
   Node* cur = _head;
   while (cur->_next != pos)
   {
    cur = cur->_next;
   }
   Node* tmp = new Node(x);
   tmp->_next = pos;
   cur->_next = tmp;
  }
 }

 void Erase(Node* pos)
 {
  assert(pos);
  if (pos == 0)
  {
   PopFront();
  }
  else if (pos->_next == NULL)
  {
   PopBack();
  }
  else
  {
   Node* cur = _head;
   while (cur->_next != pos)
   {
    cur = cur->_next;
   }
   Node* tmp = cur->_next;
   cur->_next = tmp->_next;
   delete tmp;
  }
 }

 void Print()
 {
  Node* tmp = _head;
  while (tmp != NULL)
  {
   cout <<tmp->_data << "->";
   tmp= tmp->_next;
  }
  cout <<"NULL"<<endl;
 }

private:
 Node* _head;
 Node* _tail;
};