1、 退圈模拟过程退圈模拟过程 摘要：摘要：本文将 n0 个人围坐一圈看成是一个单循环链表，每次报数到某个编号的人时，该 人退出圈，可以模拟成从链表中删除某个节点，而剩下的人仍构成一个单循环链表。直到所 有的认读退出圈时，单循环链表就为空了。由于在建立单循环链表时加上了一个头结点，所 以把第一个人的密码拿出单独处理。 每个人都有一个密码， 所以当人数较多时就可以用系统 随机为他们生成密码。模拟过程如下： （1）创建 n0 个人的圈（链表） ； （2）为每个人分配密码（用户输入或随机生成） ； （3）按照密码顺时针方向删除节点（按链表循环到密码个节点时就删除那个节点） ； （4）重复（3）的过程直到
2、所有人都出列为止（链表为空） 。 关键词关键词 圈 单循环链表 节点 密码 链表为空 一、一、问题重述问题重述 设编号为 1,2,n（n0）个人按顺时针方向围坐一圈，每人持有一个正整数密码。开 始时任意给出一个报数上限值 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时 停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起 重新自 1 起顺序报数； 如此下去， 直到所有人全部出列为止。 要求设计一个程序模拟此过程， 并给出出列人的编号序列。 二、二、基本要求基本要求 用单循环链表解决，当所有人都退出圈时，则链表为空，程序要给出每次出圈人的编号 （按
3、出圈顺序） ，还应给出每个人持有的密码（按圈中人的编号顺序给出） ，节点结构体中包 含有编号和密码。 三、三、算法思想算法思想 采用单循环链表，单循环链表的每个节点是一个结构体，由于单循环链表是有序的，所 以每个节点的结构体中只需包含有该节点位置的密码和下一个节点的指针。当一个人出圈 时，在链表中操作如下： p q 当报数到 Ai结束时，则在单循环链表中删除 Ai，让 Ai 的上一个节点 Ai-1 的指针指向 Ai的下一个节点 Ai-1，这样在删除 Ai后又形成了一个单循环链表，如此循环下去直到单循 环链表为空时就结束程序，完成模拟。 四、四、模块划分模块划分 ShowMenu()函数是显示完
4、成模拟的向导界面，运行如下： |-| | 报数退圈模拟系统 | |-| | 1.用户自定义输入圈中每个人的密码 | | 2.系统随机生成密码（介于 1-10 之间） | | 3.模拟开始！ ！ ！ | AAi-1 Ai Ai+1 An | 4.检查圈中是否还有人！ | | 0.退出：安全地退出本系统 | |-| void print(ElemType函数创建 n 个节点的链表 L, MiMa 是接受密码的数组，根据 cho 的值选择是用户自己输入还是系统随机生成密码。 void isEmpty(LinkList L)函数用来判断 L 单循环链表是否为空，即退圈是否完成。 void delete
5、Elem(LinkList int main() char i=9; LinkList la;/声明一个链表节点指针 la initList(la);/初始化单链表 la。 ShowMenu();/调用退圈模拟向导函数。 coutpep; MiMa=new intpep; createList(L,pep,MiMa,1);/*创建有 pep 个节点的单循环链表 L， MiMa 用来储存各节点的密码，1 表示用户自己输入密码*/ break; case 2: coutpep; MiMa=new intpep; createList(L,pep,MiMa,2);/*创建有 pep 个节点的单循环链表 L， MiMa 用来储存各节点的密码，1 表示用户自己输入密码*/ break; case 3: deleteElem(L,pep,print);/模拟退圈操作，退出 pep 个节点 break; case 4: isEmpty(L);/判断退圈是否完全 break; case 0: exit(0);/退出模拟 break; default: coute.sec;
