llist.h

ai 自动排序 把数字0-8顺序打乱,可自动排序好

//列举链表的两个末端；
//enum TYPE {BREADTH_FIRST, DEPTH_FIRST };

// 类举可能的A* 启发式方法，第二种启发式使用深度；
//enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES}; 
enum SIDE { LEFT, RIGHT }; 
// 链表由下面的Link结构对象组成； 
struct Link { 
  Link *LeftLink; // 指向链表中左端LINK对象的指针； 
  Link *RightLink; //指向链表中右端LINK对象的指针；
  CState *Data; // 指向状态数据的指针；
}; 

// 链表类； 
class CLList { 
private: 
  Link* LeftPointer; // 指向一个永远是空的，并且是末端的link对象；
  Link* RightPointer; //与上面的指针一样，但方向相反；
  double ListLen; // 链表的长度； 
  // 清空内存；
  void EmptyUsedMemory() { 
    CState *temp; 
    while(!IsListEmpty()) { 
      temp = Pop(LEFT); 
      delete temp; 
    } 
  } 

public: 
  class ERROR_CANT_POP_EMPTY_LIST{}; // Error Exception 

  CLList() { 
  // initialise all private variables 
    LeftPointer = new Link; 
    RightPointer = new Link; 
    ListLen = 0; 
    LeftPointer->LeftLink = 0; 
    LeftPointer->RightLink = RightPointer; 
    RightPointer->RightLink = 0; 
    RightPointer->LeftLink = LeftPointer; 
  } 
  ~CLList() { 
    EmptyUsedMemory(); 
  } 

  inline double GetListLen() { 
    return ListLen; 
  } 

  inline bool IsListEmpty() { 
    return (LeftPointer->RightLink == RightPointer); 
  } 

  //从链表中弹出数据；
  CState* Pop(SIDE Side) { 
    Link ForReturn; 
    Link* ForDelete; 
    if (!IsListEmpty()) { 
      ListLen--; 
      if (Side == LEFT) { 
        ForReturn = *(LeftPointer->RightLink); 
        ForDelete = LeftPointer->RightLink; 
        LeftPointer->RightLink = ForReturn.RightLink; 
        ForReturn.RightLink->LeftLink = LeftPointer; 
      } 
      else { 
        ForReturn = *(RightPointer->LeftLink); 
        ForDelete = RightPointer->LeftLink; 
        RightPointer->LeftLink = ForReturn.LeftLink; 
        ForReturn.LeftLink->RightLink = RightPointer; 
      } 
      delete ForDelete; 
      return ForReturn.Data; 
    } 
    return 0; 
  } 

  //向链表中压入数据 
  void Push(SIDE Side, CState* What) { 
    Link* NewLink = new Link; 
    NewLink->Data = What; 
    ListLen++; 
    if (Side == LEFT) { 
      NewLink->RightLink = LeftPointer->RightLink; 
      NewLink->LeftLink = LeftPointer; 
      LeftPointer->RightLink = NewLink; 
      NewLink->RightLink->LeftLink = NewLink; 
    } 
    else { 
      NewLink->RightLink = RightPointer; 
      NewLink->LeftLink = RightPointer->LeftLink; 
      RightPointer->LeftLink = NewLink; 
      NewLink->LeftLink->RightLink = NewLink; 
    } 
  } 

  //启发式搜索过程中，从链表中搜寻最佳状态；
  CState* PopBestByHeuristics(HEURISTIC heuristic) { 
    int BestValue=9999; 
    int Temp=0; 
    Link* BestState = 0; 
    Link* Current = LeftPointer; 
    CState* ForReturn = 0; 
    if(!IsListEmpty()) { 
      //启发式搜索可以使用MANHATTAN_DISTANCE或WrongTile方式来搜寻最佳状态
      while(Current->RightLink != RightPointer) { 
        Current = Current->RightLink; 
        if(heuristic == MANHATTAN_DISTANCE) { 
          Temp = Current->Data->GetManhattanDistance(); 
        } 
        else { 
          Temp = Current->Data->GetWrongTiles(); 
        } 
        if(Temp < BestValue) { 
          BestValue = Temp; 
          BestState = Current; 
        } 
      } 
      //从链表中删除最佳状态；
      BestState->RightLink->LeftLink = BestState->LeftLink; 
      BestState->LeftLink->RightLink = BestState->RightLink; 
      ForReturn = BestState->Data; 
      delete BestState; 
      return ForReturn; 
    } 
    return 0; 
  } 

  CState* PeekByBestHueristics(HEURISTIC heuristic) { 
    int BestValue=9999; 
    int Temp=0; 
    Link* BestState = 0; 
    Link* Current = LeftPointer; 
    CState* ForReturn = 0; 
    if(!IsListEmpty()) { 
      // Find BEST State By Wrong tile number heuristic 
      while(Current->RightLink != RightPointer) { 
        Current = Current->RightLink; 
        if(heuristic == MANHATTAN_DISTANCE) { 
          Temp = Current->Data->GetManhattanDistance(); 
        } 
        else { 
          Temp = Current->Data->GetWrongTiles(); 
        } 
        if(Temp < BestValue) { 
          BestValue = Temp; 
          BestState = Current; 
        } 
      } 
      ForReturn = BestState->Data; 
      return ForReturn; 
    } 
    return 0; 
  }
};