学生搭配问题数据结构课程设计说明书.doc

数 据 结 构课 程 设 计 说 明 书学生姓名: 学 号：1021010309学 院:软件学院专 业:软件工程题 目:学生搭配问题指导教师 2011年12月20日1. 设计任务概述一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴。实现功能：1)输出每曲配对情况；2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值。主函数第K曲配对每曲配对数据输入输出编号图1.1 系统总体框图2. 本设计所采用的数据结构 采用队列（Queue）这一数据结构，队列是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。循环队列是在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针 front 和 rear 分别指示队列头元素和队列尾元素的位置。 3. 功能模块详细设计用循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。运用循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。3.1 详细设计思想（1）要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环 队列 SqQueue1 和 SqQueue2。（2）将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。 （3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。（4）循环队列的长度分别设为男女生的个数即可。 （5）存储结构: 循环链表； 核心算法: 循环队列的入队，出队，判队满，判队空。 输入数据: 男生人数、女生人数，歌曲数量 输出数据: 每一首歌曲播放时，男生和女生搭配情况（只输出编号 即可） 当要查找的男女搭配时输出歌曲编号， 和他们搭配的总次数。3.2 核心代码 Status EnQueue (SqQueue *Q,QElemType e,int num) /* 入队列，插入元素e为Q的新的队尾元素 */ if(Q-rear+1)%(num+1) = Q-front) return ERROR; /* 队列满 */ Q-dataQ-rear = e; Q-rear = (Q-rear+1)%(num+1); return OK; /* EnQueue */ Status DeQueue(SqQueue *Q,QElemType *e,int num)/* 若队列不空，则删除Q的对头元素，用e返回其值，并返回OK/,否则返回ERROR */ if(Q-front=Q-rear) return ERROR; *e=Q-dataQ-front; Q-front=(Q-front+1)%(num+1); return OK; /* DeQueue */ Status bianhao(SqQueue *boys,SqQueue *girls) /* 队列初始化及对男女生进行编号 */ int i; InitQueue(boys,boynum); for(i=1; i=boynum; i+) if(EnQueue(boys,i,boynum)=ERROR) return ERROR; InitQueue(girls,girlnum); for(i=1; i=girlnum; i+) if(EnQueue(girls,i,girlnum)=ERROR) return ERROR; return OK; /* peidui */ Status judge() /* 判断输入每位是否满足（0-9）并且转换为数字 */ int i,j=0,k=0,s=0,h=0; char a60; gets(a); for(i=0;ai!=0;i+) /* 记录最后一个非空格字符的位置 */ if(ai!= ) h=i; for(i=0;i=h;i+) /* 去除前面的空格及判断中间是否有空格 */ j+; if(ai= ) k+; if(j!=k) return ERROR; continue; if(ak=0) return ERROR; /* 第一个非空格字符是否为0 */ if(ai9) return ERROR; /* 字符是否在0-9之间 */ else s=s*10+ai-48; /* 将字符串转换成相应的数值 */ if(s32768) return ERROR; /* 数字在1-32768之间 */ return s; Status check() /* 正确输入数据 */ int p=0; while(!p) p=judge(); if(!p) printf(tWrong number:); return p; /* check */ Status All_peidui(SqQueue *boys,SqQueue *girl）/* 输出每曲配对情况 */ int min,k,i,j; bianhao(boys,girls); min = boynumgirlnum ? girlnum:boynum; printf(nn); for (i=1;i = song_num; i+) printf(t-第%d支舞曲配对情况为-n,i); if (min5) k = min; else k = 5; for (j=0;jk;j+) printf( 男女 ); printf(n); for( j=1;j song_num) printf(t所选曲目超出曲目总数!n); while (ksong_num); min = boynumgirlnum ? girlnum:boynum; max = boynumgirlnum ? boynum:girlnum; printf(nnnttt第%d曲配对情况如下n,k); t=min*(k-1)%max; if(boynumgirlnum) for (i=1;i=t;i+) DeQueue(boys,&p1,boynum); EnQueue(boys,p1,boynum); else for (i=1;i=t;i+) DeQueue(girls,&p2,girlnum); EnQueue(girls,p2,girlnum); if (min5) a = min; else a = 5; for (i=0;ia;i+) printf( 男女 ); printf(n); for(i=1;i=min;i+) output(boys,girls); if (i%5=0) printf(n); /* for */ printf(nn); return OK; /* K_peidui */ 3.3 程序运行结果 图3.31 程序最初的运行结果 图3.32 用户输入数据界面 图3.33 各曲配对情况 图3.33 第K曲配对情况4. 课程设计心得、存在问题及解决方法 调试过程中出现的问题1：在构造队列时，设队列分配的最大空间为男女生的个数，此时便无法根据 Q.front=Q.rear 来判别队列空间是“空”还是“满”,因此，在入 队操作即插入一个新元素作为新的队尾元素时出现了问题，即最后一位同学无法入队。 解决方法：将队列分配的最大空间至少再增加一个。 调试过程中出现的问题2：此次课程设计只有一个核心算法，即进行学生搭配，在最初的设计过程中犯了一个的错误，即没有很好的进行整体布局，也没有定义统一的函数接口，以致程序的结构与函数的混乱。当各模块组合在一起的时候更是无没进行调试。 解决办法：一切从头开始，重新分配任务，以及统一定义各函数的接口。课程设计心得：通过一周的学习和实践，解决实际问题（学生搭配问题），让我对循环队列有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我知道了当一段相同的代码在程序中多次使用并且功能相对单一时，有必要将其写成一个函数，以减少工作量，并且使程序具有更好的可读性。在编写程序的过程中，及时对重要和难懂的程序段写注释是一个很好的习惯，无论是以后的测试还是以后的维护都能够节省相当多的时间。调试时最先进行各函数的调试，确保无误时再进行各模块的调试，最后才是将各模块组合在一起测试完