排序鏈接列表

-1

我幾乎完成了一個程序，但我需要按升序排序鏈接列表，我一直在嘗試幾個小時，但無法弄清楚，但程序的其餘部分工作。假設生成6個隨機數並將它們存儲在一個鏈表中並每次輸出它，直到它達到6個數字，然後停止，然後刪除每個元素直到它們全部被移除。但是假設在輸出它們時對數字進行排序。它將節點存儲在函數push_sorted中，所以我會認爲這是排序函數將去，但我再也找不出如何排序鏈接列表。不管怎麼說感謝您的幫助，這裏是我的整個程序...排序鏈接列表

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include "SortedLinkedList.h" 
#include <algorithm> 
#include <list> 
#include <array> 

using namespace std; 

struct node 
{ 
    int data; 
    node *next; 
}; 

node *head = NULL; 

void push_sorted(int value) 
{ 
    node *newNode = new node; 
    newNode->data = value; 
    newNode->next = NULL; 

    if(head == NULL) 
    { 
     head = newNode; 
    } 
    else 
    { 
     node *newNode_2 = head; 
     while(newNode_2->next != NULL) 
     { 
      newNode_2 = newNode_2-> next; 
     } 
     newNode_2->next = newNode; 
    } 
} 

void pop_front() 
{ 
    node *temp; 
    temp = head; 
    head = head->next; 
    free(temp); 
} 

void pop_back(int pos) 
{ 
    node *temp =head; 
    struct node *t = NULL; 
    if(head->next==NULL) 
    { 
    free(head); 
    head=NULL; 
    } 
    else 
    { 
    while(temp->next != NULL) 
    { 
     t=temp; 
     temp=temp->next; 
    } 
    free(t->next); 
    t->next=NULL; 
    }  


} 



bool isEmpty(int count) 
{ 
    if(count == 0) 
    { 
     return false; 
    } 

    else 
    { 
     return true; 
    } 

} 

void print() 
{ 
    node* current = head; 
    while(current != NULL) 
    { 
     cout << current-> data << " "; 
     current = current->next; 
    } 
    cout << endl; 
} 
int main() 
{ 
    int pos = 4; 
    int count = 6; 
    const int NUMS = 6;  //insert elements into the sorted linked list in an ascending order 
    const int RANGE = 21; //each element is in the range [-10, 10] 
    /*SortedLinkedList mylist;*/ 
    srand(time(0)); 
    for (int i = 0; i < NUMS; i++) 
    { 
     int data = (rand() % RANGE) - 10; 
     cout << "Adding " << data << " to the sorted linked list: " << endl; 
     push_sorted(data); 
     print(); 
    } 

    while ((isEmpty(count) == true)) 
    { 
     cout << "Removing from front..." << endl; 
     pop_front(); 
     print(); 
     count --; 
     /*if (count == 1) 
     { 
      break; 
     }*/ 
     cout << "Removing from back..." << endl; 
     pop_back(pos); 
     print(); 
     count --; 
     pos-= 2; 
    } 
    system("pause"); 
    return 0; 
}

來源

2016-07-30 T North

請在C++中使用'std :: list'和'std :: sort'。那很簡單。 –

您想知道如何將新元素添加到排序列表中，以便在添加之後，列表按排序順序排列。想想你可能會怎麼做，在紙上試試，然後嘗試單獨編碼*。如果你無法工作，請回到這裏併發布你的代碼。 – Beta

對於一個自己動手的鏈表，如學習者的例子：你可以在每個元素的排序位置插入每個元素。對於插入n個元素，這種方法通常涉及大致n²的操作（如移動指針），因此很快變得不切實際。另一種方法是以原始任意順序插入元素，然後使用* merge sort *對列表進行排序。這大致涉及n-log（n）操作，這更爲可取。 –

你應該使用std::list的建議。但是，假設你需要這個其他原因，你可以修改函數對值進行比較和交換節點如下：

void push_sorted(int value) 
{ 
    node *n = new node; 
    n->data = value; 
    n->next = NULL; 
    if (!head) 
    { 
     head = n; 
    } 
    else 
    { 
     node *cursor = head; 
     if (head->data > value) 
     { 
      node *temp = head; 
      head = n; 
      n->next = temp; 
      return; 
     } 
     while (cursor->next) 
     { 
      if (cursor->next->data > value) 
      { 
       node *temp = cursor->next; 
       cursor->next = n; 
       n->next = temp; 
       return; 
      } 
      cursor = cursor->next; 
     } 
     cursor->next = n; 
    } 
}

或者乾脆用

std::list<int> lst; 
lst.push_back(data); 
lst.sort();

您也可以考慮std::vector這出執行std::list大多數時候。

來源

2016-07-31 11:18:35

排序鏈接列表

回答

相關問題