将数字插入已排序的链接列表，为什么数字每次都插入第二个位置？

我正在开发一个关于链表的项目，我无法将数字插入到已排序的链表中。 每次插入第二个位置的数字，我无法弄清楚问题出在哪里。这是我的代码：

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是链表的头部。 我将头点初始化为第一个节点并且没有值。 以下是我如何调用此函数：

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

每次插入第二个位置的数字。 就像我想在排序的链表中插入45，插入后，列表将是。 由于某种原因，45插入第二位置。

Answer 1

问题 ：

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

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

 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并且在while循环之后的insertSort() ，它正在访问n – new->next = n->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; } 

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

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

从你调用insertSort()任何地方。

或者，您可以在insertSort()传递head指针的地址并跟踪它，如果您不想更改insertSort()的返回类型，如下所示：

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

希望这可以帮助。

Answer 2

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

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