数据结构跳舞搭配.doc

课 程 设 计课程设计名称： 数据结构课程设计 专 业 班 级 ： 计类1302 学 生 姓 名 ： 陈 哲 学 号 ： 201316920222 指 导 教 师 ： 史卫亚 课程设计时间： 2014.6.152014.6.20 计算机应用技术 专业课程设计任务书学生姓名陈哲专业班级计类1302学号201316920222题 目 学生跳舞分配系统课题性质A课题来源D指导教师史卫亚同组姓名无主要内容一共有m个女生,有n个男生(且mn),现要开一个舞会,男女分别编号坐在舞池的两边的椅子上。每曲开始时,依次从男和女中各出一个人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴。任务要求设计一系统模拟动态地显示出上述过程,要求如下: 1)输出每曲配对情况; 2)输出第K曲配对情况参考文献数据结构（C语言版）严蔚敏 清华大学出版社C语言程序设计（第三版）谭浩强 清华大学出版社审查意见指导教师签字：教研室主任签字： 2014 年 6 月 14 日 14 目录 1 需求分析.42概要设计.43 详细设计.44开发平台.45编码.56 调试分析.127测试结果.12 附图参考文献1 需求分析 学生跳舞分配系统 建立队列 匹配男女 输出数据2概要设计(1) 程序总体框架如图1所示：主函数第K曲配对每曲配对数据输入输出编号图1 程序框架图3 详细设计把输入的信息按性别分别存入maledancer和femaledancer定义两个循环队列结构体maledancer, femaledancer输入舞者信息(存入typedef struct) 主函数(void main) 判断男女哪种性别的人数少(例如男性少人数为n)开始跳舞两列各出队列n人进行匹配 n个男性 舞台 n个女性输出配对情况 例 男一号对女一号 匹配结束舞者返回队列 男性n人 女性n人 男队 舞台 女队4开发平台 操作系统 windows 8.1 系统型号 x64 编译器 vc6.0 5 编码#include#include#include#include#define queuesize 5typedef struct char name20; char sex; person_type; typedef struct person_type *qBase; int front; int rear; cir_queue; void init_queue(cir_queue *q) q-qBase =(person_type *)malloc(sizeof(person_type)*queuesize);if(!q-qBase ) printf(动态创建失败，程序终止！);exit(-1); q-front=q-rear=0; bool full_queue(cir_queue *q) if(q-rear+1) = q-front )return true;elsereturn false;bool empty_queue(cir_queue *q) if(q-front = q-rear )return true;elsereturn false;void en_queue(cir_queue *q,person_type p) if(full_queue(q) printf(队列已满，无法实现进队操作，程序终止！);exit(-1);else q-qBaseq-rear = p;q-rear=(q-rear+1)%queuesize; person_type de_queue(cir_queue *q) person_type p; if(empty_queue(q)printf(队列为空，无法实现出队操作，程序终止！);exit(-1);else p=q-qBaseq-front; q-front=(q-front+1)%queuesize; return p; int length_queue(cir_queue *q) return q-rear-q-front ; person_type queue_front(cir_queue *q) if(empty_queue(q)printf(队列为空，操作失败！);exit(-1);return q-qBaseq-front; void dancepartners(cir_queue femaledancer,cir_queue maledancer,int lun) int m = length_queue(&femaledancer); int n = length_queue(&maledancer); for(int j = 1;jn) person_type p; person_type q;person_type s;printf(-);printf(第%d轮配对情况：n,j);for(int i =1;i=n;+i ) p=de_queue(&maledancer); q=de_queue(&femaledancer); printf(男:%s,); printf(和女:%s配对成功n,); en_queue(&maledancer,p); en_queue(&femaledancer,q); printf(女队中还有%d个人在等待!n,m-n); s=queue_front(&femaledancer); printf(女队中第一个等待的是：%sn,); else if(mn) person_type p; person_type q;person_type s;printf(-); printf(第%d轮配对情况：n,j); for(int i =1;i=m;+i ) p=de_queue(&maledancer);q=de_queue(&femaledancer); printf(男:%s,); printf(和女:%s配对成功n,); en_queue(&maledancer,p); en_queue(&femaledancer,q); printf(男队中还有%d个人在等待!n,n-m); s=queue_front(&maledancer); printf(男队中第一个等待的是：%sn,); elseperson_type p; person_type q;person_type s;printf(-);printf(第%d轮配对情况：n,j); for(int i =1;i=m; +i)p=de_queue(&maledancer); q=de_queue(&femaledancer); printf(男:%s,); printf(和女:%s配对成功n,); en_queue(&maledancer,p); en_queue(&femaledancer,q); printf(没有人剩余!n); void main() person_type p,dancersqueuesize; int i,num,m,n,j; printf(输入男女dancer的总人数:n); scanf(%d,&num); printf(输入姓名和性别（用m表示男性，用f表示女性），如: nzhangsannmn); for(i=0;inum;i+) scanf(%s,&); getchar(); scanf(%c,&dancersi.sex); if(dancersi.sex!=f&dancersi.sex!=m printf(第%d个人的信息有误,请重新输入,(i-)+1); cir_queue maledancer,femaledancer;init_queue(&maledancer); init_queue(&femaledancer); for(i=0;in) person_type p; person_type q;person_type s;printf(-);printf(第%d轮配对情况：n,j);for(int i =1;i=n;+i ) p=de_queue(&maledancer); q=de_queue(&femaledancer); printf(男:%s,); printf(和女:%s配对成功n,); en_queue(&maledancer,p); en_queue(&femaledancer,q); printf(女队中还有%d个人在等待!n,m-n); s=queue_front(&femaledancer); printf(女队中第一个等待的是：%sn,); else if(mn) person_type p; person_type q;person_type s;printf(-); printf(第%d轮配对情况：n,j); for(int i =1;i=m;+i ) p=de_queue(&maledancer);q=de_queue(&femaledancer); printf(男:%s,); printf(和女:%s配对成功n,); en_queue(&maledancer,p); en_queue(&femaledancer,q); printf(男队中还有%d个人在等待!n,n-m); s=queue_front(&maledancer); printf(男队中第一个等待的是：%sn,); elseperson_type p; person_type q;person_type s;printf(-);printf(第%d轮配对情况：n,j); for(int i =1;i=m; +i)p=de_queue(&maledancer); q=de_queue(&femaledancer); printf(男:%s,); printf(和女:%s配对成功n,); en_queue(&maledancer,p); en_queue(&femaledancer,q); printf(没有人剩余!n); printf(请输入要进行的轮数：n);scanf(%d,&n); dancepartners(femaledancer,maledancer,n); 6 过程分析此次课程设计所研究的问题只有一个核心算法，即进行学生搭配，所以总的高度比较顺利。但在最初的设计过程中犯了一个的错误，即没有很好的进行整体布局，也没有定义统一的函数接口，以致程序的结构与函数的混乱。当各模块组合在一起的时候更是无没进行调试。故只有一切从头开始，重新分配任务，以及统一定义各函数的接口。当一段相同的代码在程序中多次使用并且功能相对单一时，有必要将其写成一个函数，以减少工作量，并且使程序具有更好的可读性。在编写程序的过程中，及时对重要和难懂的程序段写注释是一个很好的习惯，无论是以后的测试还是以后的维护都能够节省相当多的时间。调试时最先进行各函数的调试，确保无误时再进行各模块的调试，最后才是将各模块组合在一起测试完整的程序。在调试的过程中不断地进行改进、完善。在序能够正确运行的基础上，再对各函数进行格式的优化，加强程序的结构性，并增强程序的可读性，包括给运行界面增加相应的操作提示等，使操作界面简单而又美观。7测试结果测试结果如后文所附图片7所示。8心得体会运用循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。 本次程序设计中所用语言为C+，程序开始定义了类cir_queue，其中有头指针，尾指针及数据域等。随之定义了析构函数，释放对象，然后进行了队列的基本操作，有队列的申明，判断队空及队满，出队，入队，对各位同学编号和每队的输出情况，计算已编号的同学在第几曲中进行配对。循环队列是一种环状的队列并且对头元素指向队尾元素，学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。附图图7.1 程序最初的运行结果图7.2 各曲配对情况图7.3 输出第K曲匹配情况参考文献1严蔚敏 数据结构（C语言版） 清华大学出版社2谭浩强 C语言程序设计（第三版） 清华大学出版社3Peter Van Der Linden C专家编程人民邮电出版社4Kenneth A.Reek C和指针 人民邮电出版社 信息科学与工程 学院课程设计成绩评价表课程名称：数据结构课程设计设计题目：学生跳舞搭配专业：计类 班级：1302 姓名：陈哲 学号：201316920222序号评审项目分 数满分标准说