排序链接列表

-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

排序链接列表

回答

相关问题