在OJ平台上总是出现段错误的报错,但是检查不出来为什么
题目描述
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(编号1,2,3…n)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。用双链表实现约瑟夫环问题,并输出顺时针与逆时针结果。
输入
n m k
输出有两行,依次是约瑟夫环的顺时针和逆时针输出
样例输入
5 2 1
10 3 7
样例输出
2 4 1 5 3
5 3 1 2 4
9 2 5 8 3 7 4 1 6 10
5 2 9 6 1 7 10 3 8 4
#include<iostream>
using namespace std;
template<class T>
struct LinkNode
{
T data;
LinkNode<T> * rear;
LinkNode<T> * front;
LinkNode<T> * link;
LinkNode(){rear = front = link = NULL;}
LinkNode(const T& item)
{
data = item;
front = rear = link = NULL;
}
};
template<class T>
class List{
public:
List(int a,int b,int c);
void seqoutput();
void invoutput();
void begin();
~List(){makeEmpty();};
void makeEmpty();
private:
LinkNode<T>* first;
LinkNode<T>* start;
int n,m,k;
};
template<class T>
void List<T>::makeEmpty()
{
LinkNode<T>* q;
while(start->link != NULL)
{
q = start;
start = start->link;
delete q;
}
delete start;
start=NULL;
};
template<class T>
List<T>::List(int a,int b,int c)
{
this->n = a;
this->m = b;
this->k = c;
int nn=n;
int order = 1;
LinkNode<T> *head = new LinkNode<int>(order++);
LinkNode<T> *temp;
LinkNode<T> *r;
head->rear = head;
temp = head;
while(--nn)
{
r = new LinkNode<T>(order++);
temp->rear = r;
temp->link = r;
r->rear = head;
r->link = NULL;
r->front = temp;
temp = temp->rear;
}
head->front = temp;
first = head;
start = head;
}
template<class T>
void List<T>::begin()
{
int i = k;
while(--i)
{
first=first->rear;
}
}
template<class T>
void List<T>::seqoutput()
{
LinkNode<T> *head = first;
LinkNode<T> *last;
int mm=m;
int nn=n;
while(nn--)
{
while(--mm)
{
last = head;
head = head->rear;
}
if(nn)
cout<<head->data<<" ";
else
{
cout<<head->data<<endl;
head->rear=NULL;
last->rear=NULL;
return;
}
last->rear = head->rear;
head = head->rear;
mm=m;
}
}
template<class T>
void List<T>::invoutput()
{
LinkNode<T> *head = first;
LinkNode<T> *last;
int mm=m;
int nn=n;
while(nn--)
{
while(--mm)
{
last = head;
head = head->front;
}
if(nn)
cout<<head->data<<" ";
else
{
cout<<head->data<<endl;
head->front=NULL;
last->front=NULL;
return;
}
last->front = head->front;
head = head->front;
mm=m;
}
}
int main()
{
int m[10000]={0},n[10000]={0},k[10000]={0};
int i=1,j;
List<int> *A;
while(cin)
{
cin>>n[i]>>m[i]>>k[i];
i++;
}
i-=2;
j=1;
while(j<=i)
{
A= new List<int>(n[j],m[j],k[j]);
(*A).begin();
(*A).seqoutput();
(*A).invoutput();
delete A;
cout<<endl;
j++;
}
A=NULL;
return 0;
}