向排序链表插入一个数，为什么每次都插入到第二个位置？

Question

我正在做一个关于链表的项目，我在向排序的链表中插入数字时遇到了问题。每次都插入到第二个位置的数字，我想不通问题出在哪里is.Here是我的代码：

void insertSort(struct linkedList *n,int num,int *length){                   //insert number to a sort linked list
    node *new = (node *) malloc(sizeof(node));          //create a new node
    new->next=NULL;
    new->data = num;
    while(n!=NULL&&n->data > new->data){             // find which position     num should insert in sorted list
            n = n->next;
    }
    new->next = n->next;          
    n->next= new;       
    length += 1;

}

n 是链表的头部。我将 head 初始化为第一个节点并且没有值。下面是我如何调用这个函数：

insertSort(head->next,num,&length);

每次插入到第二个位置的数字。就像我想将 45 插入到排序链表 <16,32,72,81,97> 中，插入后，列表将是 <16,45,32,72,81,97>。 45个由于某种原因插入到第二个位置。

Answer 1

因为你从不测试节点的位置。您的代码只将新节点放在第二个位置。它不检查它应该在排序列表中的位置试试下面

 void sortedInsert(struct Node** head_ref, struct Node* new_node) {

        struct Node* current;   /* Special case for the head end */ 
        if(*head_ref == NULL || (*head_ref)->data >= new_node->data)    {

            new_node->next = *head_ref;         
            *head_ref = new_node;   
        } 
        else    { 
        /*Locate the node before the point of insertion */      
            current =*head_ref;            
            while (current->next!=NULL && current->next->data < new_node->data) 
           {            
              current = current->next;  
         }        
           new_node->next =current->next;   
           current->next = new_node;    }
     }

Answer 2

问题：

The number inserted to the second position every time...

发生是因为在这部分代码中：

while(n!=NULL&&n->data > new->data){             // find which position     num should insert in sorted list
        n = n->next;
}
new->next = n->next;          
n->next= new;

您正在 n->next 之后插入新节点。

假设你的链表的第一个节点有数据16，现在你想在链表中插入数据为45的新节点，while循环条件将失败，因为 16 > 45 将评估为 false.

while 循环后的语句 new->next = n->next; 会将新节点的下一个设置为第一个节点的下一个， n->next= new; 会将新节点插入到第一个节点之后。因此，每次都会将新节点插入到第二个位置。

你的函数还有一些问题 insertSort() 比如：

向链表插入节点时不跟踪链表的head，
如果插入的节点是链表的第一个节点会怎样？在那种情况下 n 将 NULL 并且在 insertSort() 之后 while 循环它正在访问 n - new->next = n->next; 的 next.

查看您给出的示例 - <16,32,72,81,97>，您想按升序插入。你可以这样做：

struct linkedList *insertSort(struct linkedList *n, int num, int *length) {
    struct linkedList *first_node = n;

    struct linkedList *new_node = malloc(sizeof(struct linkedList));  //create a new node
    new_node->next=NULL;
    new_node->data = num;

    if (first_node == NULL || first_node->data >= new_node->data) {
            new_node->next = first_node;
            first_node = new_node;
    } else {
            struct linkedList *temp = first_node;

            while (temp->next != NULL && temp->next->data < new_node->data) {
                    temp = temp->next;
            }
            new_node->next = temp->next;
            temp->next = new_node;
    }
    *length += 1;

    return first_node;
}

在这里，您可以看到我已经将 return 类型 void 更改为 struct linkedList * 以便在将新节点插入到链表中的适当位置后 insertSort() 将 return链表的head。这样你就可以在每次插入后跟踪链表的 head 。你只需要做：

head = insertSort(head, num, &length);

无论你在哪里打电话insertSort()。

或者，如果不想改变 insertSort() 的 return 类型，你可以在 insertSort() 中传递 head 指针的地址并跟踪它=]，像这样：

void insertSort(struct linkedList **head, int num, int *length) {
    struct linkedList *new_node = malloc(sizeof(struct linkedList));  //create a new node
    new_node->next=NULL;
    new_node->data = num;

    if (*head == NULL || (*head)->data >= new_node->data) {
        new_node->next = *head;
        *head = new_node;
    } else {
        struct linkedList *temp = *head;

        while (temp->next != NULL && temp->next->data < new_node->data) {
                temp = temp->next;
        }
        new_node->next = temp->next;
        temp->next = new_node;
    }
    *length += 1;
}

你可以这样调用insertSort()：

insertSort(&head, 32, &length);

希望这对您有所帮助。

向排序链表插入一个数，为什么每次都插入到第二个位置？

Insert a number to a sorted linked list, why the number inserts to the second position every time?

c

sorting

linked-list

insert

singly-linked-list