单链表的交并补1

单链表的交并补

1. 需求分析

任意给定两个包含10-2000个元素的集合A,B（集合中元素类型为任意整型数），求这两个集合的交集、并集和补集。

单链表合并，时间复杂度O(m*n))，空间复杂度O(n) 2. 概要设计

首先设计程序的设计结构用来表示集合

//线性表的单链表存储结构

typedefstructLNode{ char data;

structLNode*next; }LNode,*LinkList;

创建生成次集合的函数

voidCreateList_L(LinkList&L,int n)

以下是本程序的函数

void Bing(LinkListLa,LinkListLb,LinkList&Lc)//求并集

void Jiao(LinkListLa,LinkListLb,LinkList&Lc)//求交集 void Cha(LinkListLa,LinkListLb,LinkList&Lc)//求补集 void output(LinkList L)//输出元素

3. 详细设计

#include #include using namespace std; //线性表的单链表存储结构 typedefstructLNode{ char data; structLNode *next; }LNode,*LinkList;

voidCreateList_L(LinkList&L,int n) {

L=new LNode;

L->next=NULL; //先建立一个带头结点的单链表 for(int i=n;i>0;i--) {

LNode *p=new LNode; //生成新结点 cin>>p->data; //输入元素值

p->next=L->next;//插入到表头 L->next=p; } }

void Bing(LinkListLa,LinkListLb,LinkList&Lc)//求并集 { //把 La 与Lb的并集放在链表Lc中 Lc=new LNode; Lc->next=NULL; LNode *pa=La->next;

while(pa)//把集合La中的元素复制到集合Lc中 {

LNode *q=new LNode; q->data=pa->data; q->next=Lc->next; Lc->next=q;

pa=pa->next;//指向La的指针pa后移 }

LNode *pb=Lb->next;

while(pb) //如果集合b中元素不同于集合a中元素，就添加到集合c中 {

bool flag=true;//flag用来标记a,b中是否有相同元素 pa=La->next; while(pa) {

if(pa->data==pb->data)

{ flag=false; break; } else pa=pa->next; }

if(flag) { //元素不同 LNode *p=new LNode; p->data=pb->data; p->next=Lc->next; Lc->next=p; } pb=pb->next; } }

void Jiao(LinkListLa,LinkListLb,LinkList&Lc)//求交集 {

Lc=new LNode; Lc->next=NULL; LNode *pb=Lb->next;

while(pb) //如果元素即属于集合a又属于集合b,则把该元素放到集合c中 {

LNode *pa=La->next; while(pa) {

if(pa->data==pb->data) //有相同元素 { LNode *p=new LNode; p->data=pb->data; p->next=Lc->next; Lc->next=p; break;

}

else pa=pa->next;//没有继续后移 } pb=pb->next; } }

void Cha(LinkListLa,LinkListLb,LinkList&Lc) //求补集 {

Lc=new LNode; Lc->next=NULL; LNode *pa=La->next;

while(pa)//如果元素属于集合a不属于集合b,则把该元素放到集合c中 { bool flag=true; LNode *pb=Lb->next; while(pb) {

if(pb->data==pa->data)

{ flag=false; break; } elsepb=pb->next; }

if(flag) { //元素不属于b LNode *p=new LNode; p->data=pa->data; p->next=Lc->next; Lc->next=p; } pa=pa->next; } }

void output(LinkList L) //输出元素 {

LNode *p=L->next; while(p) {

cout<data<<\ p=p->next; } cout<

LinkListL,La,Lb,Lc; inti,n,a,b;

cout<<\请输入集合a的元素个数：\ cin>>a; cout<<\请输入集合a中的元素：\ CreateList_L(La,a); cout<<\请输入集合b的元素个数：\ cin>>b; cout<<\请输入集合b中的元素：\ CreateList_L(Lb,b);

cout<<\集合的并、交、差、补运算****************\cout<<\操作如下：1. a 并 b 2. a 交 b\cout<<\ 3. a 的补 4. b 的补\cout<<\ 5. 退出\while(1) {

cout<<\请选择操作：\cin>>i; switch(i) {

case 1: cout<<\并 b ：\

Bing(La,Lb,Lc); output(Lc); break;

case 2: cout<<\交 b ：\Jiao(La,Lb,Lc); output(Lc); break;

case 3: cout<<\的补：\ L=Lb; Cha(L,La,Lc); output(Lc); break;

case 4: cout<<\的补：\ L=La; Cha(L,Lb,Lc); output(Lc); break; case 5: exit(0); } cout<

4. 调试分析与用户界面与测试结果

总结;

单链表的交并补主要是对链表节点的基本操作，单链表基本操作包括链表初始化、插入、删除，其中初始化操作是指让单链表存在一个头结点，其数据域随机，头结点指向下一个结点，每次访问都要从头结点开始访问，插入结点方式有两种，尾部插入和结点前部插入，尾部插入很简单与正常的输入顺序一致，而前部插入需要时常变动头结点的指针，始终让他指向新插入的，因为如果不调整头指针的话，在输出时是无法从头结点往前访问的，所以它是单向链表。删除操作主要是定值查找删除，在链表里并不需要做什么删除操作，其实就是将前一结点指针指向目标节点的下一个结点位置，指针访问时直接跳跃，即可实现删除操作。

本文来源：https://www.bwwdw.com/article/dw5a.html