/*有n 个男孩m1，m2，…，mn 与n 个女孩w1，w2，wn。每一个男孩mi 都依照喜爱这n
个女孩的程度列成一张表，最喜欢的女孩排在第1 位，最不喜爱的女孩排在第n 位；同样地，
每一个女孩wi 也依照她喜爱n 个男孩的程度列成一张表。请写一个程序，把每一个男孩与
女孩的喜爱表格读入，并且把男孩与女孩一一配对，使得：如果mp 与wq 是一对的话，那么
第一：对mp 的喜爱表格中排在wq 之前的女孩而言，她的伴侣在她的表格中一定排在mp 之
前；第二：对wq 的喜爱表格中排在mp 之前的男孩而言，他的伴侣在他的表格中一定排在
wq 之前。这就是稳定伴侣（Stable Marriage）问题。

解题思路就是依次表白，让妹子决定是否接受。然后循环让单身汉重新表白。*/

  1 #include<stdio.h>  2 #include<stdlib.h>  3 #include<time.h>  4   5 /*----结构体----*/  6 typedef struct girl{  7     int Mate;//伴侣  8     int Name;//名字  9     int* LikeRank;//喜欢的对象排行榜 10 }Girl; 11  12  13  14 typedef struct boy{ 15     int Mate;//伴侣 16     int Name;//名字 17     int* LikeRank;//喜欢的对象排行榜 18 }Boy; 19  20  21  22 /*------全局变量-------*/ 23 int mateNumber;//情侣对数 24 const int BoySize=sizeof(Boy); 25 const int GirlSize=sizeof(Girl); 26  27 /*-----各个模块-------*/ 28 void initializeGirl(Girl* girl,int name);//初始化姑娘 将对象置为-1，名字为在数组中的次序，喜欢排行榜用shuffleArray打乱顺序 29 void initializeBoy(Boy* boy,int name);//初始化汉子 将对象置为-1，名字为在数组中的次序，喜欢排行榜用shuffleArray打乱顺序 30 void shuffleArray(int array[],int arraySize);//用随机数打乱数组顺序 31 void girlShowLikeRank(int name,int* LikeRank);//姑娘打印喜欢排行版 32 void boyShowLikeRank(int name,int* LikeRank);//汉子打印喜欢排行版 33 bool girlSayYes(int girlName,int boyName,Girl* girls,Boy* boys);//姑娘是否同意，返回结果 34 void boyFindLove(Girl* girls,Boy* boys,int boyName,int* LikeRank);//根据喜欢次序依次表白 35 int findSequenceNumber(int* LikeRank,int boyName);//姑娘寻找此人在心目中的位置 36 int findbachelor(Boy* boys);//寻找单身汉(mate为-1的),找到返回序号，没找到返回-1 37 void printMate(Boy* boys);//根据汉子打印出配对结果 38  39 /*-------主函数-----*/ 40 /* 41 首先输入情侣对数，根据个数然后初始化所有的人类 42 然后先进行一轮汉子表白 43 再无限循环寻找被抛弃的汉子直到所有人配对成功 44 最后打印出配对结果 45 */ 46 void main(){ 47     srand((unsigned)time( NULL )); 48     printf("请输入有多少对情侣:"); 49     scanf("%d",&mateNumber); 50     Girl* girls=(Girl *)malloc(GirlSize*mateNumber); 51     Boy* boys=(Boy *)malloc(BoySize*mateNumber); 52     for(int index=0;index<mateNumber;index++){ 53         initializeGirl(&girls[index],index); 54         initializeBoy(&boys[index],index); 55     } 56     for(int index=0;index<mateNumber;index++) 57         boyFindLove(girls,boys,index,boys[index].LikeRank); 58  59     int whoBachelor=findbachelor(boys); 60     while(whoBachelor!=-1){ 61         boyFindLove(girls,boys,whoBachelor,boys[whoBachelor].LikeRank); 62         whoBachelor=findbachelor(boys); 63     }; 64     printMate(boys); 65     system("pause"); 66 } 67 /*-----程序函数----*/ 68 void initializeGirl(Girl* girl,int name) 69 { 70     girl->Name=name; 71     girl->Mate=-1; 72     girl->LikeRank=(int *)malloc(sizeof(int)*mateNumber); 73     for(int i=0;i<mateNumber;i++) 74     { 75         girl->LikeRank[i]=i; 76     } 77     shuffleArray(girl->LikeRank,mateNumber); 78     girlShowLikeRank(girl->Name,girl->LikeRank); 79 } 80 void initializeBoy(Boy* boy,int name) 81 { 82     boy->Name=name; 83     boy->Mate=-1; 84     boy->LikeRank=(int *)malloc(sizeof(int)*mateNumber); 85     for(int i=0;i<mateNumber;i++) 86     { 87         boy->LikeRank[i]=i; 88     } 89     shuffleArray(boy->LikeRank,mateNumber); 90     boyShowLikeRank(boy->Name,boy->LikeRank); 91 } 92  93 void girlShowLikeRank(int name,int* LikeRank) 94 { 95     printf("我是姑娘%d,以下是我的喜欢排行榜:\n",name); 96     for(int index=0;index<mateNumber;index++) 97         printf("第%d位:%d\n",index,LikeRank[index]); 98 } 99 void boyShowLikeRank(int name,int* LikeRank)100 {101     printf("我是汉子%d,以下是我的喜欢排行榜:\n",name);102     for(int index=0;index<mateNumber;index++)103         printf("第%d位:%d\n",index,LikeRank[index]);104 }105 106 void boyFindLove(Girl* girls,Boy* boys,int boyName,int* LikeRank)107 {108     for(int index=0;index<mateNumber;index++)109         if(girlSayYes(LikeRank[index],boyName,girls,boys))110         {111                 boys[boyName].Mate=LikeRank[index];112                 break;113         }114 }115 116 bool girlSayYes(int girlName,int boyName,Girl* girls,Boy* boys)117 {118     if(girls[girlName].Mate==-1){119         printf("我是妹子%d，%d向我求爱，我没有对象于是同意\n",girlName,boyName);120         girls[girlName].Mate=boyName;121         return true;122     }123     else if(findSequenceNumber(girls[girlName].LikeRank,girls[girlName].Mate)>124         findSequenceNumber(girls[girlName].LikeRank,boyName))125     {126         printf("我是妹子%d，%d向我求爱，我抛弃原配%d\n",girlName,boyName,girls[girlName].Mate);127         boys[girls[girlName].Mate].Mate=-1; //抛弃原配128         girls[girlName].Mate=boyName;129         return true;130     }131     else {132         printf("我是妹子%d，%d向我求爱，我更喜欢原配%d\n",girlName,boyName,girls[girlName].Mate);133         return false;}134 }135 /*136 寻找仍然单身的汉子137 找到返回名字,没找到返回-1;138 */139 int findbachelor(Boy* boys)140 {141     for(int index=0;index<mateNumber;index++)142     {143         if(boys[index].Mate==-1) return index;144     }145     return -1;146 }147 148 void printMate(Boy* boys)149 {150     for(int index=0;index<mateNumber;index++)151         printf("我是汉子%d，我的稳定妹子是%d\n",index,boys[index].Mate);152 }153 154 /*---工具函数--*/155 int findSequenceNumber(int* LikeRank,int boyName)156 {157     for(int index=0;index<mateNumber;index++)158         if(LikeRank[index]==boyName) return index;159 }160 161 void shuffleArray(int array[],int arraySize)162 {163     int i,j,T=100,tmp;164     while(T--)165     {166         i=rand()%arraySize;167         j=rand()%arraySize;168         tmp=array[i];169         array[i]=array[j];170         array[j]=tmp;171     }172 }