llist.h

蚁群算法求解聚类问题

// 链表类模板
template <class Elem> class LList {
private:
  CLink<Elem>* head;       // 指向头结点的指针
  CLink<Elem>* tail;       // 尾指针 
  CLink<Elem>* fence;      // 链表中的自由指针
  int leftcnt;            // fence指向元素左侧的元素数目
  int rightcnt;           // fence指向元素右侧的元素数目
  void init() {
    fence = tail = head = new CLink<Elem>;
    leftcnt = rightcnt = 0;
  }
 
 
// 释放链表 
void removeall() {   
    while(head != NULL) {
      fence = head;
      head = head->next;
      delete fence;
    }
  }
public:

  LList() { init(); }

  ~LList() { removeall(); }

  void clear() { removeall(); init(); }
  

 
 // 在fence指针指向元素的下一个元素前插入一个新的元素  
  bool insert(const Elem& item) 
 {
  fence->next = new CLink<Elem>(item, fence->next);  
  if (tail == fence) tail = fence->next;
  rightcnt++;
  return true;
}

  

// 在链表末尾添加新的节点 
  bool append(const Elem& item)
 {
  tail = tail->next = new CLink<Elem>(item, NULL);
  rightcnt++;
  return true;
}
  

  
// 移除fence指针指向元素的下一个元素，并返回所移除元素的值
 bool remove(Elem& it) {
  if (fence->next == NULL) return false; // 如果fence指针指向的元素是末节点，则不做任何改变
  it = fence->next->element;       // 记住节点中的数据
  CLink<Elem>* ltemp = fence->next; // 记住将要移除的节点
  fence->next = ltemp->next;       // 将节点从链表中移除
  if (tail == ltemp) tail = fence; // 重新设置尾指针
  delete ltemp;                    // 释放空间
  rightcnt--;
  return true;
}


 // 判断链表是否为空
 bool is_empty()
{ 
  if(head->next==NULL)  return true;
  else return false;
}


 void setStart()  // 将fence指针指向头节点
    { fence = head; rightcnt += leftcnt; leftcnt = 0; }
 
 
 
 void setEnd()   // 将fence指针指向末节点
    { fence = tail; leftcnt += rightcnt; rightcnt = 0; }
 

 
 // 将fence指针向左移动一个节点，如果其左边没有节点，则不移动 
  void prev()
{
  CLink<Elem>* temp = head;
  if (fence != head){
	while (temp->next!=fence) temp=temp->next;
	fence = temp;
	leftcnt--; rightcnt++;
  }
} 

  
// 将fence指针向右移动一个节点，如果其右边没有节点，则不移动
  void next()
{
    if (fence != tail)
      { fence = fence->next; rightcnt--; leftcnt++; }
}
  
  int leftLength() const  { return leftcnt; }   // 返回fence指针指向元素左侧的元素数目
  
  int rightLength() const { return rightcnt; }    // 返回fence指针指向元素右侧的元素数目
 
 


// 设置fence指向元素左侧的元素数目  
  bool setPos(int pos)
{
  if ((pos < 0) || (pos > rightcnt+leftcnt)) return false;
  fence = head;
  for(int i=0; i<pos; i++) fence = fence->next;
  return true;
}

 
  
// 返回fence指向元素右侧的第一个元素
bool getValue(Elem& it) const {
    if(rightLength() == 0) return false;
    it = fence->next->element;
    return true;
}
  
  
// 将fence指针指向指定值的元素 
bool Locate( Elem& it)
{
 fence= head;
 while((fence->next != NULL)&&(fence->next->element!=it))  fence=fence->next;
 if( fence->next==NULL) return false;
 else return true;
}

};