知识分享 – 数据结构 | 每日一练(43)

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1. 带头结点且头指针为 ha 和 hb 的两线性表 A 和 B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求 A 和 B 的并集 AUB。要求该并集中的元素仍保持递增有序。且要利用 A 和 B 的原有结点空间。

类似本题的另外叙述有:

(1) 已知递增有序的两个单链表 A,B 分别存储了一个集合。设计算法实现求两个集合的并集的运算 A:=A∪B

(2)已知两个链表 A 和 B 分别表示两个集合,其元素递增排列。编一函数,求 A 与 B 的交集,并存放于A 链表中。

(3)设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法(即 L1∩L2)。要求结果链表仍是从小到大排序,但无重复元素。

(4)己知两个线性表 A ,B 均以带头结点的单链表作存储结构,且表中元素按值递增有序排列。设计算法求出 A 与 B 的交集 C,要求 C 另开辟存储空间,要求 C 同样以元素值的递增序的单链表形式存贮。

(5)已知递增有序的单链表 A,B 和 C 分别存储了一个集合,设计算法实现 A:=A∪(B∩C),并使求解结构 A 仍保持递增。要求算法的时间复杂度为 O(|A|+|B|+|C|)。其中,|A|为集合 A 的元素个数。

正确答案

ps:||代表注释

1.[题目分析]本组题有6个,本质上都是链表的合并操作,合并中有各种条件。与前组题不同的是,叙述上是用线性表代表集合,而操作则是求集合的并、交、差(A∪B,A∩B,A-B)等。本题与上面1.(2)基本相同,不同之处1.(2)中链表是“非递减有序”,(可能包含相等元素),本题是元素“递增有序”(不准有相同元素)。因此两表中合并时,如有元素值相等元素,则应删掉一个。

LinkedList Union(LinkedList ha,hb)∥线性表A和B代表两个集合,以链式存储结构存储,元素递增有序。ha和hb分别是其链表的头指针。本算法求A和B的并集A∪B,仍用线性表表示,结果链表元素也是递增有序。

{ pa=ha->next;pb=hb->next;∥设工作指针pa和pb。

pc=ha;∥pc为结果链表当前结点的前驱指针。

while(pa&&pb)

if(pa->data<pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}

else if(pa->data>pb->data)

{pc->next=pb;pc=pb;pb=pb->next;}

else∥处理pa->data=pb->data.

{pc->next=pa;pc=pa;pa=pa->next;

u=pb;pb=pb->next;free(u);}

if(pa) pc->next=pa;∥ 若ha表未空,则链入结果表。

else pc->next=pb;∥若hb表未空,则链入结果表。

free(hb); ∥释放hb头结点

return(ha);

}∥算法Union结束。

与本题类似的其它几个题解答如下:

(1) 解答完全同上2。

(2) 本题是求交集,即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下:

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->data<pb->data) {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表不作释放空间的处理

(3)本题基本与(2)相同,但要求无重复元素,故在算法中,待合并结点数据要与其前驱比较,只有在与

前驱数据不同时才并入链表。其核心语句段如下。

pa=L1->next;pb=L2->next;∥pa、pb是两链表的工作指针。

pc=L1;∥L1作结果链表的头指针。

while(pa&&pb)

if(pa->data<pb->data) {u=pa;pa=pa->next;free(u);}∥删除L1表多余元素

else if (pa->data>pb->data) pb=pb->next; ∥pb指针后移

else ∥处理交集元素

{ if(pc==L1) {pc->next=pa;pc=pa;pa=pa->next;} ∥处理第一个相等的元素。

else if(pc->data==pa->data){ u=pa;pa=pa->next;free(u);} ∥重复元素不进入L1表。

else{ pc->next=pa;pc=pa;pa=pa->next;} ∥交集元素并入结果表。

} ∥ while

while(pa) {u=pa;pa=pa->next;free(u);} ∥ 删L1表剩余元素

pc->next=null; ∥置结果链表尾。

注: 本算法中对L2表未作释放空间的处理。

(4) 本题与上面(3)算法相同,只是结果表要另辟空间。

(5) [题目分析]本题首先求B和C的交集,即求B和C中共有元素,再与A求并集,同时删除重复元素,以保持结果A递增。

LinkedList union(LinkedList A,B,C)

∥A,B和C均是带头结点的递增有序的单链表,本算法实现A= A∪(B∩C),使求解结构保持递增有序。

{pa=A->next;pb=B->next;pc=C->next;∥设置三个工作指针。

pre=A; ∥pre指向结果链表中当前待合并结点的前驱。

if(pa->data<pb->data||pa->data<pc->data)∥A中第一个元素为结果表的第一元素。

{pre->next=pa;pre=pa;pa=pa->next;}

else{ while(pb&&pc) ∥找B表和C表中第一个公共元素。

if(pb->data<pc->data)pb=pb->next;

else if(pb->data>pc->data)pc=pc->next;

else break; ∥找到B表和C表的共同元素就退出 while循环。

if(pb&&pc)∥ 因共同元素而非B表或C表空而退出上面 while循环。

if(pa->data>pb->data)∥A表当前元素值大于B表和C表的公共元素,先将B表元素链入。

{pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}∥ B,C公共元素为结果表第一元素。

}∥结束了结果表中第一元素的确定

while(pa&&pb&&pc)

{ while(pb&&pc)

if(pb->data<pc->data) pb=pb->next;

else if(pb->data>pc->data) pc=pc->next;

else break; ∥B表和C表有公共元素。

if(pb&&pc)

{ while(pa&&pa->data<pb->data) ∥先将A中小于B,C公共元素部分链入。

{pre->next=pa;pre=pa;pa=pa->next;}

if(pre->data!=pb->data){pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}

else{pb=pb->next;pc=pc->next;}∥ 若A中已有B,C公共元素,则不再存入结果表。

}

}∥ while(pa&&pb&&pc)

if(pa) pre->next=pa; ∥当B,C无公共元素(即一个表已空),将A中剩余链入。

}∥算法Union结束

[算法讨论]本算法先找结果链表的第一个元素,这是因为题目要求结果表要递增有序(即删除重复元素)。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始pre=A(头结点的头指针),这时的data域无意义,不能与后继比较元素大小,因此就需要确定第一个元素。当然,不要这样作,而直接进入下面循环也可以,但在链入结点时,必须先判断pre是否等于A,这占用了过多的时间。因此先将第一结点链入是可取的。算法中的第二个问题是要求时间复杂度为O(|A|+|B|+|C|)。这就要求各个表的工作指针只能后移(即不能每次都从头指针开始查找)。本算法满足这一要求。

最后一个问题是,当B,C有一表为空(即B和C已无公共元素时),要将A的剩余部分链入结果表。

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

-end-

正文完