数据结构课程设计报告-约瑟夫环

课程设计介绍 11.1课程设计内容 11.2课程设计要求 12课程设计原理 22.1课设题目粗略分析 22.2原理图介绍 32.2.1功能模块图 32.2.2流程图分析 43数据结构分析 73.1存储结构 73.2算法描述 74调试与分析 94.1调试过程 94.2程序执行过程 10参考文献 15附录（关键部分程序清单） 161课程设计介绍1.1课程设计内容设计程序，系统主要功能如下：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。1.2课程设计要求1.参考相应的资料，独立完成课程设计任务书。2.交规范课程设计报告和软件代码。2课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为四大模块。此四个模块相互独立，没有嵌套调用的情况，以下是四个模块的大体分析：main()函数是主要的控制函数，main()函数主要负责存储用户输入的基本数据以及调用其他子函数模块，在main()函数中还存在一个比较小的函数模块exit(0),该函数模块负责终止程序运行，另外还有两个子函数模块，分别是random()函数模块与solid()函数模块，这两个函数模块分别各自负责自己所要处理的数据以及输出功能；在程序运行之后，在程序主界面出现之后，当用户自己输入了自己想要实现的功能模块所在的数字选项后，立即进入主函数模块之中，当用户输入了所有的必要数据之后，按照用户选定的数字选项所要实现的功能调用相应的子函数；如果用户选择的是系统随机产生密码的选项，则main()函数就调用random()子函数模块，在random()函数模块中，将会随机产生各个参与者的密码，并且同时建立链表来存储、处理这些数据，在完成了所有的操作之后，random()函数就将输出结果，反之，如果用户选择的是用户自己输入密码的选项，则main()函数就调用solid()函数模块，在solid()函数模块中，将会提醒用户自己一个个的输入每个参与者的密码，与此同时建立链表来存储、处理这些数据，在完成了所有的操作之后，solid()函数就将输出结果。2.2原理图介绍2.2.1功能模块图用户输入数据random()函数模块来随机产生参与者的密码，并且存储、处理这些数据，之后输出它们exit(0)函数负责终止程序运行solid()函数模块来提示用户输入密码并且存储、处理这些数据，之后输出结果根据程序启动时用户所选的数字选项，main()函数来调用相应的子函数模块random()函数模块来随机产生参与者的密码，并且存储、处理这些数据，之后输出它们exit(0)函数负责终止程序运行solid()函数模块来提示用户输入密码并且存储、处理这些数据，之后输出结果根据程序启动时用户所选的数字选项，main()函数来调用相应的子函数模块图2.1功能模块图2.2.2流程图分析1.如图2.2，random()函数的执行过程如下；开始输入第一个报的数key及系统随机产生各个参与者的密码输入第一个报的数key及系统随机产生各个参与者的密码n==0n==0报数过程 N报数过程 Y输出出列者的编号及密码输出出列者的编号及密码结束n--结束n--图2.2random()函数流程图2.如图2.3，solid()函数的执行过程如下；开始用户输入各个参与者的密码及第一个要报的数key用户输入各个参与者的密码及第一个要报的数keyn==0n==0N报数过程报数过程 Y输出出列者的编号及密码输出出列者的编号及密码n--n--结束结束图2.3solid()函数流程图3.如图2.4，main()函数的执行过程如下。开始输入总人数n输入总人数n创建并初始化n个节点创建并初始化n个节点输入第一个要报的数key输入第一个要报的数keyn==0n==0N报数过程报数过程 Y输出出列者的编号及密码输出出列者的编号及密码结束n--结束n--图2.4main()函数流程图3数据结构分析3.1存储结构num code next图3.1数据存储结构3.2算法描述 1.用户输入数据；while(scanf("%d",&p)!=EOF) { if(p==1) random(); elseif(p==2) solid(); else exit(0); printf("*************************欢迎进入约瑟夫环问题求解系统*************************\n\n"); printf("1.按照系统随机给出的密码进行2.按照自己输入的密码进行3.退出该系统\n\n"); printf("********************请输入您要实现的功能模块所在的数字选项!********************\n\n"); }random()函数随机产生各个参与者的密码，用户在此函数中输入第一个要报的数，此函数之后会排好各个参与者的出列顺序；or(i=1;i<=n;i++) {key=rand()%100; printf("第%d个人的密码:%d\n",i,key); s=p; p=(list*)malloc(sizeof(list));//创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p);//释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code);//输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key);3.solid()函数提示用户输入各个参与者的密码及第一个要报的数，并且排好各个参与者的出列顺序。for(i=1;i<=n;i++) {scanf("%d",&key); printf("第%d个人的密码:%d\n",i,key); s=p; p=(list*)malloc(sizeof(list));//创建新的结点. s->next=p; p->num=i; p->code=key; printf("请输入密码:"); } p->next=head->next; p=head; head=head->next; free(p);//释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code);//输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key);}4调试与分析4.1调试过程在调试程序是主要遇到一下几类问题：1.调试过程中,曾出现过缺少分号、括号之类的错误,还出现过运算顺序颠倒，致使运算出现了错误，在经过仔细的检查并且向人请教,终于得出了正确结果.这次的课程设计的代码比较冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写好后运行，出现了很多错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。2.在随机设置每个结点的key时也曾是个问题，因为我做的随机函数一直都用不好，要不是每次随到的都是一样的，要么就是每次随到的数都很大，后来通过学长的耐心讲解才得以解决。在调试的过程中，类的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。4.2程序执行过程*************************欢迎进入约瑟夫环问题求解系统*************************系统使用说明：1.进入程序主界面后，会出现三个选项，按1则是随系统随机产生的密码进行该问题求解，按2则是随用户自己输入的密码进行该问题求解，按3则是退出系统；2.选定了进行方式后，输入该问题所涉及的总人数，如果用户按了1，则随机产生密码，用户则只再需要输入第一个人要报的数即可，如果用户按了2，则是用户自己手动输入密码，输入完了所有人的密码后，之后再输入第一个人要报的数；3.随着程序的运行，结果就会随之出来，随后进入下一次该问题求解进程，直到用户自己选择退出该程序，该程序才会结束。西安交通大学课程设计报告参考文献[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007.[2]张长海，陈娟.C程序设计[M].北京：高等教育出版社，2004.[3]谭浩强.C程序设计[M].北京：清华大学出版社，2005.[4]《数据结构》（用面向对象方法与C++描述），殷人昆等，清华大学出版社。[5]《算法与数据结构习题精解和实验指导》，宁正元等，清华大学出版社。[6]张乃孝,裘宗燕.数据结构C++与面向对象的途径.北京：高等教育出版社，1998[7]周云静．数据结构习题解析与上机指导．北京：冶金工业出版社，2004[8]陈慧南．数据结构—C++语言描述．北京：人民邮电出版社，2005[9]严蔚敏，吴伟民．数据结构．北京：清华大学出版社，1997附录（关键部分程序清单）程序代码#include<stdio.h>#include<stdlib.h>structlist{ intnum,code; structlist*next;};intmain(){ voidrandom(); voidsolid(); intp; printf("*************************欢迎进入约瑟夫环问题求解系统*************************\n\n"); printf("1.按照系统随机给出的密码进行2.按照自己输入的密码进行3.退出该系统\n\n"); printf("********************请输入您要实现的功能模块所在的数字选项!********************\n\n"); while(scanf("%d",&p)!=EOF) { if(p==1) random(); elseif(p==2) solid(); else exit(0); printf("*************************欢迎进入约瑟夫环问题求解系统*************************\n\n"); printf("1.按照系统随机给出的密码进行2.按照自己输入的密码进行3.退出该系统\n\n"); printf("********************请输入您要实现的功能模块所在的数字选项!********************\n\n"); } return0;}voidrandom(){ inti,j,m=1; intkey;//密码. intn;//人数.list*p,*s,*head; head=(list*)malloc(sizeof(list));//为头结点分配空间. p=head; printf("输入人的总个数:\n"); scanf("%d",&n); for(i=1;i<=n;i++) {key=rand()%100; printf("第%d个人的密码:%d\n",i,key); s=p; p=(list*)malloc(sizeof(list));//创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p);//释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code);//输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do {j=1; p=head; while(j<key){ s=p; p=p->next; j++; }//报数过程. i=p->num; key=p->code; printf("%d:第%d号成员出列\n",m,i); m++; s->next=p->next; head=p->next;//重新定义head,下次循环的开始结点. free(p);//释放已出列的结点. n--;//人数减一. }while(n>0);}voidsolid(){ inti,j,m=1; intkey;//密码. intn;//人数.list*p,*s,*head; head=(list*)malloc(sizeof(list));//为头结点分配空间. p=head; printf("输入人的总个数:\n"); scanf("%d",&n); printf("请输入密码:"); for(i=1;i<=n;i++) {scanf("%d",&key); printf("第%d个人的密码:%d\n",i,key); s=p; p=(list*)malloc(sizeof(list));//创建新的结点. s->next=p; p->num=i; p->code=key; printf("请输入密码:"); } p->next=head->next; p=head; head=head->next; free(p);//释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code);//输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do {j=1; p=head; while(j<key){ s=p; p=p->next; j++; }//报数过程. i=p->num; key=p->code; printf("%d:第%d号成员出列\n",m,i); m++; s->next=p->next; head=p->next;//重新定义head,下次循环的开始结点. free(p);//释放已出列的结点. n--;//人数减一. }while(n>0);}课程设计总结：为期二周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。指导教师评语：指导教师(签字)：年月日课程设计成绩基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统基于51单片机的嵌入式Internet系统的设计与实现单片机监测系统在挤压机上的应用MSP430单片机在智能水表系统上的研究与应用基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用单片机在高楼恒压供水系统中的应用基于ATmega16单片机的流量控制器的开发基于MSP430单片机的远程抄表系