tlist.h

这是一个求解线性规划问题的程序

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

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

   KTNode()
   {
      Next = Prior = NULL;
   }
};

enum LFLAG{B,E,BE,OK};

//链表模板类,双向链表,操纵上面的节点类 (如 KTList<int>* Paths; 使用)
template <class DATATYPE>
class KTList
{
protected:
   KTNode<DATATYPE>* Head;      //指向头节点的指针
   KTNode<DATATYPE>* Tail;      //指向尾节点的指针
   KTNode<DATATYPE>* Current;   //指向当前节点的指针
   int Count;                   //节点个数
   LFLAG Flag;  //当前指针的标记(Bof,Eof,Bof && Eof,OK)

   bool BookMarked;             //书签是否有效
   KTNode<DATATYPE>* BMCurrent; //书签的所在节点的指针
   LFLAG BMFlag;     //书签所在节点的标记

public:
   KTList(void);           //构造函数
   ~KTList(void);          //析构函数，释放所有节点空间

   operator int ();        //判断链表是否为空 if (!LOpen); 如果链表不空

   bool Next(void);        //使当前节点的指针指向当前节点的下一个节点
   bool Prior(void);       //使当前节点的指针指向当前节点的上一个节点
   bool First(void);       //使当前节点的指针指向首节点
   bool Last(void);        //使当前节点的指针指向最后一个节点

   bool IsEmpty();         //链表是否为空
   bool IsEof();           //是否最后一个节点的下一个节点
   bool IsBof();           //是否第一个节点的前一个节点
   bool IsHead();          //是否是第一个节点
   bool IsTail();          //是否是最后一个节点

   DATATYPE GetData(void)   //取得当前数据
   {
      if (IsBof() || IsEof())
         return NULL;

      return Current->Data;
   }

   bool SetData(DATATYPE aData)   //取得当前数据
   {
      if (IsBof() || IsEof())
         return false;

      Current->Data = aData;
      return true;
   }

   int GetCount(void);            //得到节点个数

   bool Insert(DATATYPE Data);   //在当前节点之前插入一个节点
   bool Delete(void);             //删除当前节点
   bool Append(DATATYPE Data);   //在链表尾部增加一个节点
   bool Cut();                    //删除最后一个节点
   void Empty();                  //清空链表
   bool Join(KTList<DATATYPE>* lList)  //把表lList连在本链表尾部
   {
      if (lList->IsEmpty()) {  //如果lList为空,不用连
        delete lList;
        return true;
      }  
 
      if (IsEmpty()) {        //如果本表为空
        Head = lList->Head;
        Tail = lList->Tail;
        Count = lList->Count;
        Current = Head;
        Flag = OK;

        lList->Head = lList->Tail = lList->Current = NULL;
        lList->Flag = BE;
        lList->Count = 0;
        delete lList;
        return true;
      }

      //如果两个表都不为空,尾节点和头节点相连
      Tail->Next = lList->Head;
      lList->Head->Prior = Tail;
      Tail = lList->Tail;
      Count = Count + lList->Count;
      Current = lList->Head;
      Flag = OK;

      lList->Head = lList->Tail = lList->Current = NULL;
      lList->Flag = BE;
      lList->Count = 0;
      delete lList;
      return true;

      //要不要释放lList链表的基本数据Head,Tail？
   }

   void SetBookMark()  //设置书签
   {
      BookMarked = true;
      BMCurrent = Current;
      BMFlag = Flag;
   }

   bool GetBookMark()  //定位到书签
   {
      if (!BookMarked)
         return false;

      Current = BMCurrent;
      Flag = BMFlag;
      return true;
   }

   void Sort();  //根据节点大小(重载)对规则从小到大排序(选择排序法)
   bool Swap(KTNode<DATATYPE>* Node1,KTNode<DATATYPE>* Node2); //交换两个节点的数据
   bool Locate(DATATYPE aData) //查找某个元素
   {
      First();
      while (!IsEof()) {
         if (Current->Data == aData)
            return true;
         Next();
      }
      return false;
   }
};



//KTList的实现
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//构造函数
template <class DATATYPE>
KTList<DATATYPE>::KTList(void)
{
   Current = NULL;
   Head = NULL;
   Tail = NULL;
   Count = 0;
   Flag = BE;

   BookMarked = false;
}

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

template <class DATATYPE>
KTList<DATATYPE>::operator int ()
{
   return IsEmpty();
}

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

   if (!Current->Next) {   //如果是最后一个节点,不动current指针！！
      Flag = E;
      return true;
   }

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

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

//使当前节点的指针指向当前节点的上一个节点
template <class DATATYPE>
bool KTList<DATATYPE>::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;
}

//使当前节点的指针指向首节点
template <class DATATYPE>
bool KTList<DATATYPE>::First(void)
{
   if (IsEmpty())
      return false;

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

//使当前节点的指针指向最后一个节点
template <class DATATYPE>
bool KTList<DATATYPE>::Last(void)
{
   if (IsEmpty())
      return false;

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

//链表是否为空
template <class DATATYPE>
bool KTList<DATATYPE>::IsEmpty()
{
   return Flag == BE;
}

//是否最后一个节点的下一个节点
template <class DATATYPE>
bool KTList<DATATYPE>::IsEof()
{
   return Flag == E || Flag == BE;
}

//是否第一个节点的前一个节点
template <class DATATYPE>
bool KTList<DATATYPE>::IsBof()
{
   return Flag == B || Flag == BE;
}

//是否是第一个节点
template <class DATATYPE>
bool KTList<DATATYPE>::IsHead()
{
   return Flag == OK && Current == Head;
}

//是否是最后一个节点
template <class DATATYPE>
bool KTList<DATATYPE>::IsTail()
{
   return Flag == OK && Current == Tail;
}


//得到节点个数
template <class DATATYPE>
int KTList<DATATYPE>::GetCount(void)
{
   return Count;
}

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

   if (IsEmpty()) {             //如果是空链表
      temp->Next  = NULL;
      temp->Prior = NULL;
      Head = Tail = temp;
   }
   else if (IsEof()) {             //如果是链表不空而且是Eof,在表尾增加一个节点
      temp->Next = NULL;
      temp->Prior = Tail;
      Tail->Next = temp;
      Tail = temp;
   }
   else if (IsBof() || Current == Head) {  //如果链表不空而且是第一个节点，在第一个节点之前插入
      temp->Next = Head;
      temp->Prior = NULL;
      Head->Prior = temp;
      Head = temp;
   }
   else {
      temp->Next = Current;         //其他情况，中间和最后一个节点，在当前节点之前插入
      temp->Prior = Current->Prior;
      Current->Prior->Next = temp;
      Current->Prior = temp;
   }
   
   Current = temp;
   Flag = OK;
   Count = Count + 1;
   return true;
}

//删除当前节点
template <class DATATYPE>
bool KTList<DATATYPE>::Delete(void)
{
   if(IsBof() || IsEof())
      return false;

   KTNode<DATATYPE> *temp = Current;

   if (Current == Head && Current == Tail) {  //如果只有一个节点
      Current = Head = Tail = NULL;
      Flag = BE;
   }
   else if (Current == Head) {  //如果是第一个节点
      Head->Next->Prior = NULL;
      Head = Head->Next;
      Current = Head;
      Flag = OK;
   }
   else if (Current == Tail) {
      Tail->Prior->Next = NULL;
      Tail = Tail->Prior;
      Current = Tail;
      Flag = OK;
   }
   else {
      Current->Prior->Next = Current->Next;
      Current->Next->Prior = Current->Prior;
      Current = Current->Next;
      Flag = OK;
   }

   if (BookMarked && BMCurrent == temp)  //如果删掉的刚好是书签所在节点
         BookMarked = false;
         
   delete temp;
   Count = Count - 1;
   return true;
}

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


//删除最后一个节点
template <class DATATYPE>
bool KTList<DATATYPE>::Cut()
{
   Last();
   return Delete();
}

//清空链表
template <class DATATYPE>
void KTList<DATATYPE>::Empty()
{
   for(First();Delete(););   //删掉所有有数据的节点
}

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

      min = Current;

      Next();
      while (!IsEof()) {
         if (Current->Data < min->Data)   //DATATYPE的类型,重载<号
            min = Current;
         Next();
      }

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

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

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

   if (Node1 == Node2)
      return true;

   DATATYPE mData;

   //直接交换两个节点的数据(指针)
   mData = Node1->Data;
   Node1->Data = Node2->Data;
   Node2->Data = mData;

   return true;
}
#endif
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------