Как сделать связанный список упорядоченным в C++?

Question

#include <iostream> 
#include <string> 
using namespace std; 
struct node 
{ 
    int num; 
    node*next; 
}; 

bool isEmpty(node *head); 
char menu(); 
void insertasfirstelement(node *&head, node *&last, int num); 
void insert(node *&head, node *&last, int num); 
void remove(node *&head, node *&last); 
void showlist(node*c); 

bool isEmpty(node*head) 
{ 
    if(head == NULL) 
     return true; 
    else 
     return false; 
} 
char menu() 
{ 
    char choice; 

    cout << "\n\nMenu:\n"; 
    cout << "\n1. Add an item"; 
    cout << "\n2. Remove an item"; 
    cout << "\n3. Show the list"; 
    cout << "\n4. Exit" <<endl; 

    cin >> choice; 
    return choice; 
} 
void insertasfirstelement(node *&head, node*&last, int num) 
{ 
    node * temp = new node; 
    temp ->num=num; 
    temp ->next=NULL; 
    head = temp; 
    last = temp; 
} 
void insert(node *&head, node *&last, int num) 
{ 
    if(isEmpty(head)) 
     insertasfirstelement(head,last,num); 
    else 
    { 
     node *temp = new node; 
     temp ->num=num; 
     temp ->next=NULL; 
     last ->next= temp; 
     last = temp; 
    } 
} 
void remove(node *&head, node *&last) 
{ 
    if(isEmpty(head)) 
     cout << "List is empty\n"; 
    else if(head == last) 
    { 
     delete head; 
     head = NULL; 
     last = NULL; 
    } 
    else 
    { 
     node *temp = head; 
     head = head -> next; 
     delete temp; 

    } 
} 
void showlist(node*c) 
{ 
    if(isEmpty(c)) 
     cout <<"The list is empty\n"; 
    else 
    { 
     cout << "The values are: \n"; 
     while(c !=NULL) 
     { 
      cout << c -> num << endl; 
      c = c -> next; 
     } 
    } 
} 
int main() 
{ 
    node *head=NULL; 
    node *last=NULL; 
    char choice; 
    int num; 

    do{ 
     choice = menu(); 

     switch(choice) 
     { 
      case '1': cout << "Please enter a number: "; 
         cin >> num; 
         insert(head, last, num); 
         break; 
      case '2': remove(head,last); 
         break; 
      case '3': showlist(head);`` 
         break; 
      default: cout << "System exit\n"; 
     } 
    } while(choice != '4'); 
} 

Таким образом, мне удалось получить рабочий список ссылок. Но я не смог понять, как его привести в порядок. Я также не знаю, как это сделать, поэтому я могу удалить число, которое я вставил. Я пытаюсь понять, как связанные списки работают лучше, поэтому, если вы можете оказать некоторую помощь, мы будем очень благодарны.

Answer 1

Оба следующих функций предположим, что вы хотите, связанный список отсортирован в порядке возрастания.

Чтобы вставить новый узел в связанном объекте списка, вы можете попробовать:

void insert(node *&head, node *&last, int num) 
{ 
    if(isEmpty(head))   
     insertasfirstelement(head,last,num); 
    else if(num > tail->num) //if new number to be inserted is greater than tail, insert at end and avoid needless iteration through list 
    { 
     node* temp = new node; 
     temp->num = num; 
     temp-next = NULL; 
     last->next = temp; 
     last = temp; 
    } 
    else 
    { 
     node *temp = new node; 
     temp ->num=num; 
     temp ->next=NULL; 
     node* ptr = head; //to lead iteration through linked list 
     node* prev = NULL; //to trail ptr 
     while(ptr && (ptr->num > temp->num)) //iterate through linked list while new node's value is less than ptr's value and ptr is not beyond end of list (assuming last->next == NULL) 
     { 
      prev = ptr; 
      ptr = ptr->next; 
     } 
     if(!prev)   // if prev never iterated, the temp node is the new head node 
     { 
      head = temp; 
      head->next = ptr; 
     } 
     else if(prev == last) //if prev is tail, the temp node is the new tail node 
     { 
      prev->next = temp; 
      tail = temp; 
     } 
     else //otherwise, insert temp node in between prev and ptr 
     { 
      prev-next = temp; 
      temp->next = ptr; 
     } 
    } 
} 

Чтобы удалить узел из вашего связанного списка объектов попробовать:

void remove(node *&head, node *&last, int x) // added a int parameter to determine which node is to be removed 
{ 
    if(isEmpty(head)) 
     cout << "List is empty\n"; 
    else 
    { 
     node* ptr = head; 
     node* prev = NULL; 
     while(ptr && (ptr->num != x) //iterate through linked list while desired value to be deleted is not found and have not gone through entire list 
     { 
      prev = ptr; 
      prt = ptr->next; 
     } 
     if(!prev)  //if prev never iterated, the head is the value to be deleted 
     { 
      node* garbage = head; 
      head = head->next; 
      delete garbage; 
     } 
     else if(ptr==tail) //if the value to be deleted is the tail's value, reassign tail to prev and delete ptr 
     { 
      tail = prev; 
      tail->next = NULL; 
      delete ptr; 
     } 
     else if(!ptr) //if ptr == NULL, value to be deleted was not in list 
     { 
      cout << "Value " << x << " could not be found in list.\n";  // or throw exception 
     } 
     else  //reassign prev's next to ptr's next and delete ptr; 
     { 
      prev-next = ptr->next; 
      delete ptr; 
     } 
    } 
} 

Answer 2

Вы можете сделать связанный список упорядочивается путем сравнения поля данных узла

Попробуйте так:

1 - До узла NULL путешествия через связанный список.

2 - Если данные текущего узла меньше данных следующего узла, замените оба данных.

3 - еще переход к следующему узлу

И если вы хотите заказать связанный список без поменяв данные ... т.е. изменение следующего узла, то вы также можете сделать это путем ..

для удаления узла

попробовать этот способ

1 Ask пользователю ввести данные узла, который он/она хочет удалить.

2- поиск этого узла, который имеет эти данные.

3- если этот узел найден, удалите этот узел.

4- else найти узел в оставшемся списке.

Примечание: Это так же, как, как это сделать ... Вы должны построить логику, так что вы можете поддерживать согласованность в связанном списке :)