单链表解约瑟夫环问题

弱弱地说一句，写得挺啰嗦的……

// Josephus.h
#include

template
struct LinkNode
{
T data;
LinkNode *link;
};

template
class List
{
private:
int lenth;
int num;
LinkNode *first;
public:
List(int size,int number);
void show();
void Josephus();
};

template
List::List(int size,int number)
{
lenth=size;
num=number;

first=new LinkNode;
LinkNode *current,*s;

current=first;
for (int i=0;i{
s=new LinkNode;
s->data=i+1;
current->link=s;
current=s;
}
current->link=first->link;
}

template
void List::show()
{
LinkNode *current;

current=first;
for (int i=0;i{
current=current->link;
cout<data<<' ';
}
cout<}

template
void List::Josephus()
{
LinkNode *current,*s;

current=first->link;
// 修改下循环条件，当最后剩下一个人的时候退出循环
//for (int i=0;iwhile (current != current->link)
{
for (int j=1;j{
s=current;
current=current->link;
}
s->link=current->link;
// 需要重定向first的link，这也是结果错误的原因
if (current == first->link) first->link = current->link;
// 记得删除current，不然内存泄露
delete current; // delete
current=s->link;
lenth--;
show();
}
// 删除最后一个
delete current;
// 删除first
delete first;
}

// main.cpp
#include "Josephus.h"
#include

int main(int argc, char* argv[])
{
List link(8,3);
link.show();

link.Josephus();
// 删除之后不需要show了，多用个show的话反而出问题。

return 0;
}