数据结构课程设计-舞伴问题.doc

分类号 编 号 华北水利水电大学 North China Institute of Water Conservancy and Hydroelectric Power 课 程 设 计题目 舞伴问题 院 系 信息工程学院 专 业 计算机科学与技术 姓 名 贾 宁 指 导 教 师 杨 彬 第一章 需求分析21.1 问题描述21.2 基本要求21.2.1 输入及输出格式21.2.2 程序所完成的功能2第二章 概要设计32.1 数据结构32.2 程序模块42.3 模块调用及算法5第三章 详细设计73.1 操作实现73.2 算法实现8第四章 编码调试104.1 调试环境104.2 调试方法104.3 调试项目及调试结果104.3.1 登陆测试104.3.2 加载学生信息114.3.3 学生配对调试124.3.4 显示总配对134.3.5 查询配对13第五章 总结15参考文献16附录 系统源代码17第一章 需求分析1.1 问题描述一班有m个女生、n个男生(m不等于n), 举办一场舞会. 男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。 1.2 基本要求1.2.1 输入及输出格式输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。在读入男女生信息时，可以从文件中直接读取学生的姓名和性别信息。输出显示时显示每首歌的配对情况，包括对应配对学生的姓名、性别以及编号。可以输出整个舞池配对过程的所有配对情况。将输出显示的内容对应写入到指定的文件中。1.2.2 程序所完成的功能从文件或者手动输入班级的学生信息，包括姓名和性别基本信息，根据性别使男女生分别坐在舞池两边的座位上，学生的座位编号顺序生成，且一旦编号确定，将不再发生变化。每一首歌曲播放时，依次从男女生队列中出来学生进行配对，由于男女生人数不一致，会使某个队列中剩下若干学生配对不成功，配对不成功者等待下首歌时再进行配对。该首歌结束时，配对成功的学生再回到座位上。然后再依次进行配对，未成功者等待下首歌再进行配对。配对成功时，会显示本首歌的详细配对情况，以及整个过程的配对情况，并且可以将配对情况写入到文件。根据男女生的姓名或者某首歌曲的名字可以查询到对应的配对情况。第二章 概要设计 2.1 数据结构学生座位队列：ADT StuQueue 数据对象：D= ai|aiElemSet，i=1,2.n;n0 数据关系：R= aiD ，i=1,2.nvoid InitQueue(StuQueue &Q) 操作结果：初始化一个空的循环队列void EnQueue(StuQueue &Q,FinalStu stu) 初始条件：循环队列Q已经存在，并且无信息 操作结果：向Q中循环加入信息void EnQueue2(StuQueue &Q,FinalStu stu) 初始条件：循环队列已存在，非首次进循环队列 操作结果：向Q中添加信息FinalStu DeQueue(StuQueue &Q) 初始条件：循环队列已存在 操作结果：使队列头的元素出队列，且返回FinalStu类型值ADT StuQueue /学生座位队列音乐队列：ADT MusicList数据对象：D= ai|aiElemSet，i=1,2.n;n0 数据关系：R= aiD ，i=1,2.nvoid InitMusic(MusicList & MList)操作结果：创建循环链表void InsertMusic(MusicList &MList,char* name)初始条件：该链表已存在 操作结果：向链表中添加数据ADT MusicList；临时队列：ADT TempQList数据对象：D= ai|aiElemSet，i=1,2.n;n0 数据关系：R= aiD ，i=1,2.nvoid InitQList(TempQList &TQL) 操作结果：初始化临时队列void EnTempQueue(TempQList & TQL,FinalStu stu) 初始条件：队列TQL已存在 操作结果：向TQL中添加信息FinalStu DeTempQueue(TempQList &TQL) 初始条件：队列TQL存在 操作结果：取出队列的对头元素，返回FinalStu类型ADT TempQList；2.2 程序模块本系统主要包括登陆模块、学生入座、自动配对、显示配对过程以及查询配对信息模块。登陆：输入正确的用户名以及密码，方可进入系统，连续输入错误三次则禁止进入系统。学生入座：以不同的方式获取学生信息后，根据学生性别依次进入两个循环队列，并为每个学生唯一编号。自动配对：每首歌开始时，男女生依次从坐席中出来进行本首歌的配对，配对不成功者等待下首歌继续配对，下首歌时，上首歌未配对成功者本首歌先进行配对。显示配对过程：在播放歌曲的过程中，显示播放的歌曲信息，以及本首歌的配对信息。查询配对：根据男女生的姓名查出两人的在哪一首歌进行过配对，根据歌曲名称查询出本首歌的配对信息。文件操作：将配对情况及学生的座位信息写入文件根据系统模块的划分，本系统的功能模块图如图2-1所示图 2-1 功能模块2.3 模块调用及算法登陆成功后进入主界面，进入主界面后，需要先运行学生入座模块，方能进行下边的操作。学生入座后会得到相关的基本信息。之后调用配对模块函数，进行学生的配对。学生配对成功后，才能利用显示配对过程进行显示配对的情况，后续的查询配对模块也必须在配对成功的基础上进行。模块间的调用流程如图2-2所示图 2-2 模块调用 在进行配对过程中用到算法，在每首歌配对时，依次从男女生队列中出来一个学生，进入到临时队列，从临时队列中获取配对的情况。在本首歌结束，下首歌开始之前，让临时队列中的男女在分别根据性别入队，依次循环，每次调用配对函数，实现学生的循环配对。第三章 详细设计3.1 操作实现本系统包含七个文件。设计分有欢迎界面，登陆系统，入队函数，配对函数，显示函数，查询函数等。登陆界面是整个系统的入口，其主要是让合法人员进入系统，入队函数主要让学生进入男女队列，配对函数主要是根据每首歌曲把男女生进行配对，显示函数主要是显示男女生的配对情况，查询函数主要是根据男女生姓名和歌曲名查找配对情况。系统首先通过程序调用void main()进入欢迎界面和系统登陆界面，根据用户的帐号和密码登陆成功后进入主菜单。根据用户的选择可分别进入：1.学生就坐；2.每曲配对；3.显示结果；4.查询配对；5.退出。选择“1.学生就坐”项，会显示学生信息来源，包括“1.按班级获取(推荐)”“2.手动输入.”两项可供选择。其中，1是从文件中获取学生信息，2是用户手动输入学生信息。选择“2.每曲配对”项，会显示播放歌曲的类型，有“1.流行”“2.复古”两个音乐风格可供选择，当用户选择其中一个风格并确定播放后，会显示出当前播放的歌曲名字和所配对的男女生。选择“3.显示结果”项，会有“1.学生座位信息”和“2.学生配对信息”两项操作可供选择。当选择1，会把学生就坐后的信息显示出来，选择2，会把每首歌学生的配对情况显示出来。选择“4.查询配对”项，也有两个操作可供选择，分别是“1.按学生姓名”“按歌曲名”两项。选择1，会根据用户输入的男女生姓名查看他们的配对情况，选择2，会根据用户输入的歌曲名称显示每首歌曲学生的配对情况。选择“5.退出”项，会出现感谢使用系统界面，并按任意键退出系统。本系统的主流程图如图3-1 所示图 3-1 主流程3.2 算法实现定义学生结构体FinalStu ，将学生的信息放到本结构体中，定义两个循环队列Boys和Girls队列，分别存储男女生的座位信息。定义MusicList循环链表，用于存放音乐信息。定义TempQueue队列，用于临时存放从男女生队列中出来的学生信息。创建一个存放每首歌配对情况的数组stuTable，用来存放播放该首歌曲时男女生的信息。每一首歌开始时，男女生依次用Boys和Girls队列中出对，依次进入临时队列TempQueue，从TempQueue中读取男女生的信息，放到stuTable数组中，表示该首歌的配对情况。下首歌开始时，让临时队列中的学生再根据性别依次进入男女循环队列。同时将存放歌曲的MusicList循环链表指针后移，播放下首歌曲，再执行上述操作，便可实现循环配对。第四章 编码调试4.1 调试环境硬件环境：Intel 1GHZ处理器（或AMD同类处理器），512M或以上内存容量，10G或以上硬盘容量,可连接互联网的相关设备。软件环境（软件、操作系统）：Windows XP（或Windows 2003或Windows vista或Windows 7）操作系统，Microsoft Visual Studio 2008。4.2 调试方法为了提高测试效率，降低测试成本，本测试方案采用黑盒法设计基本的测试方案，再用白盒法补充一些方案。在黑盒法测试方案中，采用等价划分技术，把所有可能的数据划分成几个等价类。4.3 调试项目及调试结果4.3.1 登陆测试用户根据用户名及密码登陆系统，内置用户为Admin，密码为888888。登陆成功如图4-1所示，登陆失败如图4-2所示图 4-1 登陆成功 图 4-2 登陆失败4.3.2 加载学生信息 可以从文件或者手动输入学生信息，从文件中选择时，可以选择不同的文件，其运行结果如图4-2 及图4-3 所示图 4-3 选择信息来源图 4-4 显示获取信息4.3.3 学生配对调试 在进行配对之前，需要先将音乐信息加载到系统中，其加载过程如图4-5所示图 4-5 加载音乐 学生就位及音乐加载成功后，开始播放音乐，并进行配对，其音乐播放情况及每首歌曲的配对情况如图4-6、图4-7及图4-8所示图 4-6 配对开始图 4-7 播放下一首图 4-8 循环配对4.3.4 显示总配对 在整个过程结束后，停止播放音乐，可以显示整个过程的配对情况，其结果如图4-9所示图 4-9 显示配对结果4.3.5 查询配对 可以根据男女生的姓名查询两人的配对情况，当输入两个学生姓名时，显示在整个过程中的配对情况，其结果如图 4-10所示图4-10 姓名查询配对 根据每一首歌曲情况查询在本首歌曲中的配对情况，其结果如图4-11 所示图 4-11 按歌名查找第五章 总结这次的课程设计懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为，从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是很花费时间的，在构思总体架构时，需要先将需求分析搞清楚，需要在找到了需要解决的问题后，再想办法解决该问题。而不是在设计过程中边想边解决，需要先将所有可能的问题都考虑到，再依次解决。在整个系统设计完成后，如果再遇到新的问题，可以对系统进行适当的更新。调试时经常会遇到这样那样的错误，有的时候是因为一些最基本的错误，如标点的中英错误，括号的匹配问题，数据的输入错误等。当然，也有很多地方是因为用错了解决方法。在设计的过程中，最能体现出的缺点就是基础不扎实，本可以避免的错误却一再出现。在实现舞池配对问题过程中，需要使学生循环配对，此程序设计的是当一个光盘的音乐播放结束时，整个配对过程随之结束，而没有让学生再次进去坐席，导致不再从新将学生入座，就无法实现配对。设计的是在每首歌开始之前学生进入队列，可以改为当某个学生坐席为空时，随即让学生再次进入队列，可以解决不能重复换歌曲的问题。刚开始的时候我直接在开发环境下一边看题一边写代码，瞪了半天什么也没写出来，于是我便先开始在纸上画画写写，将事件的整个过程画下来，然后考虑怎么才能运用代码来实现，一边思考一边写一些粗略的代码，最后从上到下执行代码看看是不是符合题目要求。有没有什么漏洞。等这些完成以后，再在开发环境下将代码完善、编译和调试。虽然说代码还有许多要改进的地方，有的功能还不够完善，可毕竟是自己亲自写出来的，对于程序的条理有了一个清晰的了解，对编程也有了更加深刻的认识。参考文献1 谭浩强. C程序设计(第三版)M.北京：清华大学出版社，2005.2 严蔚敏,吴伟民. 数据结构(C语言版)M.北京：清华大学出版社，1997. 3 陆丽娜. 软件工程. 北京：经济科学出版社，2005.4 姚诗斌. 数据库系统基础.计算机工程与应用,1981年第8期附录 系统源代码#include #include #include#include #include #define MAXQSIZE 20 /循环队列最大存储量#define STU_SIZE 5 /学生人数#define SIZE 100 int idCount=1000;/全局变量控制学生id自增int length;/记录每首歌配对的数量int index=0;/记录最终配对表的下标using namespace std;/舞池就坐后的学生信息结构体struct Adminchar name15;char passWord15;Admin *next;Admin *admin;struct FinalStuchar name15;char sex3;int id;FinalStu stuSTU_SIZE;FinalStu stuSeatSTU_SIZE;/用来存放入座后的学生信息FinalStu stuTableSTU_SIZE2;/用来存放没收歌曲的配对情况/舞池座位struct StuQueueFinalStu *base;int front;int rear;StuQueue Boys; /男生队列StuQueue Girls; /女生队列/初始化学生坐席void InitQueue(StuQueue &Q)Q.base=(FinalStu*)malloc(MAXQSIZE*sizeof(FinalStu);if(Q.base=NULL)return ;Q.front=Q.rear=0;/学生就坐,首次入队，需要获取学生的idvoid EnQueue(StuQueue &Q,FinalStu stu)int i=100;if(Q.rear+1)%MAXQSIZE=Q.front)return ;strcpy(Q.baseQ.rear.name,stu.name);strcpy(Q.baseQ.rear.sex,stu.sex);Q.baseQ.rear.id=idCount+;Q.rear=(Q.rear+1)%MAXQSIZE;/非首次入队，不需获取学生的idvoid EnQueue2(StuQueue &Q,FinalStu stu)strcpy(Q.baseQ.rear.name,stu.name);strcpy(Q.baseQ.rear.sex,stu.sex);Q.baseQ.rear.id=stu.id;Q.rear=(Q.rear+1)%MAXQSIZE;/从坐席上出来FinalStu DeQueue(StuQueue &Q)FinalStu stu;if(Q.rear!=Q.front)stu=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return stu;/存放音乐信息struct Musicchar M_Name15;Music *next;/存放音乐链,循环链表struct MusicListMusic *head; Music *tail;MusicList ML;Music *M_p;/初始化指针void InitMusic(MusicList & MList)MList.head=MList.tail=(Music *)malloc(sizeof(Music);MList.head-next=NULL;/向音乐链表中添加音乐void InsertMusic(MusicList &MList,char* name)Music *p=(Music*)malloc(sizeof(Music);MList.tail-next=p;strcpy(p-M_Name,name);MList.tail=p;MList.tail-next=MList.head;/临时队列，用于存放从男女生队列中配对成成功的学生信息struct TempQueueFinalStu stu;TempQueue * next;struct TempQListTempQueue *front;TempQueue *rear;TempQList TempQL; /临时队列，用于存放每次出来的男女生信息void InitQList(TempQList &TQL)TQL.front=TQL.rear=(TempQueue *)malloc(sizeof(TempQueue);TQL.front-next=NULL;void EnTempQueue(TempQList & TQL,FinalStu stu)TempQueue *p=(TempQueue *)malloc(sizeof(TempQueue);p-stu=stu;p-next=NULL;TQL.rear-next=p;TQL.rear=p;FinalStu DeTempQueue(TempQList &TQL)FinalStu stu;TempQueue *p;p=TQL.front-next;if(p=TQL.rear)stu=p-stu;TQL.rear=TQL.front;elsestu=p-stu;TQL.front-next=p-next;free(p);return stu;/=配对信息存放=struct MatchListchar musicName20;FinalStu stu2;MatchList matchTableSIZE;/从键盘读入学生信息void GetInfKey()for(int i=0;iSTU_SIZE;i+)cout输入第i+1个学生的姓名：;scanf(%s,stui.name);cout输入第i+1个学生的性别：;scanf(%s,stui.sex);/学生入座void StudentSit()for(int i=0;iSTU_SIZE;i+)if(strcmp(stui.sex,男)=0)EnQueue(Boys,stui);elseEnQueue(Girls,stui);/获取就坐后的男女生性别、姓名、编号,stuSeat 存放就坐后的学生信息，包括学生编号void GetStuSeat()int i=0; int j=0;i=Boys.front;j=Girls.front;while(i!=Boys.rear)stuSeati=Boys.basei;i+;while(j!=Girls.rear)stuSeati=Girls.basej;j+;i+;/将就座的学生信息写入文件int InFileStuSeat()FILE *fp_Seat;int res=0;if(fp_Seat=fopen(Seat.txt,wt)=NULL)cout读取学生座位信息失败！;return -1;fprintf(fp_Seat,姓名t性别t序号n);for(int i=0;iSTU_SIZE;i+)fprintf(fp_Seat,%st%st%d,stuSeati.name,stuSeati.sex,stuSeati.id);fprintf(fp_Seat,n);res+;fclose(fp_Seat);return res;void PrintStuSeat()coutttt姓名t性别t序号endl;for(int i=0;iSTU_SIZE;i+)couttttstuSeati.namet;coutstuSeati.sextstuSeati.idnext=NULL;Admin *q=admin;FILE *fp_Admin;if(fp_Admin=fopen(admin.txt,rt)=NULL)coutnext=NULL;fscanf(fp_Admin,%s%s,p-name,p-passWord);q-next=p;q=p;fclose(fp_Admin);/从文件获取学生信息void ReadStuFile(int res)FILE *fp;if(res=1)if(fp=fopen(student1.txt,rt)=NULL)cout打开文件失败！endl;return;else if(res=2)if(fp=fopen(student2.txt,rt)=NULL)cout打开文件失败！=STU_SIZE)break;fclose(fp);/加载音乐信息int LoadMusic(int cd)char music520; /存放从文件中获取的音乐名称int res=0;FILE *fp_music;if(cd=1)if(fp_music=fopen(music1.txt,rt)=NULL)cout打开音乐文件失败！endl;return -1;else if(cd=2)if(fp_music=fopen(music2.txt,rt)=NULL)cout打开音乐文件失败！endl;return -1;for(int j=0;j5;j+)if(fread(musicj,20*sizeof(char),1,fp_music)=1)res+;fclose(fp_music);InitMusic(ML);for(int i=0;i5;i+)InsertMusic(ML,musici);return res;int InFileMatchTable()FILE *fp_MTable;if(fp_MTable=fopen(matchtable.txt,wt)=NULL)cout打开文件失败endl;return -1;fprintf(fp_MTable,歌曲名称t姓名t性别t序号t姓名t性别t序号n);for(int i=0;iindex;i+)fprintf(fp_MTable,%stt%st%st%dt,matchTablei.musicName,matchTablei.stu0.name,matchTablei.stu0.sex,matchTablei.stu0.id);fprintf(fp_MTable,%st%st%dn,matchTablei.stu1.name,matchTablei.stu1.sex,matchTablei.stu1.id);fclose(fp_MTable);return 1;void StudentSitAgain()FinalStu stu;while(TempQL.front!=TempQL.rear)stu=DeTempQueue(TempQL);if(strcmp(stu.sex,男)=0)EnQueue2(Boys,stu);elseEnQueue2(Girls,stu);/播放歌曲void PlayMusic()couttt正在播放:tM_Name;/下一首void NextMusic()M_p=M_p-next;if(M_p=ML.head)M_p=ML.head-next;/学生配对void Match()/FinalStu studentSTU_SIZE;int static i=0;int j=0;length=0;while(Boys.front!=Boys.rear&Girls.front!=Girls.rear)EnTempQueue(TempQL,DeQueue(Boys); /从男生队列中出来进入临时队列EnTempQueue(TempQL,DeQueue(Girls);/从女生队列中出来进入临时队列length+;/记录每首歌的配对数/从临时队列中将信息赋值给表TempQueue *tem=TempQL.front-next;while(tem)strcpy(matchTableindex.musicName,M_p-M_Name);strcpy(matchTableindex.stu0.name,tem-stu.name);strcpy(matchTableindex.stu0.sex,tem-stu.sex);matchTableindex.stu0.id=tem-stu.id;/-每曲歌的配对情况strcpy(stuTablej0.name,tem-stu.name);strcpy(stuTablej0.sex,tem-stu.sex);stuTablej0.id=tem-stu.id;tem=tem-next;/-整个播放过程的配对表strcpy(matchTableindex.stu1.name,tem-stu.name);strcpy(matchTableindex.stu1.sex,tem-stu.sex);matchTableindex.stu1.id=tem-stu.id;/-每首歌配对表strcpy(stuTablej1.name,tem-stu.name);strcpy(stuTablej1.sex,tem-stu.sex);stuTablej1.id=tem-stu.id;tem=tem-next;index+;j+;/显示每首歌配对情况void PrintEachMatch()coutendl;cout本首歌的配对情况：endl;cout姓名t性别t序号t姓名t性别t序号endl;for(int i=0;ilength;i+) /length为每首歌的配对长度coutstuTablei0.nametstuTablei0.sextstuTablei0.idt; coutstuTablei1.nametstuTablei1.sextstuTablei1.idendl;/播放下首歌时需要进行的各种操作void Next()StudentSitAgain();NextMusic();PlayMusic();Match();PrintEachMatch();/-获取要显示信息的一些操作/-显示界面的一些函数void MainMenu()couttttt 主界面endl;coutttt1、学生就坐;coutt2、每曲配对endl;coutttt3、显示结果;coutt4、查询配对endl;couttttt 5、退出;/配对显示void PrintMatchTable()cout歌曲名称t姓名t性别t序号t姓名t性别t序号endl;for(int i=0;iindex;i+)coutmatchTablei.musicNametmatchTablei.stu0.nametmatchTablei.stu0.sextmatchTablei.stu0.idt;coutmatchTablei.stu1.nametmatchTablei.stu1.sextmatchTablei.stu1.idendl;void PrintStuRes()coutttt请选择学生信息来源：endl;coutttt1、按班级获取(推荐)endl;coutttt2、手动输入.endl;void StudentChose()PrintStuRes();coutres;swit