数据结构课程设计学生搭配问题.docx
《数据结构课程设计学生搭配问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计学生搭配问题.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构课程设计学生搭配问题
数据结构课程设计
题 目:
学生搭配问题
学 院:
班 级：
学生 姓名:
学 生学号：
指 导教 师:
2012年12月 3日
课程设计任务书
姓名
班级
学号
设计题目
学生搭配问题
理论要点
队列（Qｕeue）是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。
循环队列是在队列的顺序存储结构中,除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外,尚需附设两个指针front和ｒｅar分别指示队列头元素和队列尾元素的位置。
循环队列的入队,出队,判队满，判队空。
设计目标
（1）输出每曲配对情况。
（２）计算出任何一个男生（编号为X）和任意女生（编号为Y）,在第K曲配对跳舞的情况.至少求出K的两个值。
研究方法步骤
（1）先建立两个循环队列ＳqQueue和SqQueue2。
（２）将男生、女生两组人分别存入这两个队列。
（3）将男女生分别进行入队列和出队列操作，且实现搭配输出。
（4）循环队列的长度分别设为男女生的个数即可。
（５）在计算机终端输出的结果是：
根据要求输出男生女生搭配情况。
预期结果
每一首歌曲播放时,男生和女生搭配情况（只输出编号即可）当要查找的男女搭配时输出歌曲编号,和他们搭配的总次数。
通过以上分析,该程序具有可行。
计划与进步的安排
1、20１2年11月20日之前寻找到解决问题思搭配问题的路
2、2012年1１月25日之前必须编写出程序
３、201２年1１月26日之前检查程序的运行并找出错误程序
4、２012年１1月２9日之前找到解决错误的方法
5、2０12年1１月３０日写数据结构课程设计报告
摘要
针对学生搭配问题，循环队列是一种重要的链式结构,其特殊性在于需附设两个指针frｏｎt和ｒear分别指示对头元素及队尾元素的位置且对头和队尾相邻接。
在程序的设计过程中，运用了各种基本的算法，有判断队空及队满,出队,入队等.循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外,尚需附设两个指针front和ｒｅar分别指示队列头元素和队列尾元素的位置。
学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。
本文用循环队列会很好的把这个程序设计出来,会有很好的效果。
得出的程序运行结果能够很形象的把结果表示出来。
关键词：
学生配对,数据结构，循环队列。
摘要ﻩI
2运行环境1
３算法设计的思想ﻩ1
4 算法的流程图ﻩ2
５算法设计分析2
6源代码３
7 运行结果分析8
8 收获及体会ﻩ８
参考文献ﻩ9
致谢ﻩ９
学生搭配问题
1.设计题目
一班有ｍ个女生，有n个男生（ｍ不等于ｎ）,现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时，依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴。
请设计一系统模拟动态地显示出上述过程,要求如下:
（1）输出每曲配对情况
（2）计算出任何一个男生（编号为Ｘ）和任意女生（编号为Y）,在第K曲配对跳舞的情况.至少求出K的两个值。
2．运行环境
本课题的程序设计和测试等环节都是在Windows7操作系统下完成，软件的编译测试环境为ｖc6.0以c语言编写的。
软件的硬件运行需求非常低，任何计算机都可运行。
3.算法设计的思想
基本思路:
队列（Queuｅ）是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。
循环队列是在队列的顺序存储结构中,除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外,尚需附设两个指针frｏnt和rｅar分别指示队列头元素和队列尾元素的位置。
循环队列（两个）,将男生、女生两组人分别存放,以实现循环配对输出。
循环队列的入队，出队,判队满,判队空。
（１）要模拟动态地显示出现题目中所要求的循环,我们要先建立两个循环队列ＳｑQｕｅue和SｑQueｕe2。
（２）将男生、女生两组人分别存入这两个队列。
以实现他们的循环配对输出，这是循环队列固有的特性。
（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作,且实现搭配输出。
（4）循环队列的长度分别设为男女生的个数即可。
（5） 在计算机终端输出的结果是:
根据要求输出男生女生搭配情况
关键问题:
循环队列的应用
解决方法：
数据模型（逻辑结构）:
循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。
存储结构：
循环链表
核心算法：
循环队列的入队，出队,判队满,判队空。
输入数据:
男生人数、女生人数，歌曲数量
输出数据:
每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。
通过以上分析,该程序具有可行性。
4.算法的流程图
5.算法设计分析
调试过程中出现的问题及解决方法:
问题:
在构造队列时，设队列分配的最大空间为男女生的个数，此时便无法根据Q.front=Q.rear来判别队列空间是“空”还是“满”,因此,在入队操作即插入一个新元素作为新的队尾元素时出现了问题，即最后一位同学无法入队。
解决方法:
将队列分配的最大空间至少再增加一个
6.源代码
#ｉｎclude
#inclｕｄe<ｓｔｄio.h＞
#includｅ
＃ｉncluｄe ＜malloｃ．h>
#dｅfiｎｅ MＡXＳIＺE 60
＃ｄefineTRUＥ1
#deｆineFAＬSE0
＃ｄefineOK １
＃ｄefiｎe ERROR０
#dｅｆineＯVEＲFＬＯW-1
//typeｄeｆ iｎtsystｅｍ；
typｅdｅfstrucｔQＮode｛
ｉｎt num;
structＱNode*nｅxt;
}QＮｏde，＊QｕeuePtr;
typedefstｒuｃt{
QｕeuePtrfronｔ;
QｕeuｅＰｔrrear;
}LiｎkQuｅue；
voiｄｓleeｐ（ｃｌock_twait）
{
cｌock_tgoal;
goal= waｉt+ clocｋ（）;
wｈiｌe（goal＞clock（））；
}
voiｄＩniｔＱ（ＬｉnｋQueuｅ＆Q）
{
ﻩQｕeueＰtrｐ；
p=（QueueＰtｒ）maｌｌoc（sizeoｆ（ＱNｏde））;
Q．ｆrｏnt＝p;
Q.ｒｅar=p；
ﻩQ.fｒｏnt->neｘt=NULL;
｝
voidＥｎQｕeue（LinkQuｅue &Q,ｉnｔ ｎｕｍ）
{
ＱueuePtrp；
p=（QueuePｔｒ）mａlloc（sizeof（QNｏde））;
ﻩp->num=nｕm;
p->nexｔ=NＵＬL;
ﻩＱ.rear->ｎext=ｐ；
ﻩQ.ｒeａｒ=p;
}
voｉdＤeQｕeｕe（LiｎkQuｅue&Q,iｎt＆nuｍ）
{
QueuｅPtrｐ,ｑ；
ﻩiｆ（Q.fｒｏnt＝=Ｑ.rｅar）
ﻩprintf（"队列为空"）;
p＝Q.front－>neｘt;
nuｍ=p->nｕm;
ﻩＱ.fronｔ->nｅｘｔ=p－>next;
q=p->next;
ｉｆ（Q.ｒeaｒ==ｑ）
ﻩQ．rear=Q.front;
fｒeｅ（ｐ）;
｝
voｉｄ pｒiｎｔF（LinkQuｅue&F,intｉ）
｛
ﻩQueuePｔrｐ；
intn=1;
whiｌｅ（nﻩ{
ﻩpｒinｔf（"＿"）;
ﻩｎ++;
}
p=Ｆ.front-＞next;
while（Ｆ.ｒｅａｒ!
=p）
{
ﻩﻩprintf（＂%ｄ"，ｐ->nｕm）;
ﻩﻩｐ=p-＞next;}
ﻩprinｔｆ（"％d\n"，p->nuｍ）;
}
voｉdprinｔM（ＬinkQueue&Ｍ,int ｉ）
{
QｕeuｅＰtrp；
ﻩｉnt n=1;
ﻩwhile（n＜i）
ﻩ{
ｐｒintｆ（＂＿"）;
ﻩn++；
}
ｐ=M．fｒoｎt->neｘｔ;
wｈile（M.rear!
=p）
｛
ﻩpｒintf（"%d",ｐ－>nｕm）;
ﻩp=p->ｎeｘｔ；
ﻩ}
prｉｎｔf（"%d \n",p－>ｎuｍ）;
}
int main（）
{
ｉnｔm,n,k,ｉ,a,b；
ｉntcoｕnt=0，nｕm;
QueueＰtrp,q;
LinkQｕeueF;
ＬinkQｕｅｕｅM；
pｒintf（＂请输入女生数量:
"）;
scaｎｆ（"%ｄ",&m）；
ﻩｐrｉntf（"请输入男生数量:
＂）；
ﻩscａｎｆ（"%d",&n）；
pｒinｔf（"请输曲子号:
＂）;
ﻩscanf（"%d",＆k）;
ﻩpｒinｔf（"请输入要查找的男生编号:
"）;
scａnｆ（"%d＂,&a）；
printf（"请输入要查找的女生编号：
"）;
ﻩscanf（"%ｄ＂，&b）;
ＩnｉtQ（Ｆ）;
ﻩＩnitQ（M）；
ﻩfoｒ（i=1;ｉ<＝m;i++）
ﻩ{
ﻩＥnＱuｅｕｅ（F,ｉ）；
ﻩ｝
ﻩfor（i=1;i<=n;i++）
{
ﻩＥnQueｕｅ（M，i）;
ﻩ}
ﻩfor（i＝1;i<=k;ｉ++）
{
ﻩｓysteｍ（＂CLＳ"）;
ﻩpｒiｎｔf（"第%d首曲子\n"，i）;
ﻩpriｎｔＦ（Ｆ,ｉ）；
prｉntＭ（Ｍ,i）;
ﻩﻩｐ=F.front->next；
ﻩq=Ｍ.froｎt－>nｅxt;
ﻩﻩprintf（"目前跳舞的是第%ｄ号女生和第%d号男生\n"，ｐ－>nｕm，q->nｕｍ）;
ﻩif（ｐ->ｎｕｍ＝＝ａ＆&ｑ->num=＝ｂ）
ﻩ{
ﻩcouｎｔ+＋;
prｉntｆ（＂第%d曲是要查找的男女生跳舞\n",ｉ）；
}
ﻩｓlｅep（300０）；
DeＱueue（F,nｕm）；
ﻩ EｎQｕeue（Ｆ,num）;
ﻩDeQueｕe（Ｍ，nuｍ）;
ﻩﻩEnQueuｅ（Ｍ，ｎuｍ）;
｝
printｆ（"该对男女生共跳舞％d次\n"，cｏｕnｔ）;
ﻩsysｔem（"ＰAUSE"）;
ｒｅtuｒn0；
｝
7．运行结果分析
测试及运行结果
测试输入数据：
男女生的个数曲子数和要查找的男女生编号
输出结果为:
每首曲子男女生搭配的情况
程序运行界面:
8.收获及体会
通过一周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列有了更深的了解,对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。
我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用,使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C语言描绘出关键算法。
参考文献
[1] 数据结构（C语言版）严蔚敏吴伟明编著,清华大学出版社
[２]C语言程序设计（第三版）谭浩强著，清华大学出版社
致谢
首先,我要感谢学校给我们提供了此次课程设计的机会,能让同学们在一起学习与研究，让我们有机会对所学的理论知识进行实践。
其次,我还要特别感谢我的辅导老师张太发老师，在他的精心辅导和帮助下,我的设计才得以顺利完成,并使所学知识得以真正的应用。
对他为我的设计所提出的宝贵意见表示忠心的感谢!
最后,在设计过程中，也得到了许多同学的宝贵建议,同时还到许多校友的支持和帮助,在此一并致以诚挚的谢意。
课程设计评阅书
课程设计报告评语:
（评阅意见主要对设计任务的合理性、规范性和正确性以及设计报告书的完整性、规范性和通顺性等方面作出评价）
报告成绩:
答辩记录与评语:
答辩成绩：
课程设计总成绩:
教师签名:
年 月 日
升级会员 