数据结构考研分类复习真题 第二章 答案[45]

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

void OneToThree(LinkedList Llaldlo)∥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>=&& r>data<=)

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

else {r>next=lo>next;lo>next=r;}∥处理其它符号

}∥结束while(L!=null)

}∥算法结束

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

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []