C语言 C - 按升序插入链表

C - Inserting into linked list in ascending order

提问by StackOverflower

I am trying to create a program that inserts numbers into a linked list in ascending order. This is my insert function. It works for inserting some numbers but not others. I think it has something to do with the last part, but i cant figure it out.

我正在尝试创建一个程序，以升序将数字插入到链表中。这是我的插入功能。它适用于插入一些数字而不是其他数字。我认为这与最后一部分有关，但我无法弄清楚。

node* insert(node* head, int value) {

    //check if head hasn't been created
    if (head == NULL) {
        head = malloc(sizeof(node));
        if(head == NULL) {
            printf("Failed to create head node");
            return head;
        }
        head->value = value;
        head->next = NULL;
        return head;
    }

    //create a new node
    node *newNode;
    newNode = malloc(sizeof(node));
    if(newNode == NULL) {
        printf("Failed to create node");
        return newNode;
    }
    newNode->value = value;
    newNode->next = NULL;

    //see if new node should be placed before head
    if (value < head->value) {
        newNode->next = head;
        return newNode;
    }

    //search through to find correct spot and insert the node
    node *temp = NULL;
    temp = head;
    while(temp->next != NULL && temp->value < value) {
        temp = temp->next;
    }
    newNode->next = temp->next;
    temp->next = newNode;
    return head;

}

回答by BLUEPIXY

Part of the following bad

以下部分不好

//search through to find correct spot and insert the node
node *temp = NULL;
temp = head;
while(temp->next != NULL && temp->value < value) {
    temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;

e.g. to fix like this:

例如像这样修复：

node *temp ,*prev;
temp = head;
while(temp != NULL && temp->value <= value) {
    prev = temp;
    temp = temp->next;
}
newNode->next = temp;
prev->next = newNode;

or

或者

node *temp ,*prev;
temp = head->next;
prev = head;
while(temp != NULL && temp->value < value) {
    prev = temp;
    temp = temp->next;
}
newNode->next = temp;
prev->next = newNode;

回答by Sundar

You need to check for temp->next->valueinside the last while loop.

您需要temp->next->value在最后一个 while 循环内检查。

回答by Ajeet Murmu

//This code of mine works perfectly.

void insertInAscOrder(int val) 
{
    node *new1;
    node *temp;
    node *previous; 

    //create new node
    new1 = (node *)malloc(sizeof(node)); 

    //check whether node is created or not
    if(new1 == NULL) 
    {
        printf("Insufficient memory.");
        return;
    }   

    //Updating different parts of the node
    new1 -> info = val;
    new1 -> next = NULL;    

    //checking whether the node created is only node or not
    if (start == NULL) 
    {       
        start = new1;
    } 
    //If value is less than the value of first node
    else if(val < start -> info) 
    {
        new1 -> next = start;
        start = new1;
    } 
    else 
    {   
        previous = start;
        temp = start -> next;


            //Go to the position where node is to be inserted
            while(temp != NULL && val > temp -> info) 
            {
                previous = temp;
                temp = temp -> next;
            }


            //Insert the node at particular position
           if(temp == NULL) 
           {
                   previous -> next = new1;
           } 
           else 
           {
                   new1 -> next = temp;
               previous -> next = new1;
           }
    }
}

回答by Ziezi

It would be much better if you firstly implement (and test) functions like: push_front(), insert()(insert before), and push_back(), (probably advance (Node* curr, int steps);) and then simply take into consideration all the possibilities of insertion, i.e.:

如果您首先实现（并测试）如下函数会更好：push_front(), insert()（之前插入）和push_back(), （可能advance (Node* curr, int steps);）然后简单地考虑所有插入的可能性，即：

• empty list (current node is first, so just push_front / back())
• iterate (advance()) over all elements from headand on, till:
  • element with value larger than the new is found, insert()before it.
  • last element reached, push_back().

• 空列表（当前节点是第一个，所以只是push_front / back()）
• advance()对所有元素进行迭代 ( ) head，直到：
  • insert()在它之前找到值大于新元素的元素。
  • 最后一个元素到达，push_back()。

in your new function insert_ordered().

在您的新功能中insert_ordered()。