线性表表示集合

男娘i 2022-05-08 07:46 198阅读 0赞

集合我们高中都学过吧？

最重要的几个特点：元素不能重复、各个元素之间没有关系、没有顺序

集合内的元素可以是单元素或者是集合。

对集合的操作：交集并集差集等，还有对自身的加减等。

需要频繁的加减元素，所以顺序存储效率较低，但是我们还是说一下是怎么实现的：

用01向量表示集合，因为现实中任何一个有穷集合都能对应到一个0、1、2.....n这么一个序列中。所以可以对应过来，每位的01代表这个元素存在与否即可。

链接存储表示使用有序链表来实现，虽然集合是无序的，但是我们的链表可以是有序的。可以按升序排列。而链表理论上可以无限增加，所以链表可以表示无限集。

下面我们来实现一下：

我们定义一个节点：

typedef int ElemType;
    typedef struct SetNode{//节点定义
        ElemType data;//数据
        struct SetNode * link;
    }*LinkedSet//集合定义

然后要实现那些操作了，首先想插入吧：我们对于一个新元素，查找集合中是否存在，存在就不插入，不存在就插入到查找失败位置。

删除也简单，查找存在就删除。

我们说两个集合的操作：

求两个集合的并：

两个链表，都是升序。把他们去重合并即可。

其实和链表归并的merge过程是一样的，只是相等的时候插入一个，两个指针都向后走就行了。

我就再写一遍吧。

void UnionSet(LinkedSet & A,LinkedSet & B,LinkedSet & C)
    {
        SetNode *pa=A->link,*pb=B->link,*pc=C;
        while(pa && pb)//都不为空
        {
            if(pa->data==pb->data)//相等，插一次，两边向后
            {
                pc->link=new SetNode;
                pc->data=pa->data;
                pa=pa->link;
                pb=pb->link;
            }
            else if(pa->data<pb->data)//插小的，小的向后
            {
                pc->link=new SetNode;
                pc->data=pa->data;
                pa=pa->link;
            }
            else
            {
                pc->link=new SetNode;
                pc->data=pb->data;
                pb=pb->link;
            }
            pc=pc->link;//注意指针
        }
        if(pa)p=pa;//剩下的接上
        else p=pb;//只执行一个
        while(p)//依次复制
        {
            pc->link=new SetNode;
            pc->data=p->data;
            pc=pc->link;
            p=p->link;
        }
        pc->link=NULL;
    }

求两个集合的交，更简单，还是这三种情况，谁小谁向后，相等才插入。

求两个集合的差：高中可能没学这个概念，其实就是A-B，就是B中的元素，A都不能有了。

运算你可以把B元素全过一遍，A中有就去掉，但是这样时间复杂度太高了，我们需要O(A+B)而不是O(A\*B)

因为有序，很好操作，还是两个指针，

如果AB相同，都向后移。

或者，B小，B就向后移。

如果A小，说明B中不含这个元素，我们把它复制到结果链表里。

思想还行，实在懒得写了，有时间再说吧。