lk_list_double.h

Editor C++ 源程序 用链表实现

template <class Node_entry>
struct Node {
//  data members
   Node_entry entry;
   Node<Node_entry> *next;
   Node<Node_entry> *back;
//  constructors
   Node();
   Node(Node_entry, Node<Node_entry> *link_back = NULL,
                    Node<Node_entry> *link_next = NULL);
};


template<class Node_entry>
Node<Node_entry>::Node()
{
   next = back = NULL;
}


template<class Node_entry>
Node<Node_entry>::Node(Node_entry item, Node<Node_entry> *link_back,Node<Node_entry> *link_next)
{
   entry = item;
   next = link_next;
   back = link_back;
}


template <class List_entry>
class List {
public:
//  Add specifications for methods of the list ADT.
//  Add methods to replace compiler generated defaults.
   List();
  ~List();
   int size() const;
   bool empty() const;
   void clear();
   void traverse(void (*visit)(List_entry &));
   Error_code retrieve(int position, List_entry &x) const;
   Error_code replace(int position, const List_entry &x);
   Error_code remove(int position, List_entry &x);
   Error_code insert(int position, const List_entry &x);
   List(const List<List_entry> &copy);
   void operator =(const List<List_entry> &copy);

protected:
//  Data members for the doubly-linked list implementation follow:
   int count;
   mutable int current_position;
   mutable Node<List_entry> *current;

//  The auxiliary function to locate list positions follows:
   void set_position(int position) const;
};


template <class List_entry>
List<List_entry>::List()
{
	count=0;
	current_position=-1;
	current=NULL;
}


template <class List_entry>
bool List<List_entry>::empty() const
{
   return count==0;
}


template <class List_entry>
List<List_entry>::~List()
{
	clear();
}


template <class List_entry>
int List<List_entry>::size() const
/*
Post: The function returns the number of entries in the List.
*/
{
	return count;
}


template <class List_entry>
void List<List_entry>::clear()
{
	List_entry x;
	while(size()>0)remove(0,x);
}


template <class List_entry>
void List<List_entry>::traverse(void (*visit)(List_entry &))
/*
Post: The action specified by function (*visit) has been performed on every
      entry of the List, beginning at position 0 and doing each in turn.
*/
{
	List_entry x;
	for (int i = 0; i < count; i++){
		retrieve(i,x);
        (*visit)(x);
	}
}


template <class List_entry>
Error_code List<List_entry>::retrieve(int position, List_entry &x) const
{
    if (position < 0 || position > count-1)
		return range_error;
	set_position(position);
	x = current->entry;
    return success;
}


template <class List_entry>
Error_code List<List_entry>::replace(int position, const List_entry &x)
{
    if (position < 0 || position > count-1)
		return range_error;
	set_position(position);
	current->entry=x;
    return success;
}


template <class List_entry>
Error_code List<List_entry>::remove(int position, List_entry &x)
{
   if (position < 0 || position > count-1)
      return range_error;
   Node<List_entry> *previous, *following;
   set_position(position);
   previous = current->back;
   following = current->next;
   if(previous!=NULL)previous->next = following;
   if(following!=NULL)following->back=previous;
   x=current->entry;
   delete current;
   if(previous==NULL){
	   current=following;
	   if(following==NULL)current_position=-1;
	   else current_position=0;
   }
   else{
	   current=previous;
	   current_position=position-1;
   }
   count--;
   return success;
}


template <class List_entry>
Error_code List<List_entry>::insert(int position, const List_entry &x)
/*
Post: If the List is not full and 0 <= position <= n,
      where n is the number of entries in the List, the function succeeds:
      Any entry formerly at position and all later entries have their
      position numbers increased by 1 and x is inserted at position of the List.
      Else: the function fails with a diagnostic error code.
*/
{
   Node<List_entry> *new_node, *following, *preceding;
   if (position < 0 || position > count) return range_error;
   if (position == 0) {
      if (count == 0) following = NULL;
      else {
         set_position(0);
         following = current;
      }
      preceding = NULL;
   }
   else {
      set_position(position - 1);
      preceding = current;
      following = preceding->next;
   }
   new_node = new Node<List_entry>(x, preceding, following);

   if (new_node == NULL) return overflow;
   if (preceding != NULL) preceding->next = new_node;
   if (following != NULL) following->back = new_node;
   current = new_node;
   current_position = position;
   count++;
   return success;
}


template <class List_entry>
List<List_entry>::List(const List<List_entry> &copy)
{
   count=copy.count;
   Node<List_entry> *new_copy, *original_node;
   if(count>0){
	   copy.set_position(0);
	   original_node=copy.current;      
	   current_position = 0;
	   //  Duplicate the linked nodes.
	   current = new_copy = new Node<List_entry>(original_node->entry);
	   while (original_node->next != NULL) {
		   original_node = original_node->next;
		   new_copy->next = new Node<List_entry>(original_node->entry,new_copy,NULL);
		   new_copy = new_copy->next;
	   }
	   set_position(copy.current_position); 
   }
}


template <class List_entry>
void List<List_entry>::operator =(const List<List_entry> &copy)
{
   clear();
   count=copy.count;
   Node<List_entry> *new_copy, *original_node;
   if(count>0){
	   copy.set_position(0);
	   original_node=copy.current;      
	   current_position = 0;
	   //  Duplicate the linked nodes.
	   current = new_copy = new Node<List_entry>(original_node->entry);
	   while (original_node->next != NULL) {
		   original_node = original_node->next;
		   new_copy->next = new Node<List_entry>(original_node->entry,new_copy,NULL);
		   new_copy = new_copy->next;
	   }
	   set_position(copy.current_position); 
   }
}


template <class List_entry>
void List<List_entry>::set_position(int position) const
/*
Pre:  position is a valid position in the List: 0 <= position < count.
Post: The current Node pointer references the Node at position.
*/
{
   if (current_position <= position)
      for ( ; current_position != position; current_position++)
         current = current->next;
   else
      for ( ; current_position != position; current_position--)
         current = current->back;
}