对链表进行排序最简单的方法

Question

我正在尝试为链表编写非常基本的排序方法。我遇到了未处理的异常。我犯了什么错误？这是我的代码：-

struct LinkedNode// structure for linked list
{
    int data;
    struct LinkedNode *next;
}* start = NULL;
    

以下函数创建一个链表

void CreateLinkedList()
{
    LinkedNode *newNode, *current;
    printf("enter 5 numbers to create linked list\n");
    for(int i=0; i<5; i++)
    {
        newNode = (struct LinkedNode *)malloc(sizeof(LinkedNode));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        if(start == NULL)
        {
            start = newNode;
            current = newNode;
        }
        else
        {
            current->next = newNode;
            current = newNode;
        }
    }
}

以下函数用于对链表节点进行排序

void SortLinkedList()
{
    struct LinkedNode *node=NULL, *temp = NULL;
    int tempvar;//temp variable to store node data
    node = start;
    temp = node->next;//temp node to hold node data and next link
    while(node != NULL && node->next != NULL)
    {
        for(int j=0; j<5; j++)//value 5 because I am taking only 5 nodes
        {
            if(node->data > temp->data)//swap node data
            {
                tempvar = node->data;
                node->data = temp->data;
                temp->data = tempvar;
            }
            temp = temp->next;
        }
        node = node->next;
    }
}

Answer 1

试试这个代码

void SortLinkedList()
    {
    struct LinkedNode *node=NULL, *temp = NULL;
    int tempvar;//temp variable to store node data
    node = start;
    //temp = node;//temp node to hold node data and next link
    while(node != NULL)
    {
        temp=node; 
        while (temp->next !=NULL)//travel till the second last element 
        {
           if(temp->data > temp->next->data)// compare the data of the nodes 
            {
              tempvar = temp->data;
              temp->data = temp->next->data;// swap the data
              temp->next->data = tempvar;
            }
         temp = temp->next;    // move to the next element 
        }
        node = node->next;    // move to the next node
    }
}

1 - 外部 while 循环用于对链表进行排序所需的传递总数..

2- 在第二个 while 循环中，我们实际上是在比较要排序的节点的数据

Answer 2

您可以使用

qsort

，而不是实现自己的排序。当然，

qsort

需要一个数组，但这很容易创建。

在本例中，您知道该列表有 5 个成员。但是，如果您不知道，您可以数一下。

int size_of_list = 0;
struct LinkedNode *p;

for (p = start; p != NULL; p = p->next) ++size_of_list;

if (size_of_list == 0) {
    // Nothing to do
    return;
}

现在您可以创建数组；

struct LinkedNode *arr[size_of_list + 1], **arrp = arr;
for (p = start; p != NULL; p = p->next) *arrp++ = p;
*arrp = NULL;

然后，在

qsort

上使用

arr

。有很多例子，但诀窍是编写适当的比较函数。

int cmp_LinkedNode(const void *a, const void *b) {
    const struct LinkedNode * const *aa = a;
    const struct LinkedNode * const *bb = b;
    return ((*aa)->data > (*bb)->data) - ((*aa)->data < (*bb)->data);
}

//...
qsort(arr, size_of_list, sizeof(*arr), cmp_LinkedNode);

然后，将列表重新连接到排序顺序。

for (int i = 0; i < size_of_list; ++i) arr[i]->next = arr[i+1];
start = arr[0];

Answer 3

是的，使用节点/链接对链表进行排序是一项非常困难的工作。自己花几个小时做，但既然我已经做到了，为什么不帮助别人呢.. 您需要做的只是找到列表中的最小值。将其与头节点和 head->next 的 recur 交换。 如果您创建了 FindMin() 和 Swap() 函数，则排序代码只有 3 到 4 行。 这是 sort()、swap() 和 findmin() 的完整代码。

void sort(node **start)
{
    if (((*start)->next == NULL) || (*start == NULL))
    {
        return;
    }
    node *min = findmin(*start);
    swap(*start, min, start);
    sort(&((*start)->next));
}

void swap(node *p1, node *p2, node **start)
{
    node *p1pre = NULL;
    node *p1curr = *start;
    while (p1curr!=p1)
    {
        p1pre = p1curr;
        p1curr = p1curr->next;
    }
    node *p2pre = NULL;
    node *p2curr = *start;
    while (p2curr != p2)
    {
        p2pre = p2curr;
        p2curr = p2curr->next;
    }
    if (p1pre != NULL)
    {
        p1pre->next = p2curr;
    }
    else
    {
        *start = p2curr;
    }
    if (p2pre != NULL)
    {
        p2pre->next = p1curr;
    }
    else
    {
        *start = p1curr;
    }
    node *temp = p2curr->next;
    p2curr->next = p1curr->next;
    p1curr->next = temp;
}

node* findmin(node *start)
{
    int flag = 0;
    if (start == NULL)
    {
        cout << "list is empty" << endl;
    }
    else
    {
        node *curr = start->next;
        node *min = start;
        while (curr->next != NULL)
        {
            if (min->value > curr->value)
            {
                min = curr;
                flag++;
            }
            curr = curr->next;
        }
        if ((curr->next == NULL) && (min->value > curr->value))
        {
            min = curr;
            flag++;
        }
        if (flag > 0)
        {
            return min;
        }
    }
}