稳定匹配（C语言）
问题起源
在1962年，经济学家 David Gale 和 Lloyd Shapley 提出：能否针对生活中一些常见的匹配问题，设计一个能够自我执行（self-enforcing）获取最佳匹配的算法。这类问题可以称为稳定匹配问题。本博客讨论其中的一个最经典的问题：男女匹配。
问题描述
给出一个 n个男性的集合M 和n个女性的集合W，找到一个“稳定”匹配，其中：
- 每位男性根据对女性的心仪程度从高至低进行排名；
- 每位女性根据对男性的心仪程度从高至低进行排名。
匹配
匹配S 是一个包含有序数对 m-w的集合，其中m∈M 且w∈W ，其中：
- 每个男性最多出现在一个数对中；
- 每个女性最多出现在一个数对中。
完全匹配
如果|S| = |M|=|W| = n，则匹配 S是完美匹配，也就是说，男女数量相等且都有唯一匹配的对象。
不稳定对
给出一个完美匹配S，男性m和女性w是不稳定的，如果同时满足下列条件：
- m相比起当前配偶，更喜欢 w;
- w相比起当前配偶，更喜欢 m 。
稳定匹配
一个不包含不稳定对的完美匹配。
算法特征
- 男性根据喜好降序向女性求婚；
- 一旦一位女性找到配偶，她将不会再单身，只会替换成更好的。
如需要更详细的代码理解，请参阅：https://www.bilibili.com/video/BV1V44y167n3
算法实现
算法思路
1、对每个a∈A，选取a最偏爱的一个b∈B
- 若b还没有配对，那么可将a与b配对
- 若b已经和另外一个a’∈A配对，且b偏爱a大于a’，那么可以将a与b配对，此时a’变成未配对的
- 若b已经和另外一个a’∈A配对，且b偏爱a’大于a，那么转a下一个偏爱的b
2、当A为空时算法结束，否则转第一步
设计定义结构体
//一个人的姓名和id
typedef struct{
char name[10];
int num;
}person;
//一个人的个人信息，配偶信息以及喜欢的人的排行
typedef struct{
person me;//个人信息
person partner;//配偶信息
person person1[MAXSIZE];//喜爱异性排行
}onepersonlike;
//一个性别的群体的喜爱数组
typedef struct{
onepersonlike onepersonlike[MAXSIZE];//一个性别群体的排行（矩阵）
}wholepersonlike;
初始化main函数
注意：最初大家partner的默认值都是-1，表示没对象！！之后配对成功才会更改！
int main()
{
//初始化结构体menlike和womenlike
onepersonlike onepersonlike0 = {{"吕布",0},{"",-1},{{"貂蝉",5},{"大乔",6},{"小乔",7},{"阿丑",9},{"尚香",8}}};
onepersonlike onepersonlike1 = {{"刘备",1},{"",-1},{{"貂蝉",5},{"小乔",7},{"大乔",6},{"尚香",8},{"阿丑",9}}};
onepersonlike onepersonlike2 = {{"孔明",2},{"",-1},{{"阿丑",9},{"貂蝉",5},{"小乔",7},{"大乔",6},{"尚香",8}}};
onepersonlike onepersonlike3 = {{"周瑜",3},{"",-1},{{"小乔",7},{"大乔",6},{"尚香",8},{"貂蝉",5},{"阿丑",9}}};
onepersonlike onepersonlike4 = {{"曹操",4},{"",-1},{{"小乔",7},{"貂蝉",5},{"大乔",6},{"尚香",8},{"阿丑",9}}};
wholepersonlike menlike = {onepersonlike0,onepersonlike1,onepersonlike2,onepersonlike3,onepersonlike4};
onepersonlike onepersonlike5 = {{"貂蝉",5},{"",-1},{{"曹操",4},{"吕布",0},{"刘备",1},{"周瑜",3},{"孔明",2}}};
onepersonlike onepersonlike6 = {{"大乔",6},{"",-1},{{"周瑜",3},{"刘备",1},{"孔明",2},{"吕布",0},{"曹操",4}}};
onepersonlike onepersonlike7 = {{"小乔",7},{"",-1},{{"周瑜",3},{"孔明",2},{"刘备",1},{"曹操",4},{"吕布",0}}};
onepersonlike onepersonlike8 = {{"尚香",8},{"",-1},{{"吕布",0},{"刘备",1},{"周瑜",3},{"孔明",2},{"曹操",4}}};
onepersonlike onepersonlike9 = {{"阿丑",9},{"",-1},{{"孔明",2},{"周瑜",3},{"曹操",4},{"刘备",1},{"吕布",0}}};
wholepersonlike womenlike = {onepersonlike5,onepersonlike6,onepersonlike7,onepersonlike8,onepersonlike9};
//稳定匹配算法
match(&menlike,&womenlike);
//最后结果输出
atlast(&menlike,&womenlike);
return 0;
}
打印初始化结果
//对排行榜的打印
void printpaihang(wholepersonlike *personlike)
{
int i,j;
for(i=0;i<MAXSIZE;i++)
{
printf("最想要的partner：%d\n",personlike->onepersonlike[i].partner.num);
printf(" %s 喜爱排行是：",personlike->onepersonlike[i].me.name);
for(j=0;j<MAXSIZE;j++)
{
printf("%5s",personlike->onepersonlike[i].person1[j].name);
}
printf("\n");
}
}
稳定匹配算法
//稳定匹配算法
void match(wholepersonlike *menlike,wholepersonlike *womenlike)
{
printf("男生对于女生的喜爱排行：\n");
printpaihang(menlike);
printf("---------------------\n");
printf("女生对于男生的喜爱排行：\n");
printpaihang(womenlike);
int menlast = MAXSIZE;
//剩下未匹配男人的数量
int i,j,k;
int womennumber;
while(menlast>0)//如果剩下男人的数量>0说明还有男人未配对成功
{
for(i=0;i<MAXSIZE;i++)
{
//如果这个男人没对象
if(menlike->onepersonlike[i].partner.num==-1)
{
//获取这个男人的person对象以及他的id
onepersonlike thismanperson = menlike->onepersonlike[i];
int thismannumber = thismanperson.me.num;
printf("id=%d,名字为%s的男人没有对象\n",thismannumber,thismanperson.me.name);
//男嘉宾喜爱的女嘉宾开始循环
for(j=0;j<MAXSIZE;j++)
{
//获取他想要匹配的女人的person对象和id
person thiswomanperson = menlike->onepersonlike[i].person1[j];
int thiswomannumber = thiswomanperson.num;
printf("第%d轮：他喜欢id=%d,名字为%s的女人\n",j+1,thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num==-1)//如果刚好她喜欢的配偶也没对象
{
printf("id为%d,名字为%s的这个女人没对象\n",thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
//将该女生列为男人对象
menlike->onepersonlike[i].partner.num = thiswomannumber;
strcpy(menlike->onepersonlike[i].partner.name,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
//将男人列为女人对象
womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num = thismannumber;
strcpy(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name, menlike->onepersonlike[i].me.name);
//找到对象
menlast--;//配对成功！menlast少一个
break;
}
else//如果喜欢的女生有对象
{
//女生反选
printf("id为%d,名字为%s的这个女人有对象，开始女生反选\n",thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
int xiaosannum = thismannumber;
int xiaosanpaiwei;
int partnerpaiwei;
int thiswomanpartnernum = womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num;
for(k=0;k<MAXSIZE;k++)
{
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[k].num==xiaosannum) xiaosanpaiwei = k;
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[k].num==thiswomanpartnernum) partnerpaiwei = k;
}
printf("女嘉宾原配%s的排位为%d,小三%s的排位为%d\n",womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name,partnerpaiwei,menlike->onepersonlike[i].me.name,xiaosanpaiwei);
//原配更喜爱
if(partnerpaiwei<xiaosanpaiwei)
{
printf("女嘉宾原配喜爱度更高，男嘉宾（小三）选择下一个女嘉宾\n");
continue;
}
//男嘉宾抢人成功
else
{
printf("男嘉宾（小三）抢人成功！\n");
//把女嘉宾原配的对象置空
menlike->onepersonlike[thiswomanpartnernum].partner.num=-1;
strcpy(menlike->onepersonlike[thiswomanpartnernum].partner.name,"");
//把女嘉宾的配对换成男嘉宾（小三）
womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num=thismannumber;
strcpy(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name,menlike->onepersonlike[i].me.name);
//把男嘉宾的对象换成女嘉宾
menlike->onepersonlike[i].partner.num = thiswomannumber;
strcpy(menlike->onepersonlike[i].partner.name,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
break;
}
}
}
}
else continue;
}
}
}
可以从打印文字中查看配对过程
结果的输出
//最后对象的输出
void atlast(wholepersonlike *menlike,wholepersonlike *womenlike)
{
printf("-----------------------\n");
printf("最后的匹配结果为：\n");
int i;
for(i=0;i<MAXSIZE;i++)
{
printf("%5s 匹配 %5s\n",menlike->onepersonlike[i].me.name,menlike->onepersonlike[i].partner.name);
}
printf("-----------------------");
}
所有代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 5
typedef struct{
char name[10];
int num;
}person;
typedef struct{
person me;
person partner;
person person1[MAXSIZE];
}onepersonlike;
typedef struct{
onepersonlike onepersonlike[MAXSIZE];
}wholepersonlike;
//对排行榜的打印
void printpaihang(wholepersonlike *personlike)
{
int i,j;
for(i=0;i<MAXSIZE;i++)
{
printf("最想要的partner：%d\n",personlike->onepersonlike[i].partner.num);
printf(" %s 喜爱排行是：",personlike->onepersonlike[i].me.name);
for(j=0;j<MAXSIZE;j++)
{
printf("%5s",personlike->onepersonlike[i].person1[j].name);
}
printf("\n");
}
}
//稳定匹配算法
void match(wholepersonlike *menlike,wholepersonlike *womenlike)
{
printf("男生对于女生的喜爱排行：\n");
printpaihang(menlike);
printf("---------------------\n");
printf("女生对于男生的喜爱排行：\n");
printpaihang(womenlike);
int menlast = MAXSIZE;
int i,j,k;
int womennumber;
while(menlast>0)
{
for(i=0;i<MAXSIZE;i++)
{
//如果这个男人没对象
if(menlike->onepersonlike[i].partner.num==-1)
{
//获取这个男人的person对象以及他的id
onepersonlike thismanperson = menlike->onepersonlike[i];
int thismannumber = thismanperson.me.num;
printf("id=%d,名字为%s的男人没有对象\n",thismannumber,thismanperson.me.name);
//男嘉宾喜爱的女嘉宾开始循环
for(j=0;j<MAXSIZE;j++)
{
//获取他想要匹配的女人的person对象和id
person thiswomanperson = menlike->onepersonlike[i].person1[j];
int thiswomannumber = thiswomanperson.num;
printf("第%d轮：他喜欢id=%d,名字为%s的女人\n",j+1,thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num==-1)//如果刚好她喜欢的配偶也没对象
{
printf("id为%d,名字为%s的这个女人没对象\n",thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
//将该女生列为男人对象
menlike->onepersonlike[i].partner.num = thiswomannumber;
strcpy(menlike->onepersonlike[i].partner.name,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
//将男人列为女人对象
womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num = thismannumber;
strcpy(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name, menlike->onepersonlike[i].me.name);
//找到对象
menlast--;
break;
}
else//如果喜欢的女生有对象
{
//女生反选
printf("id为%d,名字为%s的这个女人有对象，开始女生反选\n",thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
int xiaosannum = thismannumber;
int xiaosanpaiwei;
int partnerpaiwei;
int thiswomanpartnernum = womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num;
for(k=0;k<MAXSIZE;k++)
{
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[k].num==xiaosannum) xiaosanpaiwei = k;
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[k].num==thiswomanpartnernum) partnerpaiwei = k;
}
printf("女嘉宾原配%s的排位为%d,小三%s的排位为%d\n",womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name,partnerpaiwei,menlike->onepersonlike[i].me.name,xiaosanpaiwei);
//原配更喜爱
if(partnerpaiwei<xiaosanpaiwei)
{
printf("女嘉宾原配喜爱度更高，男嘉宾（小三）选择下一个女嘉宾\n");
continue;
}
//男嘉宾抢人成功
else
{
printf("男嘉宾（小三）抢人成功！\n");
//把女嘉宾原配的对象置空
menlike->onepersonlike[thiswomanpartnernum].partner.num=-1;
strcpy(menlike->onepersonlike[thiswomanpartnernum].partner.name,"");
//把女嘉宾的配对换成男嘉宾（小三）
womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num=thismannumber;
strcpy(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name,menlike->onepersonlike[i].me.name);
//把男嘉宾的对象换成女嘉宾
menlike->onepersonlike[i].partner.num = thiswomannumber;
strcpy(menlike->onepersonlike[i].partner.name,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
break;
}
}
}
}
else continue;
}
}
}
//最后对象的输出
void atlast(wholepersonlike *menlike,wholepersonlike *womenlike)
{
printf("-----------------------\n");
printf("最后的匹配结果为：\n");
int i;
for(i=0;i<MAXSIZE;i++)
{
printf("%5s 匹配 %5s\n",menlike->onepersonlike[i].me.name,menlike->onepersonlike[i].partner.name);
}
printf("-----------------------");
}
int main()
{
onepersonlike onepersonlike0 = {{"吕布",0},{"",-1},{{"貂蝉",5},{"大乔",6},{"小乔",7},{"阿丑",9},{"尚香",8}}};
onepersonlike onepersonlike1 = {{"刘备",1},{"",-1},{{"貂蝉",5},{"小乔",7},{"大乔",6},{"尚香",8},{"阿丑",9}}};
onepersonlike onepersonlike2 = {{"孔明",2},{"",-1},{{"阿丑",9},{"貂蝉",5},{"小乔",7},{"大乔",6},{"尚香",8}}};
onepersonlike onepersonlike3 = {{"周瑜",3},{"",-1},{{"小乔",7},{"大乔",6},{"尚香",8},{"貂蝉",5},{"阿丑",9}}};
onepersonlike onepersonlike4 = {{"曹操",4},{"",-1},{{"小乔",7},{"貂蝉",5},{"大乔",6},{"尚香",8},{"阿丑",9}}};
wholepersonlike menlike = {onepersonlike0,onepersonlike1,onepersonlike2,onepersonlike3,onepersonlike4};
onepersonlike onepersonlike5 = {{"貂蝉",5},{"",-1},{{"曹操",4},{"吕布",0},{"刘备",1},{"周瑜",3},{"孔明",2}}};
onepersonlike onepersonlike6 = {{"大乔",6},{"",-1},{{"周瑜",3},{"刘备",1},{"孔明",2},{"吕布",0},{"曹操",4}}};
onepersonlike onepersonlike7 = {{"小乔",7},{"",-1},{{"周瑜",3},{"孔明",2},{"刘备",1},{"曹操",4},{"吕布",0}}};
onepersonlike onepersonlike8 = {{"尚香",8},{"",-1},{{"吕布",0},{"刘备",1},{"周瑜",3},{"孔明",2},{"曹操",4}}};
onepersonlike onepersonlike9 = {{"阿丑",9},{"",-1},{{"孔明",2},{"周瑜",3},{"曹操",4},{"刘备",1},{"吕布",0}}};
wholepersonlike womenlike = {onepersonlike5,onepersonlike6,onepersonlike7,onepersonlike8,onepersonlike9};
match(&menlike,&womenlike);
atlast(&menlike,&womenlike);
return 0;
}
实验总结
本次实验因为在上课时老师讲解了算法的思路，所以写起来还算较快，半个下午搞定（但其实走在路上吃饭的时候会思考如何构建结构体以及算法的思路），所以有了框架很快就写完了。
实验出现问题的地方有很多，比如：
- 构建结构体总是改了又改
- 算法指针和变量赋值总是出错，没分清浅复制和深复制
- 结构体的嵌套太多使得算法写起来太长有点晕头转向
- ……
但总体还算不错，只要方向对了还是很快出结果的
实验改进
- 本次实验最后发现匹配过程中会出现同样cp二次比较（比如第二轮吕布以及刘备和美女的再次比较），这样会使得时间花费更多。有想过改变结构体，使得匹配过不合适的人不会二次比较，但是这样也会使得空间花费更多。还是等上课听老师怎么解答吧。
- 每次循环都是从头开始，会浪费比较的时间。
- 太过于静态，不够有交互性
PS：“小三”是为了实验理解方便，请勿上升，如有冒犯，很抱歉。
实验改进代码
- 改进了cp二次比较：将比较过的对象不合适的num设为0，如果配对时发现为0则说明不合适，跳过此人
- 改进了从头开始的for循环，利用了栈的结构，栈中存放的都是没对象的id，通过id即可寻找还未配对的男嘉宾。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 5
#include "sequence.h"
typedef struct{
char name[10];
int num;
}person;
typedef struct{
person me;
person partner;
person person1[MAXSIZE];
}onepersonlike;
typedef struct{
onepersonlike onepersonlike[MAXSIZE];
}wholepersonlike;
sequence_stack seqone;
//对排行榜的打印
void printpaihang(wholepersonlike *personlike)
{
int i,j;
for(i=0;i<MAXSIZE;i++)
{
//printf("最想要的partner：%d\n",personlike->onepersonlike[i].partner.num);
printf(" %s 喜爱排行是：",personlike->onepersonlike[i].me.name);
for(j=0;j<MAXSIZE;j++)
{
printf("%5s%d",personlike->onepersonlike[i].person1[j].name,personlike->onepersonlike[i].person1[j].num);
}
printf("\n");
}
}
//稳定匹配算法
void match(wholepersonlike *menlike,wholepersonlike *womenlike)
{
printf("男生对于女生的喜爱排行：\n");
printpaihang(menlike);
printf("---------------------\n");
printf("女生对于男生的喜爱排行：\n");
printpaihang(womenlike);
printf("---------------------\n");
int menlast = MAXSIZE;
int i,j,k;
int womennumber;
//初始化栈
init(&seqone);
//初始所有男嘉宾都未配对
for(j=MAXSIZE-1;j>=0;j--)
{
push(&seqone,j);
}
printf("%d",seqone.top);
//当栈中还有男嘉宾id
while(seqone.top!=0)
{
i = read(&seqone);//读取男嘉宾的id通过id找下标
//如果这个男人没对象
if(menlike->onepersonlike[i].partner.num==-1)
{
//获取这个男人的person对象以及他的id
onepersonlike thismanperson = menlike->onepersonlike[i];
int thismannumber = thismanperson.me.num;
printf("\n\n\nid=%d,名字为%s的男人没有对象:\n",thismannumber,thismanperson.me.name);
//男嘉宾喜爱的女嘉宾开始循环
for(j=0;j<MAXSIZE;j++)
{
//获取他想要匹配的女人的person对象和id
person thiswomanperson = menlike->onepersonlike[i].person1[j];
int thiswomannumber = thiswomanperson.num;
printf("****第%d轮****：他喜欢id=%d,名字为%s的女人\n",j+1,thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
if(menlike->onepersonlike[i].person1[j].num==0)
{
printf("No\n");
continue;
}
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num==-1)//如果刚好她喜欢的配偶也没对象
{
printf("id为%d,名字为%s的这个女人没对象,success to get married!\n",thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
//将该女生列为男人对象
menlike->onepersonlike[i].partner.num = thiswomannumber;
strcpy(menlike->onepersonlike[i].partner.name,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
//将男人列为女人对象
womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num = thismannumber;
strcpy(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name, menlike->onepersonlike[i].me.name);
//找到对象
//出栈
pop(&seqone);
break;
}
else//如果喜欢的女生有对象
{
//女生反选
printf("id为%d,名字为%s的这个女人有对象，开始女生反选\n",thiswomannumber,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
int xiaosannum = thismannumber;
int xiaosanpaiwei;
int partnerpaiwei;
int nvpai;
int thiswomanpartnernum = womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num;
for(k=0;k<MAXSIZE;k++)
{
if(menlike->onepersonlike[thiswomanpartnernum].person1[k].num==thiswomannumber) nvpai = k;
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[k].num==xiaosannum) xiaosanpaiwei = k;
if(womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[k].num==thiswomanpartnernum) partnerpaiwei = k;
}
printf("女嘉宾原配%s的排位为%d,小三%s的排位为%d\n",womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name,partnerpaiwei,menlike->onepersonlike[i].me.name,xiaosanpaiwei);
//原配更喜爱
if(partnerpaiwei<xiaosanpaiwei)
{
printf("女嘉宾原配喜爱度更高，男嘉宾（小三）选择下一个女嘉宾\n");
//buheshi
//把女嘉宾
menlike->onepersonlike[i].person1[j].num=0;
womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[xiaosanpaiwei].num=0;
//printpaihang(menlike);
//把男嘉宾的对象换成女嘉宾
//womenlike->onepersonlike[thiswomannumber-MAXSIZE].person1[thismannumber].num=0;
continue;
}
//男嘉宾抢人成功
else
{
printf("男嘉宾（小三）抢人成功！\n");
//把女嘉宾原配的对象置空
menlike->onepersonlike[thiswomanpartnernum].partner.num=-1;
strcpy(menlike->onepersonlike[thiswomanpartnernum].partner.name,"");
menlike->onepersonlike[thiswomanpartnernum].person1[nvpai].num=0;
//把女嘉宾的配对换成男嘉宾（小三）
womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.num=thismannumber;
strcpy(womenlike->onepersonlike[thiswomannumber-MAXSIZE].partner.name,menlike->onepersonlike[i].me.name);
//把男嘉宾的对象换成女嘉宾
menlike->onepersonlike[i].partner.num = thiswomannumber;
strcpy(menlike->onepersonlike[i].partner.name,womenlike->onepersonlike[thiswomannumber-MAXSIZE].me.name);
//printpaihang(menlike);
//小三出栈
//原配进栈
pop(&seqone);
push(&seqone,thiswomanpartnernum);
break;
}
}
}
}
else continue;
}
}
//最后对象的输出
void atlast(wholepersonlike *menlike,wholepersonlike *womenlike)
{
printf("-----------------------\n");
printf("最后的匹配结果为：\n");
int i;
for(i=0;i<MAXSIZE;i++)
{
printf("%5s 匹配 %5s\n",menlike->onepersonlike[i].me.name,menlike->onepersonlike[i].partner.name);
}
printf("-----------------------");
}
int main()
{
onepersonlike onepersonlike0 = {{"吕布",0},{"",-1},{{"貂蝉",5},{"大乔",6},{"小乔",7},{"阿丑",9},{"尚香",8}}};
onepersonlike onepersonlike1 = {{"刘备",1},{"",-1},{{"貂蝉",5},{"小乔",7},{"大乔",6},{"尚香",8},{"阿丑",9}}};
onepersonlike onepersonlike2 = {{"孔明",2},{"",-1},{{"阿丑",9},{"貂蝉",5},{"小乔",7},{"大乔",6},{"尚香",8}}};
onepersonlike onepersonlike3 = {{"周瑜",3},{"",-1},{{"小乔",7},{"大乔",6},{"尚香",8},{"貂蝉",5},{"阿丑",9}}};
onepersonlike onepersonlike4 = {{"曹操",4},{"",-1},{{"小乔",7},{"貂蝉",5},{"大乔",6},{"尚香",8},{"阿丑",9}}};
wholepersonlike menlike = {onepersonlike0,onepersonlike1,onepersonlike2,onepersonlike3,onepersonlike4};
onepersonlike onepersonlike5 = {{"貂蝉",5},{"",-1},{{"曹操",4},{"吕布",0},{"刘备",1},{"周瑜",3},{"孔明",2}}};
onepersonlike onepersonlike6 = {{"大乔",6},{"",-1},{{"周瑜",3},{"刘备",1},{"孔明",2},{"吕布",0},{"曹操",4}}};
onepersonlike onepersonlike7 = {{"小乔",7},{"",-1},{{"周瑜",3},{"孔明",2},{"刘备",1},{"曹操",4},{"吕布",0}}};
onepersonlike onepersonlike8 = {{"尚香",8},{"",-1},{{"吕布",0},{"刘备",1},{"周瑜",3},{"孔明",2},{"曹操",4}}};
onepersonlike onepersonlike9 = {{"阿丑",9},{"",-1},{{"孔明",2},{"周瑜",3},{"曹操",4},{"刘备",1},{"吕布",0}}};
wholepersonlike womenlike = {onepersonlike5,onepersonlike6,onepersonlike7,onepersonlike8,onepersonlike9};
match(&menlike,&womenlike);
atlast(&menlike,&womenlike);
return 0;
}
栈结构
#define SEQSIZE 10
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int top;
}sequence_stack;
void init(sequence_stack *st)
{
st->top=0;
}
int empty(sequence_stack *st)
{
return (st->top?0:1);
}
datatype read(sequence_stack *st)
{
if(empty(st))
{
printf("\n栈是空的！");
exit(1);
}
else
{
return st->a[st->top-1];
}
}
void push(sequence_stack *st,datatype x)
{
if(st->top==SEQSIZE)
{
printf("\n栈满了！");
exit(1);
}
st->a[st->top]=x;
st->top++;
}
void pop(sequence_stack *st)
{
if(st->top==0)
{
printf("空栈！");
exit(1);
}
st->top--;
}