linked_list.h

链表和应用包括单链表和双链表等等。自己写的

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "utility.h"

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

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

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


template <class List_entry>
class List {
	public:
    // Specifications for the methods of the list ADT go here

		List();
		int size() const;
		bool full() 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 remove(int postion);
		Error_code insert(int position, const List_entry &x);

		// The following methods replace compiler-generated defaults.
        ~List();
		List(const List<List_entry> &copy);
		void operator = (const List<List_entry> &copy);

	protected:
		//data members for a contiguous list implementation
		int count;
        Node<List_entry> *head;
		//The following auxiliary function is used to locate list positions
		Node<List_entry> *set_position(int position) const;

}; 

template <class List_entry>
List<List_entry>::List() 
/*Post: The List has been created and is initialized to be empty.*/
{
	count = 0;
	head = NULL;
}
template <class List_entry>
List<List_entry>:: ~List()
{
	clear();

}

template <class List_entry>

List<List_entry>::List(const List<List_entry> &copy)
{
	Node<List_entry> *new_copy,*original_node = copy.head;
	if(original_node == NULL) head = NULL;
	else
	{
		head = new_copy = new Node(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 = new_copy->next;
		}
	}

}


template <class List_entry>
void List<List_entry>:: operator = (const List<List_entry> &copy)
{
	Node<List_entry> *new_head,*new_copy, *original_node = copy.head;
	if (original_node == NULL) new_head = NULL;
	else
	{
		new_copy = new_head = new Node<>(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=new_copy->next;
		}
        
	}
	clear();
	head = new_head;

}


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>
bool List<List_entry>::empty() const
/*Post: The function return true or false according to whether the List
        is empty or not.*/
{
	bool outcome = false;
	if(count == 0) outcome = true;
	return outcome;
}


template <class List_entry> 
void List<List_entry>::clear()
/*Post: ALl List entries have been removed; the List is empty.*/
{   
        for(int i=0;i<count;i++)
		       remove(i);

}



template <class List_entry>
Node<List_entry> *List<List_entry>::set_position(int position) const
/*Pre: position is a valid position in the List; 0<=position<count.
  Post: Return a pointer to the Node in position.*/
{
	Node<List_entry> *q =head;
	for(int i=0;i<position;i++) q=q->next;
	return q;
}

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.*/
{
	if(position<0 || position>count)
		return underflow;	
	Node<List_entry> *new_node, *previous, *following;
	if (position>0){
		previous = set_position(position-1);
		following = previous->next;
	}
	else following = head;
	new_node = new Node<List_entry> (x, following);
	if(new_node == NULL)
		return overflow;
	if(position == 0)
		head = new_node;
	else
		previous->next=new_node;
	count++;
	return success;
}

template <class List_entry>
Error_code List<List_entry>::remove(int position, List_entry &x)
/*Post: If 0<=Position<n, where n is the number of entriesin the List,
        The function succeeds: The entry at position is removed from the
		List, and all later entries have their position numbers decreased
		by 1. The parameter x records a copy of the entry formerly at
		position.
		Else: The function with a diagnostic error code.*/

{
	if(empty())
		return underflow;
	if(position<0 ||position>=count)
		return range_error;	
      Node<List_entry>  *previous, *following ,*old_node;
	if (position == 0){
		following = set_position(position+1);

		head = following;
		x = old_node->entry;
		delete old_node;
	}
	else if(position == count-1) {
		x = old_node->entry;
		delete old_node;
	}
	else{
        previous = set_position(position-1);
        old_node =set_position(position);
		following = set_position(position+1);
       previous->next = following;
	   x = old_node->entry;
	   delete old_node;
	}


	count--;
	return success;

}


template <class List_entry>
Error_code List<List_entry>::remove(int position)
/*Post: If 0<=Position<n, where n is the number of entriesin the List,
        The function succeeds: The entry at position is removed from the
		List, and all later entries have their position numbers decreased
		by 1. 
		Else: The function with a diagnostic error code.*/

{
	if(empty())
		return underflow;
	if(position<0 ||position>=count)
		return range_error;	
      Node<List_entry>  *previous, *following ,*old_node;
	if (position == 0){
		following = set_position(position+1);

		head = following;
		delete old_node;
	}
	else if(position == count-1) {

		delete old_node;
	}
	else{
        previous = set_position(position-1);
        old_node =set_position(position);
		following = set_position(position+1);
       previous->next = following;

	   delete old_node;
	}


	count--;
	return success;

}




template <class List_entry>
Error_code List<List_entry>::replace(int position, const List_entry &x)
/*Post: If 0<=position<n, where n is the number of entries in the List, the function
        succeeds; The entry at position is replaced by x; all other entries remain unchanged.
		Else: The function fails with diagnostic error code.*/
{
	if(position<0 ||position>=count)
		return range_error;
	else 
		set_position(position)->entry = x;
	return success;
}

template <class List_entry>
Error_code List<List_entry>::retrieve(int position, List_entry &x) const
/*Post: If 0<=Position<n, where n is the number of entries in the List, the function succeeds;
        The entry at position is copied to x; all List entries remain unchanged.
		Else: The function fails with a diagnostic error code.*/
{
	if(position<0 ||position>=count)
		return range_error;
	else 
		x=set_position(position)->entry;
	return success;
	
}

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.*/
{
	for(int i=0; i<count; i++)
		(*visit)(set_position(i)->entry);
	
}

#endif