c - 将元素插入排序列表

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