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

Question

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

Answer 1

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

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

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

Answer 2

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

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

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

• ll_sort.h
• ll_sort.c

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

Answer 3

void insertionsort(node *head,node *tail)
{
    node *temp1=head,*temp2=temp1->next;
    node *temp3;
    while(temp1->next!=NULL)
    {
    (temp1==tail)
            break;
    temp2=temp1->next;
    if(temp2->data<temp1->data)
    {
        int j;
        j=temp2->data;
        temp2->data=temp1->data;
        temp1->data=j;
        insertionsort(head,temp2);
    }
    temp1=temp1->next;
}
}

Answer 4

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

Answer 5

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

Существует множество других алгоритмов сортировки , из которых (T & C применяются) являются O (NlogN). Я предлагаю посмотреть на быструю сортировку или сортировку слиянием .

Answer 6

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

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