2. 考研
  3. 有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在A和B的原有结点空间上完成。要求： (1)给出算法的基

有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在A和B的原有结点空间上完成。要求： (1)给出算法的基

admin2019-08-01  16
问题 有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在A和B的原有结点空间上完成。要求：
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
    (3)分别给出算法各部分的时间复杂度。
选项
答案(1)算法的基本设计思想：分别从A、B的头结点开始，依次比较A、B中元素的内容，如果A中的元素值大于B中的元素值，则将B中的结点插入结果链表，反之将A中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果A、B中两个元素值相同，只将其中的一个加入结果链表。 (2)算法的设计如下： typedef struct LNode{ int data： struct LNode * next： } * Linkedlist； LinkedList Union(Linked List la，lb) { pa=la一>next； pb=lb一>next； ／／设工作指针pa和pb pc=la； ／／pc为结果链表当前结点的前驱指针 while(pa&&pb) { if(pa一>datadata) { 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； ／／若la表未空，则链入结果表 else pc->next=pb； ／／若lb表未空，则链入结果表 free(1b)； ／／释放lb头结点 return(1a)： } (3)本题中的主要操作是依次比较A、B链表中的数据元素值的大小，因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/8kCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)