算法2.2 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。

柔情只为你懂 2023-02-20 03:28 38阅读 0赞

### 数据结构（C语言版）严蔚敏 吴伟民 ###

#### 算法2.2 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。例如，设 ####

#### LA=（3,5,8,11） ####

#### LB=（2，6,8,9,11,15,20） ####

#### 则 ####

#### LC=(2,3,5,6,8,8,9,11,11,15,20) ####

说明：为了展示结果，代码加入线性表的抽象数据类型的全部构造，实际是UnionList函数达成该练习结果，因为该函数内需要调用抽象数据类型构造的其他函数，所以全部列出。

代码块：

#include <stdio.h>
    #include <stdlib.h>
    
    //Function result status code
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASALBE -1
    #define OVERFLOW -2
    
    //Status is the type of function whose value is the function result status code
    typedef int Status;
    
    typedef struct{
        
    	int *data;
    	int length;
    }List;
    
    void output(List *L);
    Status InitList(List *L);
    Status DestroyList(List *L);
    Status ClearList(List *L);
    Status ListEmpty(List *L);
    Status ListLength(List *L);
    Status GetElem(List *L, int i, int *e);
    Status compare(List *a, int b);
    Status LocateElem(List *L, int e, Status (*pfun)(List *ce, int num));
    Status PriorElem(List *L, int cur_e, int *pre_e);
    Status NextElem(List *L, int cur_e, int *next_e);
    Status ListInsert(List *L, int i, int e);
    Status ListDelete(List *L, int i, int *e);
    Status visit(List *L);
    Status ListTraverse(List *L, Status (*pfun)(List *ce));
    void UnionList(List *La, List *Lb);
    void MergeList(List *La, List *Lb, List *Lc);
    
    void output(List *L){
        
    	int i;
    	printf("Result: ");
    	for(i=0; i<ListLength(L); i++)
    		printf("%d ", L->data[i]);
    	printf("\n");
    }
    Status InitList(List *L){
        
    	L->data=(int*)malloc(30*sizeof(int));
    	if(!L) exit(OVERFLOW);
    	L->length=0;
    	return OK;
    }//InitList
    Status DestroyList(List *L){
        
    	free(L); 
    	return OK;
    }//DestroyList
    Status ClearList(List *L){
        
    	int i;
    	for(i=0; i<=ListLength(L); i++){
        
    		if(L->data[i]!=0)
    			L->data[i]=0;
    		L->length--;
    	}
    	L->length--;
    	return OK;
    }//ClearList
    Status ListEmpty(List *L){
        
    	if(L->length!=0)
    		return FALSE;
    	else
    		return TRUE;
    }//ListEmpty
    Status ListLength(List *L){
        
    	return L->length;
    }//ListLength
    Status GetElem(List *L, int i, int *e){
        
    	int j;
    	for(j=0; j<ListLength(L); j++)
    		if(j==i-1){
        
    			e=&L->data[j];
    			break;
    		}
    	return *e;
    }//GetElem
    Status compare(List *a, int b){
        
    	int i, judge;
    	for(i=0, judge=0; i<ListLength(a); i++){
        
    		if(a->data[i]==b){
        
    			judge=1;
    			return TRUE;
    			break;
    		}
    	}
    	if(judge==0)
    		return FALSE;
    }//compare
    Status LocateElem(List *L, int e, Status (*pfun)(List *ce, int num)){
        
    	int i;
    	for(i=0; i<ListLength(L); i++){
        
    		if(L->data[i]==e){
        
    			return i+1;
    			break;
    		}
    	}
    	if(!pfun(L, e))
    		return 0;
    }//LocateElem
    Status PriorElem(List *L, int cur_e, int *pre_e){
        
    	int i, judge;
    	for(i=0, judge=0; i<ListLength(L); i++){
        
    		if(i!=0&&cur_e==L->data[i]){
        
    			judge=1;
    			pre_e=&L->data[i-1];
    			break;
    		}
    	}
    	if(i==0||judge==0)
    		return ERROR;
    	else
    		return *pre_e;
    }//PriorElem
    Status NextElem(List *L, int cur_e, int *next_e){
        
    	int i, judge;
    	for(i=0, judge=0; i<ListLength(L); i++)
    		if(i!=ListLength(L)-1&&cur_e==L->data[i]){
        
    			judge=1;
    			next_e=&L->data[i+1];
    			break;
    		}
    	if(i==ListLength(L)-1||judge==0)
    		return ERROR;
    	else
    		return *next_e;
    }//NextElem
    Status ListInsert(List *L, int i, int e){
        
    	int j;
    	if(i<1||(i-1)>ListLength(L)) return ERROR;
    	else{
        
    		for(j=ListLength(L); j>=i; j--)
    			L->data[j]=L->data[j-1];
    		L->length++;
    		L->data[j]=e;
    		return OK;
    	}
    }
    Status ListDelete(List *L, int i, int *e){
        
    	int j, temp;
    	if(i<0||i>ListLength(L)) return ERROR;
    	temp=L->data[i];
    	for(j=i; j<ListLength(L)-1; j++)
    		L->data[j]=L->data[j+1];
    	L->length--;
    	e=&temp;
    	return *e;
    }//ListDelete
    Status visit(List *L){
        
    	int i, judge;
    	for(i=0, judge=0; i<ListLength(L); i++){
        
    		if(L->data[i]!=NULL)
    			judge=1;
    		else{
        
    			judge=0;
    			break;
    		}
    	}
    	if(judge==0)
    		return ERROR;
    	else
    		return OK;
    }//visit
    Status ListTraverse(List *L, Status (*pfun)(List *ce)){
        
    	if(pfun(L))
    		return TRUE;
    	else
    		return FALSE;
    }//ListTraverse
    void UnionList(List *La, List *Lb){
        
    	La->length=ListLength(La);
    	Lb->length=ListLength(Lb);
    	int i, re, *el=NULL;
    	Status (*pfun)(List *ce, int num);
    	for(i=0; i<Lb->length; i++){
        
    		re=GetElem(Lb, i+1, el);
    		if(!LocateElem(La, re, compare))
    			printf("ListInsert Status: %d\n", ListInsert(La, La->length+1, re));
    	}
    }//UnionList
    void MergeList(List *La, List *Lb, List *Lc){
        
    	//La and LB are arranged in non decreasing order
    	printf("InitList Lc Status: %d\n", InitList(Lc));
    	int i=0, j=0, k=0;
    	La->length=ListLength(La);
    	Lb->length=ListLength(Lb);
    	int *ai=NULL, *bj=NULL, a, b;
    	while((i<La->length)&&(j<Lb->length)){
        
    		printf("GetElem ai: %d\n", GetElem(La, i+1, ai));
    		a=GetElem(La, i+1, ai);
    		printf("GetElem bj: %d\n", GetElem(Lb, j+1, bj));
    		b=GetElem(Lb, j+1, bj);
    		printf("Lc Length: %d\n", Lc->length);
    		if(a<=b){
        
    			k++;
    			printf("ListInsert ai Status: %d\n", ListInsert(Lc, k, a));
    			i++;
    		}
    		else{
        
    			k++;
    			printf("ListInsert bj Status: %d\n", ListInsert(Lc, k, b));
    			j++;
    		}
    	}
    	while(i<La->length){
        
    		printf("GetElem ai: %d\n", GetElem(La, i+1, ai));
    		a=GetElem(La, i+1, ai);
    		i++;
    		k++;
    		printf("ListInsert ai: %d\n", ListInsert(Lc, k, a));
    	}
    	while(j<Lb->length){
        
    		printf("GetElem bj: %d\n", GetElem(Lb, j+1, bj));
    		b=GetElem(Lb, j+1, bj);
    		j++;
    		k++;
    		printf("ListInsert bj: %d\n", ListInsert(Lc, k, b));
    	}
    	output(Lc);
    }//MergeList
    
    int main()
    {
        
    	List *Li=(List*)malloc(sizeof(List));
    	printf("InitList Li Status: %d\n", InitList(Li));
    	int i, n, *r=NULL;
    	printf("Enter List Li Length: ");
    	scanf("%d", &n);
    	printf("Enter %d numbers: ", n);
    	for(i=0; i<n; i++){
        
    		scanf("%d", &Li->data[i]);
    		Li->length++;
    	}
    
    	printf("ListLength: %d\n", ListLength(Li));
    	printf("ListEmpty Status: %d\n", ListEmpty(Li));
    	printf("GetElem: %d\n", GetElem(Li, 3, r));
    	printf("LocateElem: %d\n", LocateElem(Li, 13, compare));
    	printf("PriorElem %d\n", PriorElem(Li, 16, r));
    	printf("NextElem: %d\n", NextElem(Li, 2, r));
    	printf("ListInsert Status: %d\n", ListInsert(Li, 1, 1));
    	output(Li);
    	printf("ListDelete Status: %d\n", ListDelete(Li, 2, r));
    	output(Li);
    	printf("ListTraverse Status: %d\n", ListTraverse(Li, visit));
    
    	List *Lb=(List*)malloc(sizeof(List));
    	printf("InitList Lb Status: %d\n", InitList(Lb));
    	int m;
    	printf("Enter List Lb length: ");
    	scanf("%d", &m);
    	printf("Enter %d numbers: ", m);
    	for(i=0; i<m; i++){
        
    		scanf("%d", &Lb->data[i]);
    		Lb->length++;
    	}
    	List *Lc=(List*)malloc(sizeof(List));
    	MergeList(Li, Lb, Lc);
    	printf("ClearList Status: %d\n", ClearList(Li));
    	printf("ListEmpty Status: %d\n", ListEmpty(Li));
    	printf("DestroyList Status: %d\n", DestroyList(Li));
    	system("pause");
    	return 0;
    }