Сортировка списка с помощью qsort?

Question

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

Должен ли я использовать связанные списки для представления слов?

struct node{ 
    char c; 
    struct node *next; 
}; 

И как я могу использовать qsort для сортировки слов по длине? Не работает qsort с массивами?

Я довольно новичок в программировании.

Спасибо.

Answer 1

Если вы знаете, как вы хотите отсортировать элементы, вы должны использовать сортировку вставки при чтении данных, чтобы после ввода всего ввода все, что вам нужно сделать, это написать выход. Использование связанного списка будет в порядке, хотя вы обнаружите, что он имеет O (N). Если вы храните вход в двоичном дереве, упорядоченном по длине (лучше было бы сбалансированное дерево), тогда ваш алгоритм будет иметь производительность O (NlogN). Если вы только собираетесь сделать это один раз, то пойдите для простоты реализации по эффективности.

псевдокод:

list = new list 
    read line 
    while not end of file 
     len = length(line) 
     elem = head(list) 
     while (len > length(elem->value)) 
      elem = elem->next 
     end 
     insert line in list before elem 
     read line 
    end 

// at this point the list's elements are sorted from shortest to longest 
// so just write it out in order 
elem = head(list) 
while (elem != null) 
    output elem->value 
    elem = elem->next 
end 

Answer 2

Там много способов справиться с этим ... Вы можете использовать массивы, с помощью динамического распределения памяти, с перераспределить, если вы чувствуете себя достаточно смелым, чтобы попробовать.

Стандартная реализация qsort, однако, требует, чтобы каждый элемент был фиксированной длиной, что означало бы наличие массива-указателей на строки.

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

Я думаю, что вам сказали, что вам не нужно сохранять строки в виде списка; но в связанный список:

struct node { 
    char *string; 
    node *next; 
} 

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

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

Edit:

В псевдокоде:

array = malloc(sizeof(*char)) 
array_size = 1 
array_count = 0 

while (buffer = read != EOF): 
    if(array_count == array_size) 
     realloc(array, array_size * 2) 
    array_count++ 
    sring_temp = malloc(strlen(buffer)) 
    array[array_count] = string_temp 

qsort(array, array_count, sizeof(*char), comparison) 

print array 

Конечно, это требует ТОННУ полировки. Помните, что массив имеет тип char **array, то есть «указатель на указатель на символ» (который вы обрабатываете как массив указателей); поскольку вы пропускаете указатели, вы не можете просто передать буфер в массив.

Answer 3

Да, классическая функция библиотеки «C» qsort() работает только с массивом. Это непрерывный набор значений в памяти.

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

Я думаю, что комментарий, который вы сделали, что вам сказали использовать связанный список, интересно. Действительно, список может быть хорошей структурой данных, которую можно использовать во многих случаях, но у нее есть обратная связь; например, он должен пройти, чтобы найти элементы.

В зависимости от вашего приложения вы можете использовать хеш-таблицу. В C++ вы можете использовать hash_set или hash_map.

Я бы порекомендовал вам провести некоторое время, изучая основные структуры данных. Время, проведенное здесь, будет служить сервером, и вы сможете оценить его, например, «использовать связанный список».

Answer 4

Я думаю, что есть большая проблема, чем алгоритм сортировки, который вы должны выбрать. Первый из них состоит в том, что структура, которую вы определяете, на самом деле не будет содержать список слов, а список отдельных букв (или одно слово). Строки в C представлены как массивы символов с нулевым символом , изложены следующим образом: - (. буквально один байт нулей в памяти)

| A | n | t | h | o | n | y | \0 | 

Этот массив, в идеале, быть объявлены в символьном [8] один слот для каждой буквы, плюс один слот для нулевого байта

Теперь я знаю, что вы, вероятно, знаете это, но это стоит указать на это для ясности. Когда вы работаете с массивами, вы можете просматривать несколько байтов за раз и ускорять работу. Со связанным списком вы можете смотреть только на вещи в истинное линейное время: переход от одного символа к другому. Это важно, когда вы пытаетесь сделать что-то быстро по строкам.

Более подходящий способ хранения этой информации в стиле, который очень похож на C, и используется в C++ как векторы: автоматически изменяемые размеры блоков смежной памяти с использованием malloc и realloc.

Во-первых, мы настроить структура, как это:

struct sstring { 
    char *data; 
    int logLen; 
    int allocLen; 
}; 
typedef struct string sstring; 

И мы приводим некоторые функции для них:

// mallocs a block of memory and holds its length in allocLen 
string_create(string* input); 

// inserts a string and moves up the null character 
// if running out of space, (logLen == allocLen), realloc 2x as much 
string_addchar(string* input, char c); 

string_delete(string* input); 

Теперь, это не потому что вы не можете просто прочитать в простой буфер с помощью scanf, но вы можете использовать функцию getchar(), чтобы получить одиночные символы и поместить их в строку с помощью string_addchar(), чтобы избежать использования связанного списка. Строка позволяет избежать перераспределения как можно больше, только один раз каждые 2^n вставки, и вы все равно можете использовать строковые функции на нем из библиотеки строк C! Это помогает LOT с реализацией ваших ролей.

Итак, как я могу реализовать сортировку с этим? Вы можете создать аналогичный тип, предназначенный для хранения целых строк аналогичным образом, при необходимости увеличивая, чтобы удерживать входные строки с консоли. В любом случае, все ваши данные теперь живут в смежных блоках памяти, к которым можно получить доступ как к массиву, потому что это массив! Например, скажем, у нас есть это:

struct stringarray { 
    string *data; 
    int logLen; 
    int allocLen; 
}; 
typedef struct stringarray cVector; 
cVector myData; 

И аналогичные функции, как и прежде: создавать, удалять, вставлять.

Ключ здесь в том, что вы можете реализовать свои функции сортировки с помощью strcmp() в элементе string.data, так как это просто строка C.Поскольку у нас есть встроенная реализация qsort, которая использует указатель на функции, все, что нам нужно сделать, это обернуть strcmp() для использования с этими типами и передать адрес.

Answer 5

Вы qsort связанный список путем выделения массив указателей, по одному на элемент списка.

Затем вы сортируете этот массив, где в функции сравнения вы, естественно, получаете указатели на элементы списка.

Это дает вам отсортированный список указателей.

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