数据结构-单链表排序遇到的一个有关问题

数据结构-单链表排序遇到的一个问题

在实现单链表功能的时候遇到的一个问题，mark下。

吃一堑长一智！

先看代码。

LinkList SelectSort(LinkList L)
{
    LinkList first;     /*排列后有序链的表头指针*/
    LinkList tail;      /*排列后有序链的表尾指针*/
    LinkList p_min;     /*保留键值更小的节点的前驱节点的指针*/
    LinkList min;       /*存储最小节点*/
    LinkList p;         /*当前比较的节点*/

    first = NULL;
    while (L != NULL) /*在链表中找键值最小的节点。*/
    {
        /*注意：这里for语句就是体现选择排序思想的地方*/
        for (p=L,min=L; p->next!=NULL; p=p->next) /*循环遍历链表中的节点，找出此时最小的节点。*/
        {
            if (p->next->data < min->data) /*找到一个比当前min小的节点。*/
            {
                p_min = p; /*保存找到节点的前驱节点：显然p->next的前驱节点是p。*/
                min = p->next; /*保存键值更小的节点。*/
            }
        }

        /*上面for语句结束后，就要做两件事；
            一是把它放入有序链表中；
            二是根据相应的条件判断，安排它离开原来的链表。*/

        /*第一件事*/
        if (first == NULL) /*如果有序链表目前还是一个空链表*/
        {
            first = min; /*第一次找到键值最小的节点。*/
            tail = min; /*注意：尾指针让它指向最后的一个节点。*/
        }
        else /*有序链表中已经有节点*/
        {
            tail->next = min; /*把刚找到的最小节点放到最后，即让尾指针的next指向它。*/
            tail = min; /*尾指针也要指向它。*/
        }
        /*第二件事*/
        if (min == L) /*如果找到的最小节点就是第一个节点*/
        {
            //printf("表头%d已经是最小，当前结点后移。\n", min->data);
            L = L->next; /*显然让head指向原head->next,即第二个节点，就OK*/
        }
        else /*如果不是第一个节点*/
        {
            p_min->next = min->next; /*前次最小节点的next指向当前min的next,这样就让min离开了原链表。*/
        }
    }
    if (first != NULL) /*循环结束得到有序链表first*/
    {
        tail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL*/
    }
    L = first;
    return L;
}

代码比较杂，不过很简单，利用选择排序对链表进行排序。

不过，我函数入口，我传入的是一个带头结点的链表的头指针。

然而，在我的排序算法实现中，并没有考虑到头结点，直接把头指针指向了第一个结点。

如下：

 /*第一件事*/
        if (first == NULL) /*如果有序链表目前还是一个空链表*/
        {
            first = min; /*第一次找到键值最小的节点。*/
            tail = min; /*注意：尾指针让它指向最后的一个节点。*/
        }

当我修改了代码，按从高到低排列的时候，在不同的环境里遇到了不同的问题。

如果在windows上的codeblocks这个编译器跑，一切看似正常。正常排序。

当我在mac上的xcode这个编译器跑的时候，问题出现了，最大的那个元素没了，但是最小的变成了0.（我输入的测试数据都大于0）。

后来发现，

windows上的codeblocks一个变量没赋值，默认是随机数(一般都比较大)。
mac上的codeblocks一个变量没赋值，默认是0。

因为我的头结点的数据域(data)没赋值，在windows上，数值比较大，理所应当的排在了第一个结点。当我打印的时候，调用打印函数（这个函数考虑了头结点，即L->next表示第一个结点），这时候，排序后的链表的第一个结点成了打印函数中链表的头结点，经过L->next后，自然的把原来的第一个结点（即没赋值。数字比较大的那个）省略掉了，所以结果看似正常。

然而在xcode上，默认是0. 这样导致把头结点的数据考虑进去进行排列，0自然排到了最后，并且把第一个结点给省略了，导致最大的那个元素没了，但是最小的变成了0.（我输入的测试数据都大于0）。

看来自己还是很水，老犯这样的错误，哎～～。

学习的路上，与君共勉

Re: hitwhylz昨天 22:14: 回复u012592378n晕..这是干啥

1楼u011960402昨天 21:11: 所以要养成变量赋值的习惯。

数据结构-单链表排序遇到的一个有关问题

相关推荐