数据结构实验报告-稳定婚姻匹配问题.doc

精品文档数据结构与程序设计实验实 验 报 告课程名称数据结构与程序设计实验课程编号0906550实验项目名称稳定婚姻匹配问题学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告七实验课名称：数据结构与程序设计实验实验名称：稳定婚姻匹配问题班级：学号：姓名：时间：2016.05.10一、问题描述n个男孩的集合 M=m1，m2，,mn，n个女孩的集合 W=w1，w2，,wn，若在每个男孩心中，n个女孩均有一个优先表（表示男孩对每个女孩的钟情程度， 假设没有相同的），在每个女孩心中，n个男孩也有一个优先表（也不存在相同 的）。若最后没有人是单身，且是一夫一妻制，则称得到了一个婚姻匹配集合。 若这个婚姻集合中，不失一般性，设、是一个婚姻匹配中的两个有序对，且满足以下条件，则称其是一个稳定的婚姻：A. 在 m1的优先表中，w1比 w2的优先级高,或在 w2的优先表中，m2比m1的优先级高。B. 在 m2的优先表中，w2比 w1的优先级高,或在 w1的优先表中,m1比m2的优先级高。条件A使得 m1 不会放弃自己目前的婚姻，或 w2 不愿放弃目前的婚姻，导致 m1 无法放弃目前的婚姻。条件B使得 m2 不会（也无法）放弃目前的婚姻，因此这是一个稳定的婚姻匹配。二、数据结构设计#define MAX 10int manArrayMAXMAX; /男生的优先表int ladayArrayMAXMAX; /女生的优先表int manPerferMAX; /每位男生选中的女生int manStartPosMAX; /记录每位男生选取的是心目中第几位的女生int ladayNowMAX; /女生对应的男生 stack manStack; /还处于单身的男士三、算法设计1. 算法采用了男生主动追求女孩的形式。 算法步骤描述：A. 第一轮，每个男人都选择自己名单上排在首位的女人，并向她表白。这种时候会出现两种情况：i. 该女士还没有被男生追求过，则该女士接受该男生的请求。 ii. 若该女生已经接受过其他男生的追求，那么该女生会将该男士与她的现任男友进行比较，若更喜欢她的男友，那么拒绝这个人的追求，否则，抛弃其男友。B. 第一轮结束后，有些男人已经有女朋友了，有些男人仍然是单身。C. 在第二轮追女行动中，每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个，并向她表白，不管她现在是否是单身。这种时候还是会遇到A中所说的两种情况会到A重复进行。直到所有人都不在是单身。2. 具体实现A. 在女生的优先表中选择男生的位置int GetPositionFromLaday(int ladayArrayMAX, int laday, int man, int NUM)for(int i=0; iNUM; i+)if(ladayArrayladayi = man)return i;return NIL;B. 进行一轮表白void ChoosePartener(stack& manStack, int manPos, int manArrayMAX, int ladayArrayMAX, int manPerfer, int manStartPos, int ladayNow, int NUM)/选择自己名单上排在首位的女人int perferLaday = manArraymanPosmanStartPosmanPos;/如果该女孩没有接受过表白，则接受该男孩的表白if(ladayNowperferLaday = NIL)ladayNowperferLaday = manPos;manPerfermanPos = perferLaday;else/如果已经有人向她表白，则判断其现在拥有的有没有现在追求的好Int oldPos = GetPositionFromLaday(ladayArray, perferLaday, ladayNowperferLaday, NUM);int newPos = GetPositionFromLaday(ladayArray, perferLaday, manPos, NUM); if(oldPos newPos)manStartPosmanPos+;/说明该女生更喜欢现在拥有的，选心目中第二位/加入单身行列manStack.push(manPos);else /换男友/被甩的男友恢复自由身份manStartPosladayNowperferLaday+;/加入单身行列manStack.push(ladayNowperferLaday);/将追求的男士改为现任男友ladayNowperferLaday = manPos;manPerfermanPos = perferLaday;C. 在主函数中进行优先表的初始，并进行表白，直至没有单身男生int main() int NUM; printf(男女的人数:); scanf(%d, &NUM); int x, y; for(x=0; xNUM; x+) printf(输入第%d个男孩的优先表:n,x); for(y=0; yNUM; y+) scanf(%d, &(manArrayxy); for(x=0; xNUM; x+) printf(输入第%d个女孩的优先表:n,x); for(y=0; yNUM; y+) scanf(%d, &(ladayArrayxy); for(x=0; xNUM; x+) ladayNowx = NIL;/女生对应的男生 manPerferx = 0;/每位男生选中的女生 manStartPosx = 0;/记录每位男生选取的是心目中第几位的女生 /进行第一轮迭代，每个男生都选择自己名单上排在首位的女生。for(int pos=0; posNUM; pos+)ChoosePartener(manStack, pos, manArray, ladayArray, manPerfer, manStartPos,ladayNow, NUM); /如果还有单身男生，重复进行选择过程while(manStack.size()!=0)int manPos = manStack.top();manStack.pop();ChoosePartener(manStack, manPos, manArray, ladayArray, manPerfer, manStartPos,ladayNow, NUM); printf(n稳定匹配:n);for(int i =0;iNUM; +i)cout男孩: i - 女孩: manPerferiendl; return 0;四、运行测试与分析1. 输入男女人数2. 输入男生优先表3. 输入女生优先表4. 输出稳定婚姻匹配结果五、实验收获与思考 通过本次实验，巩固了关于查找算法的知识，同时在编程过程中发现了自己的不足，遇到了很多语法错误及逻辑错误，通过不断的调试解决问题，使我对编程有了更加深入的体会和认识。六、源代码#include #include #include using namespace std;#define MAX 10#define NIL -1int manArrayMAXMAX;int ladayArrayMAXMAX;int manPerferMAX; /每位男生选中的女生int manStartPosMAX;/记录每位男生选取的是心目中第几位的女生int ladayNowMAX; /女生对应的男生 stack manStack; / 还处于单身的男士int GetPositionFromLaday(int ladayArrayMAX, int laday, int man, int NUM)for(int i=0; iNUM; i+)if(ladayArrayladayi = man)return i;return NIL;void ChoosePartener(stack& manStack, int manPos, int manArrayMAX, int ladayArrayMAX, int manPerfer, int manStartPos, int ladayNow, int NUM)/选择自己名单上排在首位的女人int perferLaday = manArraymanPosmanStartPosmanPos;/如果该女孩没有接受过表白，则接受该男孩的表白if(ladayNowperferLaday = NIL)ladayNowperferLaday = manPos;manPerfermanPos = perferLaday;else/如果已经有人向她表白，则判断其现在拥有的有没有现在追求的好int oldPos = GetPositionFromLaday(ladayArray, perferLaday, ladayNowperferLaday, NUM);int newPos = GetPositionFromLaday(ladayArray, perferLaday, manPos, NUM); if(oldPos newPos)manStartPosmanPos+;/说明该女生更喜欢现在拥有的，选心目中第二位/加入单身行列manStack.push(manPos);else /换男友/被甩的男友恢复自由身份manStartPosladayNowperferLaday+;/加入单身行列manStack.push(ladayNowperferLaday);/将追求的男士改为现任男友ladayNowperferLaday = manPos;manPerfermanPos = perferLaday;int main() int NUM; printf(男女的人数:); scanf(%d, &NUM); int x, y; for(x=0; xNUM; x+) printf(输入第%d个男孩的优先表:n,x); for(y=0; yNUM; y+) scanf(%d, &(manArrayxy); for(x=0; xNUM; x+) printf(输入第%d个女孩的优先表:n,x); for(y=0; yNUM; y+) scanf(%d, &(ladayArrayxy); for(x=0; xNUM; x+) ladayNowx = NIL;/女生对应的男生 manPerferx = 0;/每位男生选中的女生 manStartPosx = 0;/记录每位男生选取的是心目中第几位的女生 /进行第一轮迭代，每个男生都选择自己名单上排在首位的女生。for(int pos=0; posNUM; pos+)ChoosePartener(manStack, pos, manArray, ladayArray, manPerfer, manStartPos,ladayNow, NUM); /如果还有单身男生，重复进行选择过程while(manStack.size()!=0)int manPos = manStack.top();manStack.p