频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
数据结构(线性结构习题)Problem A: 求集合的交并补集
2016-12-30 09:38:28      个评论    来源:adreammaker的博客  
收藏   我要投稿

Problem A: 求集合的交并补集

Time Limit: 1 SecMemory Limit: 4 MB
Submit: 6817Solved: 1972
[Submit][Status][Web Board]

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)

解题思路:1)分析 数据/元素 需要用什么结构储存 2)设计算法实现

#include <stdio.h>     
#include <malloc.h>     
#include <iostream>     
#include <stdlib.h>     
#define LIST_INIT_SIZE 100     
#define LISTINCREMENT 10     
#define OK 1     
#define OVERFLOW -1     
#define ERROR 0     
    
        
typedef int Status;     
        
typedef int ElemType;     
        
typedef struct SqList{     
    ElemType * elem;   //数组首地址     
    int listSize;  //表容量;当前表的容量     
    int length;  //表长,代表当前数组中有效元素的个数     
}SqList;     
        
// 下面实现nitList操作,即初始化一个空的线性表     
Status InitList_Sq(SqList &L)     
{     
    L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));     
    //malloc的返回值类型是void *;     
    //使用时要及时进行强制类型转换     
    if(!L.elem)     
        exit(OVERFLOW);     
    L.listSize=LIST_INIT_SIZE;     
    L.length=0;     
    return OK;     
}     
      
    
          
Status CreateList(SqList &La,int na){      
    for(int i = 1;i<=na;++i){      
        ElemType e;      
//      printf("请输入第%d个元素",i);      
        scanf("%d",&e);      
   if(La.length >= La.listSize)   {      
        La.elem=(ElemType *)realloc(La.elem,(La.listSize+LISTINCREMENT)*sizeof(ElemType));      
        La.listSize += LISTINCREMENT;      
    }      
        La.elem[i-1]=e;      
        La.length++;      
    }      
    return OK;      
}        
  
        
void MergeList_Sq(SqList La,SqList Lb,SqList &Ld,SqList &Le)     
{  //Ld是交,Le是补   
    ElemType* pa = La.elem;     
    ElemType* pb = Lb.elem;     
  
    Ld.length = 0;     
    Ld.listSize = La.length + Lb.length;     
    Ld.elem = (ElemType*)malloc(Ld.listSize*sizeof(ElemType));     
    ElemType* pd = Ld.elem;     
    if(!Ld.elem)     
        exit(OVERFLOW);     
        
    Le.length = 0;     
    Le.listSize = La.length + Lb.length;     
    Le.elem = (ElemType*)malloc(Ld.listSize*sizeof(ElemType));     
    ElemType* pe = Le.elem;      
    if(!Le.elem)     
        exit(OVERFLOW);     
        
        
    ElemType* pa_last = La.elem + La.length -1;     
    ElemType* pb_last = Lb.elem + Lb.length -1;     
    while(pa <= pa_last && pb <= pb_last)     
    {     
        if(*pa <= *pb)     
        {     
            if(*pa == *pb)     
            {     
                *pd++ = *pa;     
                Ld.length++;     
            }     
            else  
            {     
                *pe++ = *pa;      
                Le.length++;     
            }     
           // *pc++ = *pa++;     
            pa++;   
        }     
        else  
        {     
            *pe++ = *pb;     
            Le.length++;     
          //  *pc++ = *pb++;     
            pb++;   
        }     
    }     
    while(pa <= pa_last)     
    {     
        *pe++ = *pa;     
        Le.length++;     
        //*pc++ = *pa++;     
        pa++;   
    }     
        
    while(pb <= pb_last){     
        *pe++ = *pb;     
        Le.length++;     
       // *pc++ = *pb++;    
        pb++;   
    }     
}     
        
void MergeList_Sq2(SqList La,SqList Lb,SqList &Lc)     
{     
    int i,j;     
    Lc.length = 0;     
    Lc.listSize = La.length + Lb.length;     
    Lc.elem = (ElemType*)malloc(Lc.listSize*sizeof(ElemType));     
    int n = 0;     
    for(i = 0;i < La.length;i++){     
        j = 0;     
        while((j < Lb.length)&&(La.elem[i] != Lb.elem[j])){     
            j++;     
        }     
        if(j == Lb.length){     
            Lc.elem[n] = La.elem[i];     
            ++Lc.length; ++n;    
        }     
    }     
          
}     
        
        
void ListPrint_Sq(SqList L){      
    if(L.length==0) {      
        printf("\n");      
    }      
    else  
    {      
        for(int i=0;i<L.length;++i){      
            if(i==0){      
              printf("%d",L.elem[i]);      
            }      
            else{      
              printf(" %d",L.elem[i]);      
                }      
        }      
        printf("\n");      
    }      
}      
    
        
int main()     
{     
    int num,i;     
    scanf("%d",&num);     
    for(i = 1;i <= num;i++)     
    {     
        SqList La,Lb,Ld,Le,Lf,Lg;     
        InitList_Sq(La);     
        InitList_Sq(Lb);     
    
        int na,nb;     
        scanf("%d",&na);    
        CreateList(La,na);   
        scanf("%d",&nb);     
        CreateList(Lb,nb);   
  
        MergeList_Sq(La,Lb,Ld,Le);   
        MergeList_Sq2(La,Ld,Lf);     
        MergeList_Sq2(Lb,Ld,Lg);     
        printf("Case #%d:\n",i);     
        //ListPrint_Sq(Lc);     
        ListPrint_Sq(Ld);     
        ListPrint_Sq(Le);     
        ListPrint_Sq(Lf);     
        ListPrint_Sq(Lg);     
        
    }     
        
    return 0;     
}
点击复制链接 与好友分享!回本站首页
上一篇:C语言的函数指针数组
下一篇:c语言链表,头插法和尾插法
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站