데이터 구조 - 선형 표 의 순서 표시 와 실현 (c 언어)

#include 
#include 

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1  
#define OVERFLOW -2
#define LIST_INIT_SIZE 100   //         
#define LISTINCREMENT 10   //           

//Status      ，          
typedef int Status;
typedef int ElemType;   //         ，        ，        ，        ，    
typedef struct 
{
	ElemType *elem;   //      
	int length;   //    
	int listsize;   //         （ sizeof(ElemType)   ）
}SqList;

void Init_Sq(SqList *L);
Status Insert_Sq(SqList *L, int i, ElemType e);
Status Destroy_Sq(SqList *L);
Status Delete_List(SqList *L, int i);
void Travse_Sq(SqList *L);
ElemType Next_Elem(SqList *L, int cur_elem);
ElemType Prior_Elem(SqList *L, int cur_elem);
ElemType GetElem(SqList *L, int i);
int LocateElem_Sq(SqList *L, ElemType e);
Status compare(ElemType e1, ElemType e2);
int ListLength(SqList *L);
void union_Sq(SqList *La, SqList *Lb);
void Merge_Sq(SqList *La, SqList *Lb, SqList *Lc);

void main()
{	

	/*SqList L;
	int i;
	Init_Sq(&L);
	if(	Insert_Sq(&L, 1, 4))
	{
		printf("The element is %d
", GetElem(&L, 1));
	}
	if(	Insert_Sq(&L, 2, 5))
	{
		printf("The element is %d
", GetElem(&L, 2));
	}
	if(	Insert_Sq(&L, 3, 6))
	{
		printf("The element is %d
", GetElem(&L, 3));
	}
	if(	Insert_Sq(&L, 4, 8))
	{
		printf("The element is %d
", GetElem(&L, 4));
	}
	if(	Insert_Sq(&L, 5, 18))
	{
		printf("The element is %d
", GetElem(&L, 5));
	}
	Travse_Sq(&L);
	printf("Current number:  ");
	scanf("%d", &i);
	printf("The prior of No.%d is %d
", i, Prior_Elem(&L, i));

	
	if(Delete_List(&L,1))
	{
		printf("After delete:
");
		Travse_Sq(&L);
	}
	*/

	SqList La;
	SqList Lb;
	SqList Lc;

	Init_Sq(&La);
	Init_Sq(&Lb);

	if(	Insert_Sq(&La, 1, 4))
	{
		printf("The element in La is %d
", GetElem(&La, 1));
	}
	if(	Insert_Sq(&La, 2, 5))
	{
		printf("The element in La is %d
", GetElem(&La, 2));
	}
	if(	Insert_Sq(&La, 3, 6))
	{
		printf("The element in La is %d
", GetElem(&La, 3));
	}
	if(	Insert_Sq(&La, 4, 8))
	{
		printf("The element in La is %d
", GetElem(&La, 4));
	}
	if(	Insert_Sq(&La, 5, 18))
	{
		printf("The element in La is %d
", GetElem(&La, 5));
	}

	printf("
");
	if(	Insert_Sq(&Lb, 1, 4))
	{
		printf("The element in Lb is %d
", GetElem(&Lb, 1));
	}
	if(	Insert_Sq(&Lb, 2, 15))
	{
		printf("The element in Lb is %d
", GetElem(&Lb, 2));
	}
	printf("
");

	//union_Sq(&La, &Lb);   

//	printf("After unite La and Lb:
");
//	Travse_Sq(&La);
	Merge_Sq(&La, &Lb, &Lc);
	printf("After merge La and Lb:
");
	Travse_Sq(&Lc);
	Destroy_Sq(&La);
	Destroy_Sq(&Lb);
	Destroy_Sq(&Lc);
}

void Init_Sq(SqList *L)
{
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(L->elem == NULL)
	{
		printf("Memory allocation is error!");
		exit(1);   //0      ，        
	}
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
}

//  i       e
Status Insert_Sq(SqList *L, int i, ElemType e)
{
	ElemType *newbase;   //             
	ElemType *p;
	ElemType *q;

	if(i < 1 || i > L->length +  1)
	{
		printf("The location that inserted is illegal!
");
		return TRUE;
	}

	if(!(L->length < L->listsize))   //          
		newbase = (ElemType *)realloc(&L->elem, (L->length + LISTINCREMENT) * sizeof(ElemType));

	p = &L->elem[i-1];

	for(q = &L->elem[L->length - 1]; p <= q; q--)
	{
		*(q + 1) = *q;
	}

	*p = e;
	L->length ++;
	return TRUE;
}

//     
Status Destroy_Sq(SqList *L)
{
	if(L->length < 1)
		return FALSE;
	free(L->elem);
	L->elem = NULL;
	return TRUE;
}

//          
Status Delete_List(SqList *L, int i)
{
	ElemType *p;
	int j;

	if(i < 1 && i > L->length)
	{
		printf("The site that store element is not exist!
");
		return FALSE;
	}

	p = &L->elem[i - 1];   //   p         

	for(j = i - 1; j < L->length - 1; j++)
	{
		*p = *(p+1);
		p++;
	}
	L->length --;
	return TRUE;
}

//     
void Travse_Sq(SqList *L)
{
	int i;
	if(L->length == 0)
	{
		printf("The sequence list is empty!
");
	}
	else
		for(i = 0; i < L->length; i++)
			printf("The No.%d is %d.
", i, L->elem[i]);
}

//   i   
ElemType GetElem(SqList *L, int i)
{
	if(i < 1 || i > L->length)
		return ERROR;
	return L->elem[i - 1];
}

//   cur_elem        
ElemType Prior_Elem(SqList *L, int cur_elem)
{
	if(cur_elem == 1)
		return ERROR;
	else
		return L->elem[cur_elem - 2];
}

//   cur_elem        
ElemType Next_Elem(SqList *L, int cur_elem)
{
	if(cur_elem == (L->length - 1))
		return FALSE;
	else
		return L->elem[cur_elem];
}

//        
int ListLength(SqList *L)
{
	if(L->length == 0)
	{
		printf("The sequence list is empty!
");
		return 0;
	}
	else 
		return L->length;

}

//   A B     
void union_Sq(SqList *La, SqList *Lb)
{
	//       Lb    La         La 
	int La_len, Lb_len;
	int i;
	int Lb_cur_elem;   //  Lb      

	La_len = ListLength(La);
	Lb_len = ListLength(Lb);

	//  ，    i   ，       1    
	//GetElem()      1  (        )
	for(i = 1; i <= Lb_len; i++)
	{
		Lb_cur_elem = GetElem(Lb, i);
		if(!LocateElem_Sq(La, Lb_cur_elem))
			Insert_Sq(La, ++La_len, Lb_cur_elem);
	}
}

Status compare(ElemType e1, ElemType e2)
{
	if(e1 == e2)
		return TRUE;
	else 
		return FALSE;
}

//      L        e  compare()      
//   ，     L    ，    0
int LocateElem_Sq(SqList *L, ElemType e)
{
	int i;
	ElemType *p;
	i = 1;   //i            
	p = L->elem;   //p     1        
	while(i <= L->length && (e != *p++))
		i++;
	if(i <= L->length)
		return i;
	else 
		return 0;
}

//       La， Lb         
//  La Lb         Lc，Lc           
void Merge_Sq(SqList *La, SqList *Lb, SqList *Lc)
{
	ElemType *pa;
	ElemType *pb;
	ElemType *pc;
	ElemType *pa_last;
	ElemType *pb_last;

	// Lc elem      
	Lc->elem = (ElemType *)malloc((La->length + Lb->length) * sizeof(ElemType));
	if(!Lc->elem)
	{
		printf("Error!
");
		exit(1);
	}

	pa = La->elem;   //pa  La      
	pb = Lb->elem;	 //pb  Lb      		
	pc = Lc->elem;   //pc  Lc    
	Lc->length = La->length + Lb->length;
	
	pa_last = &La->elem[La->length - 1];   //  La       （La       ）
	pb_last = &Lb->elem[Lb->length - 1];   //  Lb       （Lb       ）

	while(pa <= pa_last && pb <= pb_last)   //    
	{
		if(*pa <= *pb)
		{
			*pc++ = *pa++;
		}
		else
			*pc++ = *pb++;
	}
	while(pa <= pa_last)
		*pc++ = *pa++;
	while(pb <= pb_last)
		*pc++ = *pb++;
}