请教怎么实现单链表的直接插入排序（C语言）

请问如何实现单链表的直接插入排序（C语言）

void sortlist(linklist * head)
{
    linklist * newhead, * s, * pre ,* p;
    p=head->next;
    newhead=p->next;
    p->next=NULL; ----1
    while(newhead)
    {
        s=newhead;
        newhead=newhead->next;
        pre=head;
        p=head->next;
        while(p!=NULL && p->data < s->data) -----2
        {
            pre=p;
            p=p->next;
        }
        s->next=p;
        pre->next=s;
    }
}

这是网上找的程序，有一部分没看懂，newhead是要比较的结点吧，p,pre分别是前一个和再前一个的结点，问题：p->next=NULL是什么意思，p不是指向第一个结点吗,为什么还要p->next=NULL? 另外就是while循环里的p!=NULL是做什么用的
[解决办法]

void sortlist(linklist * head)
{//head->
[解决办法]
3
[解决办法]
->
[解决办法]
2
[解决办法]
->
[解决办法]
1
[解决办法]
->NULL
    linklist * newhead, * s, * pre ,* p;
    p=head->next;//p =>3
    newhead=p->next;//newhead=>2
    p->next=NULL; //head->｜p｜->NULL，它将成为最后一个结点。故为结点 
 
    while(newhead)
    {
        s=newhead;//s=>2
        newhead=newhead->next;//newhead=>1
        pre=head;
        p=head->next;
        while(p!=NULL && p->data < s->data)//p判断是否NULL，因为从头往后逐个遍历的，必须保证循环结束
        {//此循环是寻找插入位置
            pre=p;//保留要插入位置的前一个结点指针，为了后文插入
            p=p->next;
        }
        s->next=p;
        pre->next=s;
    }
}

查看更多 下一篇