课程设计实习报告
课程设计题目： 约瑟夫Joseph环
专业名称： 计算机科学与技术(交通信息工程) 班学
级： 2011240203 号： 201124020326
学生姓名： 王 欢 教师姓名： 张少博
2012 年 06月 25日
一．课程设计题目： 约瑟夫Joseph环 二．运行环境： 一台电脑和Microsoft Visual C++ 6.0操作环境 三．需求分析： 通过建立单链表，再形成循环链表；不断删除链表中的结点，并输出删除结点的编号，就可解决约瑟夫环问题。 四．概要设计： 1.抽象数据类型： 建立链表，并以整数存储用户的输入，以及计算出的结果； 2.算法设计的思想： (1).定义一个结构体，声明编号、密码变量； (2).建立一个带头结点的单链表； (3).使用for循环语句，使输入密码对应到每人编号； (4).使尾指针指向头指针，形成循环链表； (5).使用while循环语句，逐一删除元素结点并输出删除的编号序列。 3.程序设计及主要算法的流程图 五．源代码： #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(\"\* 3.请输入%d个人各自的密码\\n\ for(i=1;inum=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(\"\* 4.出列顺序:\\n\"); while(p->next!=p) //循环计数、报数，直到剩下最后一人的结点 { while(knext; k++; } r=p->next; printf(\"%d \ m=r->mima; //将要删除结点的密码重新赋值给m p->next=r->next; //删除元素结点 free(r); k=1; } printf(\"%d\ free(p); printf(\"\\n\"); } void main() //主函数main() { LinkList H; Node *circlehead; int m; int n; InitList(&H); printf(\"\\* * * * * * \"); printf(\"欢迎进入约瑟夫环问题测试系统\"); printf(\" * * * * * *\\n\\n\"); printf(\"1.问题描述\\n____________\\n\编号是1，2......n的n个人，按照顺时针方向围坐一圈，每个人拥有一个密码（正整数）。一开始任选一个正整数m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。\"); printf(\"\\n\\n②.开始测试\\n____________\\n\"); printf(\"\\n\* 1.请输入人数: n=\"); scanf(\"%d\ printf(\"\* 2.请输入初值: m=\"); scanf(\"%d\ circlehead=makList(H,n); ListDelete(m,circlehead); printf(\"\\n③.退出系统\\n____________\\n\"); } 六．运行结果与分析 程序根据输入的数据，运行计算后得到了正确的出列顺序 七．收获、体会及意见 1.通过本次上机实践，对链表存储结构有了更深的理解和把握，以及应用链表的 知识解决和分析问题的能力有了新的提高。 2.通过上机实践，掌握了用高级语言实现算法的基本步骤和方法。 3.通过本次实验，提高了理论和实际相结合的能力。