约瑟夫环实验报告

约瑟夫环问题的一种描述是：编号为1.2.3…….n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数），开始任意选一个整数作为报数上限值，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺时针下一个人开始重新从1开始报数，如此下去直到所有的人全部都出列为止。试设计程序实现。

要求：利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号。

测试数据：m的值初始为20：密码3 ，1，7，2，4，8，4。 正确的结果：6，1，4，7，2，3，5。

一、需求分析：

编号为1.2.3…….n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）; 构建结构体。输入输出数据。

二、概要设计：

构建结构体；

主函数:初始化链表、单循环遍历链表、输出结果。

三、详细设计

#include #include

//构建结构体 typedef struct Node {

int mun,code;//数据域 struct Node *next;

}JNode; int main() {

int i,j,n,key; JNode *p,*q,*head;

head=(JNode*)malloc(sizeof(JNode));//为头节点申请空间； p=head;

printf(\"请输入参与人数：\"); scanf(\"%d\

// 初始化链表

for(i=1;i<=n;i++) {

printf(\"参与人%d号密码为：\scanf(\"%d\q=p;

p=(JNode*)malloc(sizeof(JNode));

}

q->next=p; p->code =key; p->mun =i;

putchar(10);

p->next=head->next ; p=head;

head=head->next; free(p);//释放内存 p=head; do{

printf(\"参与人%d号密码为%d\\n\输出链表 p=p->next;

}while(p!=head);

printf(\"请输入开始密码：key=\"); scanf(\"%d\do{ j=1; p=head; while(j}

}

q=p; p=p->next; j++;

i=p->mun; key=p->code;

printf(\"出局人为%d号\\n\q->next=p->next;//跳过出局人 head=p->next; free(p);//释放内存 n--;

}while(n>0); return 0;

四、调试分析

程序的编写和调试基本正常。遇到主要问题是指针指向问题，两个指针变量有混淆。

五、用户手册

根据程序运行时输出提示，进行数据输入。得出输出结果。

六、测试结果