tksAAA约瑟夫环实验报告

约瑟夫环实验报告第 1 页 共 7 页 实验 约瑟夫环 姓名:曹国君 梁辰 唐琪皓 黄悦 班级:信息1班 学号:09125676 09125675 09125672 09125673 实验时间:第3-

约瑟夫环实验报告 第1 页共 7页 实验 约瑟夫环 姓名:曹国君 梁辰 唐琪皓 黄悦 班级:信息1班 学号:09125676 09125675 09125672 09125673 实验时间:第3-4周 1.问题描述 设有编号1,2,3。。。n(n>0)的N个人围成一个圈，每个人持有一个密码(正整 数)。开始时从第k(1<=k<=n)个人按顺时针方向自1开始顺序报数，报到m(m为第 K个人的密码)的人出圈，再以这个人顺时针方向上的下一个人的密码为m，并开始 重新从1报数。如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺 序。例如，设总人数n的初值为8，他们所持的密码分别为:3,10,7,1,4,8,4,5， 开始报数人的编号k的初值为7，则出列顺序为:2,1,3,4,8,5,7,6。 2.数据结构设计 问题中以序号标示某个人，所以结点的数据域设为一个整型类型的变量 当某人出圈后，报数的工作要从下一个人开始继续，剩下的人仍然围成一圈， 可以使用循环表。由于出圈的人将不再属于圈内，意味着数据元素的删除。因此， 算法中存有频繁的元素删除操作，存储结构宜采用链表。每个结点中既存储密码还 存储初始位置，所以结点有两个数据域，一个指针域。另外，每个结点代表一个人 所以，可以令尾结点指针指向首元结点来进行循环。 // 结点类 template <class ElemType> struct Node