yue11.cpp

解决约瑟夫环问题的一个程序

#include <iostream>
#include "yue11.h"
using namespace std;

Node* Init_ysfcycle(int n)        //本函数用于约瑟夫环的创建
{
    int i,m;
    Node *h=NULL,*p=NULL,*q=NULL;
    
    p=(Node*)malloc(sizeof(Node));     //为结点分配内存
    h=p;   
	q=p;

	for(i=1;i<=n-1;i++)
	{
        cout<<"请输入第 "<<i<<"的密码"<<endl;
		cin>>m;
        p->seq=i;
      
		p->password=m;
        p=(Node*)malloc(sizeof(Node));
        q->next=p;    
        q=p;
	}

    //以下是输入最后一个结点形成约瑟夫环
    cout<<"请输入第 "<<n<<"的密码"<<endl;
	cin>>m;
    p->seq=n;
   
    p->next=h;
	return h;
}
int random(int n)
{
	return n/2+1;
}

void displayysf(int n,Node *h)      //此函数用于显示约瑟夫环的结果
{
	int i,m;
    Node *p=NULL,*q=NULL;

	p=(Node*)malloc(sizeof(Node));
	q=(Node*)malloc(sizeof(Node));
	p->next=h;

    m=random(n);
	m=m-1;     //此处m值减1，因为密码为0头结点代表的是头结点

    if((n>1)&&(m==0))
	{
        m=h->password;
        cout<<h->seq;
        p->next=h->next;
        free(h);
        h=p->next;
	}
    p=h;

    while((n>1)&&(m!=0))
	{
        if(m>1) 
        for(i=1;i<=m-1;i++) 
            p=p->next;
        q=p->next;
        m=q->password;
        cout<<q->seq<<"  ";
        p->next=q->next;
        free(q);
        n=n-1;
	}
     cout<<p->seq<<endl;
}