约瑟夫环实验报告

班级：2011软件一班 姓名：宁雪锋 学号：1125115017 完成日期：20121006 一、需求分析

1. 本演示程序中，要求用户输入人数n和初始报数上限的值m。并依次输入n个人的密码（password）。程序输出n个人的出列顺序。 2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和越算结果显示在其后。 3. 程序执行的命令包括 1）构造链表

2）依照题意对链表进行操作，每次删除一个链表的节点并将删除节点的编号输出 3）结束

4. 测试数据

二、概要设计（算法描述） 为实现上述程序功能，应以循环列表表示n个人围坐一圈。循环列表每个节点所要包含的信息包括：1.每个人的编号 2.每个人的密码 3.指向下一个节点的指针。建好链表后，从链表的首个节点开始，顺着链表向后移m次，得到一个节点Node。输出Node的编号，并将Node从链表中删除，然后讲Node的密码值作为新的m。重复以上步骤，直到所有节点均被从链表中删除为止。算法复杂度为O(m*n) 三、详细设计 代码如下： #include using namespace std;

typedef struct LNode

{

int num; //表示该元素的编号 int password; //表示该元素的密码 struct LNode *next;

}LNode,*LinkList; // 结点类型，指针类型

int Insert(LinkList &L,int password, int num) //引用类型的参数 {

LinkList p;

if(L==NULL) //第一个结点 {

p=(LinkList)malloc(sizeof(LNode)); if(!p) {

cout<<\"分配空间失败！\"<p->num=num;

p->password=password; L=p; } else {

p=(LinkList)malloc(sizeof(LNode)); if(!p)

{

cout<<\"分配空间失败！\"<p->num=num;

p->password=password; L->next=p; p->next=NULL; L=p; }

return 0;

}

void Joseph(LinkList &L,int k,int m) //引用类型的参数 {

int i;

LinkList p,q; p=q=L;

while(q->next!=L) q=q->next; while(k>0) {

for(i=1;iq=q->next; p=p->next; }

q->next=p->next;

cout<num<<\" \";

m=p->password; //更新m的值 free(p);

k--; //人数减1 p=q->next; }

cout<int main(void) {

int m,n,i,t;

LinkList head,p=NULL;

cout<<\"请输入人数：\"; //输入人数n cin>>n;

cout<<\"请输入初始密码：\"; //输入初始密码m cin>>m;

cout<<\"请输入大家手中的密码：\"<cin>>t;

if(Insert(p,t,i)==-1) return 0;

if(i==1)

head=p; }

p->next=head; //构成约瑟夫环 cout<<\"出列的顺序如下：\"<四、调试分析

由于数值大小的问题，出现输出数据出错的情况，后面静仔细地检查后问题得以解决。 五、用户使用说明 按照提示一步步输入即可 六、测试结果