集合的并集实现

缺乏、安全感 2022-07-16 13:27 167阅读 0赞

2016年7月13日08:01:03
        假设线性表La和Lb分别表示两个集合,利用线性表基本操作来实现新的集合
        ,A=AUB,即扩大线性表A,将线性表B中A所没有的元素插入到A表中.
        1.将顺序表进行初始化;
        2.将数组中的元素插入到对应的顺序表中,即创建顺序表;
        3.将创建的顺序表输出显示;
        4.遍历集合B,对集合中的每一个元素,都在集合A中进行查找,如果发现
         集合A中不存在,则将该元素插入到集合A中去,如果集合A中存在,则进行下一个元素
         的同样操作;

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #define listSize 100
    typedef int DataType;
    
    //线性表结构体类型定义
    typedef  struct 
    {
        DataType list[listSize];
        int length;
    }LIST;
    
    //函数前置声明
    void  initList(LIST * L);
    int   insertList(LIST * L,int i,DataType  e);
    void createList(LIST * L,DataType * pArr,int len);
    void  traverseList(LIST * L);
    int   getElem(LIST * La, int pos, int * e);
    int   locateElem(LIST * L, DataType e);
    void  addElem(LIST * La, LIST * Lb);
    
    
    //初始化线性表
    void  initList(LIST * L)
    {
        L->length = 0;
    }
    
    
    //顺序表的建立
    void createList(LIST * L,DataType * pArr,int len)
    {
        int i ;
        for(i = 0;i<len;i++)
        {
            if(0 == insertList(L,i+1,pArr[i]))
            {
                printf("位置不合法 !\n");
                return;
            }
        }
        return ;
    }
    
    //顺序表中元素的插入
    int  insertList(LIST * L ,int pos, DataType  e)
    {
        int i;
        //判断线性表是否为满,如果为满,返回0;
        if(L->length==listSize)
        {
            printf("顺序表已满,不能继续插入元素!\n");
            return -1;
        }
        //判断插入元素的位置i-1是否合法
        else if(pos<1||pos>L->length+1)
        {
            printf("插入元素的位置不合适!\n");
            return 0;
        }
        else
        {
            for(i = L->length;i>=pos;i--)
            {
                L->list[i] = L->list[i-1];
            }
            L->list[pos-1] = e;
            L->length ++;
            return 1;
        }
    }
    
    //根据元素的位置查找元素,若存在,则将该元素的值保存到e,并返回1,如果不存在则返回0;
    int   getElem(LIST * La, int pos, int * e)
    {
        if(pos<1||pos>La->length)   //首先判断需要查找元素的位置是否合法:1<=pos<=L->length;
        {
            printf("元素的位置不合适:\n");
            return 0;
        }
        *e = La->list[pos-1];
        return 1;
    }
    
    //根据元素的内容查找元素,如果存在返回该元素的下标,不存在返回-1;
    int   locateElem(LIST * L, DataType e)
    {
        int i;
        for(i = 0;i< L->length;i++)
        {
            if(e == L->list[i])
            {
                return i;
            }   
        }
        return -1;
    }
    
    //求两个集合的并集
    void addElem(LIST * La,LIST * Lb)
    {
        int i;
        int * e;
        for(i = 0;i<Lb->length;i++)
        {
            if(locateElem(La,Lb->list[i])==-1)
            {
                insertList(La,La->length+1,Lb->list[i]);
            }
        }
    
    }
    
    //顺序表元素的遍历
    void traverseList(LIST * L)
    {
        int i ;
        for( i = 0;i<L->length;i++)
        {
            printf("%d ",L->list[i]);
        }
        printf("\n");
        return;
    }
    
    //主函数
    int main(void)
    {   
        int a[] = {
       2,3,17,20,9,31};
        int b[] = {
       8,31,5,17,22,9,48,67};
        LIST La,Lb ;
        initList(&La);
        initList(&Lb);
        createList(&La,a,sizeof(a)/sizeof(a[0]));
        createList(&Lb,b,sizeof(b)/sizeof(b[0]));
        printf("集合A中的元素为:\n");
        traverseList(&La);
        printf("集合B中的元素为:\n");
        traverseList(&Lb);
        addElem(&La,&Lb);
        printf("集合A与集合B的并集为:\n");
        traverseList(&La);
        return 0;
    }