《约瑟夫环课程设计.doc》由会员分享，可在线阅读，更多相关《约瑟夫环课程设计.doc（9页珍藏版）》请在三一文库上搜索。
1、班级：121004 学号：121004113姓名：王土军 指导教师： 完成日期： 课 程 设计 数据结构 目录 目录.1正文.21、 题目.21) 、问题描述.22) 、基本要求.23) 、测试数据.2二、概要设计.2三、详细设计.3四、调试分析.5五、用户使用说明.5六、测试结果.6七、参考文献.7 1、 题目：Joseph环 1）问题描述 约瑟夫环问题描述的是：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向
2、的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。如下图分析： 2） 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3） 测试数据m的初值：20 ；n=7；7个人的密码依次为：3,1,7,2,4,8,4；首先m值为6（正确的出列顺序为 6,1,4,7,2,3,5）2、 概要设计 1：算法思想 利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结
3、点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。joseph环的组成成员由密码（password）和序号(No)组成，循环链表的存储结构如下： typedefstructLNodeintpassword;/密码intNo;/序号structLNode*next;/下一成员指针member;/组成成员结构体2,由算法得流程图 开始 输入m，nn2 Head=p建立含n个结点的链表且用head指向第一个元素，结点数据域包含password、No、以及指向下一结点的指针m0且n0的整数0 N Y N输出 (m%n)=0?n:m%n= 1=i Y结束 i
4、=0，termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1=|ai-1,aiD,i=2,n基本操作：statusCreateList_Circle(member*,int);创建循环链表statusDeleteNode(member*);删除链表结点此抽象数据类型中的一些常量如下：Typedefintstatus;#defineOVERFLOW-2#defineOK1#defineERROR03、 详细设计 1、主函数模块 调用各功能模块，实现单向链表循环、输入、输出等功能。 2、节点数据结构体定义模块 oseph环的组成成员由密码（password）和序号(No)组
5、成，循环链表的存储结构如下： typedefstructLNode intpassword;/密码intNo;/序号 structLNode*next;/下一成员指针member;/组成成员结构体 3、单向循环链表创建模块 实现任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。statusCreateList_Circle(member*p_head,intn)inti;member*tail,*p;*p_head=(member*)ma
6、lloc(sizeof(member);if(!(*p_head)returnOVERFLOW;(*p_head)-No=1;/储存成员一序号printf(请输入成员1的密码:n);scanf(%d,&(*p_head)-password);/储存成员一密码while(*p_head)-passwordpassword);tail=*p_head;tail-next=NULL;for(i=2;iNo=i;/储存成员序号printf(请输入成员%d的密码:n,i);scanf(%d,&(p-password);/储存成员密码while(p-passwordpassword);tail-next=
7、p;tail=p;tail-next=*p_head;returnOK; 4、结点删除模块此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其释放。statusDeleteNode(member*pp)member*temp;(*pp)-password=(*pp)-next)-password;(*pp)-No=(*pp)-next)-No;temp=(*pp)-next;(*pp)-next=(*pp)-next-next;free(temp);returnOK; 5、输入子模块 当选择好功能后，进行人工输入。先进行光标定位，然后输入正确的值，进行测试。4、 调试分析
8、 1.此程序的时间复杂度是O(m*n)。 2.本次设计主要用到了循环链表的相关知识，求joseph环的问题。调试过程中，一开始没有想到“指向指针数据的指针变量”，使得问题一直没有明朗。 3.是否需要化简m值的语句：m=(m%n=0)?n:m%n;可根据m与总成员数的值的大小来判断。当m=n时，则此步是可以删除的；当mn时，则此步最好不删除，特别是当输入的m值很大，则化简m值的操作是很必要。 4.当m值为小于等于0时，系统提示“请输入正值：” 5.遇到的问题主要是：指针的指向的边界问题，但根据运行程序时的出错提示，很快也就解决了。 6.编写程序是没有设置编写保存数据，因此不能查找读取。五、用户使
9、用说明利用单向循环链表存储结构模拟joseph环，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。本系统菜单如下：（1）界面友好，易与操作。（2）要求使用单向循环链表模拟过程（3）输入报数上限值m和人数上限n，密码值，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。（4）演示程序以人机对话的形式进行，提供用户从键盘输入，Joseph约瑟
10、夫环的必要数据，并显示出列顺序六、测试程序及结果 程序#include#includetypedef struct Nodeint password;int num; struct Node *next; Node,*Link; void InitList(Link &L)L=(Node *)malloc(sizeof(Node);if(!L) exit(1);L-password=0;L-num=0;L-next=L; void Creater(int n,Link&L)Link p,q;q=L;for(int i=1;ipassword);p-num=i;L-next=p;L=p;L-ne
11、xt=q-next;free(q);void main()printf(*约瑟夫环*n);Link L,p,q; int n,m;int a=1;int b=1;while(b=1)L=NULL;InitList(L);printf(请输入总人数?N:?n);scanf(%d,&n);while(n=1)printf(输入的总人数有误，请重新输入大于1的总人数：n);scanf(%d,&n);printf(请输入初始的上限值M(正整数):n);scanf(%d,&m);while(m0)printf(输入上限值有误，请重新输入：n);scanf(%d,&m);Creater(n,L);printf(最终出列的顺序为:n); p=L;for(int i=1;i=n;i+)for(int j=1;jnext;q=p-next;m=q-password;printf(%d,q-num);p-next=q-next;free(q);printf(n);printf(是否继续重新输入运算(1.继续0.退出):n);scanf(%d,&b); printf(nnn); 结果 7、 参考文献 1.数据结构，严蔚敏吴伟民，清华大学出版社 2.C程序设计，谭浩强，清华大学出版社 3.数据结构课程设计，滕国文，清华大学出版社序 7