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

．[题目分析] 双向循环链表自第二结点至表尾递增有序要求将第一结点插入到链表中使整个链表递增有序由于已给条件(a<x<an)故应先将第一结点从链表上摘下来再将其插入到链表中相应位置由于是双向链表不必象单链表那样必须知道插入结点的前驱

void DInsert(DLinkedList dl)∥dl是无头结点的双向循环链表自第二结点起递增有序本算法将第一结点(a<x<an)插入到链表中使整个链表递增有序

{s=la;∥s暂存第一结点的指针

p=la>next;p>prior=la>prior;p>prior>next=p;∥将第一结点从链表上摘下

while(p>data<x)p=p>next;∥查插入位置

s>next=p;s>prior=p>prior;p>prior>next=s;p>prior=s;∥插入原第一结点s

}∥算法结束

[算法讨论] 由于题目已给a<x<an所以在查找第一结点插入位置时用的循环条件是p>data<x即在a和an间肯定能找到第一结点的插入位置若无此条件应先看第一结点数据域值x是否小于等于a如是则不作任何操作否则查找其插入位置循环控制要至多查找完a到an结点

if(p>data<x)p=p>next;else break;

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