Chinaunix首页 | 论坛 | 博客
  • 博客访问: 490169
  • 博文数量: 23
  • 博客积分: 398
  • 博客等级: 一等列兵
  • 技术积分: 850
  • 用 户 组: 普通用户
  • 注册时间: 2012-06-03 22:18
文章分类

全部博文(23)

文章存档

2013年(9)

2012年(14)

分类: C/C++

2013-04-22 22:01:37

单 向 链 表 冒 泡 排 序
    今天无意间看到以前写的单向链表冒泡排序,试着运行一下发现有bug,实在是想不起之前是怎么出错的。看了两遍代码,终于发现是头指针的问题,温故而知新啊。
    无头节点的单向链表(第一个节点也存数据),所以前面的两个节点需要交换时就要修改head指针的值,或许有人认为交换数据域就可以省去对前两个节点的特殊处理,这样可以是可以,但是当数据域多(大)的时候,就算你(程序猿)不累估计算机也累得不行啦!但是32位系统上交换指针,只有4个字节而已。

下面是修改后的样子:

点击(此处)折叠或打开


  1. //单向链表冒泡排序
  2. #include<stdio.h>
  3. #include<malloc.h>

  4. typedef struct list_node
  5. {
  6.     int num;
  7.     struct list_node *next;
  8. }list_node;

  9. void sort_list(list_node **head);
  10. void print_num(list_node *head);

  11. int main()
  12. {
  13.     list_node *head,*p;
  14.     int i=1;

  15.     puts("Input 5 nums");
  16.     
  17.     head = p = (list_node *)malloc( sizeof(list_node) );
  18.     for(i = 0; i < 5; i++)
  19.     {
  20.         p->next = (list_node *)malloc( sizeof(list_node) );
  21.         p = p->next;
  22.         scanf("%d",&p->num);
  23.     }
  24.     p->next = NULL;

  25.     printf("\nsort-before\n");
  26.     print_num(head);
  27.     sort_list(&head);

  28.     puts("sort-after");
  29.     print_num(head);
  30.     
  31.     for(p = head; p; p = p->next) {
  32.         free(p);
  33.     }

  34.     return 0;
  35. }

  36. void print_num(list_node *head)
  37. {
  38.     list_node *p;
  39.     for(p = head->next;p;p = p->next)
  40.         printf("%d->",p->num);
  41.     puts("NULL");
  42. }
  43. // (无头节点)单向链表冒泡排序,对next指针域进行交换即可
  44. void sort_list(list_node **head)
  45. {
  46.     list_node *pre, *pCur, *nextp, *start, *end;
  47.     char flat;
  48.     
  49.     if(NULL == head || NULL == *head) {
  50.         return;
  51.     }
  52.     nextp = end = NULL;
  53.     start = *head;

  54.     while(start->next != end)
  55.     {
  56.         flat=1//内层循环某趟循环不需交换时提前就可以结束
  57.         pre = start//pCur指向需要交换的节点,pre指向p的前驱
  58.         pCur = pre->next;
  59.         // 前两个节点比较(可能需要修改头指针,前两个节点特别处理)
  60.         if(pre->num > pCur->num) {
  61.             pre->next = pCur->next;
  62.             pCur->next = pre;
  63.             start = pCur;
  64.             // reset
  65.             pre = start;
  66.             pCur = pre->next;
  67.         }
  68.         // 3 个节点以上才会执行下面的while
  69.         while(pCur->next != end)
  70.         {
  71.             nextp = pCur->next;
  72.             if(pCur->num > nextp->num)
  73.             { /* exchange pointer */
  74.                     
  75.                 pre->next = nextp;
  76.                 pCur->next = nextp->next;
  77.                 nextp->next = pCur;
  78.                 flat=0;
  79.             }
  80.                 
  81.             pre = pre->next;
  82.             pCur = pre->next;
  83.         }
  84.         if(flat==1)//提前就可以结束
  85.             break;
  86.         end = pCur;//上面的一轮冒泡使得大的沉到末尾,end从后往前移动
  87.         //print_num(start);
  88.     }
  89.     (*head) = start;
  90. }

阅读(3724) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~