C++实现顺序表与链表

C++实现顺序表与链表

一、顺序表

之前已经对顺序表有了了解，需要注意的是读者如果疑惑以下代码没有实现头插与头删，是因为代码中任意插入与删除这两个函数可以实现此功能。下面有测试代码，读者也可以自行测试

。

代码如下：

#include<iostream>
using namespace std;
#include<assert.h>
typedef int DataType;
class SeqList
{
public:
  //构造函数
  SeqList()
    : _array(new DataType[3])
    , _capacity(3)
    , _size(0)
  {}

  //带参数的构造函数
  SeqList(DataType *array, size_t size)
    : _array(new DataType[size])
    , _capacity(size)
    , _size(size)
  {
    for (size_t i = 0; i < size; ++i)
      _array[i] = array[i];
  }

  //拷贝构造函数
  SeqList(const SeqList& s)
    :_array(new DataType[s._capacity])
    , _capacity(s._capacity)
    , _size(s._size)
  {
    for (size_t i = 0; i < s._size; ++i)
      _array[i] = s._array[i];
  }

  //运算符=重载
  SeqList& operator=(const SeqList& s)
  {
    DataType *tmp = new DataType[s._capacity];
    memcpy(tmp, s._array, s._size);
    delete[] _array;
    _array = tmp;
    _capacity = s._capacity;
    _size = s._size;
  }

  ~SeqList()
  {
    if (_array)
    {
      delete[] _array;
      _size = 0;
      _capacity = 0;
    }
  }

  void PushBack(int data)
  {
    _CheckCapacity();
    _array[_size] = data;
    _size++;
  }
  void PopBack()
  {
    _size--;
  }
  void Insert(size_t pos, DataType data)
  {
    _CheckCapacity();
    size_t end = _size;
    while (end >= pos)
    {
      _array[end] = _array[end - 1];
      end--;
    }
    _array[pos - 1] = data;
    _size++;
  }
  void Erase(size_t pos)
  {
    assert(pos < _size);
    size_t tmp = pos;
    while (tmp < _size)
    {
      _array[tmp-1] = _array[tmp];
      tmp++;
    }
    _array[tmp] = _array[_size-1];
    _size--;
  }
  size_t Size()const
  {
    return _size;
  }
  size_t Capacity()const
  {
    return _capacity;
  }
  bool Empty()const
  {
    return _size == 0;
  }
  DataType& operator[](size_t index)
  {
    return _array[index];
  }
  const DataType& operator[](size_t index)const
  {
    return _array[index];
  }

  // 返回顺序表中的第一个元素 
  DataType& Front()
  {
    return _array[0];
  }
  const DataType& Front()const
  {
    return _array[0];
  }
  // 返回顺序表中最后一个元素 
  DataType& Back()
  {
    return _array[_size-1];
  }
  const DataType& Back()const
  {
    return _array[_size - 1];
  }

  // 清空顺序表中的所有元素 
  void Clear()
  {
    _size = 0;
  }

  // reserve() 
  // 将顺序表中元素个数改变到newSize 
  void ReSize(size_t newSize, const DataType& data = DataType())
  {
    if (newSize <= _size)
    {
      _size = newSize;
    }
    else if ((newSize > _size)&&(newSize <= _capacity))
    {
      for (size_t i = _size; i < newSize; i++)
      {
        _array[i] = data;
      }
      _size = newSize;
    }
    else
    {
      DataType *tmp = new DataType[newSize];
      for (size_t i = 0; i < _size; i++)
      {
        tmp[i] = _array[i];
      }
      for (size_t j = _size; j < newSize; j++)
      {
        tmp[j] = data;
      }
      delete[] _array;
      _array = tmp;
      _size = newSize;
      _capacity = newSize;
    }
  }
  friend ostream& operator<<(ostream& _cout, const SeqList& s)
  {
    for (size_t i = 0; i < s._size; i++)
    {
      cout << s._array[i] << " ";
    }
    cout << endl;
    return cout;
  }
private:
  void _CheckCapacity()
  {
    if (_size == _capacity)
    {
      _capacity = _capacity * 2 + 3;
      DataType *tmp = new DataType[_capacity];
      for (size_t i = 0; i < _size; i++)
      {
        tmp[i] = _array[i];
      }
      delete _array;
      _array = tmp;
    }
  }
private:
  DataType *_array;
  size_t _size;
  size_t _capacity;
};
void test()
{
  SeqList s;
  s.PushBack(1);
  s.PushBack(2);
  s.PushBack(3);
  s.PushBack(4);
  cout << s;
  cout << s.Size() << endl;

  s.Insert(1, 0);            //头插0
  s.Erase(3);                //删除第三个数
  cout << s;

  s.PopBack();             
  s.ReSize(10);             //改变大小

  cout << s.Empty() << endl;
  cout << s.Back() << endl;
  cout << s.Front() << endl;

  cout << s.Size() << endl;
  cout << s.Capacity() << endl;
}
int main()
{
  test();
  system("pause");
  return 0;
}      

测试结果：

二、双向链表

代码如下：

#include<iostream>
#include<assert.h>
using namespace std;
typedef int DataType;
struct Node
{
  Node()
      : _pNext(NULL)
      , _pPre(NULL)
      , _data(NULL)
  {}

  Node(const DataType& data)
  : _pNext(NULL)
  , _pPre(NULL)
  , _data(data)
  {}

  Node* _pNext;
  Node* _pPre;
  DataType _data;
};

class List
{
public:
  List()
  {
    _pHead = new Node;
  }

  List(DataType* array, size_t size)
  {
    for (size_t i = 0; i < size; ++i)
      PushBack(array[i]);
  } 
  void PushBack(const DataType data)
  {
    Node* pTail = _pHead;
    while (pTail->_pNext != NULL)
    {
      pTail = pTail->_pNext;
    }
    Node* pNewNode = new Node(data);
    pTail->_pNext = pNewNode;
    pNewNode->_pPre = pTail;
  }

  void PopBack()
  {
    assert(this);
    if (_pHead->_pNext == NULL)  //空链
    {
      cout << "空链" << endl;
      return;
    }
    Node *tmp = _pHead;
    while ((tmp != NULL)&&(tmp->_pNext != NULL))
    {
      tmp = tmp->_pNext;
    }
    Node *node = tmp->_pPre;
    delete tmp;
    node->_pNext = NULL;
  }

  void PushFront(const DataType data)
  {
    assert(this);
    if (_pHead->_pNext == NULL)
    {
      PushBack(data);
    }
    else
    {
      Node *node = new Node(data);
      Node *Cur = _pHead->_pNext;
      _pHead->_pNext = node;
      node->_pPre = _pHead;
      node->_pNext = Cur;
      Cur->_pPre = node;
    }
  }

  void PopFront()
  {
    assert(this);
    if (_pHead->_pNext == NULL)
    {
      cout << "空链" << endl;
      return;
    }
    Node *node = _pHead->_pNext->_pNext;
    delete (_pHead->_pNext);
    if (node == NULL)           //只有一个节点
    {
      _pHead->_pNext = NULL;
      return;
    }
    node->_pPre = _pHead;
    _pHead->_pNext = node;
  }

  void Erase(Node* pos)
  {
    assert(this);
    Node *cur = pos->_pPre;
    Node *next = pos->_pNext;
    cur->_pNext = next;
    next->_pPre= cur;
    delete pos;
    pos = NULL;
  }

  Node *Find(const DataType d)   //查询节点位置
  {
    assert(this);
    Node *tmp = _pHead;
    while (tmp != NULL)
    {
      if (tmp->_data == d)
      {
        return tmp;
      }
      tmp = tmp->_pNext;
    }
  }

  void Insert(Node* pos, const DataType& data)   //指定位置插入
  {
    assert(this);
    Node *cur = pos->_pNext;
    Node *tmp = new Node(data);
    pos->_pNext = tmp;
    tmp->_pPre = pos;
    tmp->_pNext = cur;
    cur->_pPre = tmp;
  }

  size_t Size()              //链表元素个数
  {
    int count = 0;
    Node *cur = _pHead->_pNext;
    while (cur != NULL)
    {
      cur = cur->_pNext;
      count++;
    }
    return count;
  }   

  void Clear()                //清空
  {
    assert(this);
    if (_pHead == NULL)
    {
      cout << "空链" << endl;
      return;
    }
    Node *tmp = _pHead->_pNext;
    Node *next = tmp->_pNext;
    while (tmp->_pNext!= NULL)
    {
      delete tmp;
      tmp = next;
      next = next->_pNext;
    }
    _pHead->_pNext = NULL;
  }    

  void display()
  {
    assert(this);
    Node *cur = _pHead->_pNext;
    if (cur == NULL)
    {
      cout << "空链" << endl;
      return;
    }
    while (cur != NULL)
    {
      cout << cur->_data << " ";
      cur = cur->_pNext;
    }
    cout << endl;
  }
private:
  Node* _pHead;
};
int main()
{
  List l1;
  l1.PushFront(4);
  l1.PushFront(3);
  l1.PushFront(2);
  l1.PushFront(1);

  l1.PushBack(5);
  l1.PushBack(6);
  l1.display();

  l1.PopBack();
  l1.PopFront();
  l1.display();
  cout << l1.Size() << endl;

  l1.Erase(l1.Find(4));
  l1.display();
  l1.Insert(l1.Find(2), 3);
  l1.display();

  l1.Clear();
  cout << l1.Size() << endl;

  system("pause");
  return 0;
}      

运行结果如下：