单向链表冒泡排序

单 向 链 表 冒 泡 排 序

    今天无意间看到以前写的单向链表冒泡排序，试着运行一下发现有bug，实在是想不起之前是怎么出错的。看了两遍代码，终于发现是头指针的问题，温故而知新啊。

    无头节点的单向链表（第一个节点也存数据），所以前面的两个节点需要交换时就要修改head指针的值，或许有人认为交换数据域就可以省去对前两个节点的特殊处理，这样可以是可以，但是当数据域多（大）的时候，就算你（程序猿）不累估计算机也累得不行啦！但是32位系统上交换指针，只有4个字节而已。

下面是修改后的样子：

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

typedef struct list_node
{
    int num;
    struct list_node *next;
}list_node;

void sort_list(list_node **head);
void print_num(list_node *head);

int main()
{
    list_node *head,*p;
    int i=1;

    puts("Input 5 nums");

    head = p = (list_node *)malloc( sizeof(list_node) );
    for(i = 0; i < 5; i++)
    {
        p->next = (list_node *)malloc( sizeof(list_node) );
        p = p->next;
        scanf("%d",&p->num);
    }
    p->next = NULL;

    printf("\nsort-before\n");
    print_num(head);
    sort_list(&head);

    puts("sort-after");
    print_num(head);

    for(p = head; p; p = p->next) {
        free(p);
    }

    return 0;
}

void print_num(list_node *head)
{
    list_node *p;
    for(p = head->next;p;p = p->next)
        printf("%d->",p->num);
    puts("NULL");
}
// （无头节点）单向链表冒泡排序,对next指针域进行交换即可
void sort_list(list_node **head)
{
    list_node *pre, *pCur, *nextp, *start, *end;
    char flat;

    if(NULL == head || NULL == *head) {
        return;
    }
    nextp = end = NULL;
    start = *head;

    while(start->next != end)
    {
        flat=1; //内层循环某趟循环不需交换时提前就可以结束
        pre = start; //pCur指向需要交换的节点，pre指向p的前驱
        pCur = pre->next;
        // 前两个节点比较(可能需要修改头指针，前两个节点特别处理)
        if(pre->num > pCur->num) {
            pre->next = pCur->next;
            pCur->next = pre;
            start = pCur;
            // reset
            pre = start;
            pCur = pre->next;
        }
        // 3 个节点以上才会执行下面的while
        while(pCur->next != end)
        {
            nextp = pCur->next;
            if(pCur->num > nextp->num)
            { /* exchange pointer */

                pre->next = nextp;
                pCur->next = nextp->next;
                nextp->next = pCur;
                flat=0;
            }

            pre = pre->next;
            pCur = pre->next;
        }
        if(flat==1)//提前就可以结束
            break;
        end = pCur;//上面的一轮冒泡使得大的沉到末尾，end从后往前移动
        //print_num(start);
    }
    (*head) = start;
}