约瑟夫环课程设计报告

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：约瑟夫环院（系）：专业:班级：学号:姓名：指导教师：目录TＯC\o"1—3＂＼h\ｚ＼uHYPEＲＬIＮＫ\l"_Tｏc3４5５96９62"1课程设计介绍ﻩＰＡＧERＥF_Toc3４55９６9６2\h1ＨYPERLINＫ\ｌ＂_Ｔoc34559６9６３＂1.1课程设计内容ﻩPＡGEREF_Tｏc345596９６3\ｈ1ＨYPERLＩＮK\l”_Ｔoc３45596964”1.2课程设计要求 PAGEREF_Toｃ345596９6４\ｈ1ＨＹPEＲLIＮＫ＼l＂_Ｔoc34５5969６5"2课程设计原理 PAＧEREF_Toc34５５9６９65\h2HYPERLIＮK\l"_Ｔoc34559６966"2．1课设题目粗略分析 ＰAGＥREF_Toｃ345５96９66\ｈ２HYＰERLINK\ｌ”＿Ｔｏｃ３455９６967＂2。２原理图介绍ﻩＰAGERＥF_Tｏc3４5596967\h2ＨYPERＬINK\ｌ”_Tｏc３4５596968＂2.2．１功能模块图（如图２.1) ５５９69６8\h2ＨＹPERLINK＼l”_Toc3４5５969６9"２.２。2流程图分析 ＰＡGEREF_Ｔｏc３4559６９６9\h3ＨYPERLＩＮK\ｌ＂＿Toｃ345５9697０”3数据结构分析ﻩPAＧＥREF_Tｏｃ34５596970＼h5ＨYPEＲLＩNK\ｌ”_Toc３4559６971"３．１存储结构ﻩPAＧＥREF_Toc３４5596971\h5HYPERLINK＼l"_Ｔoc3４５59６972＂3．2算法描述 PAGEREF＿Toc３45５96972\h5HYPERLINK\ｌ”_Ｔoc3455９6９73＂4调试与分析ﻩPAGEREＦ_Toc３45５9６9７3\h6HYPERLIＮK＼l＂＿Ｔｏc３4５596974＂4。１调试过程ﻩPＡGEREF＿Ｔoｃ３４5596974＼ｈ6HYPＥRＬＩNK\l”_Tｏc34５５96975”4。２程序执行过程 ＰAGEREF＿Tｏc3４５5969７5\h６HYＰＥRLIＮK\l”_Toｃ34559６976”参考文献 PAGEREF_Ｔoc3４5596976\h8ＨYＰERLINK附录(关键部分程序清单）ﻩＰAGEREF＿Toc3４5596977＼h9１课程设计介绍1.1课程设计内容编号为1，２，……，ｎ的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数）.一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数,报ｍ的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数,如此下去,直至所有人全部出列为止，设计一个程序求出出列顺序。使用单循环链表作为存储结构分析：由题意可以将每个人看做链表上的一个节点，每个人持有的密码即为每个节点所存储的数据；相邻的人之间存在连结关系,即链表的两个相邻节点之间由指针来进行关联；最后一个人和第一个人也存在连结关系，即链表的末尾节点和头结点相连构成了单循环链表存储结构.执行报数过程可以看做一个单独指针依次指向每一个节点，有人出列即删除掉链表中相应的节点。1。２课程设计要求1。参考相应的资料，独立完成课程设计任务。2。交规范课程设计报告和软件代码。２课程设计原理2。1课设题目粗略分析根据课设题目要求，程序应该分为两大部分：1、单循环链表储存结构的建立:建立所需的单循环链表数据存储结构,对每个节点输入所需的密码、序号数据并通过指针连接成单循环链表。2、实现约瑟夫环数据出列顺序的算法:依照题目要求按照报数上限对节点进行查找和删除操作，按顺序输出出列的节点序号,依照每次出列的节点存储的密码修改报数上限循环操作直到全部节点出列完毕程序运行结束。２。2原理图介绍2。2．1功能模块图（如图2.1)约约瑟夫环输出出列顺序建立单循环链表输出出列顺序建立单循环链表图２．１功能模块图2.2．2流程图分析1。主程序图，如图２．2：首先建立单循环链表作为数据存储结构并存储数据，然后如果执行报数。如果链表中剩余节点数大于１，执行报数操作,得到节点的序号数据并输出;若链表中只剩一个节点，输出节点的序号数据，程序运行结束。开开始构建单循环链表；构建单循环链表；选定报数上限m；链链表中节点数大于1是是报数并保存报数并保存数据删除节点否否选定新的报数上限选定新的报数上限m为删除节点储存的密码

输出结果输出结果结束结束图2。2主程序图2．构建单循环链表流程图，如图2．3：首先为链表存储空间，然后判断节点数是否达到上限,若没有到达上限，构建新节点；若已到达上限，将末尾节点的指针指向头结点形成单循环链表并结束建立链表操作。开开始分配存储空间分配存储空间节点数达到最大节点数达到最大否否构建新节点构建新节点是是末尾节点指向表头末尾节点指向表头结束结束图2。3构建单循环链表流程图3数据结构分析3。1存储结构typedeｆｓtructLNｏde｛ﻩiｎtdatａ；//每个人持有的密码iｎｔnuｍ；//每个人的编号 ｓｔruｃｔLNｏｄe＊nexｔ；//指向下一个节点的指针｝LNode,＊ＬinｋList；/／定义一个结构体为一个持有密码的人３。２算法描述1。构建单循环链表：首先定义结构体节点指针节点p，链表L,头指针head。使head指向L的头结点，ｐ指向L。对结构体ｐ的数据部分进行输入赋值作为Ｌ的一个节点然后向后移一位。循环此步操作形成单链表.最后将末尾节点的指针指向头结点形成单循环链表.２.约瑟夫环出列操作：首先定义指针Ｊ和K，指针Ｊ指向单循环链表的第一个节点，随机生成一个报数上限m值.将指针p向后拨m-１次,此时p所指向节点的下一个节点即为要出列的节点，使指针K指向该节点，将这个节点从链表中删除,然后读取其中存储的序号数据输出，读取其中存储的密码作为新的ｍ值.然后继续反复执行拨指针ｐ，出列节点，读取数据操作，直到链表中只剩下一个节点停止循环操作,此时输出最后一个节点中的序号数据完成全部出列操作。4调试与分析4.1调试过程调试过程中出现eｒｒｏrC2０６５：'ranｄ’：ｕｎｄeclarｅｄｉdｅntifiｅr报错,在添加预处理命令#inclｕｄes“tｉme。h”后正常执行；在执行过程中出现极大数据，发现构建循环链表时将末尾指针指向了头结点，改为指向头结点的下一个节点之后正常运行；4。2程序执行过程1.如图4．1所示，当输入人数为５,每个人所持有的密码依次为2、4、6、8、10时，输出结果：出列顺序为：1-〉3-〉2—>５－＞4,程序运行正确。图４。１当人数为5时的程序运行结果2．如图4.2所示,当输入人数为10，每个人所持有的密码依次为9、１、5、７、３、6、８、2、4、1０时，输出结果:出列顺序为：8—＞10—〉２—>３->9-〉６->1—〉7->5－〉４，程序运行正确。图4．2当人数为1０时的程序运行结果参考文献[1］严蔚敏，吴伟民。数据结构[Ｍ］．北京：清华大学出版社，2007.[2]张长海，陈娟。C程序设计[M］．北京:高等教育出版社，20０4.［3］谭浩强.C程序设计［M］.北京:清华大学出版社,2005。［４]苏士华，黄学俊。数据结构解析．习题。课程设计［M].合肥：中国科学技术大学出版社，２0０9。［5］张瑞军.数据结构[M]。北京：清华大学出版社,2００9.［6］刘怀亮．数据结构习题解析与实验指导[M］.北京：冶金出版社，200９．［7]王敬华，林萍，张清国。Ｃ语言程序设计教程（第二版)[M].背景：清华大学出版社,200５。附录(关键部分程序清单)#incｌｕdｅ<stdafｘ.h>＃ｉnｃｌude〈stｄio。ｈ>#ｉnclude"sｔｄｌib.ｈ”#includｅ<ｓtｒing．h〉＃inｃluｄｅ〈ｍalloc．h＞#iｎclude〈ｍａth。h>＃inclｕde”ｔimｅ。h”typedefstrucｔLNode｛ﻩiｎtdata; inｔｎum； sｔrucｔLＮｏde＊nexｔ;｝LＮｏde，*LinkLiｓt；ｖoidｃｒｅatｅｌｉst(ＬinｋＬist＆L,iｎtｎ）｛ ＬinkLｉstp,head; intｉ，a； Ｌ＝(LiｎkList）malloc(sｉzeoｆ（LＮode)）; heaｄ=L；ﻩｆor（i＝０;ｉ＜ｎ；i++） ｛ﻩﻩｐ＝(LｉnkList)malｌoｃ(sizeof（LNode));ﻩﻩpriｎｔｆ（”请输入第%d个人的密码\n"，i＋1）；ﻩﻩscanf("％ｄ＂，&a）； ﻩp－＞data=a; p—〉num＝i+1； ﻩL-〉next=p； ｐ—〉nｅxt=ＮＵLL； L＝p;ﻩ}ﻩｐ->ｎeｘt＝ｈｅad—＞nｅｘt;｝voidmain（）{ﻩｉnｔn，m，x,k，ｌ；ﻩＬinkＬistJ,L，K；ﻩｐrｉnｔｆ（＂请输入人数：\n”);ﻩｓcanf（＂%d”,&n)； creａtｅlｉsｔ（L，ｎ）；ﻩJ=L;ﻩｓrａnd（（uｎsigｎed)time(NUＬL））；ﻩｍ=ｒanｄ（)%ｎ；ﻩｐriｎtf（"出列顺序为:＂);ﻩfor(l=0；l＜n－１；l++）ﻩ｛ﻩfor(ｋ=０;k＜m－１；k++)ﻩ ｛ ﻩJ=J—〉ｎexｔ；ﻩﻩ｝ Ｋ＝J-〉nｅxｔ; J—〉next=K-＞ｎeｘｔ;ﻩx＝K-＞ｎｕm;ﻩprinｔｆ(”％d->”，ｘ);ﻩﻩm=K－〉data;ﻩﻩfｒee（K)； ｝ﻩx=J—〉ｎuｍ; pｒintf（”%d\n＂，x）;｝ﻬ课程设计总结:在老师让我们在课设题目中选择一道时，我看到这道题的条件似乎很有思考的价值,有点类似于ＡCM比赛题目便选择了这道题目.在完成了课程设计的过程中我并没有遇到太大的阻碍，一开始就对题目的理解十分透彻，有很清晰的解题思路，编写代码以及调试程序的过程也十分顺利，仅仅遇到了几个小的问题，经过仔细的推敲就得以成功解决。整个过程几乎不需要借助参考和帮助就轻松独立完成。这次课程设计对我的数据结构以及C语言学习掌握有很大帮助,它让我对链表这一存储结