排序算法—-无表头链表插入排序

排序算法—-无表头链表插入排序

排序算法—-无表头链表插入排序,算法—-

  1. /*  
  2. ==========================  
  3.  功能:直接插入排序(由小到大)  
  4.  返回:指向链表表 头的指针  
  5. ==========================  
  6. */    
  7. /*  
  8.  直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值  
  9.  (就是用它排序的字段,我们取学号num为键值)排好序的,对于节点n在  
  10.  这个序列中找插入位置,使得n插入后新序列仍然有序。按照这种思想,依次  
  11.  对链表从头到尾执行一遍,就可以使无序链表变为有序链表。  
  12.    
  13. 单向链表的直接插入排序图示:  
  14. —->[1]—->[3]—-> [2]…—->[n]—->[NULL](原链表)  
  15. head   1->next  3->next  2->next   n->next  
  16.   
  17. —->[1]—->[NULL](从原链表中取第1个节点作为只有一个节点的有序链表)  
  18. head  
  19. 图11  
  20.   
  21. —->[3]—->[2]…—->[n]—->[NULL](原链表剩下用于直接插入排序的节点)  
  22. first   3->next  2->next   n->next  
  23. 图12  
  24.   
  25. —->[1]—->[2]—->[3]…—->[n]—->[NULL](排序后链表)  
  26. head   1->next  2->next  3->next   n->next  
  27.   
  28. 图13:有N个节点的链表直接插入排序  
  29.   
  30. 1、先在原链表中以第一个节点为一个有序链表,其余节点为待定节点。  
  31. 2、从图12链表中取节点,到图11链表中定位插入。  
  32. 3、上面图示虽说画了两条链表,其实只有一条链表。在排序中,实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。  
  33.    这一点请读者务必搞清楚,要不然就可能认为它和上面的选择排序法一样了。  
  34. */    
  35. struct student *InsertSort(struct student *head)    
  36. {    
  37.     struct student *first; /*为原链表剩下用于直接插入排序的节点头指针*/    
  38.     struct student *t; /*临时指针变量:插入节点*/    
  39.     struct student *p; /*临时指针变量*/    
  40.     struct student *q; /*临时指针变量*/    
  41.     
  42.     first = head->next; /*原链表剩下用于直接插入排序的节点链表:可根据图12来理解。*/    
  43.     head->next = NULL; /*只含有一个节点的链表的有序链表:可根据图11来理解。*/    
  44.     
  45.     while (first != NULL) /*遍历剩下无序的链表*/    
  46.     {    
  47.         /*注意:这里for语句就是体现直接插入排序思想的地方*/    
  48.         for (t = first, q = head; ((q! = NULL) && (q->num < t->num)); p = q, q = q->next); /*无序节点在有序链表中找插入的位置*/    
  49.         
  50.     /*退出for循环,就是找到了插入的位置*/    
  51.     /*注意:按道理来说,这句话可以放到下面注释了的那个位置也应该对的,但是就是不能。原因:你若理解了上面的第3条,就知道了。*/    
  52.         first = first->next; /*无序链表中的节点离开,以便它插入到有序链表中。*/     
  53.       
  54.         if (q == head) /*插在第一个节点之前*/    
  55.         {    
  56.             head = t;    
  57.         }    
  58.         else /*p是q的前驱*/    
  59.         {    
  60.             p->next = t;    
  61.         }    
  62.         t->next = q; /*完成插入动作*/    
  63.         /*first = first->next;*/    
  64.     }    
  65.     return head;    
  66. }   

http://www.bkjia.com/Cyy/1182096.htmlwww.bkjia.comtruehttp://www.bkjia.com/Cyy/1182096.htmlTechArticle排序算法—-无表头链表插入排序,算法—- /*
========================== 功能:直接插入排序(由小到大)
返回:指向链表表头的指针 ==============…

  1. /*
    //对于很小的数源(N<=20),插入排序比快速排序好,此时,插入排序速度快也稳定。
  2. //插入排序只用在小的或是非常接近排好序的输入数据上。

  3. ==========================  

  4.  功能:直接插入排序(由小到大)  
  5.  返回:指向链表表 头的指针  
  6. ==========================  
  7. */    
  8. /*  
  9.  直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值  
  10.  (就是用它排序的字段,我们取学号num为键值)排好序的,对于节点n在  
  11.  这个序列中找插入位置,使得n插入后新序列仍然有序。按照这种思想,依次  
  12.  对链表从头到尾执行一遍,就可以使无序链表变为有序链表。  
  13.    
  14. 单向链表的直接插入排序图示:  
  15. —->[1]—->[3]—-> [2]…—->[n]—->[NULL](原链表)  
  16. head   1->next  3->next  2->next   n->next  
  17.   
  18. —->[1]—->[NULL](从原链表中取第1个节点作为只有一个节点的有序链表)  
  19. head  
  20. 图11  
  21.   
  22. —->[3]—->[2]…—->[n]—->[NULL](原链表剩下用于直接插入排序的节点)  
  23. first   3->next  2->next   n->next  
  24. 图12  
  25.   
  26. —->[1]—->[2]—->[3]…—->[n]—->[NULL](排序后链表)  
  27. head   1->next  2->next  3->next   n->next  
  28.   
  29. 图13:有N个节点的链表直接插入排序  
  30.   
  31. 1、先在原链表中以第一个节点为一个有序链表,其余节点为待定节点。  
  32. 2、从图12链表中取节点,到图11链表中定位插入。  
  33. 3、上面图示虽说画了两条链表,其实只有一条链表。在排序中,实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。  
  34.    这一点请读者务必搞清楚,要不然就可能认为它和上面的选择排序法一样了。  
  35. */    
  36. struct student *InsertSort(struct student *head)    
  37. {    
  38.     struct student *first; /*为原链表剩下用于直接插入排序的节点头指针*/    
  39.     struct student *t; /*临时指针变量:插入节点*/    
  40.     struct student *p; /*临时指针变量*/    
  41.     struct student *q; /*临时指针变量*/    
  42.     
  43. 美高梅59599,    first = head->next; /*原链表剩下用于直接插入排序的节点链表:可根据图12来理解。*/    
  44.     head->next = NULL; /*只含有一个节点的链表的有序链表:可根据图11来理解。*/    
  45.     
  46.     while (first != NULL) /*遍历剩下无序的链表*/    
  47.     {    
  48.         /*注意:这里for语句就是体现直接插入排序思想的地方*/    
  49.         for (t = first, q = head; ((q! = NULL) && (q->num < t->num)); p = q, q = q->next); /*无序节点在有序链表中找插入的位置*/    
  50.         
  51.     /*退出for循环,就是找到了插入的位置*/    
  52.     /*注意:按道理来说,这句话可以放到下面注释了的那个位置也应该对的,但是就是不能。原因:你若理解了上面的第3条,就知道了。*/    
  53.         first = first->next; /*无序链表中的节点离开,以便它插入到有序链表中。*/     
  54.       
  55.         if (q == head) /*插在第一个节点之前*/    
  56.         {    
  57.             head = t;    
  58.         }    
  59.         else /*p是q的前驱*/    
  60.         {    
  61.             p->next = t;    
  62.         }    
  63.         t->next = q; /*完成插入动作*/    
  64.         /*first = first->next;*/    
  65.     }    
  66.     return head;    
  67. }   
admin

网站地图xml地图