数据结构实训-学生分配问题.doc

-
. z
工学院
算法设计技能训练实****报告
题目： 学生搭配问题 动手能力，提高解决问题的能力。
课程设计

一班有m个女生,有n个男生(m不等于n),现要开一个舞会. ,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.
请设计一系统模拟动态地显示出上述过程,要求如下:
1) 输出每曲配对情况
2) 计算出任何一个男生(编号为*)和任意女生(编号为Y),在第K曲配对跳舞的 .
3) 尽量设计出多种算法及程序,可视情况适当加分
2、设计思想
队列〔Queue〕是只允许在一端进展插入，而在另一端进展删除的运算受限的线性表。
循环队列是在队列的顺序存储构造中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。
循环队列〔两个〕，将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。
〔1〕 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。
〔2〕 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。
〔3〕 利用循环队列的特性，将男女生分别进展入队列和出队列操作，且实现搭配输出。
〔4〕 循环队列的长度分别设为男女生的个数即可。
〔5〕 在计算机终端输出的结果是：根据要求输出男生女生搭配情况。
3、关键算法
建立两个链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输
出。为充分利用向量空间，克制上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆
环，存储在其中成为循环队列。在循环队列中进展出队、入队操作时，头尾指针仍要加1，朝
前移动。只不过当头尾指针指向向量上界时、其加1操作是指向向量的下界。这样就可以通过
-
. z
出队再入队来实现男生女生的循环搭配。
课程设计过程中的关键算法如下：
1)关键算法之一：初始化队列
voidInitQ(LinkQueue&Q)
{
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
=p;
=p;
->ne*t=NULL;
}
(2)关键算法之二：入队函数
voidEnQueue(LinkQueue&Q,intnum)//入队函数
{
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
p->num=num;
p->ne*t=NULL;
->ne*t=p;
=p;
}
(3)关键算法之三：出队函数
voidDeQueue(LinkQueue&Q,int&num)//出队函数
{
QueuePtrp,q;
if(==)printf("队列为空");
p=->ne*t;
num=p->num;
->ne*t=p->ne*t;
q=p->ne*t;
if(==q)
=;
free(p);
}
(4)关键算法之四：输出第i首曲子时女队的情况
voidprintF(LinkQueue&F,inti)//输出第i首曲子时女队的情况
{
QueuePtrp;
intn=1;
-
. z
while(n<i)
{
printf("_");
n++;
}
p=->ne*t;
while(!=p)
{
printf("%d",p->num);
p=p->ne*t;
}
printf("%d\n",p->num);
}
-
. z
4、测试结果：
-
.