Chinaunix首页 | 论坛 | 博客
  • 博客访问: 230285
  • 博文数量: 108
  • 博客积分: 3092
  • 博客等级: 中校
  • 技术积分: 1172
  • 用 户 组: 普通用户
  • 注册时间: 2008-07-25 16:35
文章分类

全部博文(108)

文章存档

2011年(3)

2010年(43)

2009年(19)

2008年(43)

我的朋友

分类: C/C++

2008-10-25 20:17:21

周六,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;
              }
                
      
      }
}
阅读(1250) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~