如何让链接列表按字母顺序打印出内容？

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

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;

来源

2013-10-01 Dean Mikkawa

你的意思是打印出来的字母顺序还是什么？因为如果你想这样做，你需要重新整理你的整个列表（或选择不同的数据结构）。 –

+1 Dgrin91说的。使用地图并保留价值作为关键。该地图保持它的内容按键排序。 – NotAgain

@ dgrin91，好吧，所以我想我必须制作一个临时的电话簿只是为了把值，然后打印出来。 notgain，对不起，但我不知道如何使用地图，这是超出我的课目前。 –

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

来源

2013-10-01 01:49:42 acegs

这个任务我只限于option1它似乎。我会怎么写呢？ –

@DeanMikkawa，对链表进行排序的最佳方式是使用[合并排序]（http://en.wikipedia.org/wiki/Merge_sort）。 [冒泡排序]（http://en.wikipedia.org/wiki/Bubble_sort）很容易适应链表，但它具有较差的性能特征。 –

排序链表可以用几种方法完成。

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

来源

2013-10-01 02:15:14 Gene

也可以迭代地进行合并排序，这是我的偏好。 –

@MarkRansom玩得开心。它要复杂得多，不可能更快。您可能最终会在递归表达式中重复编译器对堆栈的操作。 – Gene

这是一种插入排序，不是吗？在那里：http://en.wikipedia.org/wiki/Insertion_sort是大数据列表的一些其他想法。 – harper

如何让链接列表按字母顺序打印出内容？

回答

相关问题