简单的舞伴问题实现

布满荆棘的人生 2022-07-15 10:42 108阅读 0赞

**西 安 邮电 大 学**

（计算机学院）

数据结构课内实验报告

![Image 1][]**实验名称：         舞伴问题**

![Image 1][]    ![Image 1][]**专业名称：      计算机科学与技术**

![Image 1][]**班    级：         计科1505**

![Image 1][]**    学生姓名：            贺远**

![Image 1][]**学号（8位）：      04151154**

![Image 1][]**指导教师：        初建玮、曾艳**

![Image 1][]**实验日期：   **2016年10月21日、10月31日

** **

**一. ****实验目的**

**  **1.通过对队列的学习，掌握队列的逻辑结构和存储结构，并实现舞伴问题。

2.掌握队列的基本运算。

3.通过应运队列知识，选择合适存储结构，编写算法实现舞伴问题，训练学生的分析和解决实际问题的能力。

**二. ****实验内容**

1.\[问题描述\]

舞伴问题的描述：假设在周末舞会上，男士们和女士们进入舞厅时各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求设计一个函数模拟上述舞伴配对问题，试设计程序实现之。

**三. ****实验方案设计**

1.分析

由于当男女排好队后，依次从男队和女队的队头上各出一人配成舞伴，剩下的人继续按顺序配对，具有典型的先进先出特性，因此可以用队列作为算法的数据结构。在算法中应该先设置两个队列：mdancers(mp)，wdancers(wp)分别存放男士和女士入队者。假设男士和女士的信息存放在一位数组中，作为输入，然后依次扫描该数组各元素，并根据性别来决定是进入男队还是女队。构造好两个队列后，依次将两队队头元素出队来匹配成舞伴，直至某队列变为空，此时若某队仍有待匹配者，输出等待者的名字。

2.采用的数据结构

typedef struct

char name\[20\];

char sex;

\}person;

typedef struct

person m\[20\];//存储名字和性别

int rear,front;

\}mqueue;

3.算法实现

①整体结构

main()

int num;//参与的男士与女士的总人数

person p\[20\];

mqueue \*mp;//定义男士队列

mqueue \*wp;//定义女士队列

mp=mdancers(mp);//男士队列初始化

wp=mdancers(wp);//女士队列初始化

printf("请输入参与的男士与女士的总人数：");

scanf("%d",&num);

if(num>20)  exit(1);

dencers(p,num,mp,wp);//匹配

②队列初始化

mqueue \*mdancers(mqueue \*mp)//队列初始化

mp=malloc(sizeof(mqueue));//申请一段存储空间

mp->front=-1;//置空队

mp->rear=-1;

return mp;

③入队

Inmqueue(mqueue \*mp,person p)//入队

if((mp->rear+1)%20==mp->front)

printf("队满！");

else

mp->rear++;

mp->m\[mp->rear\]=p;

④匹配

dencers(person p\[20\],int num,mqueue \*mp,mqueue \*wp)

int i;

person q;

printf("请输入参与者的姓名，性别:");

getchar();

for(i=0;i<num;i++)

scanf("%s",&p\[i\].name);

scanf("%s",&p\[i\].sex);

for(i=0;i<num;i++)//将跳舞者依其性别入队

q=p\[i\];

if (q.sex=='m') Inmqueue(mp,q);//排入男队

if(q.sex=='f') Inmqueue(wp,q);  //排入女队

printf("匹配结果：\\n");

while(!Emqueue(mp)&&!Emqueue(wp))//出队，输出下一个等待者的名字

mp->front++;

q=mp->m\[mp->front\];

printf("%s  ",q.name );

wp->front++;

q=wp->m\[wp->front\];

printf("%s  \\n",q.name );

if(!Emqueue(mp))

mp->front++;

q=mp->m\[mp->front\];

printf("下一个等待匹配的人是：%s \\n",q.name);

if(!Emqueue(wp))

wp->front++;

q=wp->m\[wp->front\];

printf("下一个等待匹配的人是：%s \\n",q.name);

4.主要算法流程图

![Image 1][]![Image 1][]

![Image 1][]

![Image 1][]![Image 1][]

![Image 1][]                                 Y            N

![Image 1][]![Image 1][]

![Image 1][]

![Image 1][]                         N                        Y

![Image 1][]![Image 1][]

![Image 1][]                                             Y                    N

![Image 1][]Y         N

![Image 1][]![Image 1][]![Image 1][]

![Image 1][]![Image 1][]

![Image 1][]![Image 1][]![Image 1][]YN

![Image 1][]

** **

**四. ****该程序的功能和运行结果**

![Image 1][]

** **

**3.**

![Image 1][]** **

** **

**五. ****实验总结  **

1．实验过程中遇到的问题及解决办法；

刚开始对队列结构缺乏清楚的认识，对队列的操作不太熟练，导致绕了很多弯路，还有就是不了解计算机内部的存储，开始输入名字时为了方便，采用字符类型，结果输入时按空格键，导致结果总是出错，后来向同学咨询，在同学讲解之后明白了其中缘由，经过改正后程序得以正确运行。

2．实验方案的优点和缺点；

优点是使用了顺序队列实现了舞伴问题，易于理解。

缺点是只能匹配一首歌曲，不能进行循环。

3．对设计及调试过程的心得体会；

从这次实验，我明白，要学好数据结构必须得亲自动手去编写算法，平时上课老师讲的还能听懂，感觉教材上的算法实例没什么好写的。可是经过本次实验我才发现自己的想法是多么的无知，就这次实验的题目，我看了一下觉得没什么难度，算法也挺简单，结果编写过程中还是出了许多问题。以后一定要加强动手编写，不能眼高手低。

[Image 1]:

简单的舞伴问题实现

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关循环队列的应用——舞伴配对问题（数据结构 C语言）

相关利用链队列解决舞伴配对问题，c语言实现

相关【数据结构】第3章栈和队列实验3：循环队列+舞伴问题

相关舞伴配对问题java_舞伴配对问题

相关简单计算器的实现

相关简单的舞伴问题实现

相关学习队列的作用队列的应用--舞伴问题

相关生产者和消费者问题（java简单实现）

相关 ioc的简单实现

相关堆的简单实现