p1.c

主要是avl,splay和binary树的insert,delete程序,主要是avl,splay.binary树的

				break;
			else if(Item < T->Left->Num) 
				T=ZigZigLeft(T);
			if(T->Left == NULL)
				break;
			/* Link right */
			RightTreeMin->Left=T;
			RightTreeMin=T;
			T=T->Left;
		}
		else  /* move the elements smaller than Item to a left-tree */
		{
			if(T->Right==NULL)
				break;
			if(Item > T->Right->Num)
				T=ZigZigRight(T);
			if(T->Right == NULL)
				break;
			/* Link Left */
			LeftTreeMax->Right=T;
			LeftTreeMax=T;
			T=T->Right;
		}
	}/* While Item != T->Num */	
	
	/* Reassemble */
	LeftTreeMax->Right=T->Left;
	RightTreeMin->Left=T->Right;
	T->Left=Header.Right;  /* make the left-tree and right-tree be the left and right sub-tree of the new tree */
	T->Right=Header.Left;

	return T;
}

SplayTree SplayInsert( int number, SplayTree T ) 
{ 
	static SplayPosition NewNode = NULL;

	if(NewNode == NULL)
	{
		NewNode  = malloc(sizeof(struct SplayNode));
		if(NewNode == NULL)
			printf("Out Of Space");
	}

	NewNode->Num = number;
	if( T== NULL ) /* when the tree has no element, just let it equal to the NewNode */
	{
		NewNode->Left=NewNode->Right=NULL;
		T= NewNode;
	}
	else
	{
		T=Splay(number, T);  /* do splay to find the position of the element you want to insert */
		if(number < T->Num) /* make the NewNode the root of the new tree, and the left as well as right sub-tree 
							of the old one be its children */
		{
			NewNode->Left=T->Left;
			T->Left=NULL;
			NewNode->Right=T;
			T=NewNode;
		}
		else
		if(number>T->Num)
		{
			NewNode->Right=T->Right;
			T->Right=NULL;
			NewNode->Left=T;
			T=NewNode;
		}	
	   /* Else number is in the tree already; we'll do nothing */ 
	}
	NewNode = NULL;
	return  T;   
}

SplayTree  SplayDelete( int number, SplayTree T ) 
{
	SplayPosition  TmpCell; 
	if ( T == NULL )   /* the tree has no element */
	{
		printf( "Element not found\n" ); 
	}
	if(T != NULL)
	{
		T = Splay( number, T);  /* do splay to move the element you want to delete to the root of the tree */
		if(T->Num==number)  /* if the element is in the tree, just delete it */
		{
			if(T->Left==NULL)
				TmpCell=T->Right;
			else
			{
				TmpCell=T->Left;
				TmpCell=Splay(number,TmpCell);  /* move the largest element in the left sub-tree to be the new root */
				TmpCell->Right = T->Right;
			}
			free(T);
			T=TmpCell;
		}
	}
	return  T; 
}

void srand(  
   unsigned int seed 
);

void swap(int *array, int num1, int num2)  /* swap the elements of a Array at positions num1 and num2 */
{
	int temp;
	temp = array[num1];
	array[num1] = array[num2];
	array[num2] = temp;
}


void main()
{
	int size;
	int choice;
	int temp1, temp2;
	int i;
	int *Array;
	SearchTree T1 = NULL;
	AvlTree T2 = NULL;
	SplayTree T3 = NULL;
L2:	printf("Please choose the case you want to test\n");
	printf("1.Insert N integers in increasing order and delete them in the same order\n");
	printf("2.Insert N integers in increasing order and delete them in the reverse order\n");
	printf("3.Insert N integers in random order and delete them in random order\n");
	printf("4.exit\n");
	scanf("%d", &choice);
	if(choice == 1)
	{
		printf("Performance on Binary Search Tree\n");
		for(size = 1000; size <=10000; size += 1000)  /* test code */
		{	start = clock();
			for(i = 1; i <= size; i++)
			 T1 = Insert(i, T1);		
			for(i = 1; i <= size; i++)
				T1 = Delete(i, T1);
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK; 
			printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		printf("/*****************************************************/\n\n");
		/****************************************/
		printf("Performance on AVLTree\n");
		for(size = 1000; size <=10000; size += 1000)  /* test code */
		{
			start = clock();
			for(i = 1; i <= size; i++)
			    T2 = AvlInsert(i, T2);
			for(i = 1; i <= size; i++)
				T2 = AvlDelete(i, T2);
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK; 
			printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		printf("/*****************************************************/\n\n");
		/*****************************************/
		printf("Performance on SplayTree\n");
		for(size = 1000; size <=10000; size += 1000)  /* test code */
		{
			start = clock();
			for(i = 1; i <= size; i++)
			    T3 = SplayInsert(i, T3);
			for(i = 1; i <= size; i++)
				T3 = SplayDelete(i, T3);
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK; 
			printf("Finished, size = %d\nThe Running Time is %f\n\n", size, duration);
		}
		printf("/*****************************************************/\n\n");
		goto L2;
	}
	else if(choice == 2)
	{
		printf("Performance on Binary Search Tree\n");
		for(size = 1000; size <=10000; size += 1000)  /* test code */
		{
			start = clock();
			for(i = 1; i <= size; i++)
		       T1 = Insert(i, T1);		
			for(i = size; i > 0; i--)
				T1 = Delete(i, T1);
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK; 
			printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		printf("/*****************************************************/\n\n");
		/*********************************************/
		printf("Performance on AVLTree\n");
		for(size = 1000; size <=10000; size += 1000)  /* test code */
		{
			start = clock();
			for(i = 1; i <= size; i++)
			    T2 = AvlInsert(i, T2);
			for(i = size; i > 0; i--)
				T2 = AvlDelete(i, T2);
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK; 
			printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		printf("/*****************************************************/\n\n");
		/**********************************************/
		printf("Performance on SplayTree\n");
		for(size = 1000; size <=10000; size += 1000)  /* test code */
		{
		start = clock();
		for(i = 1; i <= size; i++)
            T3 = SplayInsert(i, T3);		
		for(i = size; i > 0; i--)
			T3 = SplayDelete(i, T3);
		stop = clock();
		duration = ((double)(stop - start))/CLK_TCK; 
		printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		printf("/*****************************************************/\n\n");
		goto L2;
	}
	else if(choice == 3)
	{
		printf("Performance on Binary Search Tree");
		srand((unsigned)time(NULL));
		for(size = 1000; size <=10000; size += 1000) /* test code */
		{
			Array = malloc(sizeof(int) * size);
			for(i = 0; i < size; i++)
				Array[i] = i + 1;
			start = clock();
			temp2 = size;
			for(i = 1; i <= size; i++)	/*to use the array to make a series of random numbers*/	
			{	
				temp1 = rand() % temp2;	/* make a random number */
				T1 = Insert(Array[temp1], T1);
				swap(Array, temp1, --temp2);	/*swap the number and reduce the large of the numbers  */
			}
			temp2 = size;	/* initialize the tmp2 */
			for(i = 1; i <= size; i++)
			{
				temp1 = rand() % temp2;
				T1 = Delete(Array[temp1], T1);
				swap(Array, temp1, --temp2);
			}
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK;
			printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		free(Array);
		printf("/*****************************************************/\n\n");
		/******************************************************/
		printf("Performance on AVLTree");
		for(size = 1000; size <=10000; size += 1000) /* test code */
		{
			Array = malloc(sizeof(int) * size);
			for(i = 0; i < size; i++)
				Array[i] = i + 1;
			start = clock();
			temp2 = size;
			for(i = 1; i <= size; i++)
			{
				temp1 = rand() % temp2;
				T2 = AvlInsert(Array[temp1], T2);			
				swap(Array, temp1, --temp2);
			}
			printf("\n");
			temp2 = size;
			for(i = 1; i <= size; i++)
			{
				temp1 = rand() % temp2;
				T2 = AvlDelete(Array[temp1], T2);
				swap(Array, temp1, --temp2);
			}
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK;
			printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		free(Array);
		printf("/*****************************************************/\n\n");
		/******************************************************/
		printf("Performance on SplayTree");
		srand((unsigned)time(NULL));
		for(size = 1000; size <=10000; size += 1000)  /* test code */
		{
			Array = malloc(sizeof(int) * size);
			for(i = 0; i < size; i++)
				Array[i] = i + 1;
			start = clock();
			temp2 = size;
			for(i = 1; i <= size; i++)
			{
				temp1 = rand() % temp2;
				T3 = SplayInsert(Array[temp1], T3);
				swap(Array, temp1, --temp2);
			}
			temp2 = size;
			for(i = 1; i <= size; i++)
			{
				temp1 = rand() % temp2;
				T3 = SplayDelete(temp1, T3);
				swap(Array, temp1, --temp2);
			}
			stop = clock();
			duration = ((double)(stop - start))/CLK_TCK;
			printf("Finished, size = %d\nThe Running Time is %.6lf\n\n", size, duration);
		}
		free(Array);
		printf("/*****************************************************/\n\n");
		goto L2;
	}
	else if (choice == 4)
	{
	printf("EXIT THE PROGRAME\n\n\n");
	}	
	else						/*the wrong number*/
	{
		printf("Bad Commend! Try Again!\n");
		goto L2;
	}
}