数据结构课程设计摸版.doc

扬州工业职业技术学院学生课程设计题 目： * 学生姓名： * 学 号： 2011108010 所在院(系)： 电气信息工程学院 专 业： 计算机应用技术专业 班 级： 1301计算机 指 导 教 师： 郭 静 职 称： 讲 师 2014年06月 18 日任务书题目学生搭配问题1、课程设计的目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等） 一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3) 尽量设计出多种算法及程序,可视情况适当加分 提示:用队列来解决比较方便.3、主要参考文献1数据结构（C语言版），严蔚敏，清华大学出版社，20032数据结构题集，严蔚敏，清华大学出版社，20053数据结构（C语言版），刘大有，高等教育出版社，20044Data Structure with C+，William FordWilliam Topp，清华大学出版社，20034、课程设计工作计划 完成方案设计与程序框图 编写程序代码 程序调试分析和结果 课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）： 接受任务时间： 年 月 日注：任务书由指导教摘 要本次课程设计是利用数据结构的知识编写一个能够实现学生配对的问题的软件，以达到在每一首歌曲中能够有学生配对来进行舞蹈表演。为了实现这一个功能我们用利用已学的知识进行编写程序。通过学习数据结构课程和c语言的知识，主要利用数据结构的队列和C语言知识来实现软件的功能。主要是把男女生分别放在两个队列中，要涉及到队列的判断和循环等算法。判断队列的满和空的知识来完成。关键字：学生搭配问题，数据结构，队列，C语言，软件，功能目 录摘要IV1.方案设计21.1问题描述21.2需求分析21.3运行环境21.4概要设计22.算法设计42.1算法设计思想42.2算法设计的对应方式42.3算法设计流程图43.详细设计63.1设计思想63.2设计关键算法64.调试分析84.1、测试及结果85.总结10参考文献11程序清单121.方案设计1.1问题描述一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下: 1) 输出每曲配对情况 2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值。1.2需求分析核心问题：循环队列的应用数据模型（逻辑结构）：循环队列（两个），将男生、女生两组人分别存放，以后实现循环配对输出。存储结构：循环链表核心算法：循环队列的入队，出队，判队满，判队空。输入数据：男生人数、女生人数，歌曲数量输出数据：每一首歌曲播放时，男生和女生搭配情况（输出编号）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。1.3运行环境硬件开发环境：PC机软件开发环境：VC+ 6.0操作系统环境Window XP 1.4概要设计整个设计的流程图主函数输入数据每曲配对第K曲配对输出编号图1.12.算法设计2.1算法设计思想队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。 循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。（1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。（2） 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。（3） 利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。（4） 循环队列的长度分别设为男女生的个数即可。（5） 在计算机终端输出的结果是：根据要求输出男生女生搭配情况。2.2算法设计的对应方式假如有3个男生2个女生的配对方式歌曲编号（k）1234567男生编号(m=3)1231231女生编号(n=2)1212121图 22.3算法设计流程图开始InitQ输入男女个数和曲数m,n,k和查找的编号For(i=1,Inext=NULL;(2)关键算法之二：入队函数void EnQueue(LinkQueue &Q,int num)/入队函数QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode);p-num=num;p-next=NULL;Q.rear-next=p;Q.rear=p;(3)关键算法之三：出队函数void DeQueue(LinkQueue &Q, int &num)/出队函数QueuePtr p,q; if(Q.front=Q.rear)printf(队列为空);p=Q.front-next;num=p-num;Q.front-next=p-next;q=p-next;if(Q.rear=q)Q.rear=Q.front;free(p);(4)关键算法之四：输出第i首曲子时女队的情况void printF(LinkQueue &F,int i) /输出第i首曲子时女队的情况QueuePtr p; int n=1;while(nnext;while(F.rear!=p) printf(%d ,p-num);p=p-next;printf(%d n,p-num);4.调试分析4.1、测试及结果1. 测试输入数据：男女生的个数曲子数图42. 要查找学生的编号:图 53.输出结果为：每首曲子男女生搭配的情况程序运行界面如下：图 65.总结通过一周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C语言描绘出关键算法。以前我对数据结构（C语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这一周的学习让我对数据结构（C语言描述）有了新的认识，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在这次课程设计的实验中，我收获了许多知识，通过查找大量资料，请教老师，以及不懈的努力，也培养了独立思考、动手操作的能力。我也学会了许多学习和解决实际问题的方法，让我受益匪浅。时间的紧缺成为一个很大的问题。也希望老师可以为我们知道一下以后的发展方向。如果可以让每个人都有动手焊接以及参与其他的各个流程，有专门的知道就更好了。课程设计对我来说，趣味性强，不仅锻炼能力，而且可以学到很多东西，在与老师和同学的交流过程中，互动学习，将知识融会贯通，也增强了我和同学之间的团队合作的能力。让我们知道只要努力，集中精力解决问题，一定会有收获的，过程也是很重要的。在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用C语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得更好的成绩。我们会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，我们会更加珍惜拥有的，更加努力的去完善它，增进它。要是能够让输出的结果在完美一点就好了，比如说龙一个设计封面。在输出结果不会像从1-k曲连续输出一样。还有从编号的数可以超过人数。参考文献1 徐孝凯编著。数据结构实用教程（C/C+描述）。北京：清华大学出版社，19992 严蔚敏主编。数据结构题集（语言版）。北京：清华大学出版社，20063 孙巧萍主编。数据结构实训教程。北京： 科学出版社 ， 2000附页一程序清单#include #include#include #include #define MAXSIZE 60#define TRUE 1 #define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1typedef int system;typedef struct QNode int num;struct QNode *next;QNode,* QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;void sleep( clock_t wait ) /延迟函数 clock_t goal; goal = wait + clock(); while( goal clock() ) ; void InitQ(LinkQueue &Q) /建立空队列QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode);Q.front=p;Q.rear=p;Q.front-next=NULL;void EnQueue(LinkQueue &Q,int num)QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode);p-num=num;p-next=NULL;Q.rear-next=p;Q.rear=p;void DeQueue(LinkQueue &Q, int &num)QueuePtr p,q; if(Q.front=Q.rear)printf(队列为空);p=Q.front-next;num=p-num;Q.front-next=p-next;q=p-next;if(Q.rear=q)Q.rear=Q.front;free(p);void printF(LinkQueue &F,int i) /打印第i首曲子时女队的情况QueuePtr p; int n=1;while(nnext;while(F.rear!=p) printf(%d ,p-num);p=p-next;printf(%d n,p-num);void printM(LinkQueue &M,int i) /打印第i首曲子时男队的情况QueuePtr p;int n=1;while(nnext;while(M.rear!=p) printf(%d ,p-num);p=p-next;printf(%d n,p-num);void main() int m,n,k,i,a,b;int count=0,num;QueuePtr p,q;LinkQueue F; /女生队LinkQueue M; /男生队printf(请输入女生数量：);scanf(%d,&m);printf(请输入男生数量：);scanf(%d,&n);printf(请输曲子号：);scanf(%d,&k);printf(请输入要查找的男生编号：);scanf(%d,&a);printf(请输入要查找的女生编号：);scanf(%d,&b);InitQ(F);InitQ(M);for(i=1;i=m;i+)