约瑟夫环课程设计报告_第1页
约瑟夫环课程设计报告_第2页
约瑟夫环课程设计报告_第3页
约瑟夫环课程设计报告_第4页
约瑟夫环课程设计报告_第5页
已阅读5页,还剩11页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

沈阳航空航天大学课程设计报告课程设计名称:数据结构课程设计课程设计题目:约瑟夫环院(系):专业:班级:学号:姓名:指导教师:目录TOC\o"1—3"\h\z\uHYPERLINK\l"_Toc345596962"1课程设计介绍ﻩPAGEREF_Toc345596962\h1HYPERLINK\l"_Toc345596963"1.1课程设计内容ﻩPAGEREF_Toc345596963\h1HYPERLINK\l”_Toc345596964”1.2课程设计要求 PAGEREF_Toc345596964\h1HYPERLINK\l"_Toc345596965"2课程设计原理 PAGEREF_Toc345596965\h2HYPERLINK\l"_Toc345596966"2.1课设题目粗略分析 PAGEREF_Toc345596966\h2HYPERLINK\l”_Toc345596967"2。2原理图介绍ﻩPAGEREF_Toc345596967\h2HYPERLINK\l”_Toc345596968"2.2.1功能模块图(如图2.1) 5596968\h2HYPERLINK\l”_Toc345596969"2.2。2流程图分析 PAGEREF_Toc345596969\h3HYPERLINK\l"_Toc345596970”3数据结构分析ﻩPAGEREF_Toc345596970\h5HYPERLINK\l”_Toc345596971"3.1存储结构ﻩPAGEREF_Toc345596971\h5HYPERLINK\l"_Toc345596972"3.2算法描述 PAGEREF_Toc345596972\h5HYPERLINK\l”_Toc345596973"4调试与分析ﻩPAGEREF_Toc345596973\h6HYPERLINK\l"_Toc345596974"4。1调试过程ﻩPAGEREF_Toc345596974\h6HYPERLINK\l”_Toc345596975”4。2程序执行过程 PAGEREF_Toc345596975\h6HYPERLINK\l”_Toc345596976”参考文献 PAGEREF_Toc345596976\h8HYPERLINK附录(关键部分程序清单)ﻩPAGEREF_Toc345596977\h91课程设计介绍1.1课程设计内容编号为1,2,……,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个开始重新从1报数,如此下去,直至所有人全部出列为止,设计一个程序求出出列顺序。使用单循环链表作为存储结构分析:由题意可以将每个人看做链表上的一个节点,每个人持有的密码即为每个节点所存储的数据;相邻的人之间存在连结关系,即链表的两个相邻节点之间由指针来进行关联;最后一个人和第一个人也存在连结关系,即链表的末尾节点和头结点相连构成了单循环链表存储结构.执行报数过程可以看做一个单独指针依次指向每一个节点,有人出列即删除掉链表中相应的节点。1。2课程设计要求1。参考相应的资料,独立完成课程设计任务。2。交规范课程设计报告和软件代码。2课程设计原理2。1课设题目粗略分析根据课设题目要求,程序应该分为两大部分:1、单循环链表储存结构的建立:建立所需的单循环链表数据存储结构,对每个节点输入所需的密码、序号数据并通过指针连接成单循环链表。2、实现约瑟夫环数据出列顺序的算法:依照题目要求按照报数上限对节点进行查找和删除操作,按顺序输出出列的节点序号,依照每次出列的节点存储的密码修改报数上限循环操作直到全部节点出列完毕程序运行结束。2。2原理图介绍2。2.1功能模块图(如图2.1)约约瑟夫环输出出列顺序建立单循环链表输出出列顺序建立单循环链表图2.1功能模块图2.2.2流程图分析1。主程序图,如图2.2:首先建立单循环链表作为数据存储结构并存储数据,然后如果执行报数。如果链表中剩余节点数大于1,执行报数操作,得到节点的序号数据并输出;若链表中只剩一个节点,输出节点的序号数据,程序运行结束。开开始构建单循环链表;构建单循环链表;选定报数上限m;链链表中节点数大于1是是报数并保存报数并保存数据删除节点否否选定新的报数上限选定新的报数上限m为删除节点储存的密码

输出结果输出结果结束结束图2。2主程序图2.构建单循环链表流程图,如图2.3:首先为链表存储空间,然后判断节点数是否达到上限,若没有到达上限,构建新节点;若已到达上限,将末尾节点的指针指向头结点形成单循环链表并结束建立链表操作。开开始分配存储空间分配存储空间节点数达到最大节点数达到最大否否构建新节点构建新节点是是末尾节点指向表头末尾节点指向表头结束结束图2。3构建单循环链表流程图3数据结构分析3。1存储结构typedefstructLNode{ﻩintdata;//每个人持有的密码intnum;//每个人的编号 structLNode*next;//指向下一个节点的指针}LNode,*LinkList;//定义一个结构体为一个持有密码的人3。2算法描述1。构建单循环链表:首先定义结构体节点指针节点p,链表L,头指针head。使head指向L的头结点,p指向L。对结构体p的数据部分进行输入赋值作为L的一个节点然后向后移一位。循环此步操作形成单链表.最后将末尾节点的指针指向头结点形成单循环链表.2.约瑟夫环出列操作:首先定义指针J和K,指针J指向单循环链表的第一个节点,随机生成一个报数上限m值.将指针p向后拨m-1次,此时p所指向节点的下一个节点即为要出列的节点,使指针K指向该节点,将这个节点从链表中删除,然后读取其中存储的序号数据输出,读取其中存储的密码作为新的m值.然后继续反复执行拨指针p,出列节点,读取数据操作,直到链表中只剩下一个节点停止循环操作,此时输出最后一个节点中的序号数据完成全部出列操作。4调试与分析4.1调试过程调试过程中出现errorC2065:'rand’:undeclaredidentifier报错,在添加预处理命令#includes“time。h”后正常执行;在执行过程中出现极大数据,发现构建循环链表时将末尾指针指向了头结点,改为指向头结点的下一个节点之后正常运行;4。2程序执行过程1.如图4.1所示,当输入人数为5,每个人所持有的密码依次为2、4、6、8、10时,输出结果:出列顺序为:1-〉3-〉2—>5->4,程序运行正确。图4。1当人数为5时的程序运行结果2.如图4.2所示,当输入人数为10,每个人所持有的密码依次为9、1、5、7、3、6、8、2、4、10时,输出结果:出列顺序为:8—>10—〉2—>3->9-〉6->1—〉7->5-〉4,程序运行正确。图4.2当人数为10时的程序运行结果参考文献[1]严蔚敏,吴伟民。数据结构[M].北京:清华大学出版社,2007.[2]张长海,陈娟。C程序设计[M].北京:高等教育出版社,2004.[3]谭浩强.C程序设计[M].北京:清华大学出版社,2005。[4]苏士华,黄学俊。数据结构解析.习题。课程设计[M].合肥:中国科学技术大学出版社,2009。[5]张瑞军.数据结构[M]。北京:清华大学出版社,2009.[6]刘怀亮.数据结构习题解析与实验指导[M].北京:冶金出版社,2009.[7]王敬华,林萍,张清国。C语言程序设计教程(第二版)[M].背景:清华大学出版社,2005。附录(关键部分程序清单)#include<stdafx.h>#include〈stdio。h>#include"stdlib.h”#include<string.h〉#include〈malloc.h>#include〈math。h>#include”time。h”typedefstructLNode{ﻩintdata; intnum; structLNode*next;}LNode,*LinkList;voidcreatelist(LinkList&L,intn){ LinkListp,head; inti,a; L=(LinkList)malloc(sizeof(LNode)); head=L;ﻩfor(i=0;i<n;i++) {ﻩﻩp=(LinkList)malloc(sizeof(LNode));ﻩﻩprintf(”请输入第%d个人的密码\n",i+1);ﻩﻩscanf("%d",&a); ﻩp->data=a; p—〉num=i+1; ﻩL-〉next=p; p—〉next=NULL; L=p;ﻩ}ﻩp->next=head—>next;}voidmain(){ﻩintn,m,x,k,l;ﻩLinkListJ,L,K;ﻩprintf("请输入人数:\n”);ﻩscanf("%d”,&n); createlist(L,n);ﻩJ=L;ﻩsrand((unsigned)time(NULL));ﻩm=rand()%n;ﻩprintf("出列顺序为:");ﻩfor(l=0;l<n-1;l++)ﻩ{ﻩfor(k=0;k<m-1;k++)ﻩ { ﻩJ=J—〉next;ﻩﻩ} K=J-〉next; J—〉next=K->next;ﻩx=K->num;ﻩprintf(”%d->”,x);ﻩﻩm=K-〉data;ﻩﻩfree(K); }ﻩx=J—〉num; printf(”%d\n",x);}ﻬ课程设计总结:在老师让我们在课设题目中选择一道时,我看到这道题的条件似乎很有思考的价值,有点类似于ACM比赛题目便选择了这道题目.在完成了课程设计的过程中我并没有遇到太大的阻碍,一开始就对题目的理解十分透彻,有很清晰的解题思路,编写代码以及调试程序的过程也十分顺利,仅仅遇到了几个小的问题,经过仔细的推敲就得以成功解决。整个过程几乎不需要借助参考和帮助就轻松独立完成。这次课程设计对我的数据结构以及C语言学习掌握有很大帮助,它让我对链表这一存储结

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论