舞伴问题说明书

《数据结构与算法》 课程设计说明书

题 目： 学 院： 专 业： 姓 名： 学 号： 指导教师：

2012年9月9日

目 录

摘

要......................................................3 引言 .................................................... 3 1 系统概述 ............................................. 4 2 需求分析 ............................................. 4 2.1 系统需求 ............................................ 4 2.2 开发环境 ............................................ 4 4 所遇到的问题和分析解决 ............................. 135 5 系统特色及关键技术 ................................. 146 6 结论 ................................................ 17 参考文献 ............................................... 17

3 设计详解.............................................5

第 1 页

摘 要

1.系统的主要任务

学生搭配问题内容是：一班有m个女生,有n个男生(m不等于n), 现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上。每 曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功 配对者坐着等待下一曲找舞伴。应用循环队列来实现此程序。 2.设计方法

循环队列是一种环状的队列并且对头元素指向队尾元素，学 生搭配问题是典型的只有采用循环队列才能解决的问题,实验表 明该算法的空间复杂度优于其他算法，通过这次对学生搭配问题 的解决可以更好的理解和运用循环队列。 关键词：数据结构；C语言；循环队列

引言

课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课

程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是 舞伴问题。舞伴问题只是一个简单的队列运用，主要是为了方便一些小型的舞会， 在寻找舞伴的问题上得到相应的解决，同时也方便在舞伴的配对不均衡的情况下，能够有效的，快速的解决这种现象，让每一个人都能够愉快地舞蹈。其实这种舞伴问题是经常见到的，特别是在一些不是很正规的小型舞会，由于男女的不均衡，导致一些人没有机会参加跳舞。有了这个系统之后就可以很好的安排这些舞伴的问题。这样就可以安排到每一个人都可以参加跳舞了。

第 2 页

1 系统概述

舞伴配对问题的它主要运用到的是循环队列，但是我这里的代码多运用了一个结构体的单链表，主要是用来记录男女是否跳过舞，方便你需要查找某男女是否跳过舞，以及在第几轮一起跳的。为了比较美观一点我自己加了些图案进去，这样整体看上去比较有个性,而我这个代码主要是有一下的设计以及功能：

核心问题：循环队列的应用

数据模型（逻辑结构）：循环队列（两个），将男生、女生两组人分别存放，以后实现循环配对输出。

存储结构：循环链表。

核心算法：循环队列的入队，出队，判队满，判队空。 输入数据：男生人数、女生人数，歌曲数量

输出数据：每一首歌曲播放时，男生和女生搭配情况（输出编号） 以及他们在下一首歌中，等待的第一个人是谁。

当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。

2 需求分析

2.1 系统需求

为了能够更好的实现舞伴的循环的配对，这里主要运用了结构体方式的循环队列。因为循环队列

是在队列的顺序存储结构中，除了用乙组地址连续的存储单元一次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头和队列尾元素的位置。 （1） 要模拟动态地显示出现题目中所要求的循环，我们要先得定义两个队列的两个对象，Q1和Q2。

（2）将男生、女生两组人分别存入这两个队列。以实现他们的配对输出，这是循环队列固有的特性。

（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。 （4）循环队列的长度分别设为男女生的个数即可。在计算机终端输出的结果是：根据要求输出男生女生搭配情况。

舞伴配对问题的实现主要运用了一下的主要函数：