数据结构-舞伴配对实训

1、15数据结构实训报告（一） 应用程序名称及要求··································3 （二） 应用程序主体、设计目的·········&#

2、183;·······················3（三） 应用程序简介························

3、83;··················3（四） 应用程序的总体结构图及代码····························4（五

4、） 测试结果··············································10 （六） 得意之处·&

5、#183;············································14 （七） 课程设计中存在的问题··&#

6、183;·······························14 （八） 设计实践过程中的体会···············

7、83;··················14 （九） 参考文献·····························

8、3;················14（一） 应用程序名称及要求名称：舞伴问题    假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开 始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同， 则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对 问题。（二）应用程序主体、设计目的    先入队的男士或女士亦先出队配成舞伴。因此

9、该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。    在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。（三）应用程序简介整个程序是要做一个舞伴配对问题的系统，运用队列实现初始化，入队，出队，取对头，判断队列为空，遍历队列6个功能。因为数组具有全局或局部，静态或动态

10、的特定存储属性，所以用结构体数组存储人的信息（姓名，些别，身高）以及队列（头指针first，尾指针last，计数器count）。为了不浪费存储空间，假定预分配的队列空间最多为100（QueueSize）。整个程序在vc+6.0的环境下运行。（1）初始化队列 initqueue(squeue *p)【音乐】 初始条件：队列squeue不存在。 操作结果：构造一个空队列squeue。P指向的first，last，count都为零。（2） 建立顺序队列greatequeue【走进舞池】定义一个整型total用来存放要跳舞的人数。Total为一个参加舞会的人数。将要跳舞的人分成男（m，M）女（f，F）

11、两队。（3）入队append（）【选择舞伴】 此功能是输入跳舞人员的信息（姓名，性别）。（4） 出队 dequeue（）【开始跳舞】 定义整型的 Mtmp,Ftmp临时变量来记住队头，男队和女队的队头分别赋值给Mtmp,Ftmp。在之前已定义音乐的回合数round为3，所以在舞池中只能配对三次，显示出当前跳舞的人。如果男队或女队为空就重新排队。这里的while循环是表示一直跳到有个队伍结束。（5） 判断队空 empty(squeue *p)【查看队伍】 查看队伍中是不是没有人要继续跳舞了。（6） 取队头gethead(squeue *p)【挑选第一位舞伴】取出队头元素。（7） 遍历队列disp

12、lay(squeue *p) 按顺序输出数据。（4） 应用程序的总体设计结构图及代码 开始调用menu菜单函数进入wheil()主循环输入01中的一个数值，选择相应操作结束输入是否为零？调用end函数 否调用相应函数， 完成相应功能舞伴配对问题代码#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <conio.h>#define maxsize 50#define QueueSize 100 /假定预分配的队列空间最多为100个元素#define person int

13、#define true 1#define false 0typedef struct Personchar name20;char sex;/性别，f表示女，m表示男float height;Person;typedef struct squeuePerson dateQueueSize;int first;int last;int count;squeue;squeue *Total =NULL; /总的舞池squeue *Mdancers=NULL; /男性队列squeue *Fdancers=NULL; /女性队列int round=3; /回合数int empty(squeue *p

14、);void display(squeue *p);/初始化void initqueue(squeue *p)p=(squeue*) malloc ( sizeof(squeue) );if(p != NULL)p->first=0;p->last=0;p->count=0;elseprintf("memory overflow!");/建立顺序队列int greatequeue(int total)int i;for(i=0;i<=total;i+) /分男女两队 if(Total->datei.sex = 'M' | Tot

15、al->datei.sex='m') Mdancers->last=(Mdancers->last+1)%maxsize; Mdancers->dateMdancers->last=Total->datei; else if(Total->datei.sex = 'F' | Total->datei.sex = 'f') Fdancers->last=(Fdancers->last+1)%maxsize; Fdancers->dateFdancers->last=Total-

16、>datei; return 1;/入队int append() int total,i; printf("一共有几个人跳舞?n"); scanf("%d",&total); if( total >= maxsize ) printf("n队列长度溢出!"); getch();return 0; elseprintf("n依次输入队列的元素值:n");getchar();for( i = 0; i < total; i+ ) printf("请输入姓名:");Total

17、->last = (Total->last +1)%maxsize;scanf("%s",Total->dateTotal->);getchar();printf("请输入性别:");scanf("%c",&Total->dateTotal->last.sex);printf("%s,%cn", Total->dateTotal->,Total->dateTotal->last.sex);getchar();re

18、turn total;/出队int dequeue() int i; int Mtmp,Ftmp; /记住队头 Mtmp=Mdancers->first; Ftmp=Fdancers->first; if(empty(Mdancers)printf("Queue is free");return 0;if(empty(Fdancers)printf("Queue is free");return 0;else display(Mdancers); puts("a-a"); display(Fdancers); getch(

19、); for(i=0;i<round;i+) printf("nnntt第%d趟舞曲。嘀嘀.嘀.嘀.哩.哩.哩.n",i+1); while(1) /一直跳到有个队伍结束 if(Mdancers->last != Mdancers->first && Fdancers->last != Fdancers->first) printf("tt当前一起跳舞的是：%s,%c<->%s,%cn",Mdancers->dateMdancers->first+1.name,Mdancers->

20、;dateMdancers->first+1.sex ,Fdancers->dateFdancers->first+1.name,Fdancers->dateFdancers->first+1.sex); Mdancers->first=(Mdancers->first+1)%maxsize; Fdancers->first=(Fdancers->first+1)%maxsize; break; if(Mdancers->first = Mdancers->last) /队伍完，重新开始 printf("tt男队已经完

21、成！重新开始n"); Mdancers->first=Mtmp ; getch(); else if(Fdancers->first = Fdancers->last) /队伍完，重新开始 printf("tt女队已经完成！重新开始n"); Fdancers->first=Ftmp ; getch(); getch(); return 1;/队是否为空int empty(squeue *p)if(p->first = p->last)return 1; /队列是否为空return 0;/取队头int gethead(squeue *p) int val; if(empty(p) printf("Queue is freen"); getch(); return 0; val=p->first+1 %maxsize; printf("%sn",p->); getch(); return 1;/遍历