Question

高分求解c++约瑟夫环问题

本人刚学c++下边是我自己编的一个解决约瑟夫环问题的c++的程序 应该有很多错误帮我解决一下吧··
#include <iostream>
using namespace std;
typedef struct Node{
int data;
struct Node *next;
}Lnode,*LinkList;
LinkList creat(int num)
{
LinkList L;
Lnode *s,*r,*n;
L=r=NULL;
for(int i=1;i<=num;i++)
{
s=new Lnode;
s->data=num;
if(L==NULL)
{
L=s;
n=new Lnode;
n->next=s->next;
}
else if(i=num)
r->next=n->next;
else
{
r->next=s;
r=s;
}
}
return L;
}
int *Get(LinkList L,int step){
Lnode *p,*s;
p=L;
while(L!=NULL)
{
for(int i=1;i<=step;i++)
{
s=p->next;
p=p->next;
cout<<p->data;
s->next=p->next;
delete p;
}
}
return 0;
}
int main(){
int num,step;
LinkList L;
cin>>num;
cin>>step;
creat(num);
*Get(L,step);
return 0;
}
想用一个循环链表实现

Answer 1

#include <iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node * next;
}Lnode,*LinkList;
LinkList Creat(int num){
LinkList L;
Lnode *s,*r,*head;
int i=1;
L=r=NULL;
while(1){
s=new Lnode;
s->data=i;
i++;
if(L==NULL)
{ L=s;
head=L;
}
else
r->next=s;
r=s;
if(i==num+1)break;
}
r->next=head;
return L;
}
int out(LinkList L,int num,int step){
Lnode *p,*s,*n;
p=L;
for(int i=1;i<=num;i++)
{
int count=1;
//用count定位到第m个人,循环后,p1指向这个人,p2指向这个人的上一个人
while(count++<=step)
{
s=p;
p=p->next;
}

cout<<p->data<<" ";//输出当前人的编号
n=p;//p指向当前这个人
s->next=p->next;//把当前的人前的人和当前的人后的人连上.
p=p->next;//下次从当前的人的下一个人开始数
delete n;//把这个人删除(就是释放这块内存)
}
/*
int i=0;
while(1){
for(int j=0;j<step;j++)
p=p->next;
s=p;
p=p->next;
s=p->next;
cout<<p->data<<" ";

i++;
if(i==num)break;

}*/
return 0;
}

void get(LinkList L,int step){
Lnode *p,*s;
p=L;
p=p->next;
p=s;
p=p->next;
s->next=p->next;
cout<<p->data;
delete p;
}
int main(){
LinkList L;
int num,step;
cin>>num>>step;
L=Creat(num);
out(L,num,step);
//get(L,step);
return 0;
}

Answer 2

我给一个我以前写的代码
//CircleList.h
template <class Type> class CircleList;
template <class Type> class ListNode
{
friend class CircleList<Type>;
private:
Type data;
ListNode<Type> *next;
public:
ListNode():next(NULL) {};
ListNode(Type &e):data(e),next(NULL){};
Type & GetData() {return data;}
ListNode<Type> * GetNodePtr() {return next;}
void SetNodeData(Type &e){data=e;}
void SetNodePtr(ListNode<Type> * ptr){next=ptr;}
};

template <class Type>
class CircleList
{
private:
ListNode<Type> *head;
public:
CircleList(){head=new ListNode<Type>; head->next=head;}
~CircleList(){CircleClear(); delete head;}

void CircleClear();
ListNode<Type> * ListNextElem(ListNode<Type> *p=NULL);
ListNode<Type> * CircleListRemove(ListNode<Type> *p);
bool CircleListInsertAfter(int i,Type &e);
ListNode<Type> * ListGetElem(int i) const;
};

template <class Type>
void CircleList<Type>::CircleClear()
{
ListNode<Type> *p;
while(head->next!=head)
{
p=head->next;
head->next=p->next;
delete p;
}
}

template <class Type>
ListNode<Type> * CircleList<Type>::ListNextElem(ListNode<Type> *p)
{
if(p==NULL) return head;
ListNode<Type> *q=p->next;
if(q==head) q=q->next;
return q;
}

template <class Type>
ListNode<Type> * CircleList<Type>::CircleListRemove(ListNode<Type> *p) //删除p指针指向结点的直接后继
{
ListNode<Type> *q=p->next;
if(q==head)
{
q=q->next;
head->next=q->next;
}
else
p->next=q->next;

return q;
}

template <class Type>
bool CircleList<Type>::CircleListInsertAfter(int i,Type &e)
{
ListNode<Type> *p,*s;
p=ListGetElem(i);
if(!p) return false;

s=new ListNode<Type>(e);
s->next=p->next;
p->next=s;

return true;
}

template <class Type>
ListNode<Type> * CircleList<Type>::ListGetElem(int i) const
{
if(i<0) return NULL;
if(i==0) return head;
ListNode<Type> *p=head->next;
int j=1;
while(j<i)
{
p=p->next;
if(p==head) p=p->next;
j++;
}
return p;
}

//main.cpp
#include <iostream>
#include "CircleList.h"
using namespace std;

template <class Type>
void Josephus(CircleList<Type> &clist,int n, int m)
{
ListNode<Type> *p,*current;
current=clist.ListNextElem();
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=m-1;j++)
current=clist.ListNextElem(current);
p=clist.CircleListRemove(current);
cout<<"删除顺序："<<p->GetData()<<endl;
delete p;
}
current=clist.ListNextElem();
p=clist.ListNextElem(current);
cout<<"最后剩下："<<p->GetData()<<endl;
}

int main()
{
int a[]={1,2,3,4,5,6,7,8,9,10};
CircleList<int> la;
for(int i=0;i<10;i++)
la.CircleListInsertAfter(i,a[i]);

Josephus(la,10,4);
return 0;
}

Answer 3

我找的程序，不知道对不对..

void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
/* p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点*/
LinkList p,r,list;
/*建立循环链表*/
for(int i=0,i<n,i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p>link=list; /*使链表循环起来*/
p=list; /*使p指向头节点*/
/*把当前指针移动到第一个报数的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0;i<m-1;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最后被删除的元素是：％4d",P->data);
}