untitled1.cpp

传教士与野人的C语言程序 已经在VC++6.0上通过

#include   <stdio.h>                       /*头文件引入*/   
  #include<stdlib.h>                       /*头文件引入*/   
  #define   ChuanJiaoShi     3             /*定义传教士人数，可以随意修改，但要保证其>0，否则无意义，且程序运行错误*/   
  #define   YeRen                   3             /*定义野人数，要求同上一行*/   
  /*定义问题所需数据结构：这是一个结构体，作为open表和close表的节点，具体参数参照后面的说明*/   
  typedef   struct   linknod   
  {   
  int   leftChuanJiaoShi;         /*左岸的传教士人数*/   
  int   leftYeRen;                       /*左岸的野人人数*/   
  int   rightChuanJiaoShi;       /*右岸的传教士人数*/   
  int   rightYeRen;                     /*右岸的野人人数*/   
  int   locationOfShip;             /*标志船在左岸还是右岸（左岸1，右岸0）*/   
  int   selfNumber;                     /*作为节点的序号*/   
  int   fatherNumber;                 /*记录他父亲的序号，目的是打印*/   
  struct   linknod   *next;         /*连接节点的next*/   
  }State;   
    
  int   main()   
  {   
  State   *openHead;       /*open表的头节点*/   
  State   *closeHead;     /*close表的头节点*/   
  State   *openF;     /*第一个节点*/   
  State   *openQ;     /*找到open表的第一个节点*/   
  State   *closeP;   /*从open表中移出的节点的内容作为closeP指针所指close链表节点的内容，   
                                  以头查式插入close链表   */   
  State   *openM;     /*预备以尾查式插入open表的节点指针*/   
  State   *openN;     /*变历open链表的指针*/   
  State   *closeN;   /*变历close链表的指针*/   
  State   *closeM;   /*打印时作为指向父亲的指针*/   
  State   *closeS;   /*打印时作为指向儿子的指针*/   
  State   *openS;     /*找open表的最后节点*/   
    
  int   tempLC;         /*左岸传教士数的临时变量*/   
  int   tempLY;         /*左岸野人数的临时变量*/   
  int   tempRC;         /*右岸传教士数的临时变量*/   
  int   tempRY;         /*右岸野人数的临时变量*/   
  int   tempLS;         /*标志左右岸的临时变量*/   
  int   tempSN;         /*记录自己序号的临时变量*/   
  int   tempFN;         /*记录父亲序号的临时变量*/   
  int   autoNumber=1;     /*从close表中扩展到open表时，给生成的节点取的序号记数器*/   
  int   i,j;                       /*双重循环的控制变量*/   
  int   lifeSafeFlag=0;   /*检验生命是否危险，及人数是否出现负数的标志(是：0,否:1)*/   
  int   openFlag=0;           /*检测open表中是否有新扩展预备节点的标志（有：1,无：0)*/   
  int   closeFlag=0;         /*检测close表中是否有新扩展预备节点的标志（有：1,无：0)*/   
  int   enter=1;                 /*控制打印整齐的变量*/   
    
  /*控制打印清晰*/   
  printf("\n-------------------------\n");   
    
        /*创建open表和close表，都是空表*/   
  openHead=(State*)malloc(sizeof(State));   
  openHead->next=NULL;   
  closeHead=(State*)malloc(sizeof(State));   
  closeHead->next=NULL;   
    
  /*创建初始节点，然后加到open表中，本来是加到open表的末尾，介于open表此时是空表，末尾和开头   
  　无区别，所以，加到open表的开头*/   
  openF=(State*)malloc(sizeof(State));   
  openF->leftChuanJiaoShi=ChuanJiaoShi;   
  openF->leftYeRen=YeRen;   
  openF->rightChuanJiaoShi=0;   
        openF->rightYeRen=0;   
        openF->locationOfShip=1;   
        openF->selfNumber=1;   
  openF->fatherNumber=0;   
        openF->next=openHead->next;   
  openHead->next=openF;   
  openF=NULL;         /*为内存安全*/   
          
  /*采取宽度优先搜索，先检查open表是否为空，空则失败退出。否则，从open表中取出节点，   
  　放到close表中，此时检验：是否是目标节点，是则成功，直接结束循环，打印。否则，对   
  　close表中的节点以(i,j)为(0,1)(0,2)(1,0)(1,1)(2,0)五种情况扩展到open表中，   
  　扩展方法：如果船在左岸，则扩展的节点是父节点的（左岸传教士数，左岸野人数）分别减上述   
  　5种情况，（右岸传教士数，右岸野人数）分别加上述5种情况，　如果船在右岸则相反处理。   
  　预备节点能否加到open表中取决于：是否安全和有意义；是否在open表出现过相同状态的节点；是否在close   
  　表出现过相同的状态的节点。接着返回循环。*/   
  while(1)   
  {         
  /*失败退出*/   
  if(openHead->next==NULL)   
  {   
  printf("No   Way,Sorry!\n");   
  return(0);   
  }   
  /*从open表中取出第一个节点（隐含删除）*/   
  openQ=openHead->next;   
  openHead->next=openQ->next;   
  tempLC=openQ->leftChuanJiaoShi;   
  tempLY=openQ->leftYeRen;   
  tempRC=openQ->rightChuanJiaoShi;   
  tempRY=openQ->rightYeRen;   
  tempLS=openQ->locationOfShip;   
  tempSN=openQ->selfNumber;   
  tempFN=openQ->fatherNumber;   
    
  free(openQ);/*释放内存*/   
    
                /*把从open表取出的节点加入close表的开头*/   
  closeP=(State*)malloc(sizeof(State));   
  closeP->leftChuanJiaoShi=tempLC;   
  closeP->leftYeRen=tempLY;   
  closeP->rightChuanJiaoShi=tempRC;   
  closeP->rightYeRen=tempRY;   
  closeP->locationOfShip=tempLS;   
  closeP->selfNumber=tempSN;   
  closeP->fatherNumber=tempFN;   
  closeP->next=closeHead->next;   
  closeHead->next=closeP;   
    
                /*如果出现目标，结束循环*/   
  if(tempLC==0&&tempLY==0&&tempRC==ChuanJiaoShi   
  &&tempRY==YeRen&&tempLS==0)   
  break;   
                  /**/   
  for(i=0;i<3;i++)   
  {   
  for(j=0;j<3;j++)   
  {   
  /*除去无意义的情况：船上无人，船上有３人，船上有４人*/   
  if(!(i==0&&j==0||i==1&&j==2||i==2&&j==1||i==2&&j==2))   
  {   
  openM=(State*)malloc(sizeof(State));   
    
  if(tempLS==0)     /*船在右岸的扩展方式*/   
  {   
  openM->leftChuanJiaoShi=tempLC+i;   
  openM->leftYeRen=tempLY+j;   
  openM->rightChuanJiaoShi=tempRC-i;   
  openM->rightYeRen=tempRY-j;   
  openM->locationOfShip=1;   
  }   
  else     /*船在左岸的扩展方式*/   
  {   
  openM->leftChuanJiaoShi=tempLC-i;   
  openM->leftYeRen=tempLY-j;   
  openM->rightChuanJiaoShi=tempRC+i;   
  openM->rightYeRen=tempRY+j;   
  openM->locationOfShip=0;   
  }   
    
                                        /*传教士生命安全吗？此节点中人数出现负数了吗？*/   
  if((openM->leftChuanJiaoShi>=openM->leftYeRen   
  &&openM->rightChuanJiaoShi>=openM->rightYeRen   
  ||openM->leftChuanJiaoShi==0   
  &&openM->rightChuanJiaoShi>=openM->rightYeRen   
  ||openM->leftChuanJiaoShi>=openM->leftYeRen   
  &&openM->rightChuanJiaoShi==0)   
  &&(openM->leftYeRen>=0&&openM->rightYeRen>=0))   
  lifeSafeFlag=1;   
  else   
  lifeSafeFlag=0;   
    
                                        /*open表中出现过和预备插入结点openM相同状态的节点吗？*/   
  openN=openHead;   
  while(openN->next!=NULL)   
  {   
  openN=openN->next;   
  if(openN->leftChuanJiaoShi==openM->leftChuanJiaoShi   
  &&openN->leftYeRen==openM->leftYeRen   
  &&openN->rightChuanJiaoShi==openM->rightChuanJiaoShi   
  &&openN->rightYeRen==openN->rightYeRen   
  &&openN->locationOfShip==openM->locationOfShip)   
  {   
  openFlag=1;   
  break;   
  }   
  else   
  {   
  openFlag=0;   
  }   
  }   
  openN=NULL;   
    
                                        /*close表中出现过和预备插入结点openM相同状态的节点吗？*/   
  closeN=closeHead;   
  while(closeN->next!=NULL)   
  {   
  closeN=closeN->next;   
  if(closeN->leftChuanJiaoShi==openM->leftChuanJiaoShi   
  &&closeN->leftYeRen==openM->leftYeRen   
  &&closeN->rightChuanJiaoShi==openM->rightChuanJiaoShi   
  &&closeN->rightYeRen==openM->rightYeRen   
  &&closeN->locationOfShip==openM->locationOfShip)   
  {   
  closeFlag=1;   
  break;   
  }   
  else   
  {   
  closeFlag=0;   
  }   
  }   
  closeN=NULL;/*内存安全*/   
    
                                        /*如果预备节点符合传教士生命安全，不出现负数，未在open表和close表中出现过，   
  　插入open表的末尾*/   
  if(lifeSafeFlag==1&&openFlag==0&&closeFlag==0)   
  {   
  openM->selfNumber=++autoNumber;   
  openM->fatherNumber=tempSN;   
  openS=openHead;   
  while(openS->next!=NULL)   
  {   
  openS=openS->next;   
  }   
  openM->next=openS->next;   
  openS->next=openM;   
  openM=NULL;     /*内存安全*/   
  }   
  }   
  }   
  }   
  }   
    
        /*打印方法：用两个指针控制打印，closeM指向父亲，closeS指向自己，   
    判断如果closeS->fatherNumber==closeM->selfNumber,则打印出父节点   
    （注：先打印出儿子，后打印父亲）。enter变量控制打印整齐度。*/   
  closeM=closeHead->next;   
  closeS=closeM;   
  printf("(%d,%d,%d,%d,%d)",   
  closeM->leftChuanJiaoShi,   
  closeM->leftYeRen,   
  closeM->rightChuanJiaoShi,   
  closeM->rightYeRen,   
  closeM->locationOfShip);   
  while(closeM->next!=NULL)   
  {   
  closeM=closeM->next;   
  if(closeS->fatherNumber==closeM->selfNumber)   
  {   
        enter++;   
  printf("<--(%d,%d,%d,%d,%d)",   
  closeM->leftChuanJiaoShi,   
        closeM->leftYeRen,   
        closeM->rightChuanJiaoShi,   
        closeM->rightYeRen,   
        closeM->locationOfShip);   
  closeS=closeM;   
  if(enter%4==0)   
      printf("\n\n");   
  }   
  }   
  closeM=NULL;   
  closeS=NULL;   
  }