项目作业文档模板

1、PAGE PAGE 1湖南大众传媒学院网络传媒系算法与数据结构课程设计报告姓 名：班 级：学 号：指导教师师： 年月日日数据结构课程设计 PAGE 8课程设计计综合成成绩评定定设计题目目一：约瑟瑟夫生者者死者游游戏考核项目目分值AC得分设计情况况（共770分）设计工作作量与难难度20设计工作作量大与与设计有有一定难难度设计工作作量与难难度一般般，基本本达到了了要求设计方案15设计方案案正确、合理设计方案案较正确确、基本本合理，但不是是最优设计完成成情况35完成了选选题的设设计内容容，设计计功能完完整，相相关算法法设计正正确，程程序结果果正确、直观性性好基本完成成了选题题的设计计内容及及主要选选

2、题功能能，相关关算法设设计基本本正确，程序结结果正确确设计报告告（共115分）报告组织织结构及及内容10内容组织织及结构构合理、内容充充实、层层次清晰晰、图表表得当内容组织织及结构构较合理理、内容容较充实实、层次次较清晰晰、图表表应用基基本得当当报告排版版格式5格式规范范，完全全符合要要求格式基本本规范，基本符符合要求求设计态度度（共115分）15设计态度度认真、积极设计态度度比较认认真综合得分分课程设计计综合成成绩（折折合为优优、良、中、及及格与不不及格计计）其它说明明：目 录录TOC o 1-3 h z u HYPERLINK l _Toc185566256 1.约瑟瑟夫生者者死者游游戏

3、PAGEREF _Toc185566256 h 1 HYPERLINK l _Toc185566257 1.1 项目目简介 PAGEREF _Toc185566257 h 11 HYPERLINK l _Toc185566258 1.2 设计计思路 PAGEREF _Toc185566258 h 11 HYPERLINK l _Toc185566259 1.3 数据据结构 PAGEREF _Toc185566259 h 22 HYPERLINK l _Toc185566260 1.4 运行行结果 PAGEREF _Toc185566260 h 22 HYPERLINK l _Toc185566

4、266 2.总结结与分析析 PAGEREF _Toc185566266 h 4 HYPERLINK l _Toc185566267 附录 PAGEREF _Toc185566267 h 5 HYPERLINK l _Toc185566269 附录约瑟瑟夫生者者死者游游戏程序序源代码码 PAGEREF _Toc185566269 h 51.约瑟瑟夫生者者死者游游戏1.1 项目目简介约瑟夫生生者死者者游戏的的大意是是：300个旅客客同乘一一条船，因为严严重超载载，加上上风高浪浪大，危危险万分分；因此此船长告告诉乘客客，只有有将全船船一半的的旅客投投入海中中，其余余人才能能幸免遇遇难。无无奈，大大家

5、只得得同意这这种办法法，并议议定300个人围成一一圈，由由第一个个人开始始，依次次报数，数到第第9人，便把他他投入大大海中，然后从从他的下下一个人人数起，数到第第9人，再将他他投入大大海，如如此循环环，直到到剩下115个乘乘客为止止。问哪哪些位置置是将被被扔下大大海的位位置。1.2设设计思路路本游戏的的数学建建模如下下：假设设n个旅旅客排成成一个环环形，依依次顺序序编号11，2，nn。从某某个指定定的第11号开始始，沿环环计数，每数到到第m个个人就让让其出列列，且从从下一个个人开始始重新计计数，继继续进行行下去。这个过过程一直直进行到到剩下kk个旅客客为止。本游戏的的要求用用户输入入的内容包括

6、括： 1. 旅旅客的个个数，也也就是nn的值； 2. 离离开旅客客的间隔隔数，也就就是m的的值；3. 所所有旅客客的序号号作为一一组数据据要求存放放在某种种数据结结构中。本游戏要要求输出出的内容容是包括括1. 离离开旅客客的序号号； 2. 剩剩余旅客客的序号号； 所以，根根据上面面的模型型分析及输入输输出参数数分析，可以定定义一种种数据结结构后进进行算法法实现。1.3 数据据结构为了解决决这一问问题，可可以用长长度为330的数数组作为为线性存存储结构构，并把把该数组组看成是是一个首首尾相接接的环形形结构，那么每每投入大大海一个个乘客，就要在在该数组组的相应应位置做做一个删删除标记记，该单单元以

7、后后就不再再作为计计数单元元。这样样做不仅仅算法较较为复杂杂，而且且效率低低，还要要移动大大量的元元素。用用单循环环链表解解决这一一问题，实现的的方法相相对要简简单得多多。首先先要定义义链表结结点，单单循环链链表的结结点结构构与一般般的结点点结构完完全相同同，只是是数据域域用一个个整数来来表示位位置；然然后将它它们组成成具有330个结结点的单单循环链链表。接接下来从从位置为为1的结结点开始始数，数数到第88个结点点，就将将下一个个结点从从循环链链表中删删去，然然后再从从删去结结点的下下一个结结点开始始数起，数到第第8个结结点，再再将其下下一个结结点删去去，如此此进行下下去，直直到剩下下15个个

8、结点为为止。为了不失失一般性性，将330改为为一个任任意输入入的正整整数n，而报数数上限（原为99）也为为一个任任选的正正整数kk。这样样该算法法描述如如下：(1) 创建含含有n个个结点的的单循环环链表；(2) 生着与与死者的的选择：p指向链链表的第第一个结结点，初初始i置置为1；whille(iiddataa;i自增增1；(3) 输出所所有生者者的位置置。1.4运运行结果果3.总结结与分析析此程序目目前的缺缺点在于于，结点点密码数数据类型型定义的的存储类类型是iint型型，不能能超过-214474883644822147748336488，一旦旦超过则则程序输输出结果果有误，另一个个缺点就就

9、是程序序运行当当中，一一旦中途途输入出出现错误误，则无无法返回回，必须须将当前前操作结结束等到到下个主主函数的的循环开开始，或或者直接接退出重重新运行行此程序序。优点点则在于于程序运运行速度度较快，不会出出现输出出结果有有误的问问题经过这次次集中上上机的实实验，从从开始选选题到自自己上手手还是编编写程序序的过程程中，我我学会了了很多的的东西，以前对对C语言言的知识识和算法法总是模模棱两可可的，经经过这次次练习，在某些些方面上上还是经经过了加加强的训训练。此此次，实实验，从从开始构构建循环环链表然然后实现现约瑟夫夫环功能能的过程程中，中中途也遇遇见一些些问题，但都逐逐一克服服，相信信在这次次的实

10、验验中提升升了较大大的自身身动手实实践能力力。学好好数据结结构！附 录录附录1约约瑟夫生生者死者者游戏程程序源代代码LinkkLisst IInittRinng(iint n, LinnkLiist R) /尾插插入法建建立单循循环链表表函数LisstNoode *p, *qq;intt I;R=qq=(LLinkkNodde *)maallooc(ssizeeof(LinnkNoode);forr(i=1;iidaata=i;q-neext=p;q=p;p-datta=nn;p-nexxt=RR;R=pp;retturnn R;LinkkLisst DDeleeteDDeatth(iint

11、n, intt k, LiinkLListt R) /生者与与死者的的选择intt i, j;LisstNoode *p, *qq;p=RR;forr(i=1; inn/2; i+)/删删除一半半结点foor(jj=1; jneext;q=p-nexxt;p-neext=q-nexxt;prrinttf(“%4dd”, qq-ddataa);frree(q);R=p; reeturrn RR;voiid OOutRRingg(innt nn, LLinkkLisst RR) /输输出所有有生者innt ii;LiinkNNodee *pp;p=R;foor(ii=1;inexxt)pprinn

12、tf(“%4dd”, pp-ddataa)有了上述述算法分分析和设设计之后后，实现现就比较较简单了了。首先先要定义义一个链链表结构构类型，然后编编写一个个主函数数调用上上面已定定义好的的函数即即可。主主函数的的源程序序如下：#inccludde#inccluddetypeedeff sttrucct nnodeeintt daata;strructt noode * nnextt;LisstNoode;typeedeff LiistNNodee * LinnkLiist;voidd maain()LinnkLiist R;intt n,k;LinnkLiist IniitRiing(intt n, LiinkLListt R);LinnkLiist DelleteeDeaath(intt