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

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

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

　　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>= && r >data<= )　　{r >next=ld >next;ld >next=r;}∥处理数字字符　　else {r >next=lo >next;lo >next=r;}∥处理其它符号 　　}∥结束while(L!=null) 　　}∥算法结束

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