《数据结构》一般线性表的合并

一般线性表的合并

算法思想：

遍历表A和表B，查看B的每一个元素是否在A中，若不在，将B的该元素插入到A的表尾，A表的表长+1。

算法的时间复杂度和A、B的长度有关，O（m*n）.

//合并
void Combine(SqList &A,SqList &B){
	for(int i=0;i<B.length;i++){
		int count=0;
		for(int j=0;j<A.length;j++){
			if(A.elem[j]==B.elem[i]){
				count+=1;
			}
		}
		if(count==0){
			A.elem[A.length++]=B.elem[i];
		}
	}
} 

/*
一般线性表的合并 
将两个线性表合并，LA={7,5,3,11},LB={2,6,3}
合并后{7,11,2,6} 
*/
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 100

typedef struct{
	int *elem;
	int length;
}SqList;

//初始化
int InitSqList(SqList &L){
	L.elem=new int[MAX];
	if(!L.elem){
		return 0;//初始化失败 
	}else{
		L.length=0;
		return 1;//初始化成功 
	}
} 

//获取表长
int ListLength(SqList L){
	return L.length;
}

//遍历
void TraveList(SqList &L){
	for(int i=0;i<L.length;i++){
		printf("%d ",L.elem[i]);
	}
	printf("n");
} 

//创建线性表
void CreateList(SqList &L){
	printf("请输入线性表的长度:");
	int n;
	scanf("%d",&n);
	printf("请输入表的元素:n");
	int e;
	for(int i=0;i<n;i++){
		scanf("%d",&e);
		L.elem[i]=e;
		L.length=i+1;
	}
} 

//合并
void Combine(SqList &A,SqList &B){
	for(int i=0;i<B.length;i++){
		int count=0;
		for(int j=0;j<A.length;j++){
			if(A.elem[j]==B.elem[i]){
				count+=1;
			}
		}
		if(count==0){
			A.elem[A.length++]=B.elem[i];
		}
	}
} 
int main(){
	SqList A,B;
	
	if(InitSqList(A)){
		printf("线性表A初始化成功!n");
	}else{
		printf("线性表A初始化失败!n");
	}
	
	if(InitSqList(B)){
		printf("线性表B初始化成功！n");
	}else{
		printf("线性表B初始化成功!n");
	}
	
	CreateList(A);
	printf("表长:%dn",A.length);
	TraveList(A);
	CreateList(B);
	
	printf("合并后的线性表:n");
	Combine(A,B);
	TraveList(A);
}
 

数组实现上述操作：

#include<stdio.h>
#define MAX 100
int main(){
	int a[MAX];
	int b[MAX];
	
	int len1=0,len2=0;
	int m,n;
	printf("请输入两个表的长度:n");
	scanf("%d%d",&m,&n);
	printf("请输入第一个表的元素:n");
	for(int i=0;i<m;i++){
		scanf("%d",&a[i]);
		len1+=1;
	}
	
	printf("请输入第二个表的元素:n");
	for(int i=0;i<n;i++){
		scanf("%d",&b[i]);
		len2++;
	}
	
	printf("合并前两个表的长度:%d %dn",len1,len2);
	
	//合并
	for(int i=0;i<len1;i++){
		int count=0;
		for(int j=0;j<len2;j++){
			if(a[i]==b[j]){
				count+=1;
			}
		}
		if(count==0){
			b[len2++]=a[i];
		}
	} 
	
	for(int i=0;i<len2;i++){
		printf("%d ",b[i]);
	}
	printf("n");
	printf("合并后新表的长度:%dn",len2);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!