最新约瑟夫环-数据结构数据结构期末试验报告学院：专业：学号：班级：姓名：2022.12.12Joseph约瑟夫环上机实验报告实验名称：joseph约瑟夫环题目要求的约瑟夫环操作：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序实验要求：1~）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。2~）建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。3~）建立一个输出函数，将正确的输出序列4~）测试数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？实验过程：1.基本算法以及分析：本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下typedefstructNode{intIndex;在当前环中所处的位置，即编号intPassword;在当前环中的所带的密码structNode*next;}JosephuNode;程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。然后，开始调用JosephuNode*Creat_Node函数，利用单循环链表建立起约瑟夫环，tail->next=head;就是将最后一个结点的后继指向头结点，函数结尾returnhead;将约瑟夫环的头指针返回，并将它赋值head，然后主函数继续调用Josephu函数，通过讲head和Password引入函数，以建立两个嵌套循环输出并实现如下功能：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。2.程序源代码：约瑟夫环#include#includetypedefstructNode{intIndex;intPassword;structNode*next;}JosephuNode;///////////////////////////////////////////////使用单循环链表创建约瑟夫环JosephuNode*Creat_Node(intnumbers){inti,pass;JosephuNode*head,*tail;head=tail=(JosephuNode*)malloc(sizeof(JosephuNode));//申请头结点for(i=1;iIndex=i;printf("\t\t请输入第%d号所带密码:",i);//输入当前结点所带密码scanf("%d",pass);tail->Password=pass;tail->next=(JosephuNode*)malloc(sizeof(JosephuNode));//申请一个新结点tail=tail->next;//指针指向下一个结点}tail->Index=i;printf("\t\t请输入第%d号所带密码:",i);scanf("%d",pass);tail->Password=pass;tail->next=head;//将尾结点指针指向表头returnhead;}//Creat_Node/////////////////////////////////////////////////约瑟夫环voidJosephu(JosephuNode*head,intPassword){inti,j;JosephuNode*tail;for(i=1;tail!=head;++i){for(j=1;jnext;}tail->next=head->next;printf("\n\t\t第%d个出局的人的编号是：%d\t密码是：%d",i,head->Index,head->Password);Password=head->Password;free(head);head=tail->next;}i=head->Password;j=head->Index;printf("\n\t\t第7个出局的人的编号是：%d\t密码是：%d\n",j,i);free(head);}//Josephu/////////////////////////////////////voidmain(){intnumbers,Password;charstop;JosephuNode*head;printf("\t\t-----------------约瑟夫环问题-----------------\n");printf("\t\t例如：输入约瑟夫问题的人数和起始密码：7,20\n");printf("\t\t---------------------------------------------------\n");do{printf("\t\t开始...\n\t\t输入约瑟夫环问题的人数和起始密码：");scanf("%d,%d",numbers,Password);head=Creat_Node(numbers);printf("\t\t---------------\n");printf("\t\t输出结果如下\n");Josephu(head,Password);printf("\t\t-----------------------------------------------\n");printf("...