c/c++语言开发共享数据结构（线性结构习题）Problem A: 求集合的交并补集

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