用循环链表实现约瑟夫环问题

软件技术基础期末大作业报告书题 目： 约瑟夫环问题 专 业： 自动化 学 号： 学生姓名： 李龙强 任课教师： 陈文静 完成日期： 2013.6.17 用循环链表实现约瑟夫环问题1. 需求分析设计一个程序，以人机交互方式执行，用户指定约瑟夫环游戏的总人数n和初始的报数上限m，然后输入每个人所持有的密码key。模拟约瑟夫环，从头开始报数，直到所有的人出列。系统按照出列顺序给出编号。2. 概要设计程序流程可以用以下流程图来刻画：输入游戏人数n调用函数创建循环链表，录入游戏人员的密码输入初始报数上限m调用Joseph函数，按规则完成游戏并输出结果3. 详细设计采用VC+.NET作为开发工具，用STL中的Linklist模板作为约瑟夫环的存储结构，通过循环计数删除结点，直到所有的人出列，程序结束。3.1 CreatList()函数创建单循环链表给链表的每个结点分配空间，输入每人所持有的密码key，创建结点。建立一个带头结点的单循环链表。如下：struct node *CreatList(int n) /* 循环链表创建函数 */ struct node *p,*q,*head;int i=1;head=(struct node*)malloc(sizeof(struct node);p=(struct node*)malloc(sizeof(struct node);head-next=p;p-id=i;printf(请输入第1个人的密码:); /* 依次录入密码 */scanf(%d,&p-d);for(i=2;id);q-id=i; p-next=q; p=q; p-next=head; /* 首尾相连，形成循环链表 */return head;3.2输出所有成员以确认信息输入完所有人的信息之后，将所有人的密码信息输出一下，已确认所有人的密码是否输入正确，以免出错。输出函数如下：void printlst(struct node *head) /* 链表打印函数 */struct node *p;p=head-next;if(head-next=head)return;printf(当前学生信息为);while(p!=head)printf(%5d,p-d);p=p-next;printf(n);return;3.3 Joseph函数，按规则完成游戏按照约瑟夫环规则输出出圈结点并删除，直到链表只剩一个头结点。void Joseph(struct node *head) /* 出圈操作函数 */int m,i,n=1;struct node *p=head-next,*q,*k;printf(请输入m的初值:); /* 录入初始报数上限 */scanf(%d,&m);q=p;while(n)for(i=1;inext!=head) /* 跳过头结点 */i+;p=p-next;if(p=q)return;printf(第%d个人出列，他的密码是%dn,p-id,p-d);m=p-d;k=p; /* 删除结点 */q-next=p-next;p=p-next;free(k);printf(n);4. 调试分析在设计过程中主要遇到下列问题：（1） list模板的用法。通过查阅相关书籍予以解决。（2） 运算符重载的方法。通过查阅C+数据予以解决。（3） 多项格式化显示的方法，尤其当系数、指数为1的时候如何显示才更美观、更符合人的思维习惯。通过与同学多次讨论予以解决。5. 测试结果下面是我的函数整合及运行结果：#include #include typedef int ET;struct nodeint id;int d;struct node *next;void printlst(struct node *head) /* 链表打印函数 */struct node *p;p=head-next;if(head-next=head)return;printf(当前学生信息为);while(p!=head)printf(%5d,p-d);p=p-next;printf(n);return;struct node *CreatList(int n) /* 循环链表创建函数 */ struct node *p,*q,*head;int i=1;head=(struct node*)malloc(sizeof(struct node);p=(struct node*)malloc(sizeof(struct node);head-next=p;p-id=i;printf(请输入第1个人的密码:); /* 依次录入密码 */scanf(%d,&p-d);for(i=2;id);q-id=i; p-next=q; p=q; p-next=head; /* 首尾相连，形成循环链表 */return head;void Joseph(struct node *head) /* 出圈操作函数 */int m,i,n=1;struct node *p=head-next,*q,*k;printf(请输入m的初值:); /* 录入初始报数上限 */scanf(%d,&m);q=p;while(n)for(i=1;inext!=head) /* 跳过头结点 */i+;p=p-next;if(p=q)return;printf(第%d个人出列，他的密码是%dn,p-id,p-d);m=p-d;k=p; /* 删除结点 */q-next=p-next;p=p-next;free(k);printf(n);main() struct node *head;int n;head=(struct node*)malloc(sizeof(struct node); printf(请输入游戏人数：);scanf(%d,&n);head=CreatList(n); /*创建循环链表*/ printlst(head); /*输出学生信息以确认*/ Joseph(head); /*出圈操作*/测试结果：6. 总结通过“约瑟夫环问题”的课程设计，我提高了对循环链表的理解和掌握，同时复习巩固了C语言的知识，提高了我的计算机水平。在平时的学习中，主要是老师讲我们听，只有上机的时候才操作一下，对知识的掌握和理解不够。这次课程设计让我认识到自己还有很多的不足，对知识的掌握及熟练运用不够，这让我在程序编写中遇到了很多困难。通过查找资料及向老师请教，我终于编写出了程序。这次课程设计，让我学会了做任何事都要细心耐心专心，在设计过程中我的程序始终错误不断，找