单向链表的排序(冒泡法)

单向链表的排序(冒泡法)

2008-01-08 16:54

struct note   /*结构体定义并声明变量head*/
{
int total;
struct note * next;
};

struct note * sort(struct note * note head) /*排序函数*/
{
int i;
struct note *p1,*stu,*p2,*p0=NULL;
printf("\nSorting...");
if(!head || !head->next)    /*没有结点或只有一个结点，直接退出。*/
return head;
if(!head->next->next) /*有两个结点，交换两个结点后退出。*/
{
if(head->totalnext->total)
{
stu=head;
head=head->next;
head->next=stu;
stu->next=NULL;
}
return head;
}

while(p0!=head->next->next) /*三个以上结点排序,使用冒泡排序法*/
{
p1=head;stu=p1->next;p2=stu->next;
while(p2!=p0)
{
if(stu->totaltotal)
{
struct note * p;
p1->next=p2;
stu->next=p2->next;
p2->next=stu;
p=stu;stu=p2;p2=p;
}
p1=p1->next;stu=stu->next;p2=p2->next;
}
p0=stu;
}

if(head->totalnext->total)/*特殊考虑前两个结点*/
{
stu=head;
head=head->next;
stu->next=head->next;
head->next=stu;
}
return head;
}
说明:p1,stu,p2是交换两个结点时使用的临时变量,p0指示内层循环的终止位置,初始值为NULL,内层循环一 次向前移动一个结点．直到p0指到第三个结点时为止．
每次判断，若stu的total成员小于p2的total成员，就使stu和p2交换．然后将p1，stu，p2顺次 后移，直到p2遇到p0为止．