list.h

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

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

const int max_list = 10;
template <class List_entry>
class List {
	public:
    //  methods of the List ADT
		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 insert(int position, List_entry &x);
	protected:
		//data members for a contiguous list implementation
		int count;
		List_entry entry[max_list];

}; 

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



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

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.*/
{
	count==0;
}

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;
	for(int i=position; i<count-1;i++)
		entry[i]=entry[i+1];
	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;
    entry[position]=x;
	return success;
}

template <class List_entry>
Error_code List<List_entry>::retrieve(int position, 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 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;
	     x = entry[position];
		 return success;
}

template <class List_entry>
Error_code List<List_entry>::insert(int position, List_entry &x)
/*Post: If the List is not full and 0<=Position<=n, where n is the number of
        entries on 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(full())
		return overflow;
	if(position<0 || position>count)
		return range_error;
	for(int i = count -1; i>=position; i--)
		entry[i+1] = entry[i];
	    entry[position] = x;
	count++;
	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)(entry[i]);

}


#endif