main.cpp

是我们上课的课件

#include <iostream>    
#include <string>    
using namespace std;      
  
struct Children  
{  
    int number;  
    Children *next;  
};  
  
void show(Children *point,int num)//环链输出函数  
{  
    for(int i=1;i<=num;i++)  
    {  
        cout<<point->number<<",";  
        point = point->next;  
    }  
}  
  
void main()  
{  
    int num;//孩子总数  
    int interval;//抽选号码  
    cout<<"请输入孩子总数:";  
    cin>>num;  
    cout<<"请输入抽选号码:";  
    cin>>interval;  
      
    Children *josephus = new Children[num];//设置圈的起点指针,并动态开辟堆空间用于存储数据  
  
    Children *point = josephus;//用于初化链表的指针,起始地址与josephus指针相同  
  
    for(int i=1;i<=num;i++)  
    {  
        point -> number = i;  
        point -> next = josephus + i % num;//利用+1取模的方式设置节点的next指针,当到最后的时候自动指向到第一个,形成环链  
        point = point->next;//将位置移到下一个节点也就是下一个小孩的位置  
    }  
  
    show(point,num);  
  
    Children *cut_point;  
    point=&josephus[num-1];//把起始指针设置在最后一个节点,当进入循环的时候就会从0开始,这样就好让不需要的节点脱离  
    int k=0;//故意设置一个k观察while循环了多少次  
    while(point->next!=point)//通过循环不断的寻找需要放弃的节点  
    {  
        k++;  
        for(int i = 0;i<interval;i++)//找需要放弃的节点位置  
        {  
            cut_point=point;//存储截断位置指针  
            point=cut_point->next;//将point的指针移动到放弃的节点位置,此处也和while循环终止条件有关系  
        }  
        cut_point->next=point->next;//将截断出的next指针设置成放弃处节点的next指针,使放弃处节点也就是不需要的节点脱离  
        cout<<"k:"<<k<<endl;  
	//	point = cut_point;
    }  
    cout<<"\n最后的赢家:"<<endl<<point->number<<endl<<point<<endl<<point->next<<endl;  
    delete[] josephus;  
    cin.get();  
    cin.get();  
}