数据结构约瑟夫环课程设计报告

滁州学院数学系。

课程设计报告。

设计名称：约瑟夫环。

姓名：杨凤武。

小组成员：卢琼，周丽，杨凤武。

专业班级： 09信息与计算科学一班。

指导老师：袁万莲。

设计时间： 2010/2011学年度第二学期

指导教师评语：

指导教师签名。

年月日。一．课程设计目的。

1）掌握循环链表的建立。

2）熟悉循环链表的操作。

3）加深对循环链表及其基本操作的理解。

二．课程设计的内容与要求：

1 设计的内容。

编号是1,2,……n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数），一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。请设计一个程序求出出列顺序。

2 设计的基本要求。

1）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

2）测试数据：m的初值为20，n=7，7个人的密码依次为3，1，7，2，4，7，4，首先m=6，则正确的输出是什么？

3）输入数据：建立输入函数处理输入的数据，输入m、n的初值n，输入每个人的密码，建立单向循环链表。

4）输出形式：建立一个输出函数，将正确的出列顺序输出。

三．程序设计描述：

1 子函数功能介绍：

void list(linklist &l,int n)//创建循环单链表，模拟n个人围成的圈。

void input()/输入测试数据。

void output(linklist l,linklist p,int m)//输出出列顺序。

2 函数调用图。

3 主函数流程图。

4．调式分析。

主要**分析：

int i;

linklist q;

for(i=1;;i++)

if(q==p)

定义指针p用以循环链表，定义变量i计数，指针p每移动一次，i加1，直到i==m时，输出指针p所指向的节点序号，也就是令这个“人”出列，q指向该节点上一节点，令上一节点next域指向该节点下一节点，然后删除该节点，令头节点l指向该节点下一节点作为再次报数初始“人”，再令i归0，继续循环。知道q==p时，表示所有“人”出列完毕，删除最后的节点后跳出循环。

五、测试结果：

1 给出输入信息：

测试数据： n=7，7个人的密码依次为3，1，7，2，4，7，4，首先m=6

2 给出详细的输出结果：

六．课程设计总结。

通过此次课程设计，使我更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。

附录：程序**。

#include<>

int n,m;

typedef struct lnode //q为前节点。

p->next=l->next;}

void input()

if(q==p)

main(){

linklist l,p,q;

input();

list(l,n);

p=l;output(l,p,m);

数据结构约瑟夫环课程设计报告

数据结构课程设计报告约瑟夫环

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了