0

我有一个包含姓氏、名字和值的单个链接电话簿列表。我可以按它们创建的顺序打印它们，但不能按值打印。我该如何修改这个？如果您需要在代码中查看其他任何内容，请告诉我，但此功能是我主要关心的问题。

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;
4

2 回答 2

1

选项 1：对列表进行排序，然后打印
选项 2：对于每个循环，搜索下一个应该打印的项目。（昂贵）
选项 3：使用哈希/字典方法而不是链表。哈希/字典是
固定数组和链表的组合。它们有利于
比固定数组和链表更快地搜索项目。
选项 4：使用除链接列表之外的其他数据结构，它能够按顺序/按字母顺序访问您的数据。

于 2013-10-01T01:49:42.873 回答
1

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

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

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

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...
于 2013-10-01T02:15:14.903 回答