循環單連結清單

#include<iostream>

#include<assert.h>

typedef int Datatype;

using namespace std;

struct LinkNode

{

Datatype _data;

LinkNode* _next;

LinkNode(const  Datatype&x)

:_data(x)

, _next(NULL)

{}

};

class Slist

public:

Slist()

:_head(NULL)

, _tail(NULL)

~Slist()

{

Destory();

}

Slist(const Slist&s)

if (s._head == NULL)

{

return;

}

LinkNode*begin = s._head;

do

this->PushBack(begin->_data);

begin = begin->_next;

} while (begin != s._head);

void Swap(Slist&s)

swap(_head, s._head);

swap(_tail, s._tail);

Slist& operator=(const Slist&s)

if (&s != this)

Slist tmp(s); 

Swap(tmp);

return *this;

void Destory()

if (_head == NULL)

LinkNode* begin = _head;

do{

LinkNode*del = begin;

delete del;

} while (begin != _head);

_head = NULL;

_tail = NULL;

void Print()

cout << begin->_data << "->";

cout << endl;

void PushBack(const Datatype&x)

_head = new LinkNode(x);

_tail = _head;

_tail->_next = _head;

else

_tail->_next = new LinkNode(x);

_tail = _tail->_next;

void PopBack()

else if (_head == _tail)

delete _head;

_head = NULL;

_tail = NULL;

LinkNode* prev = _head;

while (prev->_next != _tail)

{

prev = prev->_next;

}

prev->_next = _head;

delete _tail;

_tail = prev;

void PushFront(const Datatype&x)

LinkNode* tmp = new LinkNode(x);

tmp->_next = _head;

_head = tmp;

void PopFront()

LinkNode*del = _head;

_head = _head->_next;

LinkNode* Find(Datatype x)

while (begin)

if (begin->_data == x)

return begin;

if (begin == _head)

break;

return NULL;

bool Remove(LinkNode*n)

assert(n);

return false;

if (_head = _tail)

if (n == _head)

delete _head;

_head = NULL;

_tail = NULL;

return true;

LinkNode* prev = _head;

while (prev->_next != n)

prev = prev->_next;

if (prev == _head)

return false;

if (n == _head)

delete n;

else if (n = _tail)

prev->_next = n->_next;

return true;

void Reverse()

if (_head ==NULL)

LinkNode*newHead = NULL;

LinkNode*newTail = _head;

LinkNode*begin = _head;

while (1)

LinkNode*tmp = begin;

tmp->_next = newHead;

newHead = tmp;

_head = newHead;

_tail = newTail;

_tail->_next = _head;

private:

LinkNode* _head;

LinkNode* _tail;

void Test1()

Slist s1;

s1.PushBack(1);

s1.PushBack(2);

s1.PushBack(3);

s1.PushBack(4);

s1.PushBack(5);

s1.PushBack(6);

s1.Print();

s1.PopBack();

}

void Test2()

Slist s2;

s2.PushFront(1);

s2.PushFront(2);

s2.PushFront(3);

s2.PushFront(4);

s2.PushFront(6);

s2.Print();

s2.PopFront();

void Test3()

Slist s3;

s3.PushBack(1);

s3.PushBack(2);

s3.PushBack(3);

s3.PushBack(4);

s3.PushBack(5);

s3.PushBack(6);

s3.Print();

LinkNode*ret = s3.Find(5);

cout << "ret:" << ret->_data << endl;

ret = s3.Find(7);

cout << "ret:" << ret << endl;

void Test4()

Slist s5;

s5.PushBack(1);

s5.PushBack(2);

s5.PushBack(3);

s5.PushBack(4);

s5.PushBack(5);

s5.PushBack(6);

s5.Print();

s2 = s5;

s2.Reverse();

int main()

//Test1();

//Test2();

//Test3();

Test4();