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

Bertha 。 2022-09-17 15:14 62阅读 0赞

**在实现单链表功能的时候遇到的一个问题，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）。**

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

**学习的路上，与君共勉**