以下讨论：当以有序表表示集合时，如何利用上述定义的有序链表类型的操作进行集合的并、交、差运算。
例2-12 假设以两个有序表分别表示集合A和B，试求集合C=A∪B。算法的基本思想为：顺序考察有序表A和B，比较当前考察的元素
和 
，将两者之中值"较小"者插入到C表中。解题分析：
假设在解题过程中，已由有序表
A =(
,
…, 
,
,
…, 
) 和B =(
,
…, 
,
,
…, 
)求得有序表
C =(
,
…, 
)当前C中所含元素是A的子集{
,
…, }和B的子集{
,
…,
}的并集，那么下一个插入到有序表C中的元素应该是哪一个呢？显然，
例如：假设
A = {3, 5, 6, 8, 9}
B = {2, 4, 5, 8, 10}
则 C = {2, 3, 4, 5, 6, 8, 9, 10}
算法2.26void union ( OrderLinkList A, OrderLinkList B, OrderLinkList &C )
{
// 已知有序链表 A 和 B 分别表示两个集合，
// 本算法求得有序链表 C 中所含元素是 A 和 B 的并集
if ( InitList(C) ) // 初始化建空表
{
m = ListLength(A); n = Listlength(B); // 分别求得表长
i = 1; j = 1;
while ( i <= m || j <= n ) // 顺序考察表中元素
{
只在存储分配失败时才会出现"FALSE"的情况。
{ // 两个表中都还有元素未曾考察到
GetCurElem(A,ea); GetCurElem(B,eb );
if ( ea <= eb )
{ // 插入和
相同的元素 if ( !MakeNode( s,ea ) ) exit(1);
++i;
if ( ea == eb )
++j; // 舍弃B表中相同元素
}
<=
时将
插入到C表，并在相等时过滤掉
。{ // 插入和
相同的元素if ( !MakeNode( s,eb ) ) exit(1);
++j;
}
}//if
else if ( GetPos(A,i) ) // A表中尚有元素未曾插入
{
GetCurElem( A,ea );
if ( !MakeNode( s,ea ) ) exit(1);
++i;
}//else
else // B表中尚有元素未曾插入
{
GetCurElem( B,eb );
if ( !MakeNode( s,eb ) ) exit(1);
++j;
}//else
InsAfter(C,s); // 插入到C表
}
} // union
算法时间复杂度为：O (Listlength(A)+ListLength(B))。
>
时将
插入到C表此时可能是(i>m)或者(j>n)。
|
|||
|
试设想，如果不是以有序表表示集合，而是以线性表表示集合，那么求集合并的算法时间复杂度该是什么？
|
|||
|