数据结构-舞伴配对实训

1、15数据结构实训报告（一） 应用程序名称及要求3 （二） 应用程序主体、设计目的3（三） 应用程序简介3（四） 应用程序的总体结构图及代码4（五） 测试结果10 （六） 得意之处14 （七） 课程设计中存在的问题14 （八） 设计实践过程中的体会14 （九） 参考文献14（一） 应用程序名称及要求名称：舞伴问题 假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开 始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同， 则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对 问题。（二）应用程序主体、设计目的 先入队的男士或女士亦先出队配成舞伴。因此

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

3、人的信息（姓名，些别，身高）以及队列（头指针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）两队。（3）入队append（）【选

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

5、输出数据。（4） 应用程序的总体设计结构图及代码 开始调用menu菜单函数进入wheil()主循环输入01中的一个数值，选择相应操作结束输入是否为零？调用end函数 否调用相应函数， 完成相应功能舞伴配对问题代码#include #include #include #include #define maxsize 50#define QueueSize 100 /假定预分配的队列空间最多为100个元素#define person int#define true 1#define false 0typedef struct Personchar name20;char sex;/性别，f表示女，

6、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);void display(squeue *p);/初始化void initqueue(squeue *p)p=(squeue*) malloc ( size

7、of(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;idatei.sex = M | Total-datei.sex=m) Mdancers-last=(Mdancers-last+1)%maxsize; Mdancers-dateMdancers-last=Total-datei; else if(Total-datei.sex = F | Total-datei.sex = f) F

8、dancers-last=(Fdancers-last+1)%maxsize; Fdancers-dateFdancers-last=Total-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 last = (Total-last +1)%maxsize;scanf

9、(%s,Total-dateT);getchar();printf(请输入性别:);scanf(%c,&Total-dateTotal-last.sex);printf(%s,%cn, Total-dateT,Total-dateTotal-last.sex);getchar();return total;/出队int dequeue() int i; int Mtmp,Ftmp; /记住队头 Mtmp=Mdancers-first; Ftmp=Fdancers-first; if(empty(Mdancers)printf(Queue

10、is free);return 0;if(empty(Fdancers)printf(Queue is free);return 0;else display(Mdancers); puts(a-a); display(Fdancers); getch(); for(i=0;ilast != Mdancers-first & Fdancers-last != Fdancers-first) printf(tt当前一起跳舞的是：%s,%c%s,%cn,Mdancers-dateMdancers-first+1.name,Mdancers-dateMdancers-first+1.sex ,Fda

11、ncers-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男队已经完成！重新开始n); Mdancers-first=Mtmp ; getch(); else if(Fdancers-first = Fdancers-last)

12、 /队伍完，重新开始 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,); g

13、etch(); return 1;/遍历队列void display(squeue *p)int pos = (p-first+1)%maxsize;if( p-first= p-last )printf(队列中无元素!n);elseprintf(队列如下:n);while( pos!= (p-last+1)%maxsize )printf(姓名：%s性别：%cn,,p-datepos.sex); pos=(pos+1)%maxsize;printf(n);printf(头指针位于:%dn,p-first);printf(尾指针位于:%dn,p-last);getch();（五）测试结果主界面：初始化队列输入数据选择舞伴开始跳舞挑选第一位舞伴查看队伍退出程序（6） 得意之处 基本上完成了整个操作过程，对队列的掌握进一步的加深。（七）课程设计中存在的问题 这次程序可惜的是没有将自己的想法完成，没有把身高的问题考