数据结构课设报告书—环

《数据结构课设报告书—环》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计说明书NO.13Joseph环1.课程设计的目的本课程设计是为了配合《数据结构》课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本设计是利用循环链表解决joseph环问题。编

2、号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。2．设计方案论证2.1设计思路2.1.1设计任务编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个

3、仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？课程设计说明书NO.13输入数据：建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。输出形式：建

4、立一个输出函数，将正确的输出序列2.1.2算法思想为了解决这一问题，可以先定义一个长度为n的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法比较复杂，而且效率低，还要移动大量的元素。用单循环链表来解决这一问题，实现的方法相对要简单的多。首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。接下来

5、从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删除，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。2.2主要功能其中的功能主要分为三项：（1）界面友好，易于操作。（2）要求使用单向循环链表模拟过程。（3）输入报数上限值m和人数上限n，密码值，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2.3结构功能优点本次课程设计Joseph环采用链式存储结构，其优点主要有以下2点：1.结点空间可动态申请和动态释放，克服了顺序

6、存储结构数据元素最大个数需要预先设定的缺点。动态分配只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度比较大，难以估计其存储规模时，采用动态链表作为存储结构较好。课程设计说明书NO.132.链式存储结构元素之间的次序是使用指针来控制的，这就不像顺序存储结构在插入或删除时需要移动大量的数据。在链表中的任何位置上进行插入和删除都需要修改指针，对于频繁进行插入和删除的线性表，宜采用链表做存储结构，若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.4Joseph环流程图

7、：Joseph环是个很有意思的问题，其意义在于它启发我们用一个循环的链来表示这个圈子，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人的标记。我们以单向循环链表的方式建立约瑟夫环。建立输入处理输入数据，输入初值m,n，建立单向链表，输入每个人的密码建立一个输出函数，将正确的出列顺序输出序列。其流程图如下：课程设计说明书NO.13开始输入m,nN建立含n个节点的链表且用head指向第一个元素，节点数据域包含password，N以及指向下一节点的

8、指针m>且n>0的整数YHead=>qn>=2（m%n）==0?n:m%n=>0i<=1输出q->N结束inext=>qi++输出q->Nq->password=>m删除q所指向结点n--图1:流程图3．设计结果与分析3.1主函数模块运行结果本模块的主要功能是初始化图形界面，调用各模块，实现软件各功能初始化图形界面如图所示：图2：系统初始界面3.2输入总人数后:课程设计说明书NO.13图3：第2次操作后相关代码为：#include