链表如何实现冒泡排序

Question

想用冒泡排序对链表数据进行排序，为什么在执行了一次p=p->next之后，p=NULL，这是哪里出现了问题

struct cell * sort(struct cell* head) {//递增排序链表，head是单链表首结点指针
 struct cell* p, * p0, * r, * r0, * q;
 p = p0 = r = r0 = q = NULL;
 p = head;
int i=0;

while(p!=NULL)
{
    while(r!=NULL||i==0)
    {

     if(i==0)//头结点交换的情况
     {r0=p;
     r=r0->next;
     i++;
         if(r0->x>r->x)
         {

            r0->next=r->next;
            r->next=r0;

            struct cell *temp;
            temp=r0;
            r0=r;
            r=temp;
            q=r0;
            r=r->next;
            r0=r0->next;
         }else
         {q=r0;
             r0=r;
             r=r->next;
         }
     }else
     {
         if(r0->x>r->x)//其他情况
         {
               struct cell *temp1;
               temp1=r->next;
               q->next=r;
               r->next=r0;
               r0->next=temp1;

               struct cell *temp2;
               temp2=r0;
               r0=r;
               r=temp2;

q=q->next;r0=q->next;r=r0->next;
         }
         else{
            q=q->next;r0=q->next;r=r0->next;
         }
     }

    }
    p=p->next;
    i++;
}
 return head;
}

Answer 1

【以下回答由 GPT 生成】

问题出现在第一个while循环中的条件判断上。在每次while循环中，r指针会迭代到链表的末尾，即r=NULL。所以在第二个while循环中的条件判断while (r != NULL || i == 0)始终为真，导致会执行第一个if语句块的代码，而在这个if语句块中有r0 = r; r = temp;的操作，将p赋值给r，并将r赋值给r0，所以执行完一次p = p->next之后，p=NULL, p赋值给了r，r赋值给了r0，所以p=NULL, r=NULL, r0=NULL，导致程序终止。

解决该问题的方法是，在第一个while循环的条件判断中，同时判断r是否为NULL，并添加一个额外的判断条件，当r为NULL时，结束内层while循环。

修改后的代码示例如下：

struct cell* sort(struct cell* head) {
    // 递增排序链表，head是单链表首结点指针

    struct cell* p, * p0, * r, * r0, * q;
    p = p0 = r = r0 = q = NULL;
    p = head;
    int i = 0;

    while (p != NULL) {
        r = p->next;
        r0 = p;
        i = 0;

        while (r != NULL && (r != NULL || i == 0)) {
            if (i == 0) {
                if (r0->x > r->x) {
                    r0->next = r->next;
                    r->next = r0;
                    head = r;

                    struct cell *temp;
                    temp = r0;
                    r0 = r;
                    r = temp;
                    q = r0;
                    r = r->next;
                    r0 = r0->next;
                }
                else {
                    q = r0;
                    r0 = r;
                    r = r->next;
                }
                i++;
            }
            else {
                if (r0->x > r->x) {
                    struct cell *temp1;
                    temp1 = r->next;
                    q->next = r;
                    r->next = r0;
                    r0->next = temp1;

                    struct cell *temp2;
                    temp2 = r0;
                    r0 = r;
                    r = temp2;

                    q = q->next;
                    r0 = q->next;
                    r = r0->next;
                }
                else {
                    q = q->next;
                    r0 = q->next;
                    r = r0->next;
                }
            }
        }
        p = p->next;
        i++;
    }
    return head;
}

这样修改后，就能够正确地对链表进行冒泡排序。

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/216316

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^