问题
问答题
设带表头结点的双向链表的定义为
typedef int ElemType；
typedef struct dnode∥双向链表结点定义
ElemType data；∥数据
struct dnode*lLink，*rLink；∥结点前驱与后继指针
)DblNode；
typedef DblNode*DblList；∥双向链表
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。
答案
参考答案：void sort(DblNode*L)
{
DblNode*S=L—＞rlink；∥指针s指向待插入结点，初始时指向第一个结点
while(S!一NULL)∥处理所有结点
{
pre=L；
p=L—＞lLink；∥指针P指向待比较的结点，pre是P的前驱指针
while(p!—NULL&&s—＞data＜p—＞data)
∥循1Link链寻找结点*S的插入位置
{
pre=P；
p=p—＞lLink；
}
pre—＞lLink=S；
s—＞ILink=p；
s—s—＞rLink；∥结点*s在lLink方向插入到*pre与*p之间
}
}