llist.h

数据结构实验——停车场管理系统 停车场管理。设停车场内只有一个可停放几辆汽车的狭长通道

template <class Elem> class Link {
public:
  Elem element;      
  Link *next;        
  Link(const Elem& elemval, Link* nextval =NULL)
    { element = elemval;  next = nextval; }
  Link(Link* nextval =NULL) { next = nextval; }
};


template <class Elem> class LList{
private:
  Link<Elem>* head;       
  Link<Elem>* tail;       
  Link<Elem>* fence;      
  int leftcnt;            
  int rightcnt;           
  void init() {           
    fence = tail = head = new Link<Elem>;
    leftcnt = rightcnt = 0;
  }
  void removeall() {   
    while(head != NULL) {
      fence = head;
      head = head->next;
      delete fence;
    }
  }
public:
  LList(int size=DefaultListSize) { init(); }
  ~LList() { removeall(); }  
  void clear() { removeall(); init(); }
  bool insert(const Elem&);
  bool append(const Elem&);
  bool remove(Elem&);
  void setStart()
    { fence = head; rightcnt += leftcnt; leftcnt = 0; }
  void setEnd()
    { fence = tail; leftcnt += rightcnt; rightcnt = 0; }
  void prev();
  void next() {
    if (fence != tail) 
      { fence = fence->next; rightcnt--; leftcnt++; }
  }
  int leftLength() const  { return leftcnt; }
  int rightLength() const { return rightcnt; }
  bool setPos(int pos);
  bool getValue(Elem& it) const {
    if(rightLength() == 0) return false;
    it = fence->next->element;
    return true;
  }
  void print() const;
};

template <class Elem> 
bool LList<Elem>::insert(const Elem& item) {
  fence->next = new Link<Elem>(item, fence->next);  
  if (tail == fence) tail = fence->next;  
  rightcnt++;
  return true;
}

template <class Elem> 
bool LList<Elem>::append(const Elem& item) {
  tail = tail->next = new Link<Elem>(item, NULL);
  rightcnt++;
  return true;
}


template <class Elem> bool LList<Elem>::remove(Elem& it) {
  if (fence->next == NULL) return false; 
  it = fence->next->element;       
  Link<Elem>* ltemp = fence->next; 
  fence->next = ltemp->next;       
  if (tail == ltemp) tail = fence; 
  delete ltemp;                    
  return true;
}


template <class Elem> void LList<Elem>::prev() {
  Link<Elem>* temp = head;
  if (fence == head) return; 
  while (temp->next!=fence) temp=temp->next;
  fence = temp;
  leftcnt--; rightcnt++;
}


template <class Elem> bool LList<Elem>::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;
}

template <class Elem> void LList<Elem>::print() const {
 if(head->next == NULL)
	cout<<"The waiting list is empty."<<endl;
 else{
	 Link<Elem>* temp = head;
	 cout << "The waiting list: "<<endl;
	 while (temp->next != NULL) {
		 cout << temp->next->element << " ";
		 temp = temp->next;
		}
	  cout <<endl;
	}
}