tlist.h

八数码问题源程序.

//---------------------------------------------------------------------------
#ifndef KTListH
#define KTListH

//节点模板类 (如 KTNode<int>* Paths; 使用)
template <class DATATYPE>
class KTNode
{
public:
   DATATYPE  Data;         //可变数据类型的节点数据
   int Weight;             //排序用的权重
   KTNode*  Next;          //指向下一个节点的指针
   KTNode*  Prior;         //指向上一个节点的指针

   KTNode()
   {
      Weight = 0;
   }

   //拷贝构造函数
   KTNode(KTNode& S)
   {
      Data=S.Data;
      Weight=S.Weight;
      Next=S.Next;
      Prior=S.Prior;
   }

   KTNode operator=(KTNode S)   //重载运算符，使两个KTNode对象能相互赋值
   {
      Data=S.Data;
      Weight=S.Weight;
      Next=S.Next;
      Prior=S.Prior;

      return *this;       //调用拷贝构造函数
   }
};

//链表模板类,双向链表 (如 KTList<int>* Paths; 使用)
template <class DATATYPE>
class KTList
{
protected:
   KTNode<DATATYPE>* Head;      //指向头节点的指针
   KTNode<DATATYPE>* Tail;      //指向尾节点的指针
   KTNode<DATATYPE>* Current;   //指向当前节点的指针
   int Count;                   //节点个数
   enum {B,E,BE,OK} Flag;  //当前指针的标记

public:
   KTList(void)                    //构造函数
   {
      Current = NULL;
      Head = NULL;
      Tail = NULL;
      Count = 0;
      Flag = BE;
   }

   ~KTList()                  //析构函数，释放所有节点空间
   {
      for(First();Delete();); //删掉所有有数据的节点
   }

   operator int ()
   {
      return IsEmpty();
   }

   bool Next(void)            //使当前节点的指针指向当前节点的下一个节点
   {
      if (IsEof())       //如果是最后一个节点的下一个节点或链表为空
         return false;

      if (!Current->Next) {   //如果是最后一个节点
         Flag = E;
         return true;
      }

      if (IsBof()) {          //如果是第一个节点的前一个节点
         Flag = OK;
         return true;
      }

      Current = Current->Next;
      Flag = OK;
      return true;
   }

   bool Prior(void)          //使当前节点的指针指向当前节点的上一个节点
   {
      if (IsBof())           //如果是第一个节点的前一个节点或链表为空
         return false;

      if (IsHead()) {  //如果是第一个节点
         Flag = B;
         return true;
      }

      if (IsEof()) {          //如果是最后一个节点的下一个节点
         Flag = OK;
         return true;
      }

      //如果是中间节点
      Current = Current->Prior;
      Flag = OK;
      return true;
   }

   bool First(void)        //使当前节点的指针指向首节点
   {
      if (IsEmpty())
         return false;

      Current=Head;
      Flag = OK;
      return true;
   }

   bool Last(void)         //使当前节点的指针指向最后一个节点
   {
      if (IsEmpty())
         return false;

      Current=Tail;
      Flag = OK;
      return true;
   }

   bool IsEmpty()         //链表是否为空
   {
      return Flag == BE;
   }

   bool IsEof()           //是否最后一个节点的下一个节点
   {
      return Flag == E || Flag == BE;
   }

   bool IsBof()           //是否第一个节点的前一个节点
   {
      return Flag == B || Flag == BE;
   }

   bool IsHead()          //是否是第一个节点
   {
      return Flag == OK && Current == Head;
   }

   bool IsTail()          //是否是最后一个节点
   {
      return Flag == OK && Current == Tail;
   }

   bool GetData(DATATYPE & Data)
   {
      if(IsEof() || IsBof())
         return false;

      Data=Current->Data;
      return true;
   }

   int GetCount(void)
   {
      return Count;
   }

   bool Insert(DATATYPE Data)  //在当前节点之前插入一个节点
   {
      KTNode<DATATYPE>* temp=new KTNode<DATATYPE>;
      temp->Data = Data;

      if (IsEmpty()) {             //如果是空链表
         temp->Next  = NULL;
         temp->Prior = NULL;
         Head = Tail = Current = temp;
         Flag = OK;
         Count = Count + 1;
         return true;
      }

      if (IsEof()) {             //如果是链表不空而且是Eof,在表尾增加一个节点
         temp->Next = NULL;
         temp->Prior = Current;
         Current->Next = temp;
         Tail = temp;
         Current = temp;
         Flag = OK;
         Count = Count + 1;
         return true;
      }

      if (IsBof() || Current == Head) {  //如果链表不空而且是第一个节点，在第一个节点之前插入
         temp->Next = Head;
         temp->Prior = NULL;
         Head->Prior = temp;
         Head = temp;
         Current = temp;
         Flag = OK;
         Count = Count + 1;
         return true;
      }

      temp->Next = Current;         //其他情况，中间和最后一个节点，在当前节点之前插入
      temp->Prior = Current->Prior;
      Current->Prior->Next = temp;
      Current->Prior = temp;

      Current = temp;
      Flag = OK;
      Count = Count + 1;
      return true;
   }

   bool Delete(void)
   {
      if(IsBof() || IsEof())
         return false;

      KTNode<DATATYPE> *temp = Current;

      if (Current == Head && Current == Tail) {  //如果只有一个节点
         Current = Head = Tail = NULL;
         delete temp;
         Flag = BE;
         Count = Count - 1;
         return true;
      }

      if (Current == Head) {  //如果是第一个节点
         Current->Next->Prior = NULL;
         Head = Current->Next;
         delete temp;
         Current = Head;
         Flag = OK;
         Count = Count - 1;
         return true;
      }

      if (Current == Tail) {
         Current->Prior->Next = NULL;
         Tail = Current->Prior;
         delete temp;
         Current = Tail;
         Flag = OK;
         Count = Count - 1;
         return true;
      }

      Current->Prior->Next = Current->Next;
      Current->Next->Prior = Current->Prior;
      Current = Current->Next;
      delete temp;
      Flag = OK;
      Count = Count - 1;
      return true;
   }

   bool Append(DATATYPE Data)   //在链表尾部增加一个节点
   {
      Last();
      Next();       //定位到Eof
      return Insert(Data);
   }

   bool Cut()   //删除最后一个节点
   {
      Last();
      return Delete();
   }

   void Empty()  //清空链表
   {
      for(First();Delete(););   //删掉所有有数据的节点
   }

   bool SetWeight(int mWeight)  //设置排序用的权重
   {
      if (IsBof() || IsEof())
        return false;

      Current->Weight = mWeight;
      return true;
   }

   void LocateWeight(int mWeight)    //定位到Weight值刚好大于等于Weight的节点的下一个节点
   {
       First();
       while (!IsEof()) {
          if (Current->Weight > mWeight)
             return;
          Next();
       }
   }

   void Sort()  //根据节点权值对规则从小到大排序(选择排序法)
   {
      KTNode<DATATYPE>* temp;      //外层循环的当前指针
      KTNode<DATATYPE>* min;       //最小权值的节点指针
      First();
      while (!IsEof()) {
         temp = Current;

         min = Current;

         Next();   
         while (!IsEof()) {
            if (Current->Weight < min->Weight)
               min = Current;
            Next();
         }

         Swap(temp,min); //交换两个节点的权值和数据

         Current = temp;
         Flag = OK;  //这一句比较难注意到，用Flag标记状态其实不是很好，
                     //很多地方都必须注意到
         Next();
      }
   }

   //本来想修改指针而不改值的，但发觉比直接交换值复杂很多，所以就直接交换值了
   bool Swap(KTNode<DATATYPE>* Node1,KTNode<DATATYPE>* Node2)
   {
      if (!Node1 || !Node2)
         return false;

      if (Node1 == Node2)
         return true;

      int temp;
      DATATYPE mData;

      //直接交换两个节点的权值和数据
      temp = Node1->Weight;
      Node1->Weight = Node2->Weight;
      Node2->Weight = temp;

      mData = Node1->Data;
      Node1->Data = Node2->Data;
      Node2->Data = mData;

      return true;
   }
};

//---------------------------------------------------------------------------
#endif