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

2016-12-30 19:45:56来源:作者:人点击

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

13 1 2 54 2 3 5 8

Sample Output

Case #1:2 51 2 3 5 813 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;     }

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台