如何使链接列表按字母顺序打印其内容

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：使用哈希/字典方法而不是链表方法。哈希/字典是
固定阵列和链路列表的组合。他们有好处
搜索项目的速度比固定数组和链表快。
选项 4：使用链接列表以外的其他数据结构，该结构能够按顺序/字母顺序访问您的数据。

Answer 2

可以通过多种方式对链表进行排序。

临时
1. 引用数组：分配一个临时数组或指针向量，并遍历链表以填充它。 对指针进行排序。图书馆std::sort或qsort都可以。 然后遍历排序后的数组以重置每个节点的"下一个"指针。 最后释放临时阵列存储。
插入排序
2. ：将元素从列表中弹出，然后在正确的排序位置重新插入新列表。
3. 合并排序：实现起来并不难，这在长列表上的运行速度比插入排序快得多。 算法很简单：将列表一分为二。 递归地合并两半。 然后通过重复删除最小的头部并附加到新列表的尾部来合并结果。
4. 快速排序：使用列表有效实现这有点棘手，但这是可能的。 我不会讨论它，因为它不是一个很好的早期编程项目，而且在许多情况下，mergesort更快。

下面是一些未经测试的插入排序代码：

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...