电梯调度算法(ms InterView)

goneWithWind

               
移臂调度算法包括以下四种：
1） 先来先服务算法； (根据访问者提出访问请求的先后次序来决定执行次序。
2） 最短寻找时间优先调度算法；(从等待的访问者中挑选寻找时间最短的那个请求执行，而不管访问者的先后次序。
3） 电梯调度算法；(从移动臂当前位置沿移动方向选择最近的那个柱面的访问者来执行，若该方向上无请求访问时，就改变移动方向再选择。)
4） 单向扫描调度算法。 (从0柱面开始往里单向扫描，扫到哪个执行哪个。
 
               
               
               
                    
  */   
  //   t1.cpp   :   定义控制台应用程序的入口点。   
  //      
  #include   "stdafx.h"   
  #include"math.h"   
  #include"stdlib.h"   
  #include"string.h"   
  struct   Head   
  {   
          int   nPosition;   
          bool   bVisited;   
  };   
  void   Visit(struct   Head   *pHead)   
  {   
      printf("visite   cy:%d\n",pHead->nPosition);   
      pHead->bVisited=true;   
  }   
  int   ReadInputKeyboard(struct   Head   *pHead,int   *pCurrentPosition,int   nMaxNumber)   
  {   
      int   i;   
      printf("please   input   Current   position:");   
      scanf("%d",pCurrentPosition);   
      printf("please   input   will   visit   position:");   
      for(i=0;inMaxNumber;i++)   
      {   
          scanf("%d",&pHead.nPosition);   
          pHead.bVisited=false;   
          if(pHead.nPosition0)   
          break;   
      }   
      return   i;   
  }   
  int   ReadInputFile(struct   Head   *pHead,int   *pCurrentPosition,int   nMaxNumber)   
  {   
      int   i;   
      char   szFileName[256],*q,*p,szTemp[20];   
      printf("please   input   filename:");   
      scanf("%s",szFileName);   
    
      FILE   *pFile=fopen(szFileName,"r");   
      if(pFile==NULL)   
      {   
          printf("open   file   %s   error",szFileName);   
          return   -1;   
      }   
    
      for(i=0;!feof(pFile)   &&inMaxNumber;)   
      {   
          p=szFileName;   
          fgets(p,256,pFile);   
          while(q=strchr(p,','))   
          {   
              memset(szTemp,0,sizeof(szTemp)*sizeof(char));   
              strncpy(szTemp,p,q-p);   
              p=q+1;   
              if(i==0)   
                  *pCurrentPosition=atoi(szTemp);   
              else   
              {   
                  pHead[i-1].nPosition=atoi(szTemp);   
                  pHead[i-1].bVisited=false;   
              }   
              i++;   
          }   
          memset(szTemp,0,sizeof(szTemp)*sizeof(char));   
          pHead[i-1].nPosition=atoi(p);   
          pHead[i-1].bVisited=false;   
          //i++;      
      }   
      fclose(pFile);   
      return   i;   
  }   
    
  int   FifoVisit(int   nCurrentPosition,struct   Head   *pHead,int   nNumber)   
  {   
      //先来先服务   
      int   nHaveVisited=0;   
      int   nMoveDistance=0;   
      int   i;   
      while(nHaveVisitednNumber)   
      {   
          for(i=0;inNumber;i++)   
          {   
              if(pHead.bVisited)   
              continue;   
              Visit(&pHead);   
              nHaveVisited++;   
              nMoveDistance+=abs(nCurrentPosition-pHead.nPosition);   
              nCurrentPosition=pHead.nPosition;   
          }   
      }   
      printf("the   sum   of   move   distance:%d\n",nMoveDistance);   
      return   nMoveDistance;   
  }      
    
  int   SsfoVisit(int   nCurrentPosition,struct   Head   *pHead,int   nNumber)   
  {   
  //   最短寻找时间优先   
      int   nHaveVisited=0;   
      int   nMoveDistance=0;   
      int   nMinDistance=0;   
      int   nMinIndex=0;   
      int   i;   
      while(nHaveVisitednNumber)   
      {   
          nMinDistance=0xffff;   
          nMinIndex=0;   
          //找最小值   
          for(i=0;inNumber;i++)   
          {   
              if(pHead.bVisited)   
              continue;   
              if(nMinDistance>abs(pHead.nPosition-nCurrentPosition))   
              {   
                  nMinDistance=abs(pHead.nPosition-nCurrentPosition);   
                  nMinIndex=i;   
              }   
          }   
          //访问   
          Visit(&pHead[nMinIndex]);   
          nHaveVisited++;   
          nMoveDistance+=nMinDistance;   
          nCurrentPosition=pHead[nMinIndex].nPosition;   
      }   
      printf("the   sum   of   move   distance:%d\n",nMoveDistance);   
      return   nMoveDistance;   
  }   
  int   DtVisit(int   nCurrentPosition,bool   bOut,struct   Head   *pHead,int   nNumber)   
  {   
  //电梯调度算法   
      int   nHaveVisited=0;   
      int   nMoveDistance=0;   
      int   nMinDistance=0;   
      int   nMinIndex=0;   
      int   i;   
      while(nHaveVisitednNumber)   
      {   
          nMinDistance=0xffff;   
          nMinIndex=0;   
          //找最小值   
          for(i=0;inNumber;i++)   
          {   
              if(pHead.bVisited)   
              continue;   
              if(bOut&&pHead.nPositionnCurrentPosition||!bOut&&pHead.nPosition>nCurrentPosition)   
              {   
                  if(nMinDistance>abs(pHead.nPosition-nCurrentPosition))   
                  {   
                      nMinDistance=abs(pHead.nPosition-nCurrentPosition);   
                      nMinIndex=i;   
                  }   
              }      
          }   
          if(nMinDistance==0xffff)   
          {   
              bOut=!bOut;   
              continue;   
          }   
    
          //访问   
          Visit(&pHead[nMinIndex]);   
          nHaveVisited++;   
          nMoveDistance+=nMinDistance;   
          nCurrentPosition=pHead[nMinIndex].nPosition;   
      }   
         printf("the   sum   of   move   distance:%d\n",nMoveDistance);   
         return   nMoveDistance;   
  }   
  int   DxVisit(int   nCurrentPosition,struct   Head   *pHead,int   nNumber)   
  {   
          //单向调度算法   
      int   nHaveVisited=0;   
      int   nMoveDistance=0;   
      int   nMinDistance=0;   
      int   nMinIndex=0;   
      int   i;   
      while(nHaveVisitednNumber)   
      {   
          nMinDistance=0xffff;   
          nMinIndex=0;   
          //找最小值   
          for(i=0;inNumber;i++)   
          {   
              if(pHead.bVisited)   
              continue;   
              if(pHead.nPosition>nCurrentPosition   )   
              {   
                  if(nMinDistance>abs(pHead.nPosition-nCurrentPosition))   
                  {   
                      nMinDistance=abs(pHead.nPosition-nCurrentPosition);   
                      nMinIndex=i;   
                  }   
                  }      
          }   
         if(nMinDistance==0xffff)   
      {   
          nMoveDistance+=199-nCurrentPosition;   
          nCurrentPosition=0;   
          continue;   
      }   
    
      //访问   
          Visit(&pHead[nMinIndex]);   
      nHaveVisited++;   
      nMoveDistance+=nMinDistance;   
      nCurrentPosition=pHead[nMinIndex].nPosition;   
      }   
      printf("the   sum   of   move   distance:%d\n",nMoveDistance);   
      return   nMoveDistance;   
  }   
  int   main(int   argc,   char*   argv[])   
  {   
  //p114   
  struct   Head   mylist[20];//={98,false,183,false,37,false,122,false,14,false,124,false,65,false,67,false};   
  //int   nCurrentPosition=53;   
  //int   nRealNumber=8;   
    
  int   nCurrentPosition=0;   
  int   nRealNumber=ReadInputFile(mylist,&nCurrentPosition,20);   
  // FifoVisit(nCurrentPosition,mylist,nRealNumber);   
  // SsfoVisit(nCurrentPosition,mylist,nRealNumber);   
  //DtVisit(nCurrentPosition,false,mylist,nRealNumber);   
  DxVisit(nCurrentPosition,mylist,nRealNumber);   
    
  return   0;   
  }   
    
    
   


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/1586/showart_1860531.html