jiangxi agricultural university
题目joseph环程序设计。
学院： 软件学院。
姓名。学号： 2010
专业： 软件工程。
年级： 1012班。
指导教师： 彭莹琼。
二0一一年 12 月。
题目概要：joseph环。
任务：编号是1，2，……n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？
要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。
输出形式：建立一个输出函数，将正确的输出序列
一、 需求分析。
1. 输入的形式和输入值的范围。
本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。
2. 输出的形式。
从屏幕显示出列顺序。
3. 程序功能。
提供用户从键盘输入，joseph约瑟夫环的必要数据，并显示出列顺序。
4. 测试数据。
输入。输出。
二、 概要设计。
利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。
joseph环的组成成员由密码（password）和序号(no)组成，循环链表的存储结构如下：
typedef struct lnode
int password; /密码。
int no; /序号
struct lnode *next; /下一成员指针。
member; /组成成员结构体。
三、 详细设计。
typedef struct lnode
int password; /密码。
int no; /序号
struct lnode *next; /下一成员指针。
member; /组成成员结构体。
typedef int status;
#define overflow -2
#define ok 1
#define error 0
#include <>
#include <>
status createlist_circle(member **int);
status deletenode(member **
status main()
int n,m;
member *head=null,*p=null; /头指针即首成员地址，遍历指针p
printf ("please enter number of people:");
scanf ("d",&n); 总成员数。
while (n<=0)
if(!createlist_circle(&head,n)) 创建循环链表，返回头指针head
return overflow;
printf ("please enter initial m:");
scanf ("d",&m); 初始值m
while (m<=0)
printf ("nthe order is:");
p=head;
while (n>=2) /寻找出列成员。
printf ("d",p->no); 输出最后一个成员序号。
return ok;
status createlist_circle(member **p_head,int n)
//此算法创建一个无头结点的循环链表，结点数n,*p_head返回链表头指针即首结点地址。
int i;
member *tail,*p;
*p_head=(member *)malloc(sizeof(member));
if (!p_head)) return overflow;
(*p_head)->no=1; /储存成员一序号。
printf ("please enter password of no. 1:");
scanf ("d",&p_head)->password); 储存成员一密码。
tail=*p_head;
tail->next=null;
for (i=2;i
tail->next=*p_head;
return ok;
status deletenode(member **pp)
//此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其free
member *temp;
(*pp)->password=((pp)->next)->password;
(*pp)->no=((pp)->next)->no;
temp=(*pp)->next;
(*pp)->next=(*pp)->next->next;
free(temp);
return ok;
四、 调试分析。
1．此程序的时间复杂度是o(m*n)。
2．本次设计主要用到了循环链表的相关知识，求joseph环的问题。调试过程中，一开始没有想到“指向指针数据的指针变量”，使得问题一直没有明朗。
3．是否需要化简m值的语句：m=(m%n==0)?n:m%n;可根据m与总成员数的值的大小来判断。
当m〈=n时，则此步是可以删除的；
当m>n时，则此步最好不删除，特别是当输入的m值很大，则化简m值的操作是很必要。
4. 遇到的问题主要是：指针的指向的边界问题，但根据运行程序时的出错提示，很快也就解决了。
五、 测试结果。
测试数据：m初值：20；n：7；
7个人的密码依次为3，1，7，2，4，7，4；
六、总结。在此次实训中，对于这次的数据结构作业感觉到了好大的压力。我选择的是第一个题目—joseph环。
过程中，感觉平时所学的知识都丢到了九天云外，完全无力了。不过在询问其他同学之后，才有了初步的理解。过程是曲折的，在同学的帮助下，终于还是做完了这次作业。
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...