有序表的合并——用顺序表实现

问题描述

已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。

La=(1,7,8) Lb=(2,4,6,8,10,11)→Lc=(1,2,4,6,7,8,8,10,11)

算法步骤

（1）创建一个空表Lc

（2）依次从La或Lb中摘取元素值较小的结点插入到表Lc的最后，直至其中一个表变空为止

（3）继续将La或Lb其中一个表的剩余结点插入在Lc表的最后

算法实现

void MergeList_Sq(SqList LA,SqList LB,SqList &LC)
{
  pa=LA.elem;
  pb=LB.elem;//指针pa和pb的初值分别指向两个表的第一个元素
  LC.length=LA.length+LB.length;//新表长度为待合并两表的长度之和
  LC.elem=new ElemType[LC.length];//为合并后的新表分配一个存储空间
  pc=LC.elem;//指针pc指向新表的第一个元素
  pa_last=LA.elem+LA.length-1;//指针pa_last指向LA的最后一个元素
  pb_last=LB.elem+LB.length-1;//指针pb_last指向LB的最后一个元素
  while(pa<=pa_last&&pb<=pb_last)//两个表都非空
  {
    if(*pa<*pb)//依次摘取两表中值较小的结点
      *pc++=*pa++;
    else
      *pc++=*pb++;
  }
  while(pa<=pa_last)
    *pc++=*pa++;//LB表已到达表尾，将LA中的剩余元素加入LC
  while(pb<=pb_last)//LA表已到达表尾，将LB中剩余元素加入LC
    *pc++=*pb++;
}

算法的时间复杂度是：O（ListLength(La)+ListLength(Lb)）

算法的空间复杂度是：O（ListLength(La)+ListLength(Lb)）

代码实现

#include<stdio.h>
#include<stdlib.h>
typedef int Status;	
typedef int ElemType;
#define LIST_INIT_SIZE 100	//顺序表存储空间的初始分配量 
#define LISTINCREMENT 10	//顺序表存储空间的分配增量
#define	OVERFLOW	-2			//堆栈上溢


typedef struct{
	ElemType *elem;//存储空间基地址 
	int length; //当前长度 
	int listsize; //当前分配的存储空间大小 
}SqList;  

Status InitList_Sq(SqList &L){
	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem){ 
		exit(OVERFLOW);
	}
	L.length=0;
	L.listsize=LIST_INIT_SIZE;
	return 1;
} 

Status ListInsert_Sq(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1){
		return 0;
	} 
	ElemType *newbase; 
	ElemType *p,*q; 
	 
	if(L.length>=L.listsize){
		newbase=(ElemType*)realloc(L.elem,
				(L.listsize+LISTINCREMENT)*sizeof(ElemType)); 
		if(!newbase){
			exit(OVERFLOW);
		}
		L.elem=newbase;
		L.listsize+=LISTINCREMENT; 
	}
	q=&(L.elem[i-1]);
	for(p=&(L.elem[L.length-1]);p>=q;p--){
		*(p+1)=*p;	 
	} 
	*q=e;
	L.length++;
	return 1; 
}
void PrintElem(ElemType e){
	printf("%d ", e);
}
 
Status ListTraverse_Sq(SqList L,void (visit)(ElemType)){		
	for(int i=0;i<L.length;i++){
		visit(L.elem[i]);
	}	
	printf("\n");	
	return 1;
} 

int ListLength_Sq(SqList L){
	return L.length;	
}

Status GetElem_Sq(SqList L,int i,ElemType *e){ 
	if(i<1||i>L.length){
		return 0;
	} 
	*e=L.elem[i-1];	
	return 1;
} 

void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
	ElemType *pa,*pb,*pc,*pa_last,*pb_last;
	pa=La.elem;
	pb=Lb.elem;
	Lc.listsize=Lc.length=La.length+Lb.length;
	pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
	if(!Lc.elem){
		exit(OVERFLOW);
	}
	pa_last=La.elem+La.length-1;
	pb_last=Lb.elem+Lb.length-1;
	while(pa<=pa_last&&pb<=pb_last){	// 归并
		if(*pa<=*pb){
			*pc++=*pa++;
		}else{
			*pc++=*pb++;
		}
	} 
	while(pa<=pa_last){
		*pc++=*pa++;	// 插入La的剩余元素
	}
	while(pb<=pb_last){
		*pc++=*pb++;	// 插入Lb的剩余元素
	}
}
int main(){
	SqList La,Lb,Lc;
	ElemType a[3]={1,7,8};
	ElemType b[6]={2,4,6,8,10,11};
	int i;
	InitList_Sq(La);	//初始化La 
	for(i=1;i<=3;i++){
		ListInsert_Sq(La,i,a[i-1]);
	}			
	InitList_Sq(Lb);	//初始化Lb 
	for(i=1;i<=6; i++){
		ListInsert_Sq(Lb,i,b[i-1]);
	}	
	printf("La= ");	ListTraverse_Sq(La, PrintElem);
	printf("Lb= ");	ListTraverse_Sq(Lb, PrintElem); 
	printf("合并La和Lb：Lc= "); 		
	MergeList_Sq(La,Lb,Lc);
	ListTraverse_Sq(Lc,PrintElem);
	return 0;
}