使用链表在C中插入排序
我必须制作电话目录程序。 程序应该从文件中读取名称和数字。 我已成功创建包含此数据的链接列表。 现在我想按字母顺序对它们进行排序。 我该怎么做？
这取决于你的目标。
如果你想有效地做到这一点，将每个元素的指针粘贴到一个数组中，然后使用像quicksort这样的算法按字母顺序对数组进行排序 （ qsort中的qsort ）; 最后，从排序的数组中重新创建列表。
另一方面，如果这是家庭作业，你必须使用插入排序作为post的标题建议，这是另一回事。
对链表进行排序需要在线算法（即不依赖于快速随机访问的算法），如插入排序或基于堆栈的mergesort实现。
如果要将（少数）项插入已排序的列表中，请使用插入排序。 如果要对完整列表进行排序（或插入大量项目），请使用mergesort。
这些算法的实现可以在这里找到：
- ll_sort.h
- ll_sort.c
如果您发现错误，请告诉我，因为代码尚未经过测试。
插入排序很慢，但是如果你想使用它，请查看http://en.wikipedia.org/wiki/Insertion_sort
还有许多其他排序算法 ，其中禁食（T＆C适用）是O（NlogN）。 我建议查看快速排序或合并排序 。
链表几乎是可以想象的最差数据结构。 如果进行插入，则必须在列表中进行线性遍历。 你确定你问的是正确的问题吗？
你想在创建链表后对它们进行排序吗？
对此类数据进行排序的最佳方法可能是使用树并在加载数据时对其进行排序。 树数据结构也可以快速搜索，尽管哈希可能是最快的。 请注意，strcmp不是排序或搜索的最快方式。 您可以维护搜索词的索引并对其进行编码，以便索引指向第一个不匹配的字符。 然后你只需要比较那个角色。 但是，我没有时间为此提供示例代码。
typedef struct directory_entry_t { char *name; char *number; directory_entry_t *before; directory_entry_t *after; } directory_entry; ... bool found; while(!found) { int result = strcmp("name", node->name); if(0 == result) { fprintf(stderr, "Duplicate entry for %s.\n", name); } else if(0 < result) { if(NULL == node->after) { /* Create a new node, populate it, and store a pointer to it at node->after. */ found = true; } else { node = node->after; } else { /* Like the above case, but for before. */ } }