Вставить сортировку в C используя связанный список

Question

Мне нужно сделать программу для телефонного справочника. Программа должна читать имена и номера из файла. Я успешно создал связанный список, содержащий эти данные. Теперь я хочу отсортировать их по алфавиту. Как мне это сделать?

Answer 1

Это зависит от вашей цели.

Если вы хотите сделать это эффективно, указатели на указатели на каждый элемент в массив, а затем отсортируйте массив по алфавиту с помощью алгоритма, такого как quicksort (qsort in C); наконец, заново создайте список из отсортированного массива.

С другой стороны, если это домашнее задание, и вы должны использовать сортировку вставки, как предполагает название должности, это другое дело.

Answer 2

Вы хотите отсортировать их после того, как создали связанный список?

Лучшим подходом для сортировки данных, подобных этому, может быть использование дерева и его сортировка при загрузке данных. Дерево данных структуры также быстро для поиска, хотя хэш, вероятно, будет быстрее. Обратите внимание, что 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. */ 
    } 
} 

Answer 3

Вставка сортировка медленно, но если вы хотите использовать его посмотреть на http://en.wikipedia.org/wiki/Insertion_sort

Есть много других sorting algoritms, постились из которых (T & C применяется) является O (NlogN). Предлагаю посмотреть либо quicksort, либо merge sort.

Answer 4

Связанный список - это наихудшая структура данных, которую можно вообразить для сортировки. Если вы выполните вставку, вам придется выполнять линейный обход по списку. Вы уверены, что задали правильный вопрос?

Answer 5

Сортировка связанных списков требует онлайн-алгоритма (то есть алгоритма, который не зависит от быстрого случайного доступа), такого как сортировка вставки или реализация слияния на основе стека.

Если вы хотите вставить (несколько) элементов в уже отсортированный список, используйте сортировку вставки. Если вы хотите отсортировать полный список (или вставить большое количество элементов), используйте mergesort.

Реализация этих алгоритмов можно найти здесь:

• ll_sort.h
• ll_sort.c

Пожалуйста, дайте мне знать, если вы нашли ошибку в код не действительно был проверен.