约瑟夫环课程设计实验报告【约瑟夫环数据结构实验报告】

数据结构实验报告

实习1 线性表及其应用

题目：编制一个演示约瑟夫环的程序

班级：1403011班 姓名：付尧 学号：[1**********] 完成日期：2015.10.25

一．需求分析

1．本程序中，人数n为任意整数，首先输入一个报数上限值整数m，程序应能自动将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。

2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。

3．程序执行的命令包括：

（1）构造线性表；（2）输入数据；（3）执行报数，删除出列人的信息以及把出列人的密码赋给m；（4）结束。

4．测试数据

（1）m初值为20，n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则正确的出列顺序为6，1，4，7，2，3，5。

二．概要设计

为了实现程序上述功能，应以单向循环链表为存储结构。

1. 基本操作：

void createList()

操作结果：构造单向循环链表，初始化每个人的密码并分配序号。

void Josephus()

初 ……此处隐藏1412个字…… =q; //插入节点P

p=q;

}

tail=p; //保存尾指针

tail->next=head->next; //形成循环链表

}

void Josephus(NODE *p,int m){

//约瑟夫函数

NODE *q;

int count=0; //报数计数器

q=tail; //q为尾结点

p=p->next; //p为第一个数据

while (p->next!=p){

count++; //当循环链表所剩元素大于1时

if (count==m){

printf("%d ",p->num); //输出当前出列者的序号

m=p->code; //更新m为出列者的密码

q->next=p->next; //删除p节点

delete(p);

p=q->next; //令p指向下一个数据结点

count=0;

}

else {

q=p;

p=p->next;

}

}

printf("%d ",p->num); //打印最后剩下的人的序号

}

int main(){

createList();

Josephus(head,m);

return 0;

}