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

线性表班级：计算机11-3班 学号：11034050333姓名：曲玉昆 成绩：_实验四 集合的交、并和差运算的实现1. 问题描述用有序单链表表示集合，实现集合的交、并和差运算。2. 基本要求 对集合中的元素，用有序单链表进行存储； 实现交、并、差运算时，不另外申请存储空间； 充分利用单链表的有序性，算法有较好的时间性能。3. 设计思想 首先，建立两个带头结点的有序单链表表示集合A和B。单链表的结点结构和建立算法请参见教材，需要注意的是：利用头插法建立有序单链表，实参数组应该是降序排列。 其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。 根据集合的运算规则，集合中包含所有既属于集合A又属于集合B的元素。因此，需查找单链表A和B中的相同元素并保留在单链表A中。算法如下： void Interest(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; else if (p-dataq-data) q=q-next; else p=p-next; q=q-next; 求集合的交集算法 根据集合的运算规则，集合中包含所有或属于集合A或属于集合B的元素。因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x不相同的元素，则将该结点插入到单链表A中。算法请参照求集合的交集自行设计。 根据集合的运算规则，集合A-B中包含所有属于集合A而不属于集合B的元素。因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x相同的结点，则将该结点从单链表A中删除。算法请参照求集合的交集自行设计。 templatestruct NodeT data;Node*next;template class LinkListpublic:LinkList(T a,int n);/建立有n个元素的单链表LinkList();void Interest(Node *A, Node *B);/求交集void Sum(Node *A,Node *B);/void Subtraction(Node *A,Node *B);void PrintList();void Show(int i);Node *first;templateLinkList:LinkList(T a,int n)Node*s;first = new Node;first-next=NULL;for(int i=0;in;i+)s = new Node;s-data=ai;s-next=first-next;first-next=s;template LinkList:LinkList()Node *p,*q;p = first;/工作指针p初始化while(p) /释放单链表的每一个结点的存储空间q = p;/暂存被释放结点p = p-next;/工作指针p指向被释放结点的下一个结点，使单链表不断开delete q;templatevoid LinkList:Interest(Node *A,Node *B)Node *pre,*p,*q;pre = A;p =A -next;q = B-next;while(p&q)if(p-data data)pre-next = p-next;p = pre-next;else if(p-data q-data)q = q-next;elsepre = p;p = p-next;q = q-next;/求并集templatevoid LinkList:Sum(Node *A,Node *BNode *pre,*p,*q;pre = A; p = A-next; q = B-next;while(p&q)if(p-data data)pre = p;p = p-next;else if(p-data q-data)q = q-next;elsepre-next = p-next;p = p-next;q = q-next;templatevoid LinkList: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-data data)pre = p;p = p-next;else if(p-data q-data)q = q-next;elsepre-next = p-next;p = pre-next;q = q-next;templatevoid LinkList:PrintList()Node *p;p=first-next;/工作指针p初始化while(p != NULL)/遍历输出所有元素coutdata;p = p-next;coutendl;/菜单函数int meun()int m;docout请输入对应数字(1、求交集2、求并集3、求差集4、结束运行)m;while(m4);return m;int a=5,4,3,2,1,b=6,4,2;int n = 5,m = 3;LinkList SL(a,n);LinkList sl(b,m);LinkList s(a,n);LinkList S(b,m);LinkList l(a,n);LinkList L(b,m);staticbool bl = true;templatevoid LinkList:Show(int i)switch(i)case 1:Node *p,*q;p = SL.first; q = sl.first;SL.PrintList();sl.PrintList();SL.Interest(p,q);SL.PrintList();coutendl;cout已求交集endl;break;case 2:Node *p,*q;p = s.first;q = S.first;s.PrintList();S.PrintList();s.Sum(p,q);s.PrintList();S.PrintList();cout已求并集endl;break;case 3:Node *p,*q;p = l.first;q = L.first;l.PrintList();L.