第 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 struct Node {// 数据成员:
ElemType data;
ElemType num; // 数据域 Node *next; // 指针域// 构造函数: Node(); // 无参数的构造函数
Node(ElemType item, ElemType item1,Node *link = NULL); // 已知数数据元素值和指针建立结构};
第 2 页 共 7 页
// 结点类的实现部分
template Node::Node()// 操作结果：构造指针域为空的结点 {
next = NULL; }
templateNode::Node(ElemType item, ElemType item1,Node *link)// 操作结果：构造一个数据域为item和item1，指针域为link的结点 {
data = item; num = item1; next = link; }
#endif
3. 算法设计
编写一个函数实现结点的删除与输入工作，另编写一个主函数main（）完成链表的创建与函数调用工作。
（1）插入
template Status LinkList::Insert(int position, const ElemType &e) // 操作结果：在线性表的第position个位置前插入元素e // position的取值范围为1≤position≤Length()+1// position合法时返回SUCCESS, 否则函数返回RANGE_ERROR {
if (position < 1 || position > Length() + 1) { // position范围错 return RANGE_ERROR; // 位置不合法 } else
{ // position合法 Node *tmpPtr;// 取出指向第position-1个结点的指针 tmpPtr = GetElemPtr(position - 1); Node *newPtr; if(position>Length())// 如果插入尾结点，则域指针指向首元结点
第 3 页 共 7 页
newPtr = new Node(e, position,head->next); elsenewPtr= new Node(e, position,tmpPtr->next);// 生成新结点 tmpPtr->next = newPtr; // 将tmpPtr插入到链表中 curPosition = position; // 设置当前位置的序号 curPtr = newPtr; // 设置指向当前位置的指针 count++; // 插入成功后元素个数加1 return SUCCESS; } }（2）删除
template Status LinkList::Delete(int position, ElemType &e)// 操作结果：删除线性表的第position个位置的元素, 并用e返回其值, // position的取值范围为1≤position≤Length(),
// position合法时函数返回SUCCESS,否则函数返回RANGE_ERROR {
// position合法 Node *tmpPtr; if(position==1)// 如果删除首元结点，取出指向尾结点的指针 tmpPtr=GetElemPtr(Length()); else
// 取出指向第position-1个结点的指针 tmpPtr = GetElemPtr(position - 1); Node *nextPtr = tmpPtr->next; if(position==1)//头结点与新的首元结点相连
head->next=nextPtr->next; // nextPtr为tmpPtr的后继 tmpPtr->next = nextPtr->next; // 删除结点 e = nextPtr->data; // 用e返回被删结点元素值
if (position == Length()) { // 删除尾结点,当前结点变为头结点 curPosition = 1; // 设置当前位置的序号 curPtr = head->next; // 设置指向当前位置的指针 } else { // 删除非尾结点,当前结点变为第position个结点 curPosition = position; // 设置当前位置的序号 curPtr = tmpPtr->next; // 设置指向当前位置的指针 } count--; // 删除成功后元素个数减1 delete nextPtr; // 释放被删结点
第 4 页 共 7 页
return SUCCESS; }
（3）出圈次序的算法描述 template int LinkList::Pass(int position , int n ,ElemType &e) { int i;curPtr = GetElemPtr(position); //当前指针指向position curPosition=position; //记录当前位置 for(i=0;inext; curPosition++; }cout<num<<\" \"; //输出起始位置 e=curPosition; } （4）主程序#include\"assistance.h\" #include\"lk_list.h\"
int POS(int n,int i) //计算当前位置的函数 {
if(n%i==0) n=i;
else n=n%i; return n; } int main(){
int tmp,i,k=0,n=0,key; int pos;
LinkList lc; //创建空链表 while(n<1||n>20) //人数 {cout<<\"请输入人数，人数小于20:\"; cin>>n; }
cout<<\"请输入每个人的密码，用空格分隔，密码大于0:\"<cin>>tmp;lc.Insert(i,tmp); //插入尾结点 } while(k<1||k>n) {
cout<<\"从几号开始？0>k;第 5 页 共 7 页
} cout<<\"出列顺序:\";
for(i=n;i>0;i--) {
if(i==n) //一开始，从k开始报数 {
lc.GetElem(k,key);
lc.Pass(k,key,tmp); //出列
pos=POS(tmp,i);
lc.Delete(pos,tmp); }
else
{ lc.GetElem(key); lc.Pass(key,tmp); pos=POS(tmp,i); lc.Delete(pos,tmp); } }
system(\"pause\"); return 0; }
//计算出列位置 //删除当前结点，当前指针指向当前位置的下游
//取当前位置的密码
//从当前位置开始报数，并出列 //计算出列位置 第 6 页 共 7 页
4.测试与运行
约瑟夫环数据测试 输入 次数 人数 1 2 3 4 5 6 7 8 9 10
8 输出 起始位置 4 密码 13 27 37 37 27 22 44 77 出列顺序 8 6 1 3 4 2 5 7 7 18 33 44 68 38 49 39 4 1 4 7 2 5 6 3 8 38 58 55 66 11 68 47 88 4 5 2 3 4 1 7 6 8 4 23 67 43 56 2 4 2 3 1 6 34 48 28 3 59 24 1 4 2 1 3 5 6 8 23 45 65 67 33 56 4 6 3 3 7 6 8 4 2 5 1 4 5 6 4 2 1 1 4 3 2 6 3 6 8 2 6 3 2 1 2 6 4 3 5 6 5 7 3 6 3 6 6 5 6 1 2 3 4 11 2 3 8 9 1 7 5 2 7 5 4 1 2 10 4 5 3 6 1 7 9 8 11 5.测试记录及收获
给出测试中遇到的问题及解决的方法和过程。总结本次实验的收获。
实验中一度遇到了算法错误，没有初始数等问题。即程序编译成功，运算结果不对。
在单向链表的赋值操作时，原来是以一个不变的L作为头节点，但是这种赋值方法带
第 7 页 共 7 页
来了诸多变量设计的问题，用不带头的循环链表更佳。
算法冗长，可以用更精简的算法简化运算过程。