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

Answer 2

一般来说，链表由"节点"组成，这些"节点"通过从每个节点指向下一个节点(或前一个节点，或两者(的链接按顺序连接在一起。 每个节点也(可能微不足道地(指向列表的实际元素之一。

要将元素插入到给定位置的链表中，只需创建一个指向该元素的节点，并根据需要更新其他指针。 对于像您这样的双向链表(其中每个节点都指向下一个节点和前一个节点(，您必须

• 将紧接在插入位置之前的节点的next指针更新为指向新节点，
• 将紧跟在插入位置之后的节点的prev指针更新为指向新节点，以及
• 将新节点的prev和next指针设置为指向这些其他节点。

通常在列表的开头或结尾插入特殊情况;详细信息取决于您的列表和节点实现。

在您的情况下，您还必须找到合适的插入点。 由于列表已排序，因此您可以从头开始遍历它，将每个节点的元素与要插入的元素进行比较，直到找到正确的位置。 如果列表很长，这种"线性搜索"并不是非常有效，但是使用通用链表不能做得更好。

Answer 3

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

有一个损失数据，因此您将 x 与覆盖写入列表中的第一个数据。İif ı 理解了您应该创建一个节点并将其插入到列表中的问题。