c - 排序链表函数(C)

Question

我是一名初学者，过去几周一直在自学数据结构。我正在尝试创建一个函数，以排序的方式将整数插入到链表中。

这是我的功能:

void sortedInsert(int n)
{
    node *temp = malloc(sizeof(node));
    temp->data= n;

    //if list is empty or n is less than minimum number in the list, insert at the beggining.
    if(head == NULL || n < head->data )
    {
        temp->next = head;
        head = temp;
    }
    else
    {
        node *cur, *prev, *temp;
        for (cur = head, prev = NULL
             cur != NULL && cur->data < n;  //if n is less than cur->value it breaks out of loop
             prev = cur, cur = cur->next);

         //now cur is pointing at last node or the node it broke out off

         if( n < cur->data)
         {
             temp->next = cur;
             prev->next = temp;
         }
         else
         {
             //if its larger than the maximun number in the list
             //insert at end 
             temp->next = NULL;
             cur->next = temp;
         }

         free(cur);
         free(prev);
    }
}

输出:

How many numbers?
4
Enter the number
10
List is:  10
Enter the number
4
List is:  4 10
Enter the number
5

Process returned -1073741819 (0xC0000005)   execution time : 7.161 s
Press any key to continue.

每当我插入的数字大于列表中的数字时，它就会崩溃。 如果我能得到任何帮助或指导，我将不胜感激。

Answer 1

错误行为在 else 语句内的 for 循环中。该循环在两种情况下终止。第一个是，如果找到一个数据大于或等于 n 的节点。第二种是当 cur 为 NULL 时。如果遍历所有链表才找到一个值大于等于n的节点，则循环会在cur变为NULL时终止。

因此您需要检查 cur 是否为 NULL，并且您不应该使用它，因为它肯定是一个非 NULL 的值。

为了实现您想要的行为，我相信您应该去掉 for 循环后面的 if-else 语句，而只使用下面的两行。

temp->next = cur;
prev->next = temp;

除此之外，在 for 循环之前，您再次声明 temp 变量会导致您在函数开头声明的 temp 对于该范围不可访问。第二个声明也应删除。

最后，虽然您没有指定函数的预期行为，但根据函数名称的语义含义，我相信您不需要调用 free()，您应该删除它们。

因此，在进行我提到的更改之后，您的代码应该如下所示。

void sortedInsert(int n)
{
    node *temp = malloc(sizeof(node));
    temp->data= n;

    //if list is empty or n is less than minimum number in the list, insert at the beggining.
    if(head == NULL || n < head->data )
    {
        temp->next = head;
        head = temp;
    }
    else
    {
        node *cur, *prev;
        for (cur = head, prev = NULL
             cur != NULL && cur->data < n;  //if n is less than cur->value it breaks out of loop
             prev = cur, cur = cur->next);

         //now cur is pointing at last node or the node it broke out off
         temp->next = cur;
         prev->next = temp;
    }
}