維護排序的鏈接列表

Question

我試圖創建和維護排序的鏈接列表。每個新元素都應該以列表保持排序的方式插入。我已經能夠編寫代碼，但對代碼不太滿意。

基本上有4個條件需要滿足根據我和我試圖實現所有他們我認爲我已經使代碼更復雜，它應該是。

只是想知道是否有人更有效地編碼它，如果你能告訴我如何改善插入功能。這是我的工作代碼和評論條件。爲了保持它小的時候沒有貼的功能刪除元素，銷燬清單等

#include <iostream> 

    using namespace std; 

    struct node{ 
     int _val; 
     node* _next; 
    }; 

    void printList(node **s){ 

     node *t = *s; 
     while(t){ 
      cout << t->_val << endl; 
      t = t->_next; 
     } 
    } 

    void insertSortElement(node** s, int val){ 

     node* t = *s; 
     if(t){ 
      if(t->_next == NULL || (t->_val > val)){ 
       node* p = new node(); 
       p->_val = val; 
       if(t->_val > val){ 
        //3. More than 1 element in the list but 1st element > val 
        p->_next = t; 
        *s = p; 
       } 
       else{ 
        //2. Only 1 element in the list and < val 
        t->_next = p; 
       } 
      } 
      else{ 
       //4. More than 1 element and 1st < val 
       node* prev = 0; 
       while(t){ 
        if(t->_val > val) 
         break; 
        prev = t; 
        t = t->_next; 
       } 
       node* p = new node(); 
       p->_val = val; 
       p->_next = t; 
       prev->_next = p; 
      } 
     } 
     else{ 

      //1. no element in the list 
      node* p = new node(); 
      p->_val = val; 
      p->_next = NULL; 
      *s = p; 
     } 
    } 

    int main(){ 
     struct node* s = 0 ; 

     insertSortElement(&s,5); 
     insertSortElement(&s,6); 
     insertSortElement(&s,4); 
     insertSortElement(&s,2); 
     insertSortElement(&s,8); 
     insertSortElement(&s,1); 
     printList(&s); 
    } 

編輯：

找到另一種實現方式，比我的要簡單得多，並處理所有案件

void insertSorted(node**s , int val){ 
     node* current = *s; 

       if(current == NULL || current->_val >= val){ 
         node* p = new node(); 
         p->_val = val; 
         p->_next = current; 
         *s = p; 
       } 
       else{ 

         while(current->_next != NULL || current->_next->_val < val) 
           current = current->_next; 

         node* p = new node(); 
         p->_val = val; 
         p->_next = current->_next; 
         current->_next = p; 
       } 
} 

Answer 1

我認爲你應該編寫一個方法insertElement，然後重寫insertSortedElement爲「搜索要插入的位置，然後在那裏調用insertElement」 - 我認爲這將清理代碼並使其更具邏輯性和可讀性。

這樣，您可以編寫更多的模塊化代碼。所有奇怪的邊緣情況都可以通過insertElement來處理，並且您可以單獨優化插入和位置搜索，這將導致更少的混淆。

一些僞代碼：

insertElement(node old_node, value val) 
    allocate memory for new node new_node 
    new_node.val = val 
    new_node.next = old_node 
    new_node.prev = old_node.prev 

insertSortedElement(value val) 
    actnode = first node 
    while actnode.next != NULL 
    if (actnode.val >= val) 
     insertElement(actnode, val) 
     break; 
    actnode = actnode.next 

應該是簡單的，希望我沒有忘記任何事情......

Answer 2

更快的方法將使用二進制搜索找到合適的地方插。它被稱爲「跳過列表」。

此外，您可以使用santinels來避免檢查第一個和最後一個元素的特殊情況。

Answer 3

Err ...爲什麼？這不是std::multiset的用途嗎？

#include <set> //for std::multiset 
#include <iterator> //for std::ostream_iterator 
#include <algorithm> //for std::copy 
#include <iostream> //for std::cout 

int main() 
{ 
    //Put things in sorted collection. 
    std::multiset<int> collection; 
    collection.insert(5); 
    collection.insert(6); 
    collection.insert(4); 
    collection.insert(2); 
    collection.insert(8); 
    collection.insert(1); 

    //Print them to show sort. 
    std::copy(collection.begin(), collection.end(), std::ostream_iterator(std::cout, "\n")); 
}