滁 州 学 院 数 学 系 课程设计报告 设计名称： 约瑟夫环 姓 名： 杨凤武 小组成员: 卢琼，周丽，杨凤武 专业班级： 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 函数调用图 main 函数 input 函数 List 函数 output 函数 3 主函数流程图 调用 input 函数输入 人数 n 和报数上限 值 m 调用 List 函数模拟 n 个人围成的圈，并赋 予每个人密码 调用 output 函数输出 出列序列 

四．调式分析 主要代码分析： int i; LinkList q; for(i=1;;i++){ q=p; p=p->next; if(i==m){ printf("编号为%d 的人出列，他的密码%d 作为新的 m 值 \n",p->num,p->data); m=p->data; q->next=p->next; q=q->next; free(p); if(q!=p){ L->next=q; p=L; } i=0; } if(q==p){ printf("编号为%d 的人出列，至此所有人出列完毕\n",p->num); free(p); break; } } 定义指针 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 #include int n,m; typedef struct LNode{ int num,data; struct LNode *next; }LNode,*LinkList; void List(LinkList &L,int n){ LinkList p,q; int i; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=0;inum=i+1; printf("输入编号为%d 的人的密码:",i+1); scanf("%d",&p->data); if(L->next==NULL) L->next=p;//头结点 L else q->next=p;//前后节点关系建立 q=p;} //q 为前节点 p->next=L->next;} void input(){ printf("输入总人数 n:"); 

scanf("%d",&n); printf("输入报数上限值 m:"); scanf("%d",&m); } void output(LinkList L,LinkList p,int m){ printf("编号为%d 的人出列，他的密码%d 作为新的 m 值 printf("编号为%d 的人出列，至此所有人出列完毕 int i; LinkList q; for(i=1;;i++){ q=p; p=p->next; if(i==m){ \n",p->num,p->data); m=p->data; q->next=p->next; q=q->next; free(p); if(q!=p){ L->next=q; p=L; } i=0; } if(q==p){ \n",p->num); free(p); break; } } } main(){ LinkList L,p,q; input(); List(L,n); p=L; output(L,p,m); }