데이터 구조 - 순서 표 와 단일 체인 표 의 실현

////////////////////////////////////////////////////////////
//
//           ，  ，  ，  ，  ，     
//
////////////////////////////////////////////////////////////
//////////////

#include 
#include 
#include 

typedef  int        ElemType ;
#define  MAXSIZE    100
#define  INCREMENT  100

typedef struct SeqList
{
	ElemType * head ;  //       
	int length ; //   
	int size ;   //     
} SeqList ;

//    
void InitSeqList( SeqList * S )
{
	S->head = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE) ;
	if( S->head == NULL )
	{
		printf("             !
") ;
		exit(0) ;
	}
	S->length = 0 ;
	S->size = MAXSIZE ;
}

//   
//       ，        ;       -1
int Find( SeqList * S , ElemType elem )
{
	int i = 0 ;
	for( ; i < S->length ; i++ )
	{
		if( S->head[i] == elem )
		{
			return i ;
		}
	}
	return -1 ;
}

//   
//                
void Insert( SeqList * S , int pos , ElemType elem )
{
	if( S->length + 1 == S->size )   //            
	{
		ElemType * top = (ElemType*)realloc( S->head , MAXSIZE + INCREMENT ) ;
		if( !top )
		{
			printf("      !
") ;
			exit(0) ;
		}
		S->head = top ;
		S->size = S->length + INCREMENT ;
	}

	if( pos > S->length  || pos < 0 )  //            
	{
		printf("        !
") ;
		exit(0) ;
	}

	int  i = S->length - 1 ;
	for( ; i >= pos ; i-- )
	{
		S->head[i+1] = S->head[i] ;
	}
	S->head[pos] = elem ;
	S->length ++ ;
}

//  
//              
void Delete( SeqList * S , ElemType elem )
{
	int pos = Find( S , elem ) ;
	int i = 0 ;
	for( i = pos ; i < S->length ; i++ )
	{
		S->head[i] = S->head[i+1] ;
	}
	S->length -- ;
}

//  
void Swap( ElemType * e1 , ElemType * e2 )
{
	ElemType tmp ;
	tmp = *e1 ;
	*e1 = *e2 ;
	*e2 = tmp ;
}

//   
//          
void Reverse( SeqList * S )
{
	int i = 0 ;
	for( ; i < S->length / 2 ; i++ )
	{
		Swap( &S->head[i] , &S->head[S->length-1-i] ) ;
	}
}

//     
//     
void Sort( SeqList * S )
{
	int i = 0 ;
	int j = 0 ;
	for( ; i < S->length - 1 ; i++ )
	{
		for( j = i + 1 ; j < S->length ; j++ )
		{
			if( S->head[i] > S->head[j] )
			{
				Swap( &S->head[i] , &S->head[j] ) ;
			}
		}
	}
}


//        
//             

void Union( SeqList * S1 , SeqList * S2 , SeqList * S3 )
{
	if( S3->size < S1->length + S2->length )
	{
		printf("     ，              !
") ;
		exit(0) ;
	}

	Sort( S1 ) ;
	Sort( S2 ) ;

	int i = 0 ; 
	int j = 0 ;
	int k = 0 ;

	while( i < S1->length && j < S2->length )
	{
		if( S1->head[i] < S2->head[j] )
		{
			S3->head[k++] = S1->head[i++] ;
		}
	    else if( S1->head[i] > S2->head[j] )
		{
			S3->head[k++] = S2->head[j++] ;
		}
		else
		{
			S3->head[k++] = S1->head[i] ;
			S3->head[k++] = S2->head[j] ;
			i++ ;
			j++ ;
		}
	}

	if( i > S1->length - 1 )
	{
		while( j < S2->length )
		{
			S3->head[k++] = S2->head[i++] ;
		}
	}

	if( j > S2->length - 1 )
	{
		while( i < S1->length )
		{
			S3->head[k++] = S1->head[i++] ;
		}
	}
	S3->length = k ;
}

//          
void Print( SeqList * S )
{
	int i = 0 ; 
	for( ; i < S->length ; i++ )
	{
		printf("%d " , S->head[i] ) ;
	}
	printf("
") ;
}

//     
int main()
{
	SeqList S1 , S2 , S3 ;

	InitSeqList( &S1 ) ;
	InitSeqList( &S2 ) ;
	InitSeqList( &S3 ) ;

	Insert( &S1 , 0 , 1 ) ;
	Insert( &S1 , 1 , 5 ) ;
	Insert( &S1 , 2 , 2 ) ;

	Insert( &S2 , 0 , 2 ) ;
	Insert( &S2 , 1 , 4 ) ;
	Insert( &S2 , 2 , 3 ) ;

	printf("S1:") ;
	Print( &S1 ) ;

	printf("S2:") ;
	Print( &S2 ) ;

	Union( &S1 , &S2 , &S3 ) ;

	printf( "S3:" ) ;
	Print( &S3 ) ;

	return 0 ;
}

#include 
#include 
#include 

typedef int ElemType ;

typedef struct Node 
{
	ElemType elem ;
	struct Node * next ;
}Node ;

typedef struct LinkList
{
	Node *head ;  //    
	int length ;  //     
} LinkList ;

void InitLinkList( LinkList * L )
{
	L->head = (Node*)malloc(sizeof(Node)) ;
	if( !L->head )
	{
		printf("      !
") ;
		exit(0) ;
	}

	L->head->next = NULL ;
	L->length = 0 ;
}

//           
bool Find( LinkList * L , Node node )
{
	Node * p = L->head ;

	while( ( p = p->next ) != NULL )
	{
		if( p->elem == node.elem )
		{
			return true ;
		}
	}
	return false ;
}

//        
void Insert( LinkList * L , ElemType elem ) 
{
	Node * node = (Node*)malloc(sizeof(Node)) ;
	if( !node )
	{
		printf("      !
") ;
		exit(0) ;
	}
	node->elem = elem ;
	node->next = NULL ;

	Node * p = L->head ;
	while( p->next != NULL )
	{
		p = p->next ;
	}
	p->next = node ;
	L->length++ ;
}

//     
bool Delete( LinkList * L , ElemType elem )
{
	Node * p = L->head ;
	Node * q = p ;

	while( p->next != NULL )
	{
		q = p ;
		p = p->next ;
		if( p->elem == elem )
		{
			q->next = p->next ;
			free( p ) ;
			L->length-- ;
			return true ;
		}
	}
	return false ;
}


void Print( LinkList * L )
{
	Node * p = L->head ;

	while( p->next != NULL )
	{
		p = p->next ;
		printf("%d " , p->elem ) ;
	}
	printf("
") ;
}

int main()
{
	LinkList L ;
	InitLinkList( &L ) ;

	Insert( &L , 5 ) ;
	Insert( &L , 4 ) ;
	Insert( &L , 8 ) ;
	Insert( &L , 2 ) ;

	Print( &L ) ;

	Delete( &L , 8 ) ;

	Print( &L ) ;

	return 0 ;
}