《数据结构实训学生分配问题》由会员分享，可在线阅读，更多相关《数据结构实训学生分配问题（14页珍藏版）》请在金锄头文库上搜索。
1、 某工学院算法设计技能训练实习报告题目： 学生搭配问题系 （院）:计算机工程学院 专 业：微软班 级：计1137学 号：1131317726姓 名：陆炎炜指导教师：周海岩学年学期: 2014 2015学年 第 1 学期2015年1月 1 日算法设计技能训练任务书课题名称学生搭配问题设计目的1、 通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握算法设计的知识。2、 能够针对某一具体问题，设计算法进行解决。3、 锻炼实践动手能力，提高解决问题的能力。实验环境硬件：1、PC机，奔腾以上CPU， 512MB以上内存，80G以上硬盘；软件：Visual C+编程工具任务要求1、 应用数据
2、结构基础知识进行实际问题求解与分析2、 作为一个完整的系统，应具有友好的界面和较强的容错能力3、 上机能正常运行代码4、 分析算法的运行效率5、 按要求撰写课程设计报告和设计总结工作进度计划序号起止日期工 作 内 容12014.12.29任务下达，查阅文献资料22014.12.292014.12.31总体设计、素材搜集、课题详细设计、调试32014.12.312015.1.3完善设计、撰写报告42015.1.4答辩指导教师（签章）：年月日 摘要针对学生搭配问题，循环队列是一种重要的链式结构，其特殊性在于需附设 两个指针front和rear分别指示对头元素及队尾元素的位置且对头和队尾相邻接。在程
3、序的设计过程中，运用了各种基本的算法，有判断队空及队满，出队，入队等.循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。本文用循环队列会很好的把这个程序设计出来，会有很好的效果。得出的程序运行结果能够很形象的把结果表示出来。关键词：学生搭配数据结构 循环队列目录一、设计目的.二、课程设计. 1、设计内容. 2、设计思想. 3、关键算法. 4、测试结果.三、实验程序.四、结论.五、 致谢
4、.六、参考文献. / 一、设计目的1、通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握 算法设计的知识。2、能够针对某一具体问题，设计算法进行解决。3、锻炼实践动手能力，提高解决问题的能力。二、 课程设计1.设计内容一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的 情况.至少求出K的两个值.3)
5、尽量设计出多种算法及程序,可视情况适当加分2、设计思想队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。 循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。 （1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。 （2） 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环
6、队列固有的特性。 （3） 利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。 （4） 循环队列的长度分别设为男女生的个数即可。（5） 在计算机终端输出的结果是：根据要求输出男生女生搭配情况。3、关键算法建立两个链式循环队列来分别存储男生和女生，然后调用入队出队函数实现循环队列的配对输出。为充分利用向量空间，克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，存储在其中成为循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界时、其加1操作是指向向量的下界。这样就可以通过出队再入队来实现男生女生的循环搭配。课程设计过程
7、中的关键算法如下：1)关键算法之一：初始化队列voidInitQ(LinkQueue&Q)QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);Q.front=p;Q.rear=p;Q.front-next=NULL;(2)关键算法之二：入队函数voidEnQueue(LinkQueue&Q,intnum)/入队函数QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);p-num=num;p-next=NULL;Q.rear-next=p;Q.rear=p;(3)关键算法之三：出队函数voidDeQueue(LinkQueue&Q
8、,int&num)/出队函数QueuePtrp,q;if(Q.front=Q.rear)printf(队列为空);p=Q.front-next;num=p-num;Q.front-next=p-next;q=p-next;if(Q.rear=q)Q.rear=Q.front;free(p);(4)关键算法之四：输出第i首曲子时女队的情况voidprintF(LinkQueue&F,inti)/输出第i首曲子时女队的情况QueuePtrp;intn=1;while(nnext;while(F.rear!=p)printf(%d,p-num);p=p-next;printf(%dn,p-num);
9、4、测试结果：三、实验程序#includetemplate class cirularQueue /定义一个一个循环队列 private: int MaxSize; int front; /头指针 int rear; /尾指针 T *data; public: cirularQueue(int MaxLength) MaxSize=MaxLength; front=rear=0; data=new TMaxLength; cirularQueue() /定义析构函数，使对象在撤销时释放 front=rear=0; delete data; void Initqueue() /队列的申明 for
10、(int i=0;imaxSize-1;i+) push(i);bool IsFull() /判断队列是否已满 if(rear+1)%MaxSize=front) return true; else return false; bool IsEmpty() /判断队列是否为空 if(front=rear) return true; else return false;void push(T info) /入队 if(IsFull() cout错误！队列已满！endl; exit(-1); else datarear=info; rear=(rear+1)%MaxSize; void Pop(T
11、 &info) /出队 if(IsEmpty() cout错误！队列为空！endl; exit(-1); else info=datafront; front=(front+1)%MaxSize; void GetHead(T &info) /取队首元素 if(IsEmpty() cout错误！队列为空！endl; exit (-1); else info=datafront; ;void Initqueue(cirularQueue&,int);void display(int,int);void charge(int,int);using namespace std;static int songnum=0; /定义歌曲的数量并初始化为0static int m=0,n=0; /男生和女生的人数 int main() /主函数 coutmn; display(m,n); int a=0,b=0; /男生和女生的编号，以判断他们在第几首歌时能在一起跳舞 char quit=y; /判断是否继续输入,如果继续输入，则输
