在已排序的链表中插入数字，为什么数字每次都插入第二个位置? [英] Insert a number to a sorted linked list, why the number inserts to the second position every time?

问题描述

我正在做一个有关链表的项目，在将数字插入到已排序的链表中时遇到麻烦.每次插入第二个位置的数字时，我都无法确定问题出在哪里.这是我的代码:

I am working on a project about linked list, I have trouble with inserting a number to a sorted linked list. The number inserted to the second position every time, I cannot figure out where the problem is.Here is my code:

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是链接列表的开头.我将头节点初始化为第一个节点，但没有值. 这是我所谓的函​​数:

n is head of the linked list. I initialized head points to the first node and has not value. Here is how I call this function:

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

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

The number inserted to the second position every time. Like I want to insert 45 into sorted linked list <16,32,72,81,97>, after inserting, the list would be <16,45,32,72,81,97>. 45 inserts to the second position for some reason.

推荐答案

问题:

每次插入第二个位置的数字...

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

之所以发生是因为在这部分代码中:

is occurring because in this part of code:

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之后插入新节点.

you are inserting the new node after the n->next.

假设链表的第一个节点包含数据16，现在您要在链表中插入数据为45的新节点，则while循环条件将失败，因为16 > 45将求值到false.

Assume the first node of your linked list is having data 16 and now you want to insert the new node with data 45 in the linked list, the while loop condition will fail as 16 > 45 will evaluate to false.

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

And the statement after while loop new->next = n->next; will set the next of new node to next of the first node and n->next= new; will insert the new node after first node. Hence, the new node inserted to second position every time.

您的函数insertSort()几乎没有其他问题，例如:

There are few more problems with your function insertSort() like:

• 在将节点插入到链表中时，它不会跟踪链表的head，并且
• 如果插入的节点是链表的第一个节点，将会发生什么?在这种情况下，n将NULL，并且在insertSort()循环之后的insertSort()中，它正在访问n-new->next = n->next;的next.

• It does not track the head of the linked list while inserting a node to the linked list and,
• What will happen if the node inserted is the first node of the linked list? In that case n will NULL and in insertSort() after while loop it is accessing next of n - new->next = n->next;.

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

Looking at the example you have given - <16,32,72,81,97>, you want to insert in ascending order. You can do:

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;
}

在这里，您可以看到我将返回类型void更改为struct linkedList *，以便在将新节点插入链表insertSort()中的适当位置后，将返回链表的head.这样，您可以在每次插入后跟踪链接列表的head.您只需要这样做:

Here, you can see that I have changed return type void to struct linkedList * so that after inserting new node to appropriate location in linked list insertSort() will return the head of the linked list. That way you can keep track of head of linked list after every insertion. You just need to do:

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

无论您在哪里呼叫insertSort().

或者，如果您不想更改insertSort()的返回类型，则可以在insertSort()中传递head指针的地址并对其进行跟踪，如下所示:

Alternatively, you can pass the address of head pointer in insertSort() and keep track of it, if you don't want to change the return type of insertSort(), like this:

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);

希望这会有所帮助.

这篇关于在已排序的链表中插入数字，为什么数字每次都插入第二个位置?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！