排序时改变指向链表的指针地址

Question

这是我用冒泡排序对链表进行排序的程序。当我使用 while 时它没问题，但是当我使用 for 循环时它有一个无限循环所以我的程序意外停止。另一方面，对于第一个和第二个元素的第一次交换，我将指针头指向第二个，但它可能不适用于整个程序。

例如，示例 1：输入：3,2,4,1,5 输出：2,3,4,5

例子2：输入：4,3,2,1,5 Output:3,4,5

例 3：输入：3,2,1 输出：2,3

我认为它只是第一次改变了head指针指向的地址，所以head在Ex1中指向2，在Ex2中指向3，在Ex3中指向2

void Swap(Node *p1, Node *p2)
{
    Node *t;
    t=p2->next;
    p2->next=p1;
    p1->next=t;
}


Node *BubbleSort(Node *head,int n) //pass the address of the first element in linked list and the linked list size 
{
    Node *tmp=head;
    int swap=1;

    for(int i=0;i<n-1;i++)
    {
        tmp=a; swap=0;
       for(int j=0;j<n-1;j++)
       {
         if((tmp->data)>(tmp->next->data))
         {
             if(j==0)  //if this is the first and second element I will change the address of the pointer
                a=tmp->next;

             Swap(tmp,tmp->next);   
             swap=1;
         }
         else tmp=tmp->next; //If the element I focus on is not greater than its folowing I will move the tmp pointer to the next.
        }       
        
        if(swap==0)
           return head;
    }
    return head;
}

int main()
{
    Node*head;
   //Assume I have a linked list with n elements
    head=BubbleSort(head,n);
   
}

我在 GeekforGeek 中搜索了其他方法，但我仍然想知道为什么我的代码不起作用。我想了将近一整天。请帮助我！

Answer 1

Swap函数被关闭了一个。因此，在最里面的循环体中你需要 Swap(tmp->prev, tmp) 而不是 Swap(tmp, tmp->next).

您需要比较和交换相同的元素，不是比较当前元素和下一个元素，而是交换下一个和第二个下一个元素。 if( (tmp->data) > (tmp->next->data) )，那么 tmp->prev->next 应该指向 tmp->next 而 tmp->next->next 应该指向 tmp。但是，需要注意一件事：当您 Swap(tmp->prev, tmp) 时，您还需要进一步启动一个元素。从 head 指向第一个元素但不包含任何数据这一事实也可以清楚地看出这一点。 first->prev应该指向head，head应该是rw。

让顶层代码保持头部是可能的，但如果 ll 代码保持它自己的头部更好。

排序时改变指向链表的指针地址

Change address of pointer to linked list when sorting

c

linked-list

bubble-sort