Вставка элемента в отсортированный список

Question

У меня возникли проблемы с тем, как вставить элемент в отсортированный список. Я новичок в связанных списках, и у меня все еще возникают проблемы. Следующая функция принимает предопределенный список и элемент в качестве аргументов. У меня есть белый, все это, но я все еще не могу понять. Спасибо за помощь.

/* 
* function: lst_insert_sorted 
* 
* description: assumes given list is already in sorted order 
*  and inserts x into the appropriate position 
*  retaining sorted-ness. 
* Note 1: duplicates are allowed. 
* 
* Note 2: if given list not sorted, behavior is undefined/implementation 
*  dependent. We blame the caller.  
*  So... you don't need to check ahead of time if it is   sorted. 
*/ 

void lst_insert_sorted(LIST *l, ElemType x) { 
    NODE *p = l->front; 
    NODE *temp; 
    NODE *current = p; 
    NODE *prev; 
    NODE *next; 

    if (p->val >= x) { // Base Case if 
     p->val = x; 
    } 

    while (p !=NULL) { 
     prev = current; 
     temp = prev->next; 
     next = current->next; 

     if (next->val >= x) { 
      temp->val = x; 
     } 

    } 

    return 0; 
} 

Answer 1

Вы не указали, как определен NODE. Поэтому я полагаю, что список является односвязным списком. В этом случае данная функция может выглядеть так:

void lst_insert_sorted(LIST *l, ElemType x) 
{ 
    NODE *current = l->front; 
    NODE *prev = NULL; 

    while ((current != NULL) && !(x < current->val)) 
    { 
     prev = current; 
     current = current->next; 
    } 

    NODE *node = malloc(sizeof(NODE)); 
    node->val = x; 

    node->next = current; 
    if (prev != NULL) 
    { 
     prev->next = node; 
    } 
    else 
    { 
     l->front = node; 
    } 
} 

Answer 2

Вообще говоря, связанный список состоит из «узлов» соединены друг с другом в определенной последовательности с помощью ссылок, указывающих из каждого узла к следующему (или к предыдущей, или обоих). Узлы каждой точки также (возможно, тривиально) относятся к одному из фактических элементов списка.

Чтобы вставить элемент в связанный список в заданную позицию, вы просто создаете узел, указывающий на этот элемент, и обновляете другие указатели по мере необходимости. С двусвязный список таких, как ваш (где каждый узел указывает как на следующий и на предыдущий), вы должны

• обновляют next указатель узла, непосредственно предшествующий положение вставки указать на новый узел,
• обновляют prev указатель узла сразу после позиции вставки в точку на новом узле и
• установить prev и next указатели нового узла, чтобы указать на эти другие узлы.

Как правило, для ввода в начале или конце списка обычно имеются особые случаи; детали зависят от вашего списка и реализации узла.

В вашем случае вы также должны найти соответствующую точку вставки. Поскольку список сортируется, вы можете просто пересечь его с самого начала, сравнивая элемент каждого узла с тем, который нужно вставить, пока не найдете нужное место. Такой «линейный поиск» не очень эффективен, если список длинный, но вы не можете сделать лучше с общим связанным списком.

Answer 3

if (p->val >= x) { // Base Case if 
    p->val = x; 
} 

есть данные о потерях, поэтому вы написали x с переписыванием первых данных в списке. İf ı понимал проблему, которую вы должны создать, и вставить ее в список.