合并两个集合

ゝ一纸荒年。 2023-06-29 12:59 11阅读 0赞

题目描述:

假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，编写一个算法求一个新的集合C=A∪B，即将两个集合的并集放在线性表LC中。

#include<stdio.h>
    #include"sqlist.cpp"
    /*
    假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，
    即线性表中的数据元素即为集合中的成员。
    编写一个算法求一个新的集合C=A∪B，
    即将两个集合的并集放在线性表LC中。  
    */
    void UnionList(SqList *LA,SqList *LB,SqList *&LC)
    {
    	int lena;//线性表LA的长度；
    	int i;
    	ElemType e;
    	InitList(LC);
    	for(i=0;i<=ListLength(LA);i++) //将LA总的所有元素插入到LC中 
    	{
    		 GetElem(LA,i,e);
    		 ListInsert(LC,i,e);
    	}
    	lena=ListLength(LA);//求线性表LA的长度
    	for(i=0;i<=ListLength(LB);i++)
    	{
    		GetElem(LB,i,e);//取LB中的每一个元素
    		if(!LocateElem(LA,e)) 
    		{
    			ListInsert(LC,++lena,e);
    		}
    	} 
    }
    
    int main(int argc,char *argv[])
    {
    	SqList *LA,*LB,*LC;
    	int a[]={1,3,2};
    	InitList(LA);//初始化线性表
    	CreateList(LA,a,3);//数组名代表数组元素的首地址 
    //	ListInsert(LA,1,1);
    //	ListInsert(LA,2,3);
    //	ListInsert(LA,3,2);
    	printf("LA:");
    	DisplayList(LA);
    	
    	int b[]={1,4,2};
    	InitList(LB);//初始化线性表
    	CreateList(LB,b,3);//数组名代表数组元素的首地址 
    //	ListInsert(LB,1,1);
    //	ListInsert(LB,2,4);
    //	ListInsert(LB,3,2);
    	printf("LB:");
    	DisplayList(LB);
    
    	UnionList(LA,LB,LC);
    	printf("LC=LA U LB\n");
    	printf("LC:");
    	DisplayList(LC);
    	
    	DestroyList(LA);
    	DestroyList(LB);
    	DestroyList(LC);
    	return 0;
    }

线性表的基本操作定义

#include<stdio.h>
    #include<malloc.h>
    #define MaxSize 100
    typedef int ElemType;
    //顺序表的类型定义 
    typedef struct{
    	ElemType data[MaxSize];
    	int length;
    }SqList;
    //建立顺序表 
    void CreateList(SqList *& L, ElemType a[], int  n)
    {
    	L = (SqList *)malloc(sizeof(SqList));
    	for (int i = 0; i < n; i++)
    		L->data[i] = a[i];
    	L->length = n;
    }
    //初始化线性表 本算法的时间复杂度为O(1) 
    void InitList(SqList  * & L)
    {
    	//初始化线性表，只需要将其长度设置为0即可
    	L = (SqList *)malloc(sizeof(SqList));
    	L->length = 0;
    }
    //销毁线性表 本算法的时间复杂度为O(1) 
    void DestroyList(SqList *&L)
    {
    	//释放线性表L的内存空间
    	free(L);
    }
    //判断线性表是否为空 本算法的时间复杂度为O(1) 
    bool ListEmpty(SqList *L)
    {
    	return (L->length == 0);
    }
    //求线性表的长度 本算法的时间复杂度为O(1) 
    int ListLength(SqList *L)
    {
    	return (L->length);
    }
    //输出线性表   本算法的时间复杂度为O(L->length) 
    void DisplayList(SqList * L)
    {
    	if (ListEmpty(L))
    		return;
    	for (int i = 0; i < L->length; i++)
    		printf("%2d", L->data[i]);
    	printf("\n");
    }
    //求线性表中某个数据元素的值 本算法的时间复杂度为O(1) 
    bool GetElem(SqList * L, int i, ElemType & e)
    {
    	if (i<1 || i>L->length)
    		return false;
    	e = L->data[i - 1];
    	return true;
    }
    //按元素值查找 本算法的时间复杂度为O(L->length) 
    int LocateElem(SqList * L, ElemType e)
    {
    	int i = 0;
    	while (i < L->length && L->data[i] != e)
    		i++;
    	if (i >= L->length)
    		return 0;
    	else
    		return i + 1;
    }
    //插入顺序表的元素 本算法的时间复杂度为O(n) 
    bool ListInsert(SqList *& L, int i, ElemType e)
    {
    	if (i<1 || i>L->length + 1)
    		return false;
    	i--;//将顺序表的逻辑序号转化为物理序号
    	for (int j = L->length; j > i; j--)
    		L->data[ j ] = L->data[ j- 1];//将元素后移一个位置
    	L->data[i] = e;//插入元素e
    	L->length ++;//顺序表的元素增加1
    	return true;
    }
    //删除顺序表的元素  本算法的时间复杂度为O(n) 
    bool ListDelete(SqList *& L, int i, ElemType &e)
    {
    	if (i<1 || i>L->length)
    		return false;
    	i--;//将顺序表的逻辑序号转化为物理序号
    	e = L->data[i];
    	for (int j = i; j < L->length;j++)
    		L->data[ j ] = L->data[ j + 1];//将元素左移一个位置
    	L->length--;//顺序表的元素增加1
    	return true;
    }