数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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-