. -
数据结构
实训报告
- -可修编.
. -
（一）应用程序名称及要求··································3
（二）应用程序主体、设计目的·································3
（三）应用程序简介···········································3
（四）应用程序的总体结构图及代码····························4
（五）测试结果··············································10
（六）得意之处··············································14
（七）课程设计中存在的问题··································14
（八）设计实践过程中的体会··································14
（九）参考文献··············································14
- -可修编.
. -
（一） 应用程序名称及要求
- -可修编.
. -
名称：舞伴问题
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
（二）应用程序主体、设计目的
先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。
在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。
（三）应用程序简介
整个程序是要做一个舞伴配对问题的系统，运用队列实现初始化，入队，出队，取对头，判断队列为空，遍历队列6个功能。因为数组具有全局或局部，静态或动态的特定存储属性，所以用结构体数组存储人的信息（，些别，身高）以及队列（头指针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）出队 dequeue（）【开始跳舞】
定义整型的 Mtmp,Ftmp临时变量来记住队头，男队和女队的队头分别赋值给Mtmp,Ftmp。在之前已定义音乐的回合数round为3，所以在舞池中只能配对三次，显示出当前跳舞的人。如果男队或女队为空就重新排队。这里的while循环是表示一直跳到有个队伍结束。
（5）判断队空 empty(squeue *p)【查看队伍】 查看队伍中是不是没有人要继续跳舞了。
（6）取队头gethead(squeue *p)【挑选第一位舞伴】 取出队头元素。
（7）遍历队列display(squeue *p) 按顺序输出数据。
（四）应用程序的总体设计结构图及代码
开始 - -可修编.
. -
否
调用menu菜单函数 进入wheil()主循环 输入0~1中的一个数值，选择相应操作 结束 输入是否为零？ 调用end函数
调用相应函数， 完成相应功能
舞伴配对问题代码
#include #include - -可修编.
. -
#include #include #define maxsize 50#define QueueSize 100 //假定预分配的队列空间最多为100个元素
#define person int
#define true 1 #define false 0
typedef struct Person {
char name[20];
char sex;//性别，f表示女，m表示男 float height; }Person;
typedef struct squeue {
Person date[QueueSize]; 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 ( sizeof(squeue) ); if(p != NULL) {
- - //总的舞池 //男性队列 //女性队列 //回合数 可修编.
. -
p->first=0; p->last=0; p->count=0; } else { printf(\"memory overflow!\"); } }
//建立顺序队列
int greatequeue(int total) {
int i;
for(i=0;i<=total;i++) //分男女两队 {
if(Total->date[i].sex == 'M' || Total->date[i].sex=='m') {
Mdancers->last=(Mdancers->last+1)%maxsize; Mdancers->date[Mdancers->last]=Total->date[i]; }
else if(Total->date[i].sex == 'F' || Total->date[i].sex == 'f') {
Fdancers->last=(Fdancers->last+1)%maxsize; Fdancers->date[Fdancers->last]=Total->date[i]; } }
return 1; }
//入队
int append() {
int total,i;
printf(\"一共有几个人跳舞?\\n\"); scanf(\"%d\ if( total >= maxsize )
- -可修编.
. -
{
printf(\"\\n队列长度溢出!\"); getch(); return 0; } else { printf(\"\\n依次输入队列的元素值:\\n\"); getchar(); for( i = 0; i < total; i++ ) { printf(\"请输入:\"); Total->last = (Total->last +1)%maxsize; scanf(\"%s\ getchar(); printf(\"请输入性别:\"); scanf(\"%c\ printf(\"%s,%c\\n\
Total->date[Total->last].name,Total->date[Total->last].sex); getchar(); } return 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();
for(i=0;iprintf(\"\\n\\n\\n\\第%d趟舞曲。嘀嘀..嘀.嘀...哩..哩....哩..\\n\ while(1) //一直跳到有个队伍结束 {if(Mdancers->last != Mdancers->first && Fdancers->last != Fdancers->first)
printf(\"\\当前一起跳舞的
是：%s,%c<----->%s,%c\\n\date[Mdancers->first+1].sex
,Fdancers->date[Fdancers->first+1].name,Fdancers->date[Fdancers->first+1].sex); Mdancers->first=(Mdancers->first+1)%maxsize; Fdancers->first=(Fdancers->first+1)%maxsize; break; }
if(Mdancers->first == Mdancers->last) //队伍完，重新开始 {
printf(\"\\男队已经完成！重新开始\\n\"); Mdancers->first=Mtmp ; getch(); }
else if(Fdancers->first == Fdancers->last) //队伍完，重新开始 {
printf(\"\\女队已经完成！重新开始\\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 free\\n\"); getch(); return 0; }
val=p->first+1 %maxsize;
printf(\"%s\\n\ getch(); return 1; }
//遍历队列
void display(squeue *p) {
int pos = (p->first+1)%maxsize; if( p->first== p->last )
- -可修编.
. -
{ printf(\"队列中无元素!\\n\"); } else { printf(\"队列如下:\\n\"); while( pos!= (p->last+1)%maxsize ) { printf(\"：%s性别：%c\\n\ pos=(pos+1)%maxsize; } printf(\"\\n\"); printf(\"头指针位于:%d\\n\ printf(\"尾指针位于:%d\\n\ getch(); } }
（五）测试结果 主界面：
- -可修编.
. -
初始化队列
- -可修编.
. -
输入数据
选择舞伴
开始跳舞
- -可修编.
. -
挑选第一位舞伴
查看队伍
- -可修编.
. -
退出程序
（六）得意之处
基本上完成了整个操作过程，对队列的掌握进一步的加深。 （七）课程设计中存在的问题
这次程序可惜的是没有将自己的想法完成，没有把身高的问题考虑进去。最后程序还才能在一个小问题就是运行到功能4的时候会出现终止程序，经过几次的调试还不能成功。最后是在别的环境下运行成功的。
（八）设计实践过程中的心得体会
- -可修编.
. -
这次的实训基本上是按照数据结构实验课上的队列的模版来完成的。并且课本上还有完整的程序可以参考，但开始对队列的操作还是不太成熟，出现很多问题，在同学的帮助下才把程序完善的。 （九）参考文献
数据结构C语言版梅，坚主编中国水利水电
数据结构人民
- -可修编.
