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;
}
运行结果如下：
