学生搭配问题.doc

山东理工大学计算机学院

课 程 设 计

（数据结构）

班 级

姓 名

学 号

指导教师

二○一一年一月二十日

课程设计任务书及成绩评定

课题名称
学生搭配问题

Ⅰ、题目的目的和要求：
1、设计目的
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
2、设计题目要求：
一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.
请设计系统动态地模拟显示出上述过程,要求如下:
1)输出每曲配对情况
2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.

Ⅱ、设计进度及完成情况

日 期
内 容
1.10-1.11
选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。
1.12~1.14
创建相关数据结构,录入源程序。
1.17~1.19
调试程序并记录调试中的问题，初步完成课程设计报告。
1.20~1.21
上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。

考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。

Ⅲ、主要参考文献及资料
[1] 严蔚敏 数据结构（C语言版）清华大学出版社 1999
[2] 严蔚敏 数据结构题集（C语言版）清华大学出版社 1999
[3] 谭浩强 C语言程序设计 清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料

Ⅳ、成绩评定：

设计成绩： （教师填写）

指导老师： （签字）

二○一一 年 一 月 二 十一 日

目 录

第一章 概述……………………………………………………………1
第二章 系统分析………………………………………………………2
第三章 概要设计………………………………………………………
第四章 详细设计………………………………………………………
第五章 运行与测试……………………………………………………
第六章 总结与心得……………………………………………………

参考文献………………………………………………………………

第一章 概述

课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是学生搭配问题。通过问题的描述可以将其转化为一个数据结构的问题进行求解，通过分析题可以为其建立相应的数据结构，并在该结构下进行相应的操作，看似复杂的问题也就迎刃而解了，通过这个问题我们可以看出在生活中看似复杂而难以解决的问题通过对其深入的分析结合数据结构就可以很容易的对其求解了，这也是学习数据结构这门课程的目的所在。

第二章 系统分析

1、 学生搭配问题的主要活动是从男生和女生中分别按对选出到舞池中跳舞，由于男生和女生的人数不相等，每个舞曲都会有剩余的男生或女生，等待下一曲继续找配对的舞伴。
2、 根据对题目的分析,我们可以用队列这种数据结构来解决这个学生搭配的问题。
3、 由题目给出的条件对输入的男女生人数和要查看的男女生的编号进行限制。
4、 演示程序是以窗口程序进行输入，结果以控制台程序输出。
5、 测试数据。

第三章 概要设计

1、数据结构的设计
根据男女生人数不相等，而且每首歌都配对后，剩余的会在下一首歌进行配对，这种配对的条件满足队列先进先出的特性，所以选择队列这种数据结构。
2、算法的设计
从总体上划分4个模块，分别是初始化模块，入队模块，出队模块，输出队列模块。
初始化模块的功能是建立空队列。
入队模块的功能是为男女生完成入队操作。
出队模块的功能是为男女生完成出队操作。
输出队列模块的功能是将队列的当前情况输出。
3、抽象数据类型的设计
void InitQ(LinkQueue &Q) //初始化模块
void EnQueue(LinkQueue &Q,int num)//入队模块
void DeQueue(LinkQueue &Q, int &num)//出队模块
void print(LinkQueue &Q,int i) //输出队列模块

第四章 详细设计

#include "stdafx.h"
#include <windows.h>
#include <string.h>
#include<stdio.h>
#include <time.h>
#include <malloc.h>

#define MAXSIZE 60
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef struct QNode{
int num;
struct QNode *next;
}QNode,* QueuePtr;

typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

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==p)
Q.rear=Q.front;
free(p);
}

void print(LinkQueue &Q,int i) //输出队列模块
{
QueuePtr p;
int n=1;
p=Q.front->next;
while(p)
{
printf("%d ",p->num);
p=p->next;
}
printf("\n");
}

void main()
{
int m,n,k,i,a,b,t,j;
int count=0,num;
QueuePtr p,q;
LinkQueue W; //女生队
LinkQueue M; //男生队
printf("请输入女生数量：");
scanf("%d",&m);
printf("请输入男生数量：");
scanf("%d",&n);
printf("请输曲子号：");
scanf("%d",&k);
printf("请输入要查找的女生编号：");
scanf("%d",&a);
printf("请输入要查找的男生编号：");
scanf("%d",&b);
InitQ(W);
InitQ(M);
for(i=1;i<=m;i++)
{
EnQueue(W,i);
}
for(i=1;i<=n;i++)
{
EnQueue(M,i);
}
for(i=1;i<=k;i++)
{
printf("第%d首曲子 \n",i);
print(W,i);
print(M,i);
p=W.front->next;
q=M.front->next;
while(p&&q)
{
printf("目前跳舞的是第%d号女生和第%d号男生\n",p->num,q->num);
if(p->num==a&&q->num==b)
{
count++;
printf("第%d曲是要查找的男女生跳舞\n",i);
}
p=p->next;
q=q->next;
}
Sleep(2000);
if(m>n) t=n;
else t=m;
for(j=1;j<=t;j++)
{
DeQueue(W,num);
EnQueue(W,num);
DeQueue(M,num);
EnQueue(M,num);
}
}
printf("%d号女生和%d号男生共跳舞%d次\n",a,b,count);
}

第五章 运行与测试

测试的数据和结果

第六章 总结与心得

在这次课程设计中，我遇到了很多困难，主要是由于我对数据结构这种开发语言不够熟悉。有时虽然是一个很小的问题，但解决起来却花费了我不少的时间，但和其它同学一起探讨，把问题解决的时候我还是觉得获益非浅，这就是在摸索中寻求到的知识。
这次课程设计，让我知道一个系统开发的过程中编码不是重要的，重要的是对分析系统以及系统模型的建立。有了一个好的系统模型之后，再将其划分成几个模块，那样做起来就会容易得多。了解编程的一个有效途径是对编程和开发过程进行实验，如果对所用语言的工作过程不甚了解，可编写一个短程序以检查此特征并看其是如何工作的，可在调试器中观看程序的执行，用一个短程序而不是一个不甚了解的大程序来测试一个概念是很好的。我相信没有做不到的程序，只要我们懂得这方面的知识，然后我们再去思考它，一步一步去完成它。只是时间上的问题和自己愿不愿意去做的问题，而不是程序难与不难的问题。因为自始到终，我都相信我能把这个程序做得出来，即使别人都已经做出了一个题目。我觉得我们应该要走不同的路，要编自己想编的程序呀，而不是大家在有选择的情况向同一个方向奔跑，应该在程序中体现自己如何对以及怎样完成这个程序的思想。

参考文献:

[1] 严蔚敏、吴伟民主编 《数据结构》（C语言版） 清华大学出版社 2002
[2] 殷人昆等著 《数据结构》（C++版） 清华大学出版社 2001
[3] 金远平著 《数据结构》（C++描述） 清华大学出版社 2005
[4] 许卓群等著 《数据结构与算法》 高等教育出版社 2004
[5] Frank M.Carrano 等著 《数据结构与Ｃ++高级教程》清华大学出版社 2004
[6] 严蔚敏、吴伟民 《数据结构习题集》（C语言版）清华大学出版社
9