《数据结构约瑟夫环问题的课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构约瑟夫环问题的课程设计.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构约瑟夫环问题的课程设计 课程设计与内容要求 约瑟夫环问题 问题描述 编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。 测试数据 m的初值为20，n=7 ,7个人的密码依次为3
2、，1，7，2，4，7，4，首先m=则正确的输出是什么？ 要求： 输入数据：首先输入待处理人员数及他们的密码，然后输入m的初值，建立单循环链表。 输出形式：建立一个输出函数，将正确的出列序列输出。 一问题描述与分析 约瑟夫问题 编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 分析 利用单循环链表解决本问题，先创建一个有n个的
3、单循环链表，依次录入密码。然后从第一个结点出发，连续略过 m-1个结点，将第m个结点从链表中删除，并将第m个结点的密码作为新的么值，接着从下个结点开始，循环此过程，直至链表为空。 二数据结构描述 利用不带头结点的单循环链表来作为约瑟夫环的存储结构 三主要算法流程描述 1主要流程图 2具体程序段及其说明 #include #include typedef struct node int number; int key; struct node* next; listnode, * circularlist;/定义了结点类型listnode和指针类型circularlist int main()
4、int amount,t,code,m,k;/ amount表示总人数，code表示相应的学生密码circularlist w=(listnode*)malloc(sizeof(listnode); w-next=w;/循环链表仅一个元素时依然满足 listnode *v; printf(请输入总人数:); scanf(%d,&amount); v=w; for(k=1;kkey=code; w-number=k; if(k!=amount) w-next=(listnode*)malloc(sizeof(listnode); w=w-next; w-next=v; /循环结束后自动生成链表头
5、 printf(“约瑟夫环已建成，可以开始！n”); printf(请输入初值: ); scanf(%d,&m); if(mnext; t+; v=w-next; w-next=v-next; printf( %d,v-number); m=v-key; m=m-1; free(v);/释放v的存储空间 while(w-next!=w); printf( %dn,w-number); free(w); /释放的存储空间 getchar(); getchar(); return(0); 四使用说明 1进入C工作环境：如Turbo C2.0, Turbo C+ 3.0，Microsoft visu
6、al C+ 6.0（本次课程设计使用环境） 2输入自己所编好的程序，通过键盘或软键盘。 3.检查一遍已输入的程序是否有错（包括输入时打错的和编程中的错误），如发现有错，及时更正。 4进行编译和连接。如果在编译和连接过程中发现错误，屏幕上会显示“报错信息”，根据 提示找到出错的位置和原因，加以改正。再进行编译，直至顺利通过编译和链接为止。 5.运行程序并分析运行结果是否合理和正确。在运行时要注意当输入不同值时所得到的结果是否正确。此时应运行几次，分别检查在不同情况下程序是否正确。 6输出程序清单和结果。 数据测试 n=7，即amount=7, 初始报数限值m=20, 7 个人的密码依次是 3,1
7、,7,2,4,7,4 可的输出序列是6 7 4 1 5 3 2 界面如下 （五）调试分析说明 测试过程中开始由于有个地方的分号没打上，出现了错误提示，然后找到症结所在。 测试数据时使用了多组数据，并用笔算了一下，看输出时是否与实际有偏差，因为程序有时会运行正确，但这并不能确定输出正确，可见实践真的很重要。 由于本程序的主要部分是单循环链表，可知该程序的时间复杂度为O(n)。 对于模块类的设计， 首先考虑到肯定要建立一个单循环链表，但是本次设计中要求不带头结点，变得复杂了些，但通过实践发现指针可以很好解决这一问题。 然后在建立第二个主模块时，想到通过将指针指向下一结点，并删除该节点的思路来解决这
8、一问题。 在程序输入过程中，尝试了一下将是负值的m输入，却发现错误，主要是在指针指向时无法进行自动的加减。 关于程序调试 把送入的源程序翻译成机器语言，即用编译程序对源程序进行语法检查并将符合语法规则的源程序语句翻译成计算机能识别的“语言”。如果经编译程序检查，发现有语法错误，那就必须用编辑程序来修改源程序中的语法错误，然后再编译，直至没有语法错误为止。 修改后的程序进行试算，这时可以假设几个模拟数据去试运行，并把输出结果与手工处理的正确结果相比较。如有差异，就表明计算机的程序存在有逻辑错误。 对于算法的改进方面 主要是希望能够不用限制初值和密码值的正负号问题，关于这方面我还在思考中。 对于约
9、瑟夫问题还可以进行扩展，用数组也可以解决这一问题。 （六）课程总结 课程设计中的收获 对于分析问题和解决问题的认识 拿到这个课题后，我首先选择了约瑟夫问题，因为它可以用我比较熟悉的单循环链表来进行解决，然后我在想它整体的结构而不用去先想它的具体实现，这个得益于以前看过该如何设计程序，划分出三个主模块后，开始了每一模块的设计，但具体到实践中，我才发现问题不 像我开始认为的那样可以很好的弄出来，首先我便遇到了对于无头结点这一要求，不过最终解决了，然后在使用指针时我又发现自己对指针掌握的并不是很好，于是我他又拿出课本，把指针这一本分的内容又重新学习了一下，前两部分建立好了，然后就是第三部分了，关键在
10、于free和getchar这两个函数。最后整个程序编完后是检查了一遍。最后调试中出了问题，就一步步解决了。 在这个过程中，我发现很多时候有很多问题是可以快速的解决，关键在于找到它的突破口，实践出真知，只有在不断地解决问题中，我们才能更好的提高自己分析问其解决问题的能力。还有一点是我们能充分利用周围的有效资源来解决问题，不能“闭门造车”，我们可以请教周围的同学及老师，或是寻早网上资源和书本资料来解决，在这个信息社会里，如何有效处理信息的能力也是解决问题所应必备的。程序书写时一定要细心，错一个标点或是符号就会使结果出现错误，还有就是我们在出现问题后如何快速的找到根源。 关于程序调试能力 字符的选择
11、上要注意不能跟命令符重合，符号不能有纰漏，同时具有易读性 作为试探的数据要选取合理，不能超出范围，又得保证其有效性 对于数据结构课程设计的思考 数据和结构是两个紧密而又相互联系的概念，现实世界中数据分为很多种，而数据最终都会转换为二进制代码在计算机中处理，由于生产和生活的需要，要求数据处理的速度越来越快，一方面要求在硬件方面能够有更高的配置，例如存储器容量和中央处理单元的反应速度，而另一方面年也在要求着数据本身的识别和存储能够更有效率，其中最重要的就是数据的结构。有时候在相同的存储大小下，分别对应着两种结构，他们输出的结果就会有很大不同，以及结果的准确性和范围也会不同。 数据结构的课程的认识
12、虽然现在编程的语言有很多，例如C，C+，C#,JAVA等，但他们都离不开数据结构，在工作和学习中，很多时候需要对于数据进行处理，而数据结构的思想尤为重要，实际上很多问题都可以转化为子问题的拼接，而这些子问题下对应不同的数据结构，在学习中有很多重要的常用模型需要我们掌握。例如环，队列。链表，树，图论知识，在实际学习的过程中，我们也可以尝试着编一些程序来解决那些很经典却又很有趣味性的问题，例如本次课程设计的约瑟夫问题，后来我上网查了下约瑟夫问题的来源，那是很久以前都有了，但并不妨碍一代又一代的人来解决它。同时和它相似的还有猴子选大王的问题，都是同一种思想。同时我们也可以用它来解决现实中的问题，例如本次课程设计中还有停车场，校园导游等问题。