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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607094.html