Question

单链表解约瑟夫环问题

#include <iostream.h>

template<class T>
struct LinkNode
{
T data;
LinkNode *link;
};

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

template<class T>
List<T>::List(int size,int number)
{
lenth=size;
num=number;

first=new LinkNode<T>;
LinkNode<T> *current,*s;

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

template<class T>
void List<T>::show()
{
LinkNode<T> *current;

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

template<class T>
void List<T>::Josephus()
{
LinkNode<T> *current,*s;

current=first->link;
for (int i=0;i<lenth-1;i++)
{
for (int j=1;j<num;j++)
{
s=current;
current=current->link;
}
s->link=current->link;
current=s->link;
lenth--;
show();
}
}

#include "stdafx.h"
#include "Josephus.h"
#include <iostream.h>

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

link.Josephus();
link.show();

return 0;
}

为什么s不能循环？程序哪里错了？（希望在原程序上改动，不要给出另外算法），谢谢~

Answer 1

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

// Josephus.h
#include <iostream.h>

template<class T>
struct LinkNode
{
T data;
LinkNode *link;
};

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

template<class T>
List<T>::List(int size,int number)
{
lenth=size;
num=number;

first=new LinkNode<T>;
LinkNode<T> *current,*s;

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

template<class T>
void List<T>::show()
{
LinkNode<T> *current;

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

template<class T>
void List<T>::Josephus()
{
LinkNode<T> *current,*s;

current=first->link;
// 修改下循环条件，当最后剩下一个人的时候退出循环
//for (int i=0;i<lenth-1;i++)
while (current != current->link)
{
for (int j=1;j<num;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 <iostream.h>

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

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

return 0;
}