约瑟夫环.cpp

数据结构的源程序约瑟夫环和最短路径

#include <iostream.h>
#include <stdlib.h>


struct Node
	{ 
		int data;
		Node  *link;
	};

void main ( )
{   
    cout<<"In the following programe,I will creat a circular list"<<endl;
	cout<<"There are seven number which are 1,2,3,4,5,6,7 in the list"<<endl;
	cout<<"For each number,I will give it a password.The password funcation"<<endl;
	cout<<"is i*i+2.Then I can give you the JosephRing Programe following."<<endl;     
	Node  *head;
		   Node  *rear;
		   int  count;
	       head=NULL;
		   rear=NULL;
           count=0;
	Node *pPre;
	Node *pNew;
	for( int d=1;d<=7;d++)
	{	
		
		if(!(pNew=new Node)) {
			cout<<"memory overflow";
			exit(1);
		}
	    pNew->data=d;
	    pNew->link=NULL;
	    if(count==0)
		{
			head=pNew;
			pNew->link=head;
		}
	    else
		{
			pPre=head;
			while(pPre->link!=head)
			{
				pPre=pPre->link;
			}
			pNew->link=pPre->link;
			pPre->link=pNew;
		}
		count++;
	
	}
	cout<<"LIST HAS BEEN CREATED"<<endl;
		int list1[7];
		for(int i=0;i<=6;i++)
			list1[i]=1;
        Node*p1;
		p1=head;
        int m;
		cout<<"please inter a number m="<<endl;
		cin>>m;
		if(m<=0)
		{
			cout<<"please inter a nuber which is biger than zero."<<endl;
	    	return;
		}
		else
		{
		    for(int b=1;b<=m;b++)
			{
			    pPre=p1;
			    p1=p1->link;
			
			}
		}
		
		int dataout=p1->data;
		pPre->link=p1->link;
		delete p1;
        cout<<"The first number is "<<dataout<<endl;
        Node *p2;
		p2=pPre->link;
		for (int c=1;c<=6;c++)

		{     
			for(int i=1;i<=list1[dataout-1]-1;i++)
			{
			    pPre=p2;
				p2=p2->link;
			    
			}
              dataout=p2->data;
		     pPre->link=p2->link;
              
	          cout<<"The following number is "<<dataout<<endl;
			  delete p2;
			  p2=pPre->link;
		}
}