学生搭配问题 课程设计.doc

课 程 设 计课程设计名称： 数据结构综合课程设计 专 业 班 级 ： 计科0604 学 生 姓 名 ： 林 玉 芳 学 号 ： 20064140425 指 导 教 师 ： 白 浩 课程设计时间： 2008年6月23日 计算机科学与技术专业课程设计任务书学生姓名林玉芳专业班级计科0604学号20064140425题 目学生搭配问题课题性质其它课题来源自拟课题指导教师白浩同组姓名无主要内容一班有m个女生，有n个男生（m不等于n），现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。 任务要求请设计一系统模拟动态地显示出上述过程，要求如下：（1）输出每曲配对情况；（2）计算出任何一个男生（编号为X）和任意女生（编号为Y），在第K曲配对跳舞的情况。至少求出K的两个值；（3）尽量设计出多种算法及程序，可视情况适当加分。（提示：用队列来解决比较方便。） 参考文献数据结构（c语言版） 严蔚敏 吴为民 清华大学出版社数据结构题集（c语言版） 严蔚敏 吴为民 米宁 清华大学出版社审查意见指导教师签字：教研室主任签字： 2008年 5 月 8 日 一、 需求分析（1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列f_SqQueue和m_SqQueue。（2） 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。（3） 利用循环队列的特性，将男女生分别进行入队和出队列操作，且实现搭配输出。（4） 循环队列的长度分别设为男女生的个数即可。（5） 在计算机终端输出的结果是：1、创建或修改数据2、每首舞曲的配对情况查询3、任意一首舞曲配对情况查询4、任意一男生与一女生的配对情况查询5、退出二、 概要设计队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表循环队列是在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需要附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。1.设定队列的抽象数据类型定义：ADT Queue数据对象： D=ai | ai ElemSet,i=1,2,3 ，n，n0数据关系 R1= | ai-1 ,aiD,i=2,，n 约定其中a1端为对列头，an端为队列尾基本操作： InitQueue（&Q）操作结果：构造一个空队列Q。 DestroyQueue（&Q） 初始条件：队列已存在。 操作结果：队列Q被销毁，不再存在。 ClearQueue（&Q） 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 QueueEmpty（&Q） 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则FALSE。 QueueLength（&Q） 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetQueue（Q，&e） 初始条件：队列Q为非空队列。 操作结果：用e返回Q的队头元素。 EnQueue（&Q，e） 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。DeQueue（&Q，&e） 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse（Q，visit()） 初始条件：Q已存在且非空。 操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT Queue2.本程序包含三个模块 （1）主程序模块： void main() while(命令 != “退出”) 接收命令； 处理命令； （2）循环队列模块实现循环队列抽象数据类型（3）命令模块实现各种功能。各模块之间的调用关系如下：主程序模块 命令模块 循环队列模块三、 运行环境软件环境：WindowsXP操作系统硬件环境：PC四、 开发工具和编程语言开发工具：Microsoft Visual C+ 6.0编程语言：C+语言五、 详细设计1、源程序清单#include #include #include #include #define OK 1#define OVERFLOW -1#define ERROR 0typedef int Status;/全局变量int MAXQSIZE;int gcount=0; /记录班上女同学的人数int bcount=0; /记录班上男同学的人数int num_dance; /记录舞曲曲数typedef struct char sex; /性别，F表示女性，M表示男性 char card7; /编号Student; typedef Student QElemType;/-循环队列-队列的顺序存储结构-typedef struct Student *base; /初始化的动态分配存储空间 int front; /头指针，若队列不空，指向队列头元素 int rear; /尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/-循环队列的基本算法-Status InitQueue(SqQueue &q,int MAXQSIZE) /构造一个空队列 q.base = (QElemType * )malloc(MAXQSIZE+1) * sizeof(QElemType); if(!q.base) printf(存储分配失败n); exit(OVERFLOW); /存储分配失败 q.front = q.rear = 0; return OK;Status DestroyQueue(SqQueue &q) /销毁一个循环队列if(q.base)free(q.base);q.base=NULL;q.front= q.rear=0;return OK;Status EnQueue(SqQueue &q,QElemType e,int MAXQSIZE) /插入元素stu为q的新队头元素 if(q.rear+1) % (MAXQSIZE+1) = q.front) /队列满printf(队列已满!n); return ERROR; q.baseq.rear = e;q.rear = (q.rear+1)%(MAXQSIZE+1);return OK;Status DeQueue(SqQueue &q,QElemType &e,int MAXQSIZE) /若队列不空，则删除Q的对头元素，用e返回其值，并返回OK，否则返回ERRORif(q.front = q.rear)printf(队列为空!);return ERROR;e = q.baseq.front;q.front = (q.front + 1) % MAXQSIZE;return OK;Status print_Queue(SqQueue q,int MAXQSIZE) /输出队列各个成员的数据while(q.front != q.rear)printf(%c%s ,q.baseq.front.sex,q.baseq.front.card);q.front = (q.front+1) % (MAXQSIZE+1);printf(n);return OK;Status judge() /判断男同学及女同学的数据是否创建；if(bcount = 0 | gcount = 0 | num_dance = 0)printf(数据还未创建完全，请先创建数据!n);return ERROR;return OK;int seach_stu(SqQueue q,int count,Student stu)int order = -1;int i;Student stu2;for(i=0;icount;i+)DeQueue(q,stu2,count);if(strcmp(stu.card,stu2.card) = 0)order = i+1;return order;return order;int creat_queue(SqQueue &f_queue,SqQueue &m_queue)Student stu; int i, b = 1;while(b)printf(请输入今晚共有多少首舞曲：); scanf(%2d,&num_dance);if(num_dance 0 | num_dance = 0)printf(输入错误，请重新输入舞曲数目!);else b=0;b=1; while(b)printf(请输入班上女同学的总人数：); scanf(%2d,&gcount); printf(请输入班上男同学的总人数：); scanf(%2d,&bcount); if(gcount = bcount | gcount = 0 | gcount 0 | bcount = 0 | bcount 0) printf(nt输入错误，女同学的总人数和男同学的总人数不能相同或不能小于0，请重新输入!nn);elseb = 0;InitQueue(f_queue,gcount);InitQueue(m_queue,bcount);printf(n请按座位的顺序依次输入女同学的编号：nn);for(i=1;i=gcount;i+)printf(t);printf(第%2d个女同学的编号：,i);scanf(%s,stu.card);stu.sex = F;EnQueue(f_queue,stu,gcount);printf(n请按座位的顺序依次输入男同学的编号：nn);for(i=1;i bcount) count = bcount;b=judge();if(b = 0) return OK; printf(按座位顺序输出女同学的编号：nnt);print_Queue(f_queue,gcount);printf(n按座位顺序输出男同学的编号：nnt);print_Queue(m_queue,bcount);printf(*nn); while(num=num_dance)printf(n第%2d首舞曲的舞伴搭配情况如下：nnt,num+);for(i=0;icount;i+)DeQueue(f_queue,stu,gcount);printf(%c%s - ,stu.sex,stu.card); DeQueue(m_queue,stu,bcount);printf(%c%s ,stu.sex,stu.card);printf(n);printf(*nn);return OK;int each_partner(SqQueue f_queue,SqQueue m_queue) /输出某一首舞曲的学生搭配情况，并输出本曲未成功配对者int num = 1; int count = gcount; int i, b;Student stu; b=judge(); if(b = 0) return ERROR;b = 1;while(b) printf(n请输入您要查询的哪一首舞曲的配对情况（今晚共有%2d首舞曲）：,num_dance); scanf(%2d,&num); if(num=0 & num num_dance) printf(nt输入错误，请重新输入!nn);else b=0;if(gcount bcount) count = bcount;f_queue.front = (f_queue.front+(num-1)*count)%gcount; m_queue.front = (m_queue.front+(num-1)*count)%bcount;printf(n第%2d首舞曲的舞伴搭配情况如下：nnt,num);printf(搭配成功的如下：nntt);for(i=0;icount;i+)DeQueue(f_queue,stu,gcount);printf(%c%s - ,stu.sex,stu.card); DeQueue(m_queue,stu,bcount);printf(%c%s ,stu.sex,stu.card);printf(nnt未找到舞伴的如下：nntt);if(count = gcount)for(i=0;ibcount-count;i+)DeQueue(m_queue,stu,bcount);printf(%c%s ,stu.sex,stu.card);if(count = bcount)for(i=0;i bcount) count = bcount;printf(n他们在以下这几首舞曲配对成功：nnt);for(i=0;inum_dance;i+)if(gorder = border)printf(第%d首 ,i+1);c+;gorder = gorder-count; border = border-count;if(gorder 0 | gorder = 0) gorder+=gcount;if(border 0 | border = 0) border+=bcount;if(c=0)printf(未找到符合条件的舞曲!);printf(nn);return OK; int Interprer(SqQueue &f_queue,SqQueue &m_queue,int select)int b = 3;switch(select)case 1 :system(CLS);creat_queue(f_queue,m_queue);while(b != 0 & b !=1)printf(tt返回上级菜单请按“1”键，退出请按“0”：);scanf(%2d,&b);if(b != 0 & b !=1)printf(nttt输入错误，请重新输入!nn);system(CLS);break;case 2 : system(CLS); every_partner(f_queue,m_queue); while(b != 0 & b !=1) printf(tt返回上级菜单请按“1”键，退出请按“0”：); scanf(%2d,&b); if(b != 0 & b !=1)printf(nttt输入错误，请重新输入!nn); system(CLS);break;case 3 : while(b != 0 & b !=1)system(CLS); each_partner(f_queue,m_queue);b=3;while(b != 0 & b !=1 & b != 2)printf(tt继续查询请按“2”，返回上级菜单请按“1”键，退出请按“0”：); scanf(%2d,&b); if(b != 0 & b !=1 & b != 2) printf(nttt输入错误，请重新输入!nn);system(CLS); break; case 4 :while(b != 0 & b !=1)system(CLS); search_dance(f_queue,m_queue);b=3;while(b != 0 & b !=1 & b != 2)printf(tt继续查询请按“2”，返回上级菜单请按“1”键，退出请按“0”：); scanf(%2d,&b); if(b != 0 & b !=1 & b != 2)printf(nttt输入错误，请重新输入!nn);system(CLS); break;case 5 :printf(tt欢迎您的使用，谢谢!nnn);b = 0;break; default : printf(nnt输入错误，请重新输入!nn); return b;int main()SqQueue f_queue,m_queue; int select,b=1; while(b)printf(ttt*n); printf(ttt* 学生搭配问题 *n); printf(ttt*nnn);printf(ttt1.创建或修改数据n);printf(ttt2.每首舞曲配对情况查询n);printf(ttt3.任意一首舞曲配对情况查询n);printf(ttt4.任意一男生与一女生的配对情况查询n);printf(ttt5.退出n);printf(ttt请选择（15）：); scanf(%2d,&select);printf(nnn);b=Interprer(f_queue,m_queue,select); if(bcount != 0)DestroyQueue(f_queue); DestroyQueue(m_queue); return OK;2、函数的调用关系图放映了演示程序的层次结构：主程序Interprer creat_queue every_partner each_partner search_dance InitQueue EnQueue judge print_Queue DeQueue judge DeQueue 五、调试分析1、调试过程中所遇到的问题及解决方法此题主要运用队列的顺序存储结构循环队列，虽然比较简单，但是在调试的过程中仍遇到了许多问题：首先，在构造队列时，设队列分配的最大空间为男女生的个数，此时变无法根据Q.front=Q.rear来判别队列空间是“空”还是“满”，因此，在入队操作即插入一个新元素