用有序单链表表示集合，实现集合的交、并、差运算 基本要求： 空间复杂度为 O(1)
二、课程设计内容及要求
集合的交、并和差运算的实现
问题描述：用有序单链表表示集合，实现集合的交、并、差运算
基本要求： 空间复杂度为 O(1)
系统功能模块
4.1输出和销毁函数设计
void DispList(LinkList*L)
{
LinkList *p=L->next;
while(p!=NULL)
{
cout<<"%c “,p->data;
p=p->next;
}
cout<<”\n";
}
void DestroyList(LinkList &L)
{
LinkListp=L->next,*pre=L;
while(p!=NULL)
{
free(pre);
pre=p;
p=pre->next;
}
free(pre);
}
4.2尾插法建立单链表设计流程图
P
L1
4.3有序单链表算法设计分析
有序表中的操作要充分利用线性表的有序性。在一个有序单链表中插入一个元素值为小的结点，使插入后单链表任然有序。分析：先建立一个带插入结点，然后依次与单链表中各结点的数据域比较大小，找到该结点的插入位置，最后插入该结点。
思路流程图：(P指向L的第二个数据结点，构造有序表只含一个数据结点。)
4.4主要功能的代码详细设计
4.4.1实现集合A和集合B的并集
void Union(LinkList ha,LinkListhb,LinkList*&hc)
{
LinkList *pa=ha->next,*pb=hb->next,*pc,s;
hc=new LNode;
pc=hc;
while(pa!=NULL &&pb!=NULL )
{
if(pa->datadata)
{
s=new LNode;
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
}
else if(pa->data>pb->data)
{
s=new LNode;
s->data=pb->data;
pc->next=s;
pc=s;
pb=pb->next;
}
else{
s=new LNode;
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
pb=pb->next;
}
}
if(pb!=NULL)
pa=pb;
while(pa!=NULL)
{
s=new LNode;
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
}
pc->next=NULL;
}
4.4.2实现集合A和集合B的交集
void InterSect(LinkList ha,LinkListhb,LinkList&hc)
{
LinkList *pa=ha->next,*pb,*pc,s;
hc=new LNode;
pc=hc;
while(pa!=NULL)
{
pb=hb->next;
while(pb!=NULL&&pb->datadata)
pb=pb->next;
if(pb!=NULL &&pb->data==pa->data)//B节点在A节点中复制A节点
{
s=new LNode;
s->data=pa->data;
pc->next=s;
pc=s;
}
pa=pa->next;
}
pc->next=NULL;
}
4.4.3实现集合A和集合B的差集
void Subs(LinkList ha,LinkListhb,LinkList&hc)
{
LinkList *pa=ha->next,*pb,*pc,*s;
hc=new LNode;
pc=hc;
while(pa!=NULL)
{
pb=hb->next;
while(pb!=NULL&&pb->datadata)
pb=pb->next;
if(!(pb!=NULL &&pb->data==pa->data))///B节点不在A节点中复制A节点
{
s=new LNode;
s->data=pa->data;
pc->next=s;
pc=s;
}
pa=pa->next;
}
pc->next=NULL;
}
4.5主函数测试详细设计
int main()
{
LinkList *ha,*hb,*hc;
int n,k;
while(1)
{
cout<<"\n\t\t —集合的简单运算—\n\n";
cout<<"\t\t\t 菜单 \n";
cout<<"\t\t\t ——— ————— ——\n";
cout<<"\t\t\t 1. 请输入A集合个数与A集合的元素 \n";
cout<<"\t\t\t 2. 请输入B集合个数与B集合的元素 \n";
cout<<"\t\t\t 3. A集合的有序集合 \n";
cout<<"\t\t\t 4. B集合的有序集合 \n";
cout<<"\t\t\t 5. AB集合的并集 \n";
cout<<"\t\t\t 6. AB集合的交集 \n";
cout<<"\t\t\t 7. AB集合的差集 \n";
cout<<"\t\t\t 8. 退出 \n";
cout<<"\t\t\t ———————————\n";
cout<<"\t\t\t 请选择(1-8):";
cin>>k;
switch(k)
{
case 1: cout<<“请输入A集合的个数与A集合元素：”;
cin>>n;
CreateList_L1(ha,n);break;
case 2:cout<<“请输入B集合的个数与B集合元素”;
cin>>n;
CreateList_L1(hb,n); break;
case 3:sort(ha);cout<<"\n A的有序集合为：";
DispList(ha);break;
case 4:sort(hb);cout<<"\n B的有序集合为：";
DispList(hb);break;
case 5:Union(ha,hb,hc);cout<<"\n AB集合的并集为：";
DispList(hc);break;
case 6:InterSect(ha,hb,hc);cout<<"\n AB集合的交集为：";
DispList(hc);break;
case 7:Subs(ha,hb,hc);cout<<"\n AB集合的差集为：";
DispList(hc);break;
case 0: cout<<"\n\t\t\t------ 谢谢使用！-------\n";
cout<<"\n\t\t\t按任意键退出…\n";
return 0;
}
}
DestroyList(ha);
DestroyList(hb);
DestroyList(hc);
return 0;
}
5调试分析：
调试程序中出现的问题出现了错误，先掌握molloc函数的用法，利用molloc函数在申请新的内存时，当无法知道内存具体位置时，想要绑定真正的内存空间，就会利用到molloc函数。改正错误，直接用new来创建一个新的结点(例如：s=new LNode)
改正错误，直接用new来创建一个新的结点(例如：s=new LNode;)调试程序合适。
6用户使用说明：
功能序号 菜单功能
1 输入集合A的个数和元素
2 输入集合B的个数和元素
3 A集合排序
4 B集合排序
5 AB集合的并集
6 AB集合的交集
7 AB集合的差集
8 退出