文章目录
一、写在前面
数据结构线性表可以用来模拟集合，通过线性表的各种操作实现集合的基本运算。例如已知集合A和B，求A和B的并集A∪B。这里分无序集和有序集分别讨论。无论无序集和有序集，都可以用顺序表或者链表描述。下面是详细讨论。
二、无序集合求并集
1.用顺序表描述
/*-----合并顺序表La Lb-----*/
void mergeList(List &La, List &Lb)
{
for (int i=1; i<=Lb.length; ++i) //遍历Lb
{
ElemType e = Lb.elem[i-1]; //取出Lb中第i个元素
int j, k;
for (j=1; j<=La.length; ++j) //La中查找e 查到则跳出循环
if (e == La.elem[j-1]) break;
if (j == La.length+1) //如果不在La中
{
La.elem[j-1] = e; //在La表尾插入 e
++La.length;
}
}
}
2.用链表描述
/*-----合并链表La Lb-----*/
void mergeList(List &La, List &Lb)
{
List pa = La->next;
List pb = Lb->next;
List pre = Lb; //辅助指针
while (pb) //遍历Lb
{
while (pa->next && pa->data != pb->data) //pa未到达La表尾 La未找到与pb的值相等的结点
pa = pa->next; //La中查找与b相同的元素
if(pa->data != pb->data) //*p是表尾结点 pb链接pa后面
{
pre->next = pb->next; //临时保存结点*pb后继
pa->next = pb; //更新当前结点*pa后继为*pb
pb->next = NULL; //标记为表尾
pb = pre->next; //Lb工作指针后移
}
else //释放pb
{
pre->next = pb->next; //临时保存结点*pb后继
delete pb; //释放pb
pb = pre->next; //工作指针后移
}
pa = La->next; //pa回溯到首元结点 以备下一次查找
}
delete Lb; //释放Lb表头
}
三、有序集合求并集
1.用顺序表描述
/*-----合并非递减顺序表La Lb-----*/
void mergeList(List &La, List &Lb, List &Lc)
{
// 初始化
Lc.length = La.length+Lb.length; //新表长度为A、B之和
Lc.elem = new ElemType[Lc.length];
ElemType *pa = La.elem;
ElemType *pb = Lb.elem;
ElemType *pc = Lc.elem;
ElemType *pa_last = La.elem+La.length-1; //La表尾
ElemType *pb_last = Lb.elem+Lb.length-1; //Lb表尾
while (pa<=pa_last && pb<=pb_last) //La Lb均为到达表尾
{
if(*pa <= *pb) *pc++=*pa++;
else *pc++ = *pb++;
}
while (pa <= pa_last) *pc++=*pa++; //Lb先到达表尾 处理La剩余元素
while (pb <= pb_last) *pc++=*pb++; //La先到达表尾 处理Lb剩余元素
}
2.用链表描述
/*-----合并有序链表La Lb-----*/
void mergeList(List &La, List &Lb, List &Lc)
{
List pa = La->next;
List pb = Lb->next;
List pc = Lc = La;
List prea = La; //辅助指针 pa前驱
List preb = Lb; //辅助指针 pb前驱
while (pa && pb) //pa pb 均未到达表尾
{
if(pa->data <= pb->data)
{
cout << "正在插入" << pa->data <<endl;
pc->next = pa; //pa链接到pc表尾
pc = pc->next; //pc后移
pa = pa->next; //pa后移
}
else
{
cout << "正在插入" << pb->data <<endl;
pc->next = pb;
pc = pc->next; //pc后移
pb = pb->next; //pb后移
}
}
while (pa)
{
cout << "正在插入" << pa->data <<endl;
pc->next = pa; //pa链接到pc表尾
pc = pc->next; //pc后移
pa = pa->next; //pa后移
}
while (pb)
{
cout << "正在插入" << pb->data <<endl;
pc->next = pb;
pc = pc->next; //pc后移
pb = pb->next; //pb后移
}
delete Lb;
}
总结
| 无序集 | 有序集 | ||
| 时间复杂度 | 顺序表 | O(mn) | O(m+n) |
| 链表 | |||
| 空间复杂度 | 顺序表 | O(n) | |
| 链表 | O(1) | ||