Помещение узла связанного списка в алфавитном порядке

Question

Мне нужно сделать так, чтобы пользователь мог вставлять слова, пока они не нажмут «xxx». эта часть уже выполнена, но тогда мне нужен список, который всегда будет в алфавитном порядке. Я не могу понять, как это сделать. Я должен сделать это в алфавитном порядке в функции, которая добавляет новый узел, а не функцию, которая печатает узлы на экране. это потому, что это для класса и требуется.

Узла заголовок файл:

struct Node 
{ 
    string  word; 
    struct Node *next; 
}; 

Функция заголовок прототипа файл:

Node *add_node(Node *list, const string &s); 
Node *del_node(Node *list, const string &s); 

void deallocate(Node *list); 
void print(Node *list); 

Код, который компилируется:

#include <iostream> 
#include <iomanip> 
#include <string> 
using namespace std; 

#include "Node.h" 
#include "funcs.h" 

int main() 
{ 
    struct Node *list = 0;  // list is a pointer to struct Node 

    cout << "please enter a few words (xxx to terminate list):\n"; 

    string s;     // s is a string object 

    while (cin >> s)   // read a string into s 
    { 
     if (s == "xxx") 
     { 
      break;    // terminate loop when string is equal to   "xxx" 
     } 
     // add s to list in alphabetical order 
     list = add_node(list, s); 

     cout << "\nlist:\n"; 
     print(list); 
     cout << '\n'; 
    } 

    cout << "\nhere is the list:\n"; 
    print(list); 
    cout << '\n'; 

    cout << "please enter word words to delete from the list (xxx to terminate):\n"; 
     while (cin >> s) 
     { 
      if (s == "xxx") 
      { 
       break;    // terminate loop when string is equal to "xxx" 
      } 
      // delete first node containing string s 
      //list = del_node(list, s); 

      cout << "\nlist:\n"; 
      print(list); 
      cout << '\n'; 
     } 

    cout << "\nthe final list:\n"; 
    print(list); 
    cout << '\n'; 
    // deallocate the linked list 
    cout << "\ndeallocating the list:\n"; 
    deallocate(list); 

    cout << "\nall done!\n"; 
    return 0; 
} 

Код с функциями:

#include <iostream> 
#include <iomanip> 
#include <string> 
using namespace std; 

#include "Node.h" 


Node *add_node(Node *list, const string &s) 
{ 
    struct Node *n = new struct Node; 
    n->word = s;   // copy string s to word 
    n->next = list; 

    // add node n to the list 
    // the list should always be in ascending alphabetical order 

    list = n; 

    return list;   // returning pointer to beginning of the list 
} 


Node *del_node(Node *list, const string &s) 
{ 
    // delete node in the list that contains s 
    // the list should always be in ascending alphabetical order 

    // if s does not appear in the list, there is nothing to do 
    // if s appears multiple times in the list, delete the first occurrence 
    Node *lastp = 0; 
    Node *p = list; 
    for (; p; p = p->next) 
    { 
     if (p->word == s) 
     { 
      lastp->next = p->next; 
      delete p; 
      break; 
     } 
     lastp = p; 
    } 


    return list;   // returning pointer to beginning of the list 
} 


void deallocate(Node *list) 
{ 
    for (struct Node *p = list; p;) 
    { 
     struct Node *tmp = p; // remember current pointer 

     p = p->next;   // advance p to the next node 

     delete tmp;    // deallocate tmp 

     // OK to print pointers tmp and p 
     cout << "deallocated\t" << tmp << "\tnext is\t" << p << '\n'; 
    } 
} 


void print(Node *list) 
{ 
    for (struct Node *p = list; p; p = p->next) 
    { 
     cout << p << '\t' << setw(8) << p->word 
      << '\t' << "next:" << '\t' << p->next << '\n'; 
    } 
} 

Весь код, вероятно, не требуется для ответа на вопрос, но я решил, что включу его.

Answer 1

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

#include <iostream> 
#include <string> 

struct Node 
{ 
    std::string word; 
    struct Node *next; 
}; 

Node *add_node(struct Node *list, const std::string &s) 
{ 
    struct Node *prev = nullptr; 
    struct Node *current = list; 

    while (current && !(s < current->word)) 
    { 
     prev = current; 
     current = current->next; 
    } 

    if (prev == nullptr) 
    { 
     list = new Node { s, list }; 
    } 
    else 
    { 
     prev->next = new Node { s, prev->next }; 
    } 

    return list; 
} 

void print_list(const struct Node *list) 
{ 
    for (; list != nullptr; list = list->next) std::cout << list->word << ' '; 
} 

int main() 
{ 
    struct Node *list = nullptr; 

    // for (const std::string &s : { "B", "X", "A", "C", "F", "G" }) 
    for (const char *s : { "B", "X", "A", "C", "F", "G" }) 
    { 
     list = add_node(list, s); 
    } 

    print_list(list); 
    std::cout << std::endl; 

    return 0; 
} 

Выход

A B C F G X