数据结构实现－链表－单链表.txt

包括数据结构中的常见的排序

/********************************************************************************************
** Program Name : Correlative Operation Of Single Chain
** Anthor       : Lu jian Hua
** Time         : 2007-5-26
*********************************************************************************************/

#include <iostream>

using namespace std ;

const int DEL_NULL_LIST    = -1 ;
const int DEL_NO_SUCH_DATA = 0 ;
const int DEL_NORMAL       = 4 ;

class Node						// class Of Node					
{
public:
	int data ;					// data segment 
	Node *next ;				// pointer segment 
} ;

/********************************************************************************************
** Function Name : List_Builder
** Parameters    : void
** Return Value  : Node *(return the front node of the chain)
*********************************************************************************************/
Node* List_Builder()			// List_Builder
{
	Node *front  = NULL ;
	Node *recent = front ;
	char c = 0 ;

	while (true)
	{
		cout << "Another node?(Y/N) " ;
		cin  >> c ;
		
		if ( c != 'n' && c != 'N' )				
		{
			Node *temp = new Node() ;

			cout << "The value of the node : " ;
			cin  >> temp->data ;				
			temp->next = NULL ;					// initialize the NEXT of the new node NULL

			if (front == NULL)					// if front node, update front node first
				front = temp ;
			else
				recent->next = temp ;			// if not front node, added it to the chain directly

			recent = temp ;						// update recent
		}
		else
			break ;
	}

	return front ;
}


/********************************************************************************************
** Function Name : List_Printer
** Parameters    : Node *front	(the front node address of the chain to be realease)
** Return Value  : void
*********************************************************************************************/
void List_Printer(const Node *header)			// List_Printer
{
	const Node *recent = header ;

	while (recent)
	{
		cout << recent->data << " --> " ;
		recent = recent->next ;
		if (recent == NULL) 
			cout << "NULL" ;
	}

	cout << endl << endl ;
}

/********************************************************************************************
** Function Name : List_Cleaner
** Parameters    : Node *front	(the front node address of the chain to be realease)
** Return Value  : Node *	(return the front node of the chain)
*********************************************************************************************/
void List_Cleaner(Node** front)					// release all the space that nodes occupancy
{						
	Node *record = NULL ;						// record the next node of the node to be released
	
	while (*front)
	{
		record = (*front)->next ;
		delete (*front) ;						// release the front node
		(*front) = record ;						//  update the front node
	}

	cout << "\nCleaner has done its work..." << endl << endl ;
}

/********************************************************************************************
** Function Name : Get_Node_Count
** Parameters    : Node *front	(ponter to the front node address of the chain to be realease)
** Return Value  : int		(return the count of nodes of the chain)
*********************************************************************************************/
int Get_Node_Count( Node** header)
{
	Node *recent = *header ;
	int count = 0 ;

	while (recent)
	{
		++count ;
		recent = recent->next ;
	}

	return count ;
}

/********************************************************************************************
** Function Name : Get_Certain_Node
** Parameters    : Node *front	(the front node address of the chain to be realease)
** Return Value  : Node *	(return the certain node of the chain)
*********************************************************************************************/
Node* Get_Certain_Node(Node **front, int no)		// get the ceration node of a chain Eg:1,2,3,4,5...n
{
	if ( no < 0 || no > Get_Node_Count(front) )		// check for security
		return NULL ;

	Node *recent = (*front) ;
	int count = 0 ;									

	while (recent)
	{
		++count ;
		if (count == no)
			return recent ;

		recent = recent->next ;
	}

	return NULL ;									
}

/********************************************************************************************
** Function Name : List_Converter
** Parameters    : Node *front	(the front node address of the chain to be realease)
** Return Value  : void
*********************************************************************************************/
void List_Converter(Node **header)					// inverse a chain
{
	Node *prev = NULL ;								// previous node
	Node *recent = (*header) ;						// current  node

	while (recent)
	{
		Node *NEXT = recent->next ;					// record the next node first

		recent->next = prev ;						// deal with the current node

		if (NEXT == NULL)							// if the current node is the last node, stop and return
		{
			(*header) = recent ;					// make last node front node 
			break ;									// break
		}
													// prepare for the next disposal
		prev = recent ;								// next previous node = current node
		recent = NEXT ;								// current node = the record node(has been backed up)
	}
}

/********************************************************************************************
** Function Name : Del_Node
** Parameters    : Node *front	(the front node address of the chain to be realease)
	           int del_data (for query the certain node)
** Return Value  : NO_SUCH_DATA (no data founded!)
		   DEL_NOMAL	(delete normally)
*********************************************************************************************/
int Del_Node(Node **front, int del_data)			// delelte a node from the chain
{
	bool deleted = false ;							// tag: indicate some nodes has been deleted?

	Node *HEADER = new Node() ;						// if no HEADER exists, a HEADER will be added
	HEADER->next = (*front) ;						

	Node *prev = HEADER ;							// previous node of the current node

	while (prev->next)								// recent->the last priv->previous of the last
	{
		Node *recent = prev->next ;

		if (recent->data == del_data)				
		{
			if (recent == (*front))					// if front is the node to be delete
			{
				Node *link = (*front)->next ;		
				delete (*front) ;					// 1> delete
				(*front) = link ;					// 2> repoint the front node
				deleted = true ;					

				HEADER->next = (*front) ;			// repoint HEADER
				prev = HEADER ;						// repoint prev

				continue ;							// continue searching...
			}
			else									// middle node and tail node have the same disposal
			{
				Node *link = recent->next ;			
				delete recent ;						// 1> delete
				prev->next = link ;					// 2> reconnect
				deleted = true ;
							
				continue ;							// continue searching...
			}
		}

		prev = prev->next ;
	}

	if (deleted)	
		return DEL_NORMAL ;
	else
	{
		cout << "-------- No Such Data Found ! -----------" << endl << endl ;
		return  DEL_NO_SUCH_DATA ;
	}

}


int main()
{
	int select = 0 ;
	
	Node *front = List_Builder() ;				// build a chain

	while (true) 
	{
		cout << "Please select : " << endl << endl
			 << "              1> Print the list" << endl << endl
			 << "              2> Convert the list" << endl << endl
			 << "              3> Delete nodes of list" ;
		cin >> select ;
		cout << endl ;
		
		switch (select)
		{
		case 1:
			List_Printer(front) ;			break ;
		case 2:
			List_Converter(&front) ;			
			List_Printer(front) ;			break ;
		case 3:
			while (true)
			{
				char c = 0 ;
				cout << "Delete Again ? (Y/N) " ;
				cin >> c ;
				cout << endl ;
				
				if (c == 'n' || c == 'N')
					break ;
				else
				{
					int value = 0 ;
					cout << "Delete Value ? " ;
					cin >> value ;
					cout << endl ;
					Del_Node(&front, value) ;
					List_Printer(front) ;
				}
			}
			break ;
		}
	}
	
	return 0 ;
}





/********************************************************************************
*
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/