Мне нужно сделать программу для телефонного справочника. Программа должна читать имена и номера из файла. Я успешно создал связанный список, содержащий эти данные. Теперь я хочу отсортировать их по алфавиту. Как мне это сделать?Вставить сортировку в C используя связанный список
ответ
Это зависит от вашей цели.
Если вы хотите сделать это эффективно, указатели на указатели на каждый элемент в массив, а затем отсортируйте массив по алфавиту с помощью алгоритма, такого как quicksort (qsort
in C); наконец, заново создайте список из отсортированного массива.
С другой стороны, если это домашнее задание, и вы должны использовать сортировку вставки, как предполагает название должности, это другое дело.
Вы хотите отсортировать их после того, как создали связанный список?
Лучшим подходом для сортировки данных, подобных этому, может быть использование дерева и его сортировка при загрузке данных. Дерево данных структуры также быстро для поиска, хотя хэш, вероятно, будет быстрее. Обратите внимание, что 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. */
}
}
Вставка сортировка медленно, но если вы хотите использовать его посмотреть на http://en.wikipedia.org/wiki/Insertion_sort
Есть много других sorting algoritms, постились из которых (T & C применяется) является O (NlogN). Предлагаю посмотреть либо quicksort, либо merge sort.
Связанный список - это наихудшая структура данных, которую можно вообразить для сортировки. Если вы выполните вставку, вам придется выполнять линейный обход по списку. Вы уверены, что задали правильный вопрос?
Сортировка связанных списков требует онлайн-алгоритма (то есть алгоритма, который не зависит от быстрого случайного доступа), такого как сортировка вставки или реализация слияния на основе стека.
Если вы хотите вставить (несколько) элементов в уже отсортированный список, используйте сортировку вставки. Если вы хотите отсортировать полный список (или вставить большое количество элементов), используйте mergesort.
Реализация этих алгоритмов можно найти здесь:
Пожалуйста, дайте мне знать, если вы нашли ошибку в код не действительно был проверен.
quicksort требуется случайный доступ для выбора поворота и не может использоваться (эффективно) со связанными списками – Christoph 2010-12-06 14:11:57
@Christoph Нет, если вы соглашаетесь с тем, что первый элемент является стержнем. – marcog 2010-12-06 14:25:16