数据结构】第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;
}
四、实验结果
五、实验讨论
（1）熟悉了C++的上机环境，进一步掌握C++的结构特点；
（2）掌握了求两个集合LA和LB(用单链表表示)的并和交集的方法。
更多推荐
【数据结构】第2章 线性表 实验4：求两个集合LA和LB(用单链表表示)的并和交集
发布评论