今天聊一下数据结构 | 每日一练(44)

数据结构

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

——老子

1

每日一练

1.知 L1、L2 分别为两循环单链表的头结点指针,m,n 分别为 L1、L2 表中数据结点个数。要求设计一算法,用最快速度将两表合并成一个带头结点的循环单链表。

类似本题的另外叙述有:

(1)试用类 Pascal 语言编写过程 PROC join(VAR la:link; lb:link) 实现连接线性表 la 和

lb(lb 在后)的算法,要求其时间复杂度为 0(1), 占用辅助空间尽量小。描述所用结构。

(2)设有两个链表,ha 为单向链表,hb 为单向循环链表。编写算法,将两个链表合并成一个单向链表,要求算法所需时间与链表长度无关。

正确答案

ps:||代表注释

1.[题目分析]循环单链表L1和L2数据结点个数分别为m和n ,将二者合成一个循环单链表时,需要将一个循环链表的结点(从第一元素结点到最后一个结点)插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“,因此应找结点个数少的链表查其尾结点。

LinkedList Union(LinkedList L1,L2; int m,n)∥L1和L2分别是两循环单链表的头结点的指针,m和n分别是L1和L2的长度。

∥本算法用最快速度将L1和L2合并成一个循环单链表。

{ if(m<0||n<0) {printf(“表长输入错误\n”);exit(0);}

if(m<n) ∥若m<n,则查L1循环单链表的最后一个结点。

{ if(m==0) return(L2);∥L1为空表。

else{p=L1;

while(p->next!=L1) p=p->next;∥查最后一个元素结点。

p->next=L2->next;∥将L1循环单链表的元素结点插入到L2的第一元素结点前。

L2->next=L1->next;

free(L1);∥释放无用头结点。

}

}∥处理完m<n情况

else∥ 下面处理L2长度小于等于L1的情况

{ if(n==0) return(L1);∥L2为空表。

else{p=L2;

while(p->next!=L2) p=p->next;∥查最后元素结点。

p->next=L1->next;∥将L2的元素结点插入到L1循环单链表的第一元素结点前。

L1->next=L2->next;

free(L2);∥释放无用头结点。

}

}∥算法结束。

类似本题叙述的其它题解答如下:

(1)[题目分析]本题将线性表la和lb连接,要求时间复杂度为O(1),且占用辅助空间尽量小。应该使用只设尾指针的单循环链表。

LinkedList Union(LinkedList la,lb)

∥la和lb是两个无头结点的循环单链表的尾指针,本算法将lb接在la后,成为一个单循环链表。

{ q=la->next; ∥q指向la的第一个元素结点。

la->next=lb->next; ∥将lb的最后元素结点接到lb的第一元素。

lb->next=q; ∥将lb指向la的第一元素结点,实现了lb接在la后。

return(lb); ∥返回结果单循环链表的尾指针lb。

}∥算法结束。

[算法讨论]若循环单链表带有头结点,则相应算法片段如下:

q=lb->next; ∥q指向lb的头结点;

lb->next=la->next; ∥lb的后继结点为la的头结点。

la->next=q->next; ∥la的后继结点为lb的第一元素结点。

free(q); ∥释放lb的头结点

return(lb); ∥返回结果单循环链表的尾指针lb。

(2)[题目分析]本题要求将单向链表ha和单向循环链表hb合并成一个单向链表,要求算法所需时间与链表长度无关,只有使用带尾指针的循环单链表,这样最容易找到链表的首、尾结点,将该结点序列插入到单向链表第一元素之前即可。其核心算法片段如下(设两链表均有头结点)

q=hb->next; ∥单向循环链表的表头指针

hb->next=ha->next; ∥将循环单链表最后元素结点接在ha第一元素前。

ha->next=q->next; ∥将指向原单链表第一元素的指针指向循环单链表第一结点

free(q); ∥释放循环链表头结点。

若两链表均不带头结点,则算法片段如下:

q=hb->next; ∥q指向hb首元结点。

hb->next=ha; ∥hb尾结点的后继是ha第一元素结点。

ha=q; ∥头指针指向hb的首元结点。

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

-end-

正文完