北京化工大学程序设计实训（报告）

迈不过友情╰ 2022-06-07 13:06 230阅读 0赞

北京化工大学  
程序设计实训（报告）

题 目： 　  
学生姓名： 　　　　　　　　  
学 号： 　　　　　　  
所在学院： 　　信息科学与技术学院  
专 业： 　计算机科学与技术专业  
班 级： 　　　　　　  
指导教师：

2017年7月 7 日

摘要  
本次课程设计是利用数据结构的知识编写一个能够实现学生配对的问题的软件，以达到在每一首歌曲中能够有学生配对来进行舞蹈表演。为了实现这一个功能我们用利用已学的知识进行编写程序。  
通过学习数据结构课程和c语言的知识，主要利用数据结构的队列和C语言知识来实现软件的功能。  
主要是把男女生分别放在两个队列中，要涉及到队列的判断和循环等算法。判断队列的满和空的知识来完成。

关键字：学生搭配问题，数据结构，队列，C语言，软件，功能

目 录

摘要 I  
1.方案设计 2  
1.1问题描述 2  
1.2需求分析 2  
1.3运行环境 2  
1.4概要设计 3  
2.算法设计 4  
2.1算法设计思想 4  
2.2算法设计的对应方式 4  
2.3算法设计流程图 5  
3.详细设计 6  
3.1设计思想 6  
3.2设计关键算法 6  
4.调试分析 8  
4.1、测试及结果 8  
5.总结与自评 10  
5.1总结 10  
5.2 自评 10  
参考文献 11

1.方案设计  
1.1问题描述  
一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.  
每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.  
请设计一系统模拟动态地显示出上述过程,要求如下:  
1) 输出每曲配对情况  
2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值。  
1.2需求分析  
核心问题：循环队列的应用  
数据模型（逻辑结构）：循环队列（两个），将男生、女生两组人分别存放，以后实现循环配对输出。  
存储结构：循环链表  
核心算法：循环队列的入队，出队，判队满，判队空。  
输入数据：男生人数、女生人数，歌曲数量  
输出数据：每一首歌曲播放时，男生和女生搭配情况（输出编号）  
当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。  
通过以上分析，该程序具有可行性。  
1.3运行环境  
硬件开发环境：PC机  
软件开发环境：VC++ 6.0  
操作系统环境Window XP  
1.4概要设计  
整个设计的流程图

图1

2.算法设计  
2.1算法设计思想  
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。  
循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。  
循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。  
（1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。  
（2） 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。  
（3） 利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。  
（4） 循环队列的长度分别设为男女生的个数即可。  
（5） 在计算机终端输出的结果是：根据要求输出男生女生搭配情况。  
2.2算法设计的对应方式  
假如有3个男生2个女生的配对方式

歌曲  
编号  
（k）  
1  
2  
3  
4  
5  
6  
7  
男生编号  
(m=3)  
1  
2  
3  
1  
2  
3  
1  
女生编号  
(n=2)  
1  
2  
1  
2  
1  
2  
1

图 2  
2.3算法设计流程图

图 3

3.详细设计  
3.1设计思想  
建立链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输出。为了充分利用向量空间，克服上述存储结构上溢现象的方法是将向量空间想象为一个首尾相接的圆环，存储在其中成为循环队列。再循环队列中进行入队、出队操作时，头指针仍要加1，向前移动。只不过当头指针指向上界时其加1操作变为指向下界，这样就可以通过出队再入队来实现男生女生的循环搭配了。

3.2设计关键算法  
(1)关键算法之一：初始化队列  
void InitQ(LinkQueue &Q)  
\{  
QueuePtr p;  
p=(QueuePtr)malloc(sizeof(QNode));  
Q.front=p;  
Q.rear=p;  
Q.front->next=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(n