Как сделать список ссылок распечатать его содержимое в алфавитном порядке?

Question

У меня есть список связанных списков телефонной книги с именами, именами и значениями. Я могу распечатать их в том порядке, в котором они были созданы, но не по значению. Как я могу это изменить? Если вам нужно увидеть что-нибудь еще в коде, дайте мне знать, но эта функция является моей главной заботой.

ostream& operator<<(ostream& out, const PhoneBook& p) // out stream 
{ 
    if(p.head==NULL) 
    { 
     cout << "is empty"; 
    }else 
    { 
     PhoneBookItem* item = p.head; 
     for(int i=0; i < p.num; i++) 
     { 
      cout << item->lastname<< " "; 
      cout << item->firstname<< " : "; 
      cout << item->phone<<endl; 
      item = item->next; 
     } 
    } 
    return out; 

Answer 1

Вариант 1: Сортировка списка, а затем распечатать
Вариант 2: Для каждого цикла, поиск какой элемент должен быть напечатан в следующем. (Дорого)
Вариант 3: Использовать Hash/Dictionary подход вместо связанного списка. Hash/Dictionary -
комбинация фиксированного массива и списка ссылок. Они хороши для
поиск предметов быстрее, чем фиксированный массив и связанный список.
Вариант 4: Используйте другую структуру данных, отличную от списка ссылок, которая имеет возможность доступа к вашим данным в порядке/в алфавитном порядке.

Answer 2

Сортировка связанного списка может быть выполнена несколькими способами.

1. Временная контрольная матрица: выделите временный массив или вектор указателей и перейдите по связанному списку, чтобы заполнить его. Сортируйте указатели. Библиотека std::sort или qsort подходит для этого. Затем перемещайте отсортированный массив, чтобы сбросить «следующий» указатель на каждый узел. Наконец, выпустите временное хранилище массивов.
2. Вставка сортировки: вырезать элементы из списка и вставлять их в новый список в правильном отсортированном месте.
3. Mergesort: Это не слишком сложно реализовать, и это выполняется намного быстрее в длинных списках, чем сортировка вставки. Алгоритм прост: разделите список в 2. Скомпилируйте половинки рекурсивно. Затем объедините результаты, неоднократно удаляя самую маленькую голову и добавляя ее в хвост нового списка.
4. Quicksort: Это немного сложно реализовать с помощью списков, но это возможно. Я не буду обсуждать это, потому что это не очень хороший проект раннего программирования, и во многих случаях слияние происходит быстрее.

Вот некоторые непроверенные код для вставки вида:

PhoneBookItem* sorted = NULL; 
while (p.head) { 

    // Pop 
    PhoneBookItem* head = p.head; 
    p.head = head->next; 
    head->next = NULL; 

    // Find the place to insert. 
    PhoneBookItem* lead = sorted; 
    PhoneBookItem* trail = NULL; 
    while (lead && lead->phone <= head->phone) { 
     trail = lead; 
     lead = lead->next; 
    } 

    // Insert either within the list or at the head. 
    head->next = lead; 
    if (trail) 
     trail->next = head; 
    else 
     sorted = head; 
} 
p.head = sorted; 
// Now print the sorted list as before...