如果输入数据不在列表末尾，则带有插入排序的 C 双链表会继续覆盖

Question

我正在尝试使用用户输入实现插入排序双向链表，每次用户输入数据时都会对列表进行排序。

如果在用户输入所有数据后调用插入排序函数，我的代码就可以正常工作。

User Input: 5  
User Input: 1
User Input: 3
User Input: 8
User Input: 7
User Input: 9

Unsorted List: 5  1  3  8  7  9

//Insertion Sort Function gets called after all the data have been entered//

Output: 1  3  5  7  8  9

但是如果每次用户输入新数据时我都调用插入排序函数，它就会变得混乱，如果插入的节点不在列表的末尾，即使它已成功插入，它也会以某种方式覆盖下一个节点列表之间的新数据。

User Input: 1
//Insertion Sort Function gets called//
Output: 1

User Input: 2
//Insertion Sort Function gets called//
Output: 1  2

User Input: 9
//Insertion Sort Function gets called//
Output: 1  2  9

User Input: 3
//Insertion Sort Function gets called//
Output: 1  2  3 9

User Input: 4
//Insertion Sort Function gets called//
Output: 1  2  3  4

如您所见，3 被很好地插入到列表中，但不知何故，我的代码认为列表的末尾现在在 3 之后，所以当我输入新数据时，例如，4 到新列表中列表，9 被覆盖，因为它认为 3 是列表的末尾。

我的插入排序功能有问题吗？

如何导航回列表末尾并使其在列表末尾添加新数据？

我的全部代码包含在下面，

#include<stdio.h> 
#include<stdlib.h> 
  
//// structure for a node ////
struct Node 
{ 
    int data; 
    struct Node *prev;
    struct Node *next; 
}; 


typedef struct Node NODE;
  
void UserInput();
void printList(struct Node *head, );
void insertionSort(struct Node **head_ref);
void sortedInsert(struct Node** head_ref, struct Node* newNode);

  
void main() 
{ 
UserInput();

_getch();  
} 




void UserInput()
{
    
    int loop=0; 
    int data;
  
    struct Node *temp;
    NODE *tail = NULL;
    
    
    struct Node *head;
    head = (struct Node*)malloc(sizeof(struct Node));  ////create node, store address to temp
    
        printf("\nEnter Data: "); 
        scanf(" %d" , &data);
        head->data = data;
        head->prev = NULL; //// head node's prev is set to NULL
        head->next = NULL; //// head node's next is set to NULL
        tail = head;
        printList(head);
      
    while (loop < 9999) 
    {
        temp = (struct Node*)malloc(sizeof(struct Node));  ////create node, store address to temp
        printf("\nEnter Data: "); 
        scanf(" %d" , &data);
        if(data == 9999)
        {
            break;
        }
        
        temp->data = data;
        printList(head);
        temp->prev = tail; //// prev pointer of temp is referenced to the last node
        temp->next = NULL; //// next pointer of temp is NULL
        tail->next = temp; //// next pointer of the tail node is referenced to the temp
        tail = temp;       //// temp is made as the tail node
        
        insertionSort(&head);
        printList(head);
        loop++;
    }
    
    
    printf("Insertion of Numbers Terminated.");
    //// If insertionSort function is called after all  User Inputs, there are no problems in sorting.
    //insertionSort(&temp);
    printList(temp);

    
}

////Printing Function to get called every loop////
void printList(struct Node *head) 
{ 
 struct Node *temp1 = head; 

 temp1 = head;
 
 printf("\nSorted Numbers: ");

 while(temp1 != NULL)
 {
 printf(" %d ", temp1->data);
 temp1 = temp1->next;
 }
 
}
  

////Insertion Sort Algorithm to sort the list////
void insertionSort(struct Node **head_ref) 
{ 
    //// Initialize 'sorted' - a sorted doubly linked list 
    struct Node* sorted = NULL; 
  
    //// Traverse the given doubly linked list and insert every node to 'sorted' 
    struct Node* current = *head_ref; 
    while (current != NULL) { 
  
        //// Store next for next iteration 
        struct Node* next = current->next; 
  
        //// removing all the links so as to create 'current' as a new node for insertion 
        current->prev = current->next = NULL; 
  
        //// insert current in 'sorted' doubly linked list 
        sortedInsert(&sorted, current); 
  
        //// Update current 
        current = next; 
    } 
  
    //// Update head_ref to point to sorted doubly linked list 
    *head_ref = sorted;
} 



void sortedInsert(struct Node** head_ref, struct Node* newNode) 
{ 
    struct Node* current; 
  
    //// if list is empty 
    if (*head_ref == NULL)
    {
        *head_ref = newNode;
    }
    //// if the node is to be inserted at the beginning of the doubly linked list 
    else if ((*head_ref)->data >= newNode->data) 
    { 
        newNode->next = *head_ref; 
        newNode->next->prev = newNode; 
        *head_ref = newNode; 
    }
  
    else 
    { 

        current = *head_ref; 
  
        //// locate the node after which the new node is to be inserted 
        while (current->next != NULL && current->next->data < newNode->data)
        {
            current = current->next;
        }
  
        ////Make the appropriate links ////
  
        newNode->next = current->next; 
  
        //// if the new node is not inserted at the end of the list 
        if (current->next != NULL)
        {
            newNode->next->prev = newNode;
        }

        current->next = newNode; 
        newNode->prev = current; 
    } 
}

Answer 1

问题出在UserInput()插入数据时临时节点的下一个应该指向尾部的下一个所以改变这一行

temp->next = NULL;

进入这个

temp->next = tail->next;

为什么？？因为您正在交换节点本身，所以在每个 insertionSort() 之后，下一个更新的尾巴不会为 NULL，而是指向某个先前添加的节点地址，因为我们正在交换节点，因此地址正在互换。在此处检查示例代码：https://ideone.com/gSKK7B

如果输入数据不在列表末尾，则带有插入排序的 C 双链表会继续覆盖

C Doubly Linked List w/ Insertion Sort keeps overwriting if Inputted Data is not at the End of the List

c

doubly-linked-list

insertion-sort