约瑟夫环详解！！

此程序共写了一个类，3个小函数和一个主函数。

1.类中定义了2个变量一个指针，其中一个变量用来存放学生的编号，另一个变量用来存放学生的密码，next指针是用来做链表的.

2.第一个函数是用类定义的，需要输入学生的编号和密码。主要靠用new在堆区申请了类大小的内存来存放需要输入的变量来实现结点的创建。按照习惯创建了一个头结点，并且创建了一个指向头结点的指针，完成后就要进行学生编号和密码的录入。因为要录入多个学生，所以采用了for循环来写。首先要明确需要录入的学生人数n，之后才能确定循环的轮数，因此我程序运行的第一步就是输入n值。在循环中需要为各个学生编号和输入密码，我就在堆区用new开辟了n个空间，每个空间起到3个作用，每次循环都将temp向后移动，用temp指向新创建的结点来实现将结点连接起来。在将单链表写完之后，因为考虑到这个程序是需要链表不断循环因此我将链表的最后一个结点和头结点连接起来，最后返回头结点。

3.第二个函数是一个比较简单的函数，考虑到需要更改学生手中的密码，因此我运用了for循环加一个指向头结点的指针，让这个指向头结点的指针随着for循环不断往后来寻找需要更改密码的学生，找到后输入一个数字，将这个数字赋值给temp指针指向的那个在堆区申请的new空间里面的存放密码的位置。

4.第三个函数就是学生最后是怎么选出来的，需要两个指针来选择，因为根据观察第一次选择的时候有一个指针必须指向头结点，因此刚开始头结点不能删除，如果没有这个指向头结点的指针，如果学生第一个选择的数字是1 ，就无法把首元结点删除，除非定义一个指针指向最后一个结点。我看题目说m一定小于n所以第一次选择的时候留下首结点是没有影响的，所以我第一次选择是没有删除首结点（我觉得一上来就删除首结点会更麻烦）temp指针用来选择那个需要出列的学生并输出他的编号和密码，head指针每次进入while出来后都会在temp指针前面一个，因此用head指针指向temp后一个指针来实现将选择出来的学生删除掉。在进行完第一次选择后head指针和temp指针全都进入了结点中，首元结点就失去了作用，而且会干扰我们题目的实现，因此我选择下一步将头结点删掉。

头结点删掉之后就进入了我们题目的关键，实现其他学生信息的输出，定义了一个x来计数是第几个出列的学生，同时用temp和head指针做和第一次选择相同的工作

就能选择出真确的出列顺序，同时最关键的要加上循环所需要的条件就是temp指针无法指向的时候代表程序结束（这个地方我不是很理解）

5.主程序我首先就进行了学生编号和密码的录用了第一个写的函数，然后开始更改需要修改密码的学生的密码，我用了for循环可以来实现多个学生密码的修改，在循环中调用了第二个函数，接下来我生成随机数m调用了时间随机数来生成这个m（这个m感觉很不稳定）生成随机数之后再调用第三个函数就实现了整个程序

下面是程序的运行结果，我输入了5个学生，并且在游戏开始前选择了更改两个学生的密码，他自动生成的随机数为3。

约瑟夫环详解！！

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
class Node
{
public:
int no;
int value;
Node *next;
};
Node *link();//创建链表，输入学生密码，创建学生的编号和密码
void renew(Node *p,int a,int num);//更新某个同学的密码
void cut(Node *p,int m);//将第m个同学选出来
int main()
{

Node *p=link();
int k;
cout << "需要更改密码的人数k:";
cin >> k;
for(int i=0;i<k;i++)
{
      int a,num;
      cout << "请输入需要更改密码的同学的序号i:";
      cin >> a;
      cout << "请输入更改后的密码num:";
      cin >> num;
      renew(p,a,num);
}
int n;
cout << "密码更改完毕，游戏开始，确定人数n:";
cin >> n;
int m;
srand(time(NULL));
m=(int)rand()%n;//生成随机数m
cut(p,m);
return 0;
}
Node *link()
{
int num;
int n;
Node *p=new Node [sizeof(Node)];//头结点
Node *temp=p;//声明一个指向头结点的指针
cout << "需要录入学生n:";
cin >> n;
for(int i=1;i<=n;i++)
{
      Node *a=new Node [sizeof(Node)];
      cout << "输入学生"<<i<< "的密码:";
      cin >>num;
      a->no=i;
      a->value=num;
      cout << "此学生编号为"<<i<<",密码为"<<num<<endl;
      a->next=NULL;
      temp->next=a;
      temp=temp->next;
}
temp->next=p;
    return p;
}
void renew(Node *p,int a,int num)
{
Node *temp=p;
for (int i=1;i<=a;i++)
{
      temp=temp->next;
}
temp->value=num;
}
void cut(Node *p,int m)
{
//生成两个指针，一个指针负责选择，一个指针负责将选出来的结点删除
Node *temp=p->next;
Node *head=p;
while(temp->no!=m)
{
      head=temp;
      temp=temp->next;
}
cout <<"第1个出列的学生的编号为:"<<temp->no<<"\t"<<"第1个出列的学生的密码为:"<<temp->value<<endl;
head->next=temp->next;
//选出第一个人后，将空结点删除
Node *last=p;
while(last->next!=p)
{
     last=last->next;
}
last->next=p->next;
int x=1;
while(temp->next!=temp)
{
      x++;
      for(int i=1;i<=m;i++)
      {
          head=temp;
          temp=temp->next;
      }
      cout <<"第"<< x << "个出列的学生的编号为:"<<temp->no<<"\t"<<"第"<<x<<"个出列的学生的密码为:"<<temp->value<<endl;
      head->next=temp->next;
}
}

约瑟夫环详解！！

相关推荐