【数据结构】第2章线性表实验4：求两个集合LA和LB(用单链表表示)的并和交集

本文主要是介绍【数据结构】第2章线性表实验4：求两个集合LA和LB(用单链表表示)的并和交集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【单链表的初始化、表长、取值、查找、遍历、后插法（尾插法）创建、合并（并集、交集）】实验报告+完整代码

题目: 求两个集合LA和LB(用单链表表示)的并和交集

一、实验目的和要求

（1）熟悉C++的上机环境，进一步掌握C++的结构特点；
（2）掌握求两个集合LA和LB(用单链表表示)的并和交集的方法。

二、实验环境

Windows10, CodeBlocks.

三、实验内容及实施

【实验内容】
在实验2的基础上，使用单链表表示集合。编写两个算法（求交算法和求并算法），并输出最终的结果。
测试用例：集合A为{3，4，1，6}，集合A为{2，3，6，7}，交集为{3，6}，并集为{1，2，3，4，6，7}
【程序流程】
略
【源程序】

#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef int ElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1//-----单链表的储存结构-----
typedef struct LNode
{ElemType data;              //结点的数据域struct LNode *next;         //结点的指针域
}LNode, *LinkList;              //LinkList为指向结构体LNode的指针类型LinkList LA, LB, LC;//1、单链表初始化 O(1)
Status InitList(LinkList &L)
{//构造一个带头结点的空单链表LL = new LNode;              //生成新的结点作为头结点，用头指针L指向头结点L->next = NULL;             //头结点的指针域置空return OK;
}//5、单链表表长 O(n)
Status ListLength(LinkList L)
{//返回带头结点的单链表的长度LNode *p = L;                   //p指向头结点int j = 0;                      //计数器j初值赋为0while(p->next)                  //直到p的后继为空时停止{p = p->next;                //p指向下一个结点j++;                        //计数器j相应加1}return j;
}//6、单链表取值 O(n)
Status GetElem(LinkList L, int i, ElemType &e)
{//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个元素的值LNode *p = L->next;             //p指向首元结点int j = 1;                      //计数器j初值赋为1while(p && j < i)               //直到p为空或p指向第i个元素时停止{p = p->next;                //p指向下一个结点               j++;                        //计数器j相应加1                       }if(!p || j > i)                 //i值不合法，即i > n或i < 1return ERROR;e = p->data;                    //取第i个结点的数据域return OK;
}//7、单链表查找 O(n)
LNode *LocateElem(LinkList L, ElemType e)
{//在带头结点的单链表中查找值为e的元素，返回e的地址（所以LNode *LocateElem）LNode *p = L->next;             //p指向首元结点while(p && p->data != e)        //直到p为空或p所指结点的数据域等于e时停止p = p->next;                //p指向下一个结点return p;                       //查找成功返回值为e的结点地址p，查找失败p为NULL
}//10、单链表插入 O(n)
Status ListInsert(LinkList &L, int i, ElemType e)
{//在带头结点的单链表L中第i个位置插入值为e的新结点LNode *p = L;                   //p指向头结点int j = 0;                      //计数器j初值赋为0while(p && j < i - 1)           //直到p为空或p指向第i-1个结点时停止{p = p->next;                //p指向下一个结点j++;                        //计数器j相应加1}                               if(!p || j > i - 1)             //i值不合法，即i > n + 1或i < 1return ERROR;LNode *s = new LNode;           //生成新结点*ss->data = e;                    //将结点*s的数据域置为es->next = p->next;              //先接后链p->next = s;                    //再接前链return OK; 
}//12、单链表遍历 O(n)
Status TraverseList(LinkList L)
{LNode *p = L->next;             while(p->next){cout<<p->data<<' ';p = p->next;}cout<<p->data<<'\n';return OK;
}//14、后插法创建单链表 O(n)
void CreateList_R(LinkList &L, int n)
{//正位序输入n个元素的值，建立带头结点的单链表LL = new LNode;                  //先初始化一个带头结点的空链表L->next = NULL;                 LNode *r = L;                   //尾指针r先指向头结点for(int i = 0; i < n; i++){LNode *p = new LNode;       //生成新结点*pcin>>p->data;               //输入元素值赋给新结点*p的数据域p->next = NULL;             //后置空后链             r->next = p;                //再接前链r = p;                      //r指向新的尾结点*p}
}//16、单链表合并_求并集 O(m * n)
void MergeList(LinkList &LA, LinkList LB)
{//将所有在线性表LB中但不在LA中的数据元素插入到LA中int m = ListLength(LA), n = ListLength(LB);     //求线性表长度for(int i = 1; i <= n; i++) {ElemType e;GetElem(LB, i, e);                          //取LB中的第i个元素赋给eif(!LocateElem(LA, e))                      //LA中不存在与e相同的数据元素ListInsert(LA, ++m, e);                 //将e插在LA的最后，先++，再传值}
}//16、单链表合并_求交集 O(m * n)
void MixList(LinkList LA, LinkList LB, LinkList &LC)
{//将线性表LB中和LA中共有的数据元素插入到LC中int m = ListLength(LA), n = ListLength(LB);     //求线性表长度int k = 0;for(int i = 1; i <= n; i++) {ElemType e;GetElem(LB, i, e);                          //取LB中的第i个元素赋给eif(LocateElem(LA, e))                       //LA中存在与e相同的数据元素ListInsert(LC, ++k, e);                 //将e插在LC的最后，先++，再传值}
}//实验4：求两个集合LA和LB(用单链表表示)的并和交集
int main()
{int n;cout<<"请输入集合A的元素个数：";cin>>n;cout<<"请按顺序输入这"<<n<<"个元素：";CreateList_R(LA, n);cout<<"请输入集合B的元素个数：";cin>>n;cout<<"请按顺序输入这"<<n<<"个元素：";CreateList_R(LB, n);cout<<'\n';cout<<"集合A为：";TraverseList(LA);cout<<"集合B为：";TraverseList(LB);InitList(LC);MixList(LA, LB, LC);cout<<"A与B的交集为：";TraverseList(LC);MergeList(LA, LB);cout<<"A与B的并集为：";TraverseList(LA);return 0;
}