利用C++简单实现顺序表和单链表的示例代码
本文主要给大家介绍了关于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;
};
总结
以上是 利用C++简单实现顺序表和单链表的示例代码 的全部内容， 来源链接： utcz.com/z/319602.html
