// 结构定义
typedef struct LNode { // 结点结构
ElemType data;
struct LNode *next;
} *SLink;
讨论利用有序表表示集合并实现集合的并、交、差三种操作。
以链式存储结构表示有序表，首先定义一个有序链表类型。
typedef struct { // 链表结构
SLink head, // 指向有序链表中的头结点
tail, // 指向有序链表中最后一个结点
curPtr; // 指向操作的当前结点，称为"当前指针"
int length, // 指示有序链表的长度
curPos; // 指示当前指针所指结点的位序
} OrderedLinkList;
其中部分操作的伪码算法如下：
bool MakeNode( SLink &p, ElemType e )
{
// 生成一个数据元素和 e 相同的新结点 *p，并返回TRUE，
// 若存储分配失败，则返回 FALSE。
p = new LNode;
if (!p) return FALSE;
p->data = e; p->next = NULL;
return TRUE;
}
bool InitList( OrderedLinkList &L )
{
// 构造一个空的有序链表 L，若存储分配失败，
// L.head = NULL 并返回 FALSE，否则返回 TRUE。
if ( MakeNode( L.head, 0 ) )
{ L.tail = L.curPtr = L.head;
L.length= L.curPos = 0;
return TRUE; }
else
{ L.head = NULL;
return FALSE; }
} // InitList
bool GetPos (OrderedLinkList L, int pos )
{
// 若1≤pos≤LengthList(L)，则移动当前指针指向第pos个结点,
// 且返回函数值为TRUE,否则不移动当前指针且返回函数值为FALSE。
if ( pos < 1 || pos > L.len )
return FALSE;
if ( L.curPos > pos )
{ L.curPtr = L.head -> next; L.curPos = 1; }
while ( L.curPos < pos )
{ L.curPtr = L.curPtr -> next; ++L.curPos; }
return TRUE;
}
bool LocateElem ( OrderedLinkList L, ElemType e,
int ( *compare )( ElemType, ElemType ) )
{
// 若有序链表L中存在和e相同的数据元素，则当前指针指向第1个
// 和e相同的结点，并返回 TRUE，
// 否则当前指针指向第一个大于e 的元素的前驱，并返回FALSE。
L.current = L.head; L.curPos = 0;
while ( L.current -> next &&
compare( e,L.current -> next -> data )> 0 )
{
L.current = L.current -> next; // 指针后移，继续查询
L.curPos ++;
}
if ( L.current -> next &&
compare( e,L.current -> next -> data ) == 0 )
{ // 查到和 e 相同元素，当前指针后移
L.current = L.current -> next; L.curPos ++;
return TRUE;
}
else return FALSE; // 当前指针所指后继元素大于 e
} // LocateElem
void InsAfter ( LinkList &L, SLink s )
{
// 在有序链表L中当前指针所指结点之后插入一个新的结点 *s，
// 并移动当前指针指向新插入的结点。
L.curPtr -> next = s;
if ( L.tail == L.curPtr )
L.tail = s; // 若新结点插入在尾结点之后，则修改尾指针
L.curPtr = s; ++L.curPos; // 移动当前指针
++L.length; // 表长增 1
}
bool DelAfter( LinkList &L, ElemType& e )
{
// 若当前指针所指非单链表L中最后一个结点，
// 则删除当前指针所指结点之后的结点，以 e 带回它的数据元素
// 并返回 TRUE，否则不进行删除操作且返回 FALSE。
//若当前指针已经指向最后一个结点，它没有后继，因此不能进行删除。
if ( L.curPtr == L.tail )
return FALSE;
p = L.curPtr -> next; e = p -> data;
L.curPtr -> next = p -> next; // 修改当前结点的指针
if ( L.tail == p )
L.tail = L.curPtr; // 删除尾结点时修改尾指针
delete p; // 释放被删结点
--L.length; // 表长减1
return TRUE;
} // DelAfter
void 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 ) // 顺序考察表中元素
{
if ( GetPos(A,i) && GetPos(B,j) )
{ // 两个表中都还有元素未曾考察到
GetCurElem(A,ea); GetCurElem(B,eb );
if ( ea <= eb )
{ // 插入和 相同的元素
if ( !MakeNode( s,ea ) ) exit(1);
++i;
if ( ea == eb )
++j; // 舍弃B表中相同元素
}
else
{ // 插入和 相同的元素
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
void Intersection (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 ) // 顺序考察表中元素
{
if ( GetPos(A,i) && GetPos(B,j) )
{ // 两个表中都还有元素未曾考察
GetCurElem( A,ea ); GetCurElem( B,eb );
if ( ea < eb ) ++i;
else if ( ea > eb ) ++j;
else
{ // 插入和 相同的元素
if ( !MakeNode( s,ea ) ) exit(1);
++i;++j;
InsAfter(C,s);
} // else
} // if
} // while
} // if
} // Intersection
