周六,job prepare time,做EMC的笔试题,单链表排序,发现自己的数据结构就要还给老师了。。。
拣起来,要拣起来,热个身先,伪代码先。
被排序的节点 POINT;
sort_p(POINT* head)
{
POINT *pre_p1;
POINT *pre_p2;
POINT *min;
POINT *p1;
for(p1=link;p1->next!=NULL;pre_p1=min,p1=min->next)
/*从头开始到尾巴节点结束(不包括尾巴),pre_p1在每轮循环结束时记录上一轮的最小节点,p1记 录最小节点的后一个节点(最小节点一直都是在最前面的)*/
{
min = p1;
POINT *p2;
for(p2=p1; p2->next!=NULL;p2=p2->next)
/*p2后移与min不断进行比较*/
{
if(p2->next->num < min->num)
{
pre_p2=p2;
min=p2->next;
} /*记录最小的节点和它前面的节点*/
if(min == p1)
{
NO_NEED_SORT;
continue;
} /*如果最小的节点就是这次比较循环的“排头”,那么不用排了*/
/*否则要将min与当前的小排头交换*/
if(p1==head)
{
head=min;
} /*如果刚是第一轮循环,排头就是头,那么不存在pre_f1*/
else
{
pre_p1->next=min;
} /*否则pre_f1的下一个节点要连接成min了*/
POINT *temp=min->next;/*temp储存min的下一个节点*/
/*如果排头和新一轮的小排头是相邻的*/
if(p1->next==min)
{
min->next=p1;
p1->next=temp;
}
/*否则要将小排头的下一个节点连接到p1的下一个,min的前一个的下一个要连到p1,p1的下一个则要连接到min原来的下一个temp*/ 终于折腾完了....
else
{
min->next=p1->next;
pre_p2->next=p1;
p1->next=temp;
}
}
}
阅读(1280) | 评论(0) | 转发(0) |