将元素插入排序列表

我无法弄清楚如何将元素插入到排序列表中。我是链接列表的新手，但仍然遇到麻烦。以下函数将预定义列表和元素作为参数。我有白人登上了整个事情，但我仍然无法弄清楚。感谢您的帮助。将元素插入排序列表

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

来源

2014-12-05 Rbutler93

列表是单链表吗？ – 2014-12-05 17:38:42

您没有显示如何定义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; 
    } 
}

来源

2014-12-05 17:50:33

一般来说，一个链表由“节点”的通过从每个节点指向下一个（或上一个一个，或两者）链接在序列连接在一起。每个节点也指向（也许不重要）列表的实际元素之一。

要将元素插入给定位置的链接列表中，只需创建一个指向该元素的节点，并根据需要更新其他指针。用双向链表如你的（其中每个节点指向两者到下一个和前一个），则必须

更新next指针的节点的紧接插入位置之前，以在点新的节点，
更新prev指针立即插入位置在新节点指向下列的节点，和
设置新节点的prev和next指针指向这些其他节点。

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

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

来源

2014-12-05 17:25:40

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

有一个损失数据，所以你写了x覆盖到列表中的第一个数据。我们知道你应该创建一个节点并将其插入到列表中。

来源

2014-12-05 17:25:49 batuhan

将元素插入排序列表

回答

相关问题