d_list.cpp

简单的循环链表算法

// D_List.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"


#include<iostream.h>
enum Error_code {success,range_error};
typedef  List_entry, Node_entry;

//template<class Node_entry>
//class Node{
//	public:
//		List_entry entry;
//		index next;
//};
template<class Node_entry>
struct Node{
	Node_entry entry;
	Node<Node_entry> *next;
	Node<Node_entry> *back;
	Node();
	Node(Node_entry ,Node<Node_entry> *link_back=NULL,Node<Node_entry> *link_next=NULL);
};
Node::Node()
{
	next=NULL;
	back=NULL;
}
Node::Node(Node_entry ,Node<Node_entry> *link_back,Node<Node_entry> *link_next)
{
	next=link_next;
	back=link_back;
}
template<class List_entry>
class List{
	public:
		List();
		~List();
		List(const List<List_entry> &copy);
		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 insert(int position,const List_entry &x);
		Error_code remove(int position,List_entry &x)const;
		void operator = (const List<List_entry> &copy);
	protected:
		int count;
		Node<List_entry> *head;
		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()//set the head of the double link lists 
/*{
	count=0;
	current_position=0;
	current=head=NULL;
}*/
{
	head=new List<List_entry>;
	head->following=head->preceding=head;
	current=NULL;
}
template<class List_entry>
List<List_entry>::~List()
{
	while(!empty())
		clear();
}
template<class List_entry>
List<List_entry>::List(const List<List_entry> &copy)//copy constructor
{
	Node *new_copy,*copy_node=copy.current;
	if(copy_node==NULL)current=NULL;
	else{//Duplicate the linked nodes
		current=new_copy=new Node(copy_node->entry);
		while(copy_node->next!=NULL){
			copy_node=copy_node->next;
			new_copy->next=new Node(copy_node->entry);
			new_copy=new_copy->next;
		}
	}
}

template<class List_entry>
Error_code List<List_entry>::insert(int position,const List_entry &x)
{
	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>
void List<List_entry>::set_position(int position)const
{
	if(current_position<=position)
		for(;current_position!=position;current_position++)
			current=current->next;
		else
			for(;current_position!=position;current_position--)
				current=current->back;
}
template<class List_entry>
int List<List_entry>::size()const
{
	Node<List_entry> *following,*preceding;
	Node<List_entry> *p=head->following;
	int count=0;
	while(p!=head)
	{
		p=p->following;
		count++;
	}
	return count;
}
template<class List_entry>
bool List<List_entry>::empty()const
{
	bool outcome=true;
	if(count>0)outcome=false;
	return outcome;
}
template<class List_entry>
bool List<List_entry>::full()const
{
	bool outcome=true;
	if(set_position(count-1)!=NULL);
	else outcome=false;
	return outcome;
}
template<class List_entry>
void List<List_entry>::clear();
{ 
	set_position(0);
	new_head=head=current;
	while(!empty())
	{
		new_head=new_head->next;
		remove();
	}
}
template<class List_entry>
Error_code List<List_entry>::remove(int position,List_entry &x)const
{
	Node<List_entry> *following,*preceding;

	if(current!=NULL){
		Node<List_entry> *temp=current;
		current=current->following;
		current->preceding=temp->preceding;
		temp->preceding->following;
		delete temp;
		if(current==head)
			if(empty())current=NULL;
			else current=current->following;
	}
	return success;
}
template<class List_entry>
void List<List_entry>::operator = (const List<List_entry> &copy)
/*  Post: The front of the CircList retrieved to the output parameter
   item.If the CircList is empty return an Error_code of underflow.*/
{
	Node *new_head,*new_copy,*copy_node=copy.head;
	if(original_node==NULL)new_head=NULL;
	else{
		new_copy=new_current=new Node(copy_node->entry);
		while(copy_node->next!=NULL){
			copy_node=copy_node->next;
			new_copy->next=new Node(copy_node->entry);
			new_copy=new_copy->next;
		}
	} 
	while(!empty())    //Clean out old CircList entries
		clear();
	head=new_head;   //and replace them with new entries
}

template<class List_entry>
Error_code List<List_entry>::retrieve(int position,List_entry &x)const
{
	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);
			return range_err;
		}
	}
	else{
		set_position(position-1);
		x=current->next->entry;
		return success;
	}
}
template<class List_entry>
Error_code List<List_entry>::replace(int position,const List_entry &x)
{
	Node<List_entry> *following,*preceding;
	if(position<0||position>count)return range_error;
	if(position==0)
	{
		if(count==0)following=NULL;
		else{
			set_position(0);	
			current=x;
			following=current;
		}
		preceding=NULL;
	}
	else{
		set_position(position-1);
		current=x;
		preceding=current;
		following=preceding->next;
	}
	return success;
}
template <class List_entry>
void  List<List_entry>::traverse(void(*visit)(List_entry &))
{
	Node<List_entry>*visit=head;
	for(visit!=NULL)
	{
		visit=visit->next;
	}
}

int main()
{
	cout<<"Input the count of the number:"<<endl;
	return 0;
}