UC知道关于冒泡法链表排序
来源：百度知道 编辑：UC知道 时间：2024/09/26 00:23:51
下面是一个子程序,用冒泡法给一个无序链表按照学号顺序进行排序(由小到大).但程序出现一个问题,如果最后一个结点不是最大的结点,那么循环不停,我设置了断点,发现,如果最后一个结点不是最大结点的话,那么最大的那个结点一直在与0进行交换,我不太明白其中的道理.
struct student *sort(struct student *head)
{struct student *p,*p1,*p2,*p3,*temp;
p=head;
while(p->next!=NULL)p=p->next;
while(p!=head)
{
p3=p1=head;/*p3记录p1前一个结点*/
p2=p1->next;/*p2记录p1后一个结点*/
/***注释****/while(p1!=p)/*一直排到最后一个未排序的结点*/
{if(p1->num>p2->num)/*当前一个大于后一个则换位*/
{if(p1==head)head=p2;/*如果是头结点要换位，则head要换*/
else p3->next=p2;
temp=p2->next;
p2->next=p1;
p1->next=temp;
printf("%d,%d ",p1->num,p2->num);
getchar();
temp=p1;/*注意换位之后，p1与p2的指向也要相应地换*/
p1=p2;
p2=temp;
}
p3=p1;/*p3记录p1*/
p1=p1->next;/*p1后移一个结点*/
p2=p1->next;/*p2记录p1后面的结点*/
}
p=p3;/*p前移一个结点*/
}
return(head);
}
如果把注释的那一个while的条件改成wh
struct student *sort(struct student *head)
{struct student *p,*p1,*p2,*p3,*temp;
p=head;
while(p->next!=NULL)p=p->next;
while(p!=head)
{
p3=p1=head;/*p3记录p1前一个结点*/
p2=p1->next;/*p2记录p1后一个结点*/
/***注释****/while(p1!=p)/*一直排到最后一个未排序的结点*/
{if(p1->num>p2->num)/*当前一个大于后一个则换位*/
{if(p1==head)head=p2;/*如果是头结点要换位，则head要换*/
else p3->next=p2;
temp=p2->next;
p2->next=p1;
p1->next=temp;
printf("%d,%d ",p1->num,p2->num);
getchar();
temp=p1;/*注意换位之后，p1与p2的指向也要相应地换*/
p1=p2;
p2=temp;
}
p3=p1;/*p3记录p1*/
p1=p1->next;/*p1后移一个结点*/
p2=p1->next;/*p2记录p1后面的结点*/
}
p=p3;/*p前移一个结点*/
}
return(head);
}
如果把注释的那一个while的条件改成wh
P 指向 的是没有交换前的 最后个节点
有可能和 倒数第二个 交换
所以p不一定是最后一个节点
我也用C用链表进行冒泡排序法排序过，你看看我写的源代码，希望对你有好处：
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct x
{
int num;
struct x *next;
};
main()
{
int i,j,temp=0,d,e,a;
struct x *p1,*p2,*tail,*head;
p1=p2=tail=head=0;
printf("请输入个数:");
scanf("%d",&a);
for (d=1;d<=a;d++)
{
if (1 == d)
{
p1=(struct x*)malloc(sizeof(struct x));
p2=tail=head=p1;
}
else
{
p1=(struct x*)malloc(sizeof(struct x));
tail->next=p1;
tail=p1;
}
}
p1=head;
printf("请输入%d个数字:\n",a);
for (i=1;i<=a;i++)
{
scanf("%d",&p1->num);
if