数据结构约瑟夫环课程设计实验报告.doc

徐州工程学院信电工程学院数据结构课程设计成绩 *学院课 程 设 计 报 告 课 程 名 称 数据结构课程设计报告 专 业 班 级 学 生 姓 名 学 号 设 计 题 目 约瑟夫环 指 导 教 师 设计起止时间： 年 月 日至 年 月 日任务书1.课程设计背景：数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术应用等，都是对数据进行加工处理的过程。因此，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的关系及其对应的存储表示，并利用这些等性结合相关编程技术，运用合适、熟练的方法，才能设计出符合要求、可操作性强、有利用价值的应用程序。2课程设计的要求和内容：编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止。该题目要求用单循环链表作为存储结构，进行一个带密码的约瑟夫环的运算问题。而且从键盘输入总人数、初始报数上限值m及各人密码，然后输出出列的人员的编号顺序。按照题目的要求，要采用单循环链表来作为存储结构，然后在循环链表的基础上去实现约瑟夫环的运行。在主函数里，定义完各项之后，我先用一个while的循环语句来实现能够反复进行运算。关于约瑟夫环的运算，先创建一个只有头结点的空链表，然后输入总人数N，和初始的上限值M，用总人数N去初始化循环链表，然后在循环链表里面从键盘输入对应的密码值。3主要参考文献：1、算法与数据额结构 C语言版 机械工业出版社 陈守孔 孟佳娜 武秀川2、C语言程序设计（第二版）清华大学出版社 谭浩强3、数据结构（C语言）版 清华大学出版社 严蔚敏 吴伟民4课程设计进度计划（以天为单位）：起 止 日 期工 作 内 容备 注2011年6月20号2011年6月21号至2011年6月22号2011年6月23号2011年6月24号系统分析与设计阶段程序编制与调试阶段答辩和考核设计报告和书写说明书约瑟夫环分析与设计对约瑟夫环进行编程第 7 页 共 7 页目 录一、题目设计与分析 41.1问题描述 41.2采用类c语言定义相关的数据类型 41.3各模块的伪码算法 4二、流程图 5三、源程序清单 6四、调试过程、运行结果 9五、程序有待改进的地方 10六、设计收获和建议 10一、题目设计与分析1.1问题描述关于这次题目的设计，根据题目的要求，主要用了一个单循环链表作为存储结构。首先是进行一系列的定义结点，其中就有包括每个人的密码和编号。然后有空链表的创建和循环链表的初始化。在这里，我们将输入每个人密码的步骤放在循环链表的初始化里，在初始化链表时从键盘输入密码和直接给每个人进行编号，而不是在主函数中进行。然后在主函数里面主要就是实现约瑟夫环的运行，从第一个开始，找到对应上限值的的人，然后输出编号，将头指针指向下一个结点，将该编号人员的密码赋值为新上限值，然后清空该结点的数据，一直这样的运行，直到所有结点都被清空，就完成了约瑟夫环的运行。在设计的前期，本是设计将密码输入的这一部分放在主函数之中去执行，而建立单循环链表是单独的一个函数，但是无法实现将数据从主函数键入切能被准确使用，于是后改成在初始化链表的时候键入密码，从而达到目标。1.2采用类c语言定义相关的数据类型typedef struct Node int password; /每个人持有的密码int num; /人员的编号struct Node *next; /指向下一个节点Node,*Link;1.3各模块的伪码算法InitList(Link &L)操作结果:构造一个空的线性表L(Node *)malloc(sizeof(Node)动态分配内存存储空间Creater(int n,Link &L)初始化链表，初始化人员编号和输入每个人的密码Creater(n,L)建立一个循环列表，赋予初始编号和输入每个人的密码，构成一个约瑟夫环开始建立线性表对线性表初始化，并赋值为1到n。令最后一个节点指向第一个节点。赋值m为上限值p=p-next;q=p-next;m=q-password;Printf(“%d”,q-num);p-next=q-next;Free(q);判断n是否大于1判断m是否大于0NNYY二、流程图三、源程序清单#include#include typedef struct Node int 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-next=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);四、调试过程、运行结果基本界面，关于各项值和密码的输入。然后得到正确的结果。同时进行询问判断，是否继续。如果选择继续，则可以重复输入各项继续进行运算。如果不选择继续，则输入0后退出。如果一开始输入的数据有错，则会提示输入的数据有错，要求重新输入。如果输入的初始上限值有错。也会进行提醒然后要求重新输出。经过测试，正确地输入数据。就能得出想要的约瑟夫环运算的结果。五、程序有待改进的地方运行环境下有待加强，因为程序只能在MICROSOFT VISUAL C+6.0里面运行，对于其他运行软件却不能运行。六、设计的收获和建议在这次数据结构的课程设计中，让我进一步地了解单循环链表的用法，也更清楚地明白关于约瑟夫环的一些内容。在设计的过程中，重点的问题有两个，一个是约瑟夫环该怎么样去实现，还有就是每个人的密码应该如何输入。起初，密码的输入是设计在主函数中去解决，最后在查阅资料和动手实践过之后，决定将密码的输入放在循环链表的初始化过程中，这样的话，能够更条理清晰