数据结构 | 每日一练（64）

数据结构

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

——老子

1

每日一练

1．已知 L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。（要求用最少的时间和最少的空间）

正确答案

ps：||代表注释

1. [题目分析] 将一个结点数据域为字符的单链表，分解成含有字母字符、数字字符和其它字符的三个循环链表，首先要构造分别含有这三类字符的表头结点。然后从原链表第一个结点开始，根据结点数据域是字母字符、数字字符和其它字符而分别插入到三个链表之一的链表。注意不要因结点插入新建链表而使原链表断链。另外，题目并未要求链表有序，插入采用“前插法”，每次插入的结点均成为所插入链表的第一元素的结点即可。

void OneToThree（LinkedList L，la，ld，lo）∥L是无头结点的单链表第一个结点的指针，链表中的数据域存放字符。本算法将链表L分解成含有英文字母字符、数字字符和其它字符的带头结点的三个循环链表。

{la=（LinkedList）malloc（ sizeof（LNode））； ∥建立三个链表的头结点

ld=（LinkedList）malloc（ sizeof（LNode））；

lo=（LinkedList）malloc（ sizeof（LNode））；

la->next=la；ld->next=ld；lo->next=lo；∥置三个循环链表为空表

while（L!=null）∥分解原链表。

{r=L; L=L->next; ∥L指向待处理结点的后继

if（r->data>=‘a’&& r->data<=‘z’|| r->data>=‘A’&& r->data<=‘Z’）

{r->next=la->next； la->next=r；} ∥处理字母字符。

else if（r->data>=‘0’&& r->data<=‘9’）

{r->next=ld->next；ld->next=r；} ∥处理数字字符

else {r->next=lo->next；lo->next=r；} ∥处理其它符号。

}∥结束 while（L!=null）。

}∥算法结束

[算法讨论] 算法中对L链表中每个结点只处理一次，时间复杂度O（n），只增加了必须的三个表头结点，符合题目“用最少的时间和最少的空间”的要求。

转发朋友圈，点下“在看”就是对小编的最大帮助！

-end-