数据结构课程设计报告-- joseph环程序设计

《数据结构课程设计报告-- joseph环程序设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、JIANGXIAGRICULTURALUNIVERSITY数据结构课程设计报告题目：Joseph环程序设计学院：软件学院姓名：学号：2010专业：软件工程年级：1012班指导教师：彭莹琼二0一一年12月题目概要：joseph环任务：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到

2、所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列一、   需求分析1.输入的形式和输入值的范围   本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”

3、为结束标志的正整数。2.输出的形式   从屏幕显示出列顺序。3.程序功能   提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4.测试数据（1）输入20,7输出003740744二、   概要设计利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后

4、按照出列的顺序用一个for语句实现。joseph环的组成成员由密码（password）和序号(No)组成，循环链表的存储结构如下：typedefstructLNode{intpassword;//密码intNo;//序号structLNodenext;//下一成员指针}member;//组成成员结构体输入m、nm>0且n>0的整数建立含n个结点的链表且用head指向第一个元素，结点数据域包含password、No、以及指向下一结点的指针head=>pn≥2(m%n)==0?n:m%n=>m1=>ii

5、→next=>pi++输出p→Nop→password=>m删除p所指向结点n--输出p→No结束开始三、   详细设计typedefstructLNode{intpassword;//密码intNo;//序号structLNodenext;//下一成员指针}member;//组成成员结构体typedefintstatus;#defineOVERFLOW-2#defineOK1#defineERROR0#include#includestatusCreateList_

6、Circle(member,int);statusDeleteNode(member);statusmain(){intn,m;memberhead=NULL,p=NULL;//头指针即首成员地址，遍历指针pprintf("Pleaseenternumberofpeople:");scanf("%d",&n);//总成员数while(n<=0){printf("nmustbepositive,pleaseenteragain:");scanf("%d",&n);}if(!CreateList_Ci

7、rcle(&head,n))//创建循环链表，返回头指针headreturnOVERFLOW;printf("Pleaseenterinitialm:");scanf("%d",&m);//初始值mwhile(m<=0){printf("mmustbepositive,pleaseenteragain:");scanf("%d",&m);}printf("Theorderis:");p=head;while(n>=2)//寻找出列成员{inti;m=(m%n==0)?n:m%n;//化简m

8、值for(i=1;inext;//p指向出列成员printf("%d",p->No);//输出出列成员序号m=p->password;//修改mDeleteNode(&p);//删除链表中的出列成员n--;//成员数自减}printf("%d",p->No);//输出最后一个成员序号returnOK;}statusCreateList_Circle(memberp_head,intn){//此算