C语言 用于对链表进行排序的常规函数

Question

是否有任何通用的用户定义函数可用于对任何给定的链表进行排序，因为它具有指针字段和数据字段。

该函数不应在节点之间交换数据。交换应通过使用pointers来完成。

我在网上找到了一个，但它使用的是用户定义的函数。我不允许使用任何其他功能，但气泡排序一个。

我们被要求不要初始化任何新变量，除了函数中的temp structs变量。所以，我不能使用整数或变量，如swapped.

我正在使用的那个如下：

/* Bubble sort the given linked lsit */
void bubbleSort(struct node *start)
{
    int swapped, i;
    struct node *ptr1;
    struct node *lptr = NULL;
    /* Checking for empty list */
    if (ptr1 == NULL)
        return;
    do
    {
        swapped = 0;
        ptr1 = start;
        while (ptr1->next != lptr)
        {
            if (ptr1->data > ptr1->next->data)
            { 
                swap(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    }
    while (swapped);
}
/* function to swap data of two nodes a and b*/
void swap(struct node *a, struct node *b)
{
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}

鉴于我的链表结构如下：

struct node
{
    int data;
    struct node *next;
};

Answer 1

对于您的情况，您可以使用您提供的函数的编辑版本。此处省略了交换功能。

//Sorting according to the data, ascending order
void bubbleSortLL(struct node *header){
struct node *temp1, *temp2, *temp3, *temp4, *temp5;
temp4=NULL;
while(temp4!=header->next)
{
    temp3=temp1=header;
    temp2=temp1->next;
    while(temp1!=temp4)
    {
        if(temp1->data > temp2->data)
        {
            if(temp1==header)
            {
                temp5=temp2->next;
                temp2->next=temp1;
                temp1->next=temp5;
                header=temp2;
                temp3=temp2;
            }
            else
            {
                temp5=temp2->next;
                temp2->next=temp1;
                temp1->next=temp5;
                temp3->next=temp2;
                temp3=temp2;
            }
        }
        else
        {
            temp3=temp1;
            temp1=temp1->next;
        }
        temp2=temp1->next;
        if(temp2==temp4)
            temp4=temp1;
        }
    }
}

这将通过将指定的列表作为参数传递来工作。尽管如此，我不明白为什么你不能使用交换功能。

Answer 2

要摆脱对交换函数的调用，请将函数调用及其内容：

而不是

 swap(ptr1, ptr1->next);

写

int temp = ptr1->data;
ptr1->data = ptr1->next->data;
ptr1->next->data = temp;

---

要交换元素而不是数据，您需要以跟踪上一个元素。

这里有一个关于交换元素的建议（可能需要 NULL 检查）

 previous->next = ptr1->next;
 previous->next->next=ptr1;

除了ptr1=ptr1->next，您需要：

     previous=previous->next;
     ptr1=previous->next;