课 程 设 计 实 习 报 告 课程设计题目： 约瑟夫 Joseph 环 专 业 名 称： 计算机科学与技术(交通信息工程) 班 学 级： 2011240203 号： 201124020326 学 生 姓 名： 王 欢 教 师 姓 名： 张少博 2012 年 06 月 25 日 

一．课程设计题目： 约瑟夫 Joseph 环 二．运行环境： 一台电脑和 Microsoft Visual C++ 6.0 操作环境 三．需求分析： 通过建立单链表，再形成循环链表；不断删除链表中的结点，并输出删除结点的 编号，就可解决约瑟夫环问题。 四．概要设计： 1.抽象数据类型： 建立链表，并以整数存储用户的输入，以及计算出的结果； 2.算法设计的思想： (1).定义一个结构体，声明编号、密码变量； (2).建立一个带头结点的单链表； (3).使用 for 循环语句，使输入密码对应到每人编号； (4).使尾指针指向头指针，形成循环链表； (5).使用 while 循环语句，逐一删除元素结点并输出删除的编号序列。 3.程序设计及主要算法的流程图 

//声明编号变量 //声明密码变量 //创建一个空链表。 //给每人分配编号、密码。 //定义新动态指针 //使用 for 循环语句，使输入密码对 应到每人位置 //使尾指针指向头指针，形成循环链表 五．源代码： #include #include typedef struct Node { int num; int mima; struct Node *next; }Node,*LinkList; InitList(LinkList *H) { *H=(LinkList)malloc(sizeof(Node)); (*H)->next = NULL; } LinkList makList(LinkList H ,int n) { Node *r, *s; int i; r=H; printf("\t* 3.请输入%d 个人各自的密码\n",n); for(i=1;imima); s->num=i; r->next=s; r=s; } r->next=H->next; free(H); return r; } void DeleList(int m,Node *circlehead) { Node *p,*r; int k=1; p=circlehead; printf("\t* 4.出列顺序:\n"); while(p->next!=p) { while(knext; k++; //循环计数、报数，直到剩下最后一人的结点 

} r=p->next; printf("%d ",r->num); m=r->mima; p->next=r->next; free(r); k=1; } printf("%d",p->num); free(p); printf("\n"); } void main() { //将要删除结点的密码重新赋值给 m //删除元素结点 //主函数 main() LinkList H; Node *circlehead; int m; int n; InitList(&H); printf("\t\t* * * * * * "); printf("欢迎进入约瑟夫环问题测试系统"); printf(" * * * * * *\n\n"); printf("1.问题描述\n____________\n\t 编号是 1，2......n 的 n 个人，按照顺 时针方向围坐一圈，每个人拥有一个密码（正整数）。一开始任选一个正整数 m，从 第一个人开始顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将 他的密码作为新的 m 值，从他的顺时针方向的下一个人开始重新从 1 报数，如此下去， 直到所有人全部出列为止。"); printf("\n\n②.开始测试\n____________\n"); printf("\n\t* 1.请输入人数: n="); scanf("%d",&n); printf("\t* 2.请输入初值: m="); scanf("%d",&m); circlehead=makList(H,n); ListDelete(m,circlehead); printf("\n③.退出系统\n____________\n"); } 

六．运行结果与分析 程序根据输入的数据，运行计算后得到了正确的出列顺序 七．收获、体会及意见 1.通过本次上机实践，对链表存储结构有了更深的理解和把握，以及应用链表的 知识解决和分析问题的能力有了新的提高。 2.通过上机实践，掌握了用高级语言实现算法的基本步骤和方法。 3.通过本次实验，提高了理论和实际相结合的能力。