温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

利用C++简单实现顺序表和单链表的示例代码

发布时间:2020-10-18 10:35:51 来源:脚本之家 阅读:169 作者:Suhw 栏目:编程语言

本文主要给大家介绍了关于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);
 }

 //[]运算符重载
 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;
};

二、单链表(不含头结点)示例代码

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

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对亿速云的支持

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI