数据结构课设学生搭配问题生活休闲服装配饰_高等教育-大学课件.pdf

《数据结构课设学生搭配问题生活休闲服装配饰_高等教育-大学课件.pdf》由会员分享，可在线阅读，更多相关《数据结构课设学生搭配问题生活休闲服装配饰_高等教育-大学课件.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数 据 结 构 课程设计报告书 班级 学号 专业 姓名 课题描述：一、需求分析：1.设计内容 一班有m 个女生,有n个男生(m 不等于n),现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1)输出每曲配对情况 2)计算出任何一个男生(编号为 X)和任意女生(编号为 Y),在第 K 曲配对跳舞的 情况.至少求出 K 的两个值.3)尽量设计出多种算法及程序,可视情况适当加分 2.需求 本课题要对数目不等的男生女生跳舞进行搭配，设计需要解决每一首曲子 男生女生

2、的搭配情况，要采用循环队列的模式来解决，男生和女生各在两个循环 的队列中，每首曲子开始，便在两个队首各取一人成功配对跳舞，并进入队尾，等待下一次配对。例如：（3 男 5 女情况）第一首：男 1 和女 1 第二首：男 2 和女 2 .第四首：男 1 和女 4 二、总体结构设计：为实现上述功能和目的，要用到循环队列的相关知识，同时，要定义一定的抽的数据类型，主函数调用各个函数模块 个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不

3、等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 1.各模块函数介绍：1)class cirularQueue 作用：定义一个一个循环队列 2)cirularQueue()作用：定义析构函数，使对象在撤销时释放 3)bool IsFull()作用：判断队列是否已

4、满 4）bool IsEmpty()作用：判断队列是否为空，用于出队列前使用 5）void push(T info)作用：入队。每对舞伴跳完舞之后，做入队处理，到达队尾，等待下次跳舞。6）void Pop(T&info)作用：出队。每取曲子响起时男生队列和女生队列作出队处理，两人跳舞。7）void GetHead(T&info)作用：取队首元素，对出队的男女进行识别。8）void Initqueue(cirularQueue&,int);作用：初始化队列 9）void display(int,int);作用：根据男生和女生的人数和曲目的数目，来判断每曲歌的男女配对情况 10）void char

5、ge(int,int);作用：判断指定组合能否配对成功 2.本程序包含三个模块：1)主程序模块：void main()初始化；do 接受命令；个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函

6、数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 处理命令；while(“命令”=”退出”)2)、集合单元模块实现集合的各个函数模块 3)、结点结构单元模块定义集合的结点结构 三、各子模块设计：1 主函数调用关系图 图 main()主函数 k 曲配对 每曲配对 数据输入 输出 编号 class cirularQueue cirularQueue()void Pop(T&info)IsEmpty()void push(T info)void GetHead(T bool IsFull()个舞会男女

7、生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 2

8、 初始化示意 否 图 void Initqueue(cirularQueue&Q,int m)3 每曲配对函数调用关系图 void display(int,int)否 是 iMaxsizePush(i)end began 初始化男女循环队列 k=songnumman.pop(x)woman.pop(y)输出 k 首男 x 女 yman.push(x)woman.push(y)end k+个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题

9、要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 图 void display(int,int)4 第 k 曲配对函数调用图 void charge(int,int)图 void charge(int,int)4 队满判断 bool IsFull()5

10、 对空判断原则 bool IsEmpty()首尾指针相等 队列为空 首尾顺序相邻 队列为满 输出他们不会一起跳 break end count=songnman.pop(x)woman.pop(y)count+初始化男女循环队列(x=a)&(y=b)man.push(x)woman.push(y)男 a 女 b 第 count 跳 个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子

11、男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 6 入队流程 void push(T info)7 出队流程 void Pop(T&info)8.取队首元素代码 void GetHead(T&info)四、编程实现：#include template class cirularQueue /定义一个一个循

12、环队列 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()/队列的申明 不能入队 队满 队尾进入 尾指针移不能出队 队空 队头出列 头指针移个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对

13、跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 for(int i=0;imaxSize-1;i+)push(i);boo

14、l 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&info)/出队 if(IsEmpty()cout错误！队列为空！endl;exit(-1);

15、else info=datafront;front=(front+1)%MaxSize;void GetHead(T&info)/取队首元素 if(IsEmpty()cout错误！队列为空！endl;exit(-1);else info=datafront;个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每

16、首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 void Initqueue(cirularQueue&,int);void display(int,int);void charge(int,int);using namespace std;static int songnum=0;/定义歌曲的数量并初始化为 0 static int m=0,n=0;/男生和女生的人数 int

17、main()/主函数 coutmn;display(m,n);int a=0,b=0;/男生和女生的编号，以判断他们在第几首歌时能在一起跳舞 char quit=y;/判断是否继续输入,如果继续输入，则输入y；否则输入n while(quit!=n)coutab;while(am)|(bn)/如果输入错误 coutab;charge(a,b);coutquit;return 0;void Initqueue(cirularQueue&Q,int m)/初始化队列 for(int i=1;i=m;i+)Q.push(i);void display(int m,int n)cirularQueue

18、 man(m+1);cirularQueue woman(n+1);Initqueue(man,m);Initqueue(woman,n);coutsongnum;cout每曲的配对情况为:endl;for(int k=1;k=songnum;k+)int x=0,y=0;/男生和女生的编号 man.Pop(x);/男生按顺序出对跳舞 woman.Pop(y);/女生按顺序出对跳舞 个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对

19、数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 cout第k曲:tx号男生y号女生endl;/他们在一起跳舞 man.push(x);/跳完舞后男生再次进入队列等在下一次跳舞 woman.push(y);/跳完舞后男生再次进入队列等在下一次跳舞 void

20、 charge(int a,int b)int count=0;/定义舞曲计数以记录他们能在第几曲时在一起跳舞 cirularQueue man1(m+1);cirularQueue woman1(n+1);Initqueue(man1,m);Initqueue(woman1,n);while(count=songnum)int x,y;count+;man1.Pop(x);woman1.Pop(y);man1.push(x);woman1.push(y);if(x=a)&(y=b)cout第count首曲:ta号男生b号女生endl;break;/如果他们在这个舞会上不能在一起跳舞，则输出

21、if(count=songnum+1)cout他们在这个舞会上不可能在一起跳舞endl;五、测试结果：个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环

22、队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 六、总结：本设计采用的是循环队列的基本操作顺利的解决学生舞曲搭配问题，主要利用用循环队列的环状结构，循环地执行出列入列操作并在出队列时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如

23、下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞 本次程序设计中所用语言为 C+，程序开始定义了类 cirular，其中有头指针，尾指针及数据域等。随之定义了析构函数，释放对象，然后进行了队列的基本操作，有

24、队列的申明，判断队空及队满，出队，入队，其核心是 display()函数和 charge()函数，其中 display()用于对各位同学编号和每队的输出情况，charge()用于计算已编号的同学在第几曲中进行配对。循环队列是一种环状的队列并且对头元素指向队尾元素，学生搭配问题是典型的只有采用循环队列才能解决的问题，实验表明该算法的空间复杂度优于其他算法。通过这次实验，我发现自己在数据结构这方面真是知之甚少，以前学习的知识也多有遗忘。与其说这是一次学习，倒不如说这是一次检测。所以，这次实验让我很好的认清自己对数据结构这门课学习程度如何，知道自己哪些方面还存在不足、对该学科重视程度还不够，以后要努

25、力学习。对一学期的学习的数据结构通过这次实训，虽然并没有掌握的非常好，但是对某些重点需要掌握和了解的还是有了深入的探讨，也让我明白学的东西再多也要学会运用，通过实例去探讨可能比理论上更容易理解。七、参考文献 实用数据结构基础（第二版）陈元春等 中国铁道出版社 C+程序 谭浩强编著 2004 年 6 月第 1 版 !|个舞会男女生分别编号坐在舞池的两边的椅子上每曲开始时依次从男生和女生中各出一人配对跳舞本曲没成功配对者坐着等待下一曲找舞伴请设计一系统模拟动态地显示出上述过程要求如下输出每曲配对情况计算出任何一个男生编求本课题要对数目不等的男生女生跳舞进行搭配设计需要解决每一首曲子男生女生的搭配情况要采用循环队列的模式来解决男生和女生各在两个循环的队列中每首曲子开始便在两个队首各取一人成功配对跳舞并进入队尾等待下一次的相关知识同时要定义一定的抽的数据类型主函数调用各个函数模块各模块函数介绍作用定义一个一个循环队列作用定义析构函数使对象在撤销时释放作用判断队列是否已满作用判断队列是否为空用于出队列前使用作用入队每对舞