將元素插入排序列表

我無法弄清楚如何將元素插入到排序列表中。我是鏈接列表的新手，但仍然遇到麻煩。以下函數將預定義列表和元素作爲參數。我有白人登上了整個事情，但我仍然無法弄清楚。感謝您的幫助。將元素插入排序列表

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

將元素插入排序列表

回答

相關問題