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;

        }
    }
}

这可以通过将指定的列表作为参数传递来实现。不过，我不明白为什么你不能使用交换功能。