8_2.cpp

这是一个双向链表的问题

/*第2题	双向链表--源代码及关键源代码注解如下：*/
// Author : Vinayak Marwah 

#include <iostream.h>
#include <conio.h>
#include "Double Link List.h"

void main()
{
	DoubleLinkList< int > List;
	int Value = 0 ,Option = 0;
	do
	{
		cout<<"\n\t\t Driver To Test  Link List "
			<<"\n\t\t\t\t Menu ."
			<<"\n\t\t\t\t______ "
			<<"\n 1.) Insert At Front Of A Double Linked List . "
			<<"\n 2.) Insert At Rear Of A Double Linked List . "
			<<"\n 3.) Insert In Middle Of A Double Linked List . "
			<<"\n 4.) Remove From Front Of A Double Linked List. "
			<<"\n 5.) Remove From Rear Of A Double Linked List. "
			<<"\n 6.) Remove From Middle Of The Double Linked List . "
			<<"\n 7.) Traverse Forward A Double Linked List ."
			<<"\n 8.) Traverse Backwards A Double Linked List . "
			<<"\n 9.) Lenght Of The Double Linked List ."
			<<"\n 10.) End Double Linked List Processing & Exit . "
			<<"\n     Enter Your Choice : \t";
		cin>>Option;
		switch(Option)
			{
			case 1 :
				{
					cout<<"\n Enter Data : ";
					cin>>Value;
					List.InsertAtFront(Value);
					break;
				}
			case 2 :
				{
					cout<<"\n Enter Data : ";
					cin>>Value;
					List.InsertAtRear(Value);
					break;
				}
			case 3:
				{
					cout<<"\n Enter Data : ";
					cin>>Value;
					List.InsertAtMiddle(Value);
					break;
				}
			case 4 :
				{
					List.RemoveFromFront();
					break;
				}
			case 5 :
				{
					List.RemoveFromRear();
					break;
				}
			case 6:
				{
					List.RemoveFromMiddle();
					break;
				}

			case 7 :
				{
					List.TraverseForward();
					break;
				}
			case 8 :
				{
					List.TraverseBackwards();
					break;
				}
			case 9 :
				{
					cout<<"\n The Lenght Of A Double Linked List "
						<<"\n (ie Number Of Nodes In A Double Linked List ) : "
						<<List.LenghtOfDoubleLinkList();
					break;
				}
			case 10 :
				{
					break;
				}
			default :
				{
					Option = 10;
					break;
				}
			}
		}
	while( Option != 10 );
}

#include <iostream.h>
#include <conio.h>
#include <assert.h>
#include "Double Link List.H"
template< class NodeType >
Node< NodeType >::Node()
:Data( NULL ),NextNode( NULL ),PreviousNode( NULL ) {}
/**********************************************************************/
template< class NodeType >
Node< NodeType >::Node( NodeType &Value )
:Data( Value ),NextNode( NULL ),PreviousNode( NULL ) 
{
	cout<<"\n A Node Created Successfully . ";
}
/**********************************************************************/
template< class NodeType >
Node< NodeType >::~Node()
{
	cout<<"\n A Node Destroyed Successfully .";
}
/**********************************************************************/
template< class NodeType >
DoubleLinkList< NodeType >::DoubleLinkList()
:FirstNode( NULL ),RearNode( NULL )
{
	cout<<"\n A Double Linked List Created Successfully .";
}

/**********************************************************************/

template< class NodeType >
DoubleLinkList< NodeType >::~DoubleLinkList()
{
	cout<<"\n Mission : Destroy A Double Linked List . \n";
	Node< NodeType > *CurrentNode = FirstNode, *TempNode ;
	while( CurrentNode != NULL )
		{
		TempNode = CurrentNode;
		CurrentNode = CurrentNode->NextNode;
		cout<<TempNode->Data<<" , ";
		delete TempNode;
		}
	cout<<"\n Status : Mission Successfull . "
		<<"\n A Double Linked List Destroyed Successfully ."
		<<"\n Press Any Key To Continue ";
	getch();
}
/**********************************************************************/
template< class NodeType >
bool DoubleLinkList< NodeType >::IsEmpty()
{
	if( FirstNode == NULL )
		{
		cout<<"\n No Double Linked List Exists . ";
		return true;
		}
	else
		return false;
}
/**********************************************************************/
template< class NodeType >
Node< NodeType > *DoubleLinkList< NodeType >::CreateNode( NodeType &Value )
{
	Node< NodeType > *NewNode = new Node< NodeType >( Value );
	assert( NewNode != NULL );
	return NewNode ;
}
/**********************************************************************/
template< class NodeType >
void DoubleLinkList< NodeType >::InsertAtFront( NodeType &Value )
{
	cout<<"\n Mission : Insertion Of A Node At The Front Of The Linked List .\n";
	Node< NodeType > *NewNode = CreateNode(Value);
	if ( IsEmpty() )
		{
		cout<<"\n Mission : Generating A New Double Link List . ";
		FirstNode = RearNode = NewNode ;
		}
	else
		{
		FirstNode->PreviousNode = NewNode;
		NewNode->NextNode = FirstNode;
		FirstNode = NewNode;
		FirstNode->PreviousNode = NULL;
		}
	cout<<FirstNode->Data;
	cout<<"\n Status : Mission SuccessFull ."
		<<"\n Node Inserted At Front SuccessFully . "
		<<"\n Press Any Key To Continue . ";
	getch();
}
/**********************************************************************/
template< class NodeType >
void DoubleLinkList< NodeType >::InsertAtMiddle( NodeType &Value )
{
	cout<<"\n Operation : Insertion Of A Node In The Middle Of The Linked List .\n";
	Node< NodeType > *NewNode = CreateNode(Value);
	if ( IsEmpty() )
		{
		cout<<"\n Mission : Generating A New Double Link List . ";
		FirstNode = RearNode = NewNode ;
		}
	else
		{
		Node< NodeType > *CurrentNode = FirstNode,*TempNode;
		int Middle = (LenghtOfDoubleLinkList()/2),Position = 0;
		while( Position != Middle )
			{
			CurrentNode = CurrentNode->NextNode;
			Position++;
			}
		TempNode = CurrentNode;
		NewNode->PreviousNode = CurrentNode->PreviousNode;
		NewNode->NextNode = CurrentNode;
		CurrentNode = CurrentNode->PreviousNode;
		CurrentNode->NextNode = NewNode ;
		TempNode->PreviousNode = NewNode;
		}
	cout<<NewNode->Data;
	cout<<"\n Status : Mission SuccessFull ."
		<<"\n Node Inserted In Middle SuccessFully . "
		<<"\n Press Any Key To Continue . ";
	getch();
}
/**********************************************************************/
template< class NodeType >
void DoubleLinkList< NodeType >::InsertAtRear( NodeType &Value )
{
	cout<<"\n Operation : Insertion Of A Node At The End Of The Linked List .\n";
	Node< NodeType > *NewNode = CreateNode(Value);
	if ( IsEmpty() )
		{
		cout<<"\n Mission : Generating A New Double Link List . ";
		FirstNode = RearNode = NewNode ;
		}
	else
		{
		NewNode->PreviousNode = RearNode;
		RearNode->NextNode = NewNode;
		RearNode = NewNode;
		RearNode->NextNode = NULL;
		}
	cout<<RearNode->Data;
	cout<<"\n Status : Mission SuccessFull ."
		<<"\n Node Inserted At Rear SuccessFully . "
		<<"\n Press Any Key To Continue . ";
	getch();
}
/**********************************************************************/
template< class NodeType >
bool DoubleLinkList< NodeType >::RemoveFromFront()
{
	cout<<"\n Operation : Removal Of A Node From Front Of A Double Linked List .\n";
	if( IsEmpty() )
		{
		cout<<"\n Invalid Operation ."
			<<"\n Status : Mission Failed . "
			<<"\n Press Any Key To Continue . ";
		getch();
		return false;
		}
	else
		{
		Node< NodeType > *CurrentNode = FirstNode;
		if( FirstNode == RearNode )
			FirstNode = RearNode = NULL;
		else
			{
			cout<<"\n Data In The First Node Is : ";
			cout<<CurrentNode->Data;
			FirstNode = FirstNode->NextNode;
			FirstNode->PreviousNode = NULL ;
			}
		delete CurrentNode;
		cout<<"\n Status : Mission SuccessFull ."
			<<"\n Node Removed From Front Of The Doubled Linked List Successfully ";
		return true;
		}
		cout<<"\n Press Any Key To Continue . ";
		getch();
}
/**********************************************************************/
template< class NodeType >
bool DoubleLinkList< NodeType >::RemoveFromMiddle()
{
	cout<<"\n Operation : Insertion Of A Node In The Middle Of The Linked List .\n";
	if( IsEmpty() )
		{
		cout<<"\n Invalid Operation ."
			<<"\n Status : Mission Failed . "
			<<"\n Press Any Key To Continue . ";
		getch();

		return false;
		}
	else
		{
		Node< NodeType > *CurrentNode = FirstNode,*TempNode,*TEmpNode;
		int Middle = (LenghtOfDoubleLinkList()/2),Position = 0;
		while( Position != Middle )
			{
			CurrentNode = CurrentNode->NextNode;
			Position++;
			}
		TempNode = CurrentNode ;
		CurrentNode = CurrentNode->NextNode ;
		CurrentNode->PreviousNode = TempNode->PreviousNode ;
		TEmpNode = TempNode->PreviousNode ;
		TEmpNode->NextNode = CurrentNode ;
		cout<<TempNode->Data;
		delete TempNode;
		}
	cout<<"\n Status : Mission SuccessFull ."
		<<"\n Node Removed From Middle SuccessFully . "
		<<"\n Press Any Key To Continue . ";
	getch();
	return true;
}
/**********************************************************************/
template< class NodeType >
bool DoubleLinkList< NodeType >::RemoveFromRear()
{
	cout<<"\n Operation : Removal Of A Node From Rear Of A Double Linked List .\n";
	if( IsEmpty() )
		{
		cout<<"\n Invalid Operation ."
			<<"\n Status : Mission Failed . "
			<<"\n Press Any Key To Continue . ";
		getch();

		return false;
		}
	else
		{
		Node< NodeType > *TempNode = RearNode;
		if( FirstNode == RearNode )
			FirstNode = RearNode = NULL;
		else
			RearNode = RearNode->PreviousNode;
		RearNode->NextNode = NULL;
		cout<<TempNode->Data;
		delete TempNode;
		cout<<"\n Status : Mission SuccessFull ."
			<<"\n Node Removed From Rear Of The Double Linked List Successfully  .";
		return true;
		}
		cout<<"\n Press Any Key To Continue . ";
		getch();
}
/**********************************************************************/
template< class NodeType >
void DoubleLinkList< NodeType >::TraverseForward()
{
	Node< NodeType > *CurrentNode = FirstNode ;
	cout<<"\n Mission : Traversing & Printing A Double Linked List ."
		<<"\n           In Forward Direction ."
		<<"\n The Double Linked List Follows : \n";
	while ( CurrentNode != NULL)
		{
		cout<<CurrentNode->Data<<" , ";
		CurrentNode = CurrentNode->NextNode;
		}
	cout<<"\n Status : Operation Successfull ."
		<<"\n Traversed & Printed Double Linked List Successfully . "
		<<"\n Press Any Key To Continue .";
	getch();
}
/**********************************************************************/
template< class NodeType >
void DoubleLinkList< NodeType >::TraverseBackwards()
{
	Node< NodeType > *CurrentNode = RearNode ;
	cout<<"\n Mission : Traversing & Printing A Double Linked List ."
		<<"\n           In Backward Direction "
		<<"\n The Double Linked List Follows : \n";
	while ( CurrentNode != NULL)
		{
		cout<<CurrentNode->Data<<" , ";
		CurrentNode = CurrentNode->PreviousNode;
		}
	cout<<"\n Status : Operation Successfull ."
		<<"\n Traversed & Printed Double Linked List Successfully . "
		<<"\n Press Any Key To Continue .";
	getch();
}
/**********************************************************************/
template< class NodeType >
int DoubleLinkList< NodeType >::LenghtOfDoubleLinkList()
{
	int NosOfNodes = 0 ;
	Node< NodeType > *CurrentNode = FirstNode ;
cout<<"\n Mission : Traverse & Calculate The Number Of Nodes In A Double Linked List ."<<"\n The Double Linked List Follows : \n";
	while ( CurrentNode != NULL)
		{
		NosOfNodes++;
		CurrentNode = CurrentNode->NextNode;
		}
	cout<<"\n Status : Operation Successfull ."
<<"\n Traversed & Calculated Number Of Nodes In A Double Linked List Successfully . "<<"\n Press Any Key To Continue .";
	getch();
	return NosOfNodes;
}