Joseph环课程设计

1、目 录1需求分析说明1.Joseph环的总体功能要求2. 各功能模块的功能描述3. 需要测试的数据2概要设计说明1. 程序流程图2. 模块调用图3详细设计说明1. 主函数模块2. 节点数据结构体定义模块3单向循环链表创建模块4结点删除模块5输入子模块4调试分析5用户使用说明6课程设计总结7测试结果8参考书目一、需求分析说明1. Joseph环的总体功能要求：Joseph环的总体目标：在Microsoft Visual C+ 6.0 的开发环境下，利用所学C语言和数据结构的相关知识，编写约瑟夫环（Joseph）问题的程序，要求如下：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个

2、密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。其中的功能主要分为四项：（1）界面友好，易与操作。（2）要求使用单向循环链表模拟过程（3）输入报数上限值m和人数上限n，密码值，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。（4）演示程序以人机对话的形式进行，提供用户从键盘输入，Joseph约瑟夫环的必要

3、数据，并显示出列顺序2. 各功能模块的功能描述：（1）主函数模块本模块的主要功能是初始化图形界面，调用各模块，实现软件功能。（2）节点数据结构体定义模块本模块的主要功能是进行数据对象及数据关系的创建（3）单向循环链表创建模块本模块的主要功能是用一个循环链表表示joseph环，结构中有两个成员，其一为指向下一个人的指针，已构成joseph环的链，其二为该人的标记。（4）结点删除模块本模块的主要功能是将结点的下一结点复制到该结点后后将其释放（5）输入子模块本模块的主要功能是进行光标定位，输出提示文字，并对用户输入数据进行处理。 3. 需要测试的数据：1、总成员数n：7各成员密码：3 1 7 2 4

4、 7 4初始值m:202、总成员数n：7各成员密码：3 1 7 2 4 7 4初始值m:6二、概要设计说明1. 程序流程图输入m、nm>0且n>0的整数建立含n个结点的链表且用head指向第一个元素，结点数据域包含password、No、以及指向下一结点的指针head=>pn2(m%n)=0?n:m%n=>m1=>ii<mpnext=>p i+输出pNoppassword=>m删除p所指向结点n-输出pNo结束开始2. 模块调用图：主函数模块节点数据结构体定义模块单向循环链表创建模块结点删除 模块输入子模 块抽象数据类型的定义为：ADT Link

5、List数据对象：D= ai | ai termset,i=1,2,n,n>=0，termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1=<ai-1,ai> | ai-1, ai D , i=2,n基本操作：status CreateList_Circle(member *,int);创建循环链表status DeleteNode(member *);删除链表结点此抽象数据类型中的一些常量如下：typedef int status;#define OVERFLOW -2 #define OK 1 #define ERROR 0三、详细设计说明1、主函数

6、模块调用各功能模块，实现单向链表循环、输入、输出等功能。2节点数据结构体定义模块joseph环的组成成员由密码（password）和序号(No)组成，循环链表的存储结构如下：typedef struct LNode int password; /密码 int No; /序号 struct LNode *next; /下一成员指针member; /组成成员结构体3单向循环链表创建模块实现任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。st

7、atus CreateList_Circle(member *p_head,int n) int i; member *tail,*p; *p_head=(member *)malloc(sizeof(member); if (!(*p_head) return OVERFLOW; (*p_head)->No=1; /储存成员一序号 printf ("请输入成员1的密码:n"); scanf ("%d",&(*p_head)->password); /储存成员一密码 while(*p_head)->password<=0)

8、 printf("请输入正值:"); scanf ("%d",&(*p_head)->password); tail=*p_head; tail->next=NULL; for (i=2;i<n+1;i+) p=(member *)malloc(sizeof(member); if (!p) return OVERFLOW; p->No=i; /储存成员序号 printf ("请输入成员%d的密码:n",i); scanf("%d",&(p->password); /储

9、存成员密码 while(p->password<=0) printf("请输入正值"); scanf("%d",&(p->password); tail->next=p; tail=p; tail->next=*p_head; return OK;4结点删除模块 此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其释放。 status DeleteNode(member *pp)member *temp; (*pp)->password=(*pp)->next)->passwo

10、rd; (*pp)->No=(*pp)->next)->No; temp=(*pp)->next; (*pp)->next=(*pp)->next->next; free(temp); return OK;5输入子模块 当选择好功能后，进行人工输入。先进行光标定位，然后输入正确的值，进行测试。四、调试分析1.此程序的时间复杂度是O(m*n)。2.本次设计主要用到了循环链表的相关知识，求joseph环的问题。调试过程中，一开始没有想到“指向指针数据的指针变量”，使得问题一直没有明朗。3.是否需要化简m值的语句：m=(m%n=0)?n:m%n;可根据m与总

11、成员数的值的大小来判断。当m=n时，则此步是可以删除的；当m>n时，则此步最好不删除，特别是当输入的m值很大，则化简m值的操作是很必要。 4.当m值为小于等于0时，系统提示“请输入正值：” 5.遇到的问题主要是：指针的指向的边界问题，但根据运行程序时的出错提示，很快也就解决了。 6.编写程序是没有设置编写保存数据，因此不能查找读取。五、用户使用说明利用单向循环链表存储结构模拟joseph环，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点

12、，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。本系统菜单如下：（1）界面友好，易与操作。（2）要求使用单向循环链表模拟过程（3）输入报数上限值m和人数上限n，密码值，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。（4）演示程序以人机对话的形式进行，提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序六、测试结果七、课程设计总结在完成设计的过程中，我遇到了一系列的问题，能明显感觉到自己在很多方面的不足，但另一方面，问题是要分析解决的，找出问题以便为完善学习计划，改变学习内容与方法提供实践依据。所以在整个过程中，我不断

13、加深了对数据结构的理解与一些程序写书时要注意的事项，体会了数据结构这门课程在解决现实生活问题上的可行性，也更进一步地激发了我的学习热情。 通过学习和实践，使我明白在进行面向过程的程序设计时，一般首先考虑程序所要实现的功能，然后设计为实现这些功能所必须采取的步骤，这些步骤就是过程。如果一个过程比较复杂而不能直接使用已有的抽象进行实现，则对这个过程进行分解，使分解之后的每一步（更低级的过程）能够直接对应着一条语句。通过将分解之后的一系列过程封装在一个函数抽象中，程序员在特定的时刻只关心有限的细节，这个新的函数抽象比其较低级的抽象更接近问题求解的过程，因而，能够很好地映射问题求解中的过程。如果这个过

14、程出现在许多问题求解中，那么，这个函数抽象就可能被重复利用。由于是第一次用“以数据结构为中心”的思想编程，所以并不是很习惯，在主函数中还是充斥着很多基本语句，以后仍要多多练习。 做一个课程设计要注意很多方面，无论是格式，还是书写的内容和要表达的思想都得严格要求自己，所以做起来真的不算容易。本次课程设计涉及了很多知识，由于往日没有学得很扎实，对某些问题仍然比较疑惑，所以要进行充足的补习。期间，我翻阅了很多书籍，知识总是联系很紧密的，解决完这个问题又发现了新的问题，之后，为了解决新问题又发现了更多的问题，就这样，我得等到一个一个把问题处理完。问题越多，明白的也就会越来越多，做一次课程设计就像从头到尾做了一次系统的复习，从基础到难点，从轮廓到每个知识点，数据结构的研究内容在我的脑海里就再也不像以前那么模糊了。设计程序来解决现在存在的问题，把理论知识付诸于实践，对于我们这些计算机专业的本科生来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践，这也是我们学习的目的。做完设计，我已深刻