文档章节

求集合的交并补集

 流氓兔来啦
发布于 2016/11/12 21:41
字数 839
阅读 18
收藏 0

#Problem A: 求集合的交并补集 Time Limit: 1 Sec   Memory Limit: 4 MB 

###Description

任意给定两个包含1-30000个元素的集合A,B(集合中元素类型为任意整型数,且严格递增排列),求A交B、A并B、A-B和B-A集合。

###Input

输入第一行为测试数据组数。每组测试数据两行,分别为集合A、B。每行第一个数n(1<=n<=30000)为元素数量,后面有n个严格递增的绝对值小于2^31代表集合中包含的数。

###Output

对每组测试数据输出5行,第1行为数据组数,后4行分别为按升序输出两个集合的A交B、A并B、A-B和B-A集合。格式见样例。

###Sample Input

1 3 1 2 5 4 2 3 5 8 ###Sample Output

Case #1: 2 5 1 2 3 5 8 1 3 8 ###HINT

考察知识点:有序表合并,时间复杂度O(n),空间复杂度O(n)

#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 60000
using namespace std;
typedef int ElemType; 
typedef int status; //定义返回类型

typedef struct{
    ElemType *elem; // 顺序表基地址
    int length;
}SqList;

///初始化
int InitListSq(SqList &L)
{
    L.elem=new ElemType[MAX_SIZE];
    if(!L.elem)
        exit(-2);
    L.length=0;
    return 0;
}
///创建
int Create_SqList(SqList &L,int n)
{
    //InitListSq(L);///加一句试试 // 没用
    int i;
    if(n>=MAX_SIZE)
        return 0;
    for(i=0;i<n;i++)
    {
            scanf("%d",&(L.elem[i]));/// ///////////////////////
    }
    L.length=n;
    ///进行一次排序,变为递增数列
//    int j,k,m,g=0;
//    m=L.length;
//    for(j=1;j<L.length;j++)
//    {
//        m-=1;
//        for(k=0;k<m;k++)
//        {
//            if(L.elem[k]>L.elem[k+1])
//            {
//                g=L.elem[k];
//                L.elem[k]=L.elem[k+1];
//                L.elem[k+1]=g;
//            }
//        }
//    }

    return 0;
}
void Delete_Sqlist(SqList &C)
{
    delete[] C.elem;
    C.length=0;
// 不加可能会内存超限 Memory Error
}

///交集
void Jiao_Sqlist(SqList &A,SqList &B)
{
    int flag=0;
    int i=0;
    int j=0;
    while(i<A.length&&j<B.length)
    {
      if(*(A.elem+i)<*(B.elem+j))
        {
            i++;
        }
        else if(*(A.elem+i)>*(B.elem+j))
        {
            j++;
        }
        else
        {
            if(flag==0)
            {
                printf("%d",*(A.elem+i));
                flag=1;
            }
            else
            {
                 printf(" %d",*(A.elem+i));
            }
            i++;
            j++;
        }
    }
    printf("\n");
}


///并集
void Bing_SqList(SqList &A,SqList &B)
{
    int flag=0;
    int i=0;
    int j=0;
    while(i<A.length&&j<B.length)
    {
        if(*(A.elem+i)<*(B.elem+j))
        {
            if(flag==0)
            {
                printf("%d",*(A.elem+i));
                flag=1;
            }
            else
            {
                printf(" %d",*(A.elem+i));
            }
            i++;
        }
        else if(*(A.elem+i)>*(B.elem+j))
        {
             if(flag==0)
            {
                printf("%d",*(B.elem+j));
                flag++;
            }
            else
            {
                printf(" %d",*(B.elem+j));
            }
            j++;
        }
        else
        {
            if(flag==0)
            {
                printf("%d",*(A.elem+i));
                flag++;
            }
            else
            {
                printf(" %d",*(A.elem+i));
            }
            i++;
            j++;
        }
    }
    //i++;
    if(i<A.length)
    {
        while(i<A.length)
        {
             if(flag==0)
            {
                printf("%d",*(A.elem+i));
                flag=1;
            }
            else
            {
                printf(" %d",*(A.elem+i));
            }
            i++;
        }
    }
    if(j<B.length )
    {
        while(j<B.length)
        {
             if(flag==0)
            {
                printf("%d",*(B.elem+j));
                flag++;
            }
            else
            {
                printf(" %d",*(B.elem+j));
            }
            j++;
        }
    }
    printf("\n");
}

/// 补集A_B
void A_B_SqList(SqList &A,SqList &B)
{
     int flag=0;
     int i=0;
     int j=0;
     while(i<A.length&&j<B.length)
     {
         if(*(A.elem+i)<*(B.elem+j))
         {
              if(flag==0)
            {
                printf("%d",*(A.elem+i));
                flag=1;
            }
            else
            {
                printf(" %d",*(A.elem+i));
            }
            i++;
         }
         else if(*(A.elem+i)>*(B.elem+j))
         {
             j++;
         }
         else
         {
             i++;
             j++;
         }
     }
     //if(j==B.length-1 && i<A.length)
     if(i<A.length)///  if(j==B.length-1 && i<A.length)
     {
         while(i<A.length)
         {
            if(flag==0)
            {
                printf("%d",*(A.elem+i));
                flag=1;
            }
            else
            {
                printf(" %d",*(A.elem+i));
            }
            i++;
         }
     }
     printf("\n");
}
///补集B_A
void B_A_SqList(SqList &A,SqList &B)
{
    int flag=0;
    int i=0;
    int j=0;
    while(i<A.length&&j<B.length)
    {
        if(*(A.elem+i)<*(B.elem+j))
        {
            i++;
        }
        else if(*(A.elem+i)>*(B.elem+j))
        {
               if(flag==0)
            {
                printf("%d",*(B.elem+j));
                flag=1;
            }
            else
            {
                printf(" %d",*(B.elem+j));
            }
            j++;
        }
        else
        {
            i++;
            j++;
        }
    }
    if(j<B.length )
    {
        while(j<B.length)
        {
              if(flag==0)
            {
                printf("%d",*(B.elem+j));
                flag=1;
            }
            else
            {
                printf(" %d",*(B.elem+j));
            }
            j++;
        }
    }
    printf("\n");
}
int main()
{
    int Case;
    int i;
    scanf("%d", &Case);
    for(i=1;i<=Case;i++)
    {
        SqList A,B;
        ///初始化顺序表
        InitListSq(A);
        InitListSq(B);
        ///创建顺序表
        int la;
        scanf("%d",&la);
        A.length=la;
        Create_SqList(A,la);
        int lb;
        scanf("%d",&lb);
        B.length=lb;
        Create_SqList(B,lb);
        printf("Case #%d:\n",i);


        ///交集
        Jiao_Sqlist(A,B);

        ///并集
        Bing_SqList(A,B);
        ///补集
        A_B_SqList(A,B);
        B_A_SqList(A,B);
        ///释放
        Delete_Sqlist(A);
        Delete_Sqlist(B);
    }
    return 0;
}

© 著作权归作者所有

粉丝 2
博文 26
码字总数 14893
作品 0
青岛
其他
私信 提问
利用线性表的顺序结构求集合的并、交、差、补(C语言实现)

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算,做个记录,希望也能帮助到其他人。 一、算法分析   (1)用数组A,B,C,E表示集合。假定A={1,3,4,5,6...

Tim_JX
2014/03/24
0
0
Swift讲解专题五——集合类型

Swift讲解专题五——集合类型 一、引言 Swift中提供了3种集合类型,Array数据类型,Set集合类型,Dictionary字典类型。Array用于存放一组有序的数据,数据角标从0开始一次递增;Set用于存放一...

珲少
2016/05/11
376
0
Python全栈工程师(集合、函数)

ParisGabriel               感谢 大家的支持 你们的阅读评价就是我最好的动力 我会坚持把排版内容以及偶尔的错误做的越来越好                        ...

巴黎香榭
2018/07/11
0
0
ParisGabriel:Python全栈工程师(0基础到精通)教程 第十三课

ParisGabriel               感谢 大家的支持 你们的阅读评价就是我最好的动力 我会坚持把排版内容以及偶尔的错误做的越来越好                        ...

ParisGabriel
2018/07/11
0
0
【原创】Lua 语言中的模式匹配

与其他脚本语言不同的是,Lua 并不使用符合 POSIX 规范的正则表达式(也写作 regexp)来进行模式匹配。然而,Lua 中的模式匹配功能是很强大的,并且包含了一些标准 POSIX 模式匹配不容易实现...

摩云飞
2013/03/08
0
4

没有更多内容

加载失败,请刷新页面

加载更多

0.01-Win10安装linux子系统

一、安装Debian子系统 -1、控制面板设置: -1.1、打开“控制面板” —— “程序” —— “启用或关闭Windows功能” —— 勾选 “适用于Linux的Windows子系统” -2、设置: -2.1、打开“设置”...

静以修身2025
昨天
0
0
init 0-6 (启动级别:init 0,1,2,3,4,5,6)

启动级别: init 0,1,2,3,4,5,6 这是个很久的知识点了,只是自己一直都迷迷糊糊的,今天在翻出来好好理解下。。 0: 停机 1:单用户形式,只root进行维护 2:多用户,不能使用net file system...

圣洁之子
昨天
2
0
Android Camera HAL浅析

1、Camera成像原理介绍 Camera工作流程图 Camera的成像原理可以简单概括如下: 景物(SCENE)通过镜头(LENS)生成的光学图像投射到图像传感器(Sensor)表面上,然后转为电信号,经过A/D(模数转...

天王盖地虎626
昨天
2
0
聊聊Elasticsearch的ProcessProbe

序 本文主要研究一下Elasticsearch的ProcessProbe ProcessProbe elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/monitor/process/ProcessProbe.java public class ProcessProb......

go4it
昨天
2
0
mysql PL(procedure language)流程控制语句

在MySQL中,常见的过程式SQL语句可以用在存储体中。其中包括IF语句、CASE语句、LOOP语句、WHILE语句、ITERATE语句和LEAVE语句,它们可以进行流程控制。 IF语句相当于Java中的if()...else if(...

edison_kwok
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部