数据结构（线性结构习题）Problem A: 求集合的交并补集

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;     
}