西安交通大学数据结构上机报告之约瑟夫环问题仿真

1、约瑟夫环问题仿真设编号为1，2，…，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出

1、约瑟夫环问题仿真 设编号为1，2，…，n(n>0)个人按顺时针方向围坐一圈，每人 持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人 开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列， 将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自 1报数；如此下去直到所有人全部出列为止。 （1）问题分析 可利用单循环链表解决此问题，建立一个单循环链表，依次录入 密码，然后从第一个节点出发，连续略过N-1个结点，将第N个节点 从链表中删除，并将第N个结点的密码作为新的m值，接着从下一个 结点开始，循环此过程，直至链表为空。 （2）数据结构设计 此程序实现的方法是建立一个单循环链表，然后对循环链表进行 相关操作,模拟整个报数及出列过程。 主要为以下三个步骤： 1.建立一个具有n个链结点，无头结点的循环链表 2.确定第1个报数人的位置 3.不断地从链表中删除链结点，直到链表为空 首先，建立建立一个单循环链表，将每个人的信息用一个结点存 储，包括三个信息，一是他的编号num,二是他持有的密码key,三是