假定有一种带表头附加节点的链表,每个节点含三个域:data,next,range ,其中data为整型值域,next,range为指针域,现在所有节点已经由于next域链接起来,试编一算法,利用range域把所有节点按照其值从小到大的顺序链接起来,,由此域链接得到的单链表的表头指针保存在表头附加节点的range域中,

不知该怎么做?

这和单链表排序是一样的吧.只是这里多用了一个指针域,同时不改变next指针的指向.


/*从链表中拆出节点，插入到一新链表中*/
nodelink paixu(nodelink*head1)
{
nodelink p,pre,s,q,head ;
p=*head1 ;
pre=NULL ;
head=NULL ;
s=head ;
q=NULL ;
while(p!=NULL)
{
pre=p->next ;
/*保留P的原值，以便下一次访问*/
//p->next=NULL;
if(head==NULL)head=p ;
else
{
s=head ;
q=NULL ;
/*没找到，下移*/
while((s!=NULL)&&(p->info<=s->info))
{
q=s ;
s=s->range ;
}
if(q==NULL)
{
p->range=head ;
head=p ;
}
else
{
p->range=s ;
q->range=p ;
}
}
p=pre ;
}
return(head);
}

/*我只把红色部分由原来的next改成range*/