Сортировка списка с помощью qsort? - PullRequest
Новая
       18

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

1 голос
/ 26 апреля 2009

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

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

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

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

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

Спасибо.

Ответы [ 5 ]

3 голосов
/ 26 апреля 2009

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

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

Этот массив в идеале должен быть объявлен как char [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 !! Это помогает МНОГО в реализации ваших родов.

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

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

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

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

1 голос
/ 26 апреля 2009

Если вы знаете, как вы хотите отсортировать элементы, вы должны использовать сортировку вставок при чтении данных, чтобы после ввода всех входных данных все, что вам нужно было сделать, - записать выходные данные. Использование связанного списка было бы хорошо, хотя вы обнаружите, что он имеет производительность O (N 2 ). Если вы сохраняете входные данные в двоичном дереве, упорядоченном по длине (лучше всего использовать сбалансированное дерево), тогда ваш алгоритм будет иметь производительность 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
0 голосов
/ 26 апреля 2009

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

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

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

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

0 голосов
/ 26 апреля 2009

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

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

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

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

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

0 голосов
/ 26 апреля 2009

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

Однако для стандартной реализации 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, то есть «указатель на указатель на символ» (который вы обрабатываете как массив указателей); поскольку вы передаете указатели, вы не можете просто передать буфер в массив.

...