集合的交、并和差运算的实现.doc

《集合的交、并和差运算的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班级：计算机11-3班学号：11034050333姓名：曲玉昆成绩：_________实验四集合的交、并和差运算的实现1.问题描述用有序单链表表示集合，实现集合的交、并和差运算。2.基本要求⑴对集合中的元素，用有序单链表进行存储；⑵实现交、并、差运算时，不另外申请存储空间；⑶充分利用单链表的有序性，算法有较好的时间性能。3.设计思想首先，建立两个带头结点的有序单链表表示集合A和B。单链表的结点结构和建立算法请参见教材，需要注意的是：利用头插法建立有序单链表，实参数组应该是降序排列。其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。⑴根据集合的运算规则，集合中包含所有既属

2、于集合A又属于集合B的元素。因此，需查找单链表A和B中的相同元素并保留在单链表A中。算法如下：voidInterest(Node*A,Node*B){//A、B分别是两个单链表的头指针，最后的结果在单链表A中pre=A;p=A->next;q=B->next;while(p&&q){if(p->datadata){pre->next=p->next;p=pre->next;}elseif(p->data>q->data)q=q->next;else{p=p->next;q=q->next;}}}求集合的交集算法⑵根据集合的运算规则，集合中包含所有或属于集合A或属于集合B的元素。

3、因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x不相同的元素，则将该结点插入到单链表A中。算法请参照求集合的交集自行设计。⑶根据集合的运算规则，集合A-B中包含所有属于集合A而不属于集合B的元素。因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x相同的结点，则将该结点从单链表A中删除。算法请参照求集合的交集自行设计。templatestructNode{Tdata;Node*next;};templateclassLinkList{public:LinkList(Ta[],intn);//建立有n个元素的单链表~Lin

4、kList();voidInterest(Node*A,Node*B);//求交集voidSum(Node*A,Node*B);/voidSubtraction(Node*A,Node*B);voidPrintList();voidShow(inti);Node*first;};templateLinkList::LinkList(Ta[],intn){Node*s;first=newNode;first->next=NULL;for(inti=0;i;s->data=a

5、[i];s->next=first->next;first->next=s;}}templateLinkList::~LinkList(){Node*p,*q;p=first;//工作指针p初始化while(p)//释放单链表的每一个结点的存储空间{q=p;//暂存被释放结点p=p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开deleteq;}}templatevoidLinkList::Interest(Node*A,Node*B){Node*pre,*p,*q;pre=A;p=A->next

6、;q=B->next;while(p&&q){if(p->datadata){pre->next=p->next;p=pre->next;}elseif(p->data>q->data){q=q->next;}else{pre=p;p=p->next;q=q->next;}}}//求并集templatevoidLinkList::Sum(Node*A,Node*B{Node*pre,*p,*q;pre=A;p=A->next;q=B->next;while(p&&q){if(p->datadata){pre=p;p=p->next

7、;}elseif(p->data>q->data){q=q->next;}else{pre->next=p->next;p=p->next;q=q->next;}}}templatevoidLinkList::Subtraction(Node*A,Node*B){Node*pre,*p,*q,*pra;pre=A;pra=B;p=A->next;q=B->next;while(p&&q){if(p->da