数据结构实现－广义表－广义表的简单实现.txt

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

/***********************************************************************************************************
** Program Name : Implementation of Generalized List
** Author       : Lu Jian Hua
** Time         : 2007-5-29
************************************************************************************************************/

#include <iostream>
using namespace std ;

class GLNode								// class of node in generalized lists
{
public:
	GLNode() : type(0), next(NULL) {}
	int type ;								// type of the node
	union 
	{
		char value ;						// value of the node
		GLNode *link ;
	} ;
	GLNode *next ;							// next node 
} ;

GLNode* Create_GLNode()
{
	GLNode *temp  = NULL ;					// notice: new a structor, but not only a null pointer

	cout << "Another node ? (Y/N)  " ;
	char c = 0 ;
	cin >> c ;	cout << endl ;
	if (c != 'n' && c != 'N')
	{
		temp = new GLNode() ;				// new a GLNode object

		cout << "Please select :" << endl << endl
			 << "1> An atom" << endl << endl
			 << "2> A GLNode link  " ;
		char select = 0 ;
		cin >> select ;	cout << endl ;

		if (select == '1')					// an atom
		{
			temp->type = 0 ;				// indicate the node is an atom
			cout << "Please enter the value : " ;
			cin  >> temp->value ;
			cout << endl ;

		}
		else								// a GLNode link
		{
			temp->type = 1 ;
			temp->link = Create_GLNode() ;
		}

		temp->next = Create_GLNode() ;		// continue the next node...
	}

	return temp ;
}


/***********************************************************************************************************
** Program Name   : Deepth_Of_GLNode
** Parameters     : GLNode *front		(the front pointer)
** Value Returned : int					(the deepth of the generalized list)
** Details        : get the deepth of a generalized list 
************************************************************************************************************/
int Deepth_Of_GLNode(const GLNode *front)	// compute the deepth of the Generalized List
{
	static int max_deepth = 0 ;

	int deepth = 0 ;

	while (front)
	{
			if (front->type == 0)			// if type=0, deepth = 0 
				deepth = 0 ;
			else if (front->type == 1 && front->link == NULL)	// if type=1 and the link is null, deepth=1
				deepth = 1 ;
			else
				deepth += Deepth_Of_GLNode(front->link) ;		// other conditions, the same disposal

			if (max_deepth < deepth)
				max_deepth = deepth ;

			front = front->next ;
	}

	return (1+max_deepth) ;
}


/***********************************************************************************************************
** Program Name   : GLNode_Printer
** Parameters     : GLNode *front		(the front pointer)
** Value Returned : void
** Details        : print all the nodes of the generalized list 
************************************************************************************************************/
void GLNode_Printer(const GLNode *front)
{
	const GLNode *recent = front ;

	cout << "{" ;
	while (recent)
	{
		if (recent->type == 0)
			cout << recent->value ;
		else if ( recent->type == 1 && recent->link == NULL)
			cout << "{}" ;
		else
			GLNode_Printer(recent->link) ;

		if (recent->next != NULL)
			cout << "," ;

		recent = recent->next ;
	}
	cout << "}" ;
}


int main()
{
	GLNode *front = Create_GLNode() ;
	GLNode_Printer(front) ;
	cout << "\n\nThe max deepth of the Generalized list is : " << Deepth_Of_GLNode(front) << endl << endl ;
	return 0 ;
}


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