第二章 线性表(14)

else

{r=pb->next; ∥ 将pb 的后继结点暂存于r pb->next=la->next; ∥将pb结点链于结果表中，同时逆置 la->next=pb;

pb=r; ∥恢复pb为当前待比较结点 }

if(pa) pb=pa; ∥避免再对pa写下面的while语句 while(pb!=null)

{r=pb->next; pb->next=la->next; la->next=pb; pb=r; } }∥算法Union结束

43

［算法讨论］上面两链表均不为空的表达式也可简写为while(pa&&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后while语句将尚未到尾的表逆置到结果表中。

21．已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学 2001 六（10分）】 [题目分析]本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下：

pa=la->next;pb=lb->next;∥设工作指针pa和pb；

pc=la; ∥结果表中当前合并结点的前驱的指针 while(pa&&pb)

if(pa->data==pb->data)∥交集并入结果表中 { pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next;free(u); }

else if(pa->datadata) {u=pa;pa=pa->next;free(u);} ∥释放结点空间 else {u=pb; pb=pb->next; free(u);}

while(pa){ u=pa; pa=pa->next; free(u);}∥释放结点空间 while(pb) {u=pb; pb=pb->next; free(u);}∥释放结点空间 pc->next=null;∥置链表尾标记。

free(lb); ∥注： 本算法中也可对B表不作释放空间的处理

22．己知两个线性表A ，B均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A与B的交集C，要求C另开辟存储空间，要求C同样以元素值的递增序的单链表形式存贮。【西北大学 2000 五 ( 8分)】 [题目分析]本题要求结果表要另辟空间。 LinkedList Union(LinkedList A,B)

∥线性表A和B以带头结点的单链表作为存储结构。本算法求A和B的交集C，C另辟空间

{pa=A->next;pb=B->next;∥pa、pb是两链表的工作指针

pc=C=(LinkedList)maloc(sizeof(LNode)); pc->data=MaxElemType ∥监视哨

while(pa&&pb)

if(pa->datadata) pa=pa->next; ∥pa指针后移 else if(pa->data>pb->data) pb=pb->next; ∥pb指针后移 else ∥处理交集元素

if(pc->data==pa->data){pa=pa->next;pb=pb->next;} ∥删除重复元素 else{ p=(LinkedList)maloc(sizeof(LNode)); p->data=pa->data; pc->next=p;pc=p;

pa=pa->next;pb=pb->next; } ∥交集元素并入结果表

pc->next=null; ∥置结果链表尾 return C;}

44

23．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学 2000 四.2（4分）】

[题目分析]带头结点的链表分解为数据值小于0和大于0的两个链表，其类C算法如下。

void DisCreat1(LinkedList A)

∥本算法将带头结点的单链表A分解成数据域值小于零和大于零的两个单链表B和C

{B=A;

C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间 C->next=null ∥C初始化为空表 p=A->next; ∥p为工作指针 B->next=null; ∥B表初始化 while(p!=null)

{r=p->next; ∥暂存p的后继 if(p->data<0)∥小于0的放入B表

{p->next=B->next; B->next=p; }∥将小于0的结点链入B表 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点 }

}∥算法结束

[算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素之前）。另外，表C中包括值为0的结点。 24．试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist &L） 【北京理工大学2001九.3(8分)】

[题目分析]在单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。 LinkedList Delete（LinkedList L）

∥L是带头结点的单链表，本算法删除其最小值结点

{p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空 pre=L； ∥pre指向最小值结点的前驱

q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点 while（p->next）

{if（p->next->datadata）{pre=p；q=p->next；} ∥查最小值结点 p=p->next； ∥指针后移 }

pre->next=q->next；∥从链表上删除最小值结点 free（q）；return L;∥释放最小值结点空间 }∥结束算法delete

[算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void delete（linklist &L），是按C++的“引用”来写的，目的是实现变量的“传

45