# include
using namespace std;
class Node{
public:
int data;
Node * next;
Node * prev;
Node(const int &d)
{
data = d;
next = this;
prev = this;
}
Node()
{
next = this;
prev = this;
}
};
class linklist{
public:
Node * first;//or head
Node * last;//or end
int size;
linklist(){
first = new Node();
first->next = first;
first->prev = first;
size = 0;
}
/*
linklist(int * a, int len){
size = 0;
if (len == 0)
{
first = 0;
last = 0;
}
else
{
for (int i=0; inext = p;
//ִ����˲�֮��lastָ�������ڵĽ��
last = p;
}
size++;
}
}
}
*/
~linklist()
{
while (!first)
{
Node * t = first->next;
delete first;
first = t;
}
}
/*
int IsEmpty()
{
if (first->next == 0)
{
return 0;
}
return 1;
}*/
void display()
{
if (first->next != NULL)
{
Node * current = first->next;
while (current != first)
{
cout << current->data << " "<< "[" << current << "]";
current = current->next;
}
cout << endl;
}
}
void insert(Node * curr, int data)
{
Node * Newnode = new Node(data);
Node * prevNode = curr->prev;
Newnode->next = curr;
Newnode->prev = prevNode;
curr->prev = Newnode;
prevNode->next = Newnode;
size++;
}
void Eraser(Node * curr)
{
if (curr->next == curr)
{
delete curr;
}
else
{
Node * prevNode = curr->prev;
Node * nextNode = curr->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
delete curr;
}
size--;
}
/*
Node * find(int d)
{
Node * current = first;
if (current == NULL)
{
return NULL;
}
while (current->data != d)
{
current = current->next;
if(current == NULL)
{
cout << "���ҵ�ֵ������" << endl;
return NULL;
}
}
return current;
}*/
//ð��
/*
void bbsort()
{
if (first == NULL || first->next == NULL)return;
Node * p1 = first;
Node * p2;
Node * p1pre = 0;
Node * tail = 0;//βָ���������źõ�һλ
while (p1 != NULL && first->next != tail)//�ڶ����������ж��Ƿ�ֻʣ��������
{
p2 = p1->next;
while (p2 != tail)
{
if (p1->data > p2->data)
{
if (p1pre == NULL)
{
first = p2;
}
else
{
p1pre->next = p2;
}
p1->next = p2->next;
p2->next = p1;
p1pre = p2;
p2 = p1->next;
}
else
{
p1pre = p1;
p1 = p1->next;
p2 = p2->next;
}
}
tail = p1;
p1 = first;
p1pre = NULL;
}
}*/
//��ʦ��
/*
void RankByNode()//�������ܣ��������ڵĽڵ�ͨ�������������� ��������С����
{
Node *p1, *p2; //p1Ϊ��ǰ�ڵ㣬p2Ϊ��һ���ڵ� p2=p1->next
Node *p1pre = 0; //p1��ǰ��
Node *tail = 0; //���ڱ����Ѿ��ź���Ľڵ�λ��
Node * pHead = first;
p1 = pHead;
while (p1 != NULL && tail != pHead->next)
{
p2 = p1->next;
while (p2 != tail)
{
if (p1->data > p2->data)
{
if (p1pre == NULL)
{
pHead = p2;
}
else
{
p1pre->next = p2;
}
p1->next = p2->next;
p2->next = p1;
p1pre = p2;
p2 = p1->next;
}
else
{
p1pre = p1;
p1 = p1->next;
p2 = p2->next;
}
// LookThrough();
}
// if (p1->next == p2)
tail = p1;
//else
// tail = p2;
// LookThrough();
p1 = pHead;
p1pre = NULL;
}
first = pHead;
};*/
//����
/*
void reserve()
{
if (first == NULL || first->next == NULL)return;
Node * prev = first;
Node * cur = prev->next;
while (cur != NULL)
{
Node * temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
first->next = NULL;
first = prev;
} */
//ѡ����������ָ����
/*
void selectsort()
{
if (first == NULL || first->next == NULL)return;
int min = 1000000000;
Node * cur = first;
Node * p = NULL;//���ڼ�¼��ǰ��Сֵ��λ��
Node * p2 = NULL;//���ڼ�¼��ǰ��Сֵ��ǰ��
int size = 0;
//�Ȼ�ͷָ��
Node * prev;//ǰ��
while (cur != NULL)
{
size++;
if (cur->data < min)
{
min = cur->data;//������Сֵ
p = cur;//��¼��ǰ
p2 = prev;//��¼��ǰ��ǰ��
}
prev = cur;
cur = cur->next;
}
Node * prev1 = p;//�Ѿ��ź����λ�õ����һ��
Node * prev2 = NULL;//cur��ǰ��
p2->next = p->next;//��Сֵǰ������һ������Сֵ����һ��
p->next = first;//��Сֵ��һ����first
first = p;//ͷָ��ָ��ǰ
//��������
for (int i=2; inext;//��ǰ�� �Ѿ��ź����λ�õ����һ�� ����һ��
prev2 = prev1;//��ǰ��ǰ���� �Ѿ��ź����λ�õ����һ��
min = 1000000000;//������
while (cur != NULL)
{
if (cur->data< min)
{
min = cur->data;
p = cur;
p2 = prev2;
}
prev2 = cur;
cur = cur->next;
}
p2->next = p->next;//�Ѷϵ��ĵط�������
Node * temp = prev1->next;//��temp��¼ �Ѿ��ź����λ�õ���һ��
prev1->next = p;//�Ѿ��ź����λ�õ���һ�������Сֵ�Ľ��
p->next = temp;//Сֵ�Ľ�����ӵ�temp
prev1 = p;//�ź���ĺ���һλ
}
}
*/
void josephus(int n, int m)
{
int i,j;
for (i=1; i<=n; ++i)
{
insert(first, i);
}
Node *curr = first->next;
for (i=1;inext;
if (curr == first)
curr = curr->next;
}
cout << curr->data << " ";
curr = curr->next;
Eraser(curr->prev);
if (curr == first)
curr = curr->next;
}
cout << endl;
cout << curr->data <<"wins the cruise" <next;
cout << next << endl;
list.Eraser(next);
list.display();
list.insert(list.first, 5);
list.insert(list.first, 1);
list.insert(list.first, 7);
list.insert(list.first, 6);
list.display();
//ɾ��Ԫ����prev
Node * prev = list.first->prev;
cout << prev << endl;
list.Eraser(prev);
list.display();
linklist jose;
jose.josephus(41,3);
// list.display();
// int f = list.IsEmpty();
// if (!f)
// {
// cout << "�����ǿ�" << endl;
// }
// else
// {
// cout << "������" << endl;
// }
// list.Eraser(2);
// list.push(3);
// list.display();
// cout << list.find(4) << endl;
// cout << list.find(3) << endl;
// list.Eraser(3);
// cout << list.find(3) << endl;
// list.display();
// list.push(5);
// list.push(6);
// list.display();
// list.Eraser(3);
// list.Eraser(6);
// list.display();
// cout << list.find(5) << endl;
// list.push(7);
// list.push(7);
// list.push(9);
// list.push(4);
// list.push(3);
// list.push(8);
// list.display();
// list.selectsort();
// list.display();
// list.reserve();
// list.display();
// list.RankByNode();
// list.display();
// list.reserve();
// list.display();
// list.bbsort();
// list.display();
list.~linklist();
jose.~linklist();
system("pause");
return 0;
}
/*
*/
