Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [СИ]сортировка хоара

Автор: MemphisMayFire 20.5.2011, 15:38

Добрый день! помогите, пожалуйста, написать сортировку хоара(рекурсивный метод) для массива структур, с элементами: Код typedef struct {   char val[256];   int key; } elem; Сортировать нужно по ключу (d[i].val) Я не могу найти, где бы нормально был описан алгоритм(может не догоняю просто). Если вам не сложно, то напишите как вообще реализовывать это. Было бы совсем отлично, если бы кто-нибудь дал код, курсовую надо сдать в выходные  Вот код с добавлением элементов в массив: Код iint main() { int n, i = 0, j = 0; scanf("%d", &n); elem d[n]; for (i = 0; i < n; i++) {   scanf("%d ", &d[i].key);   scanf("%[^\n]", d[i].val); }  }  заранее спасибо! вот рабочий код для данной задачи: Код #include <stdio.h> typedef struct {   char val[256];   int key; } elem; void sortHoar(elem *d, int from, int to) { int i, j; elem x, temp; if (from >= to) {   return; } i = from; j = to; x = d[(from+to)/2]; temp = d[i]; while (i <= j) {   while (d[i].key < x.key) {     i++;   }   while (d[j].key > x.key) {     j--;   }   if (i <= j) {     temp = d[i];      d[i] = d[j];     d[j] = temp;     i++;     j--;   } } sortHoar(d, from, j); sortHoar(d, i, to); } int main() { int n, i = 0, j = 0; scanf("%d", &n); elem d[n]; for (i = 0; i < n; i++) {   scanf("%d ", &d[i].key);   scanf("%[^\n]", d[i].val); }  sortHoar(d, 0, n-1); for (i = 0; i < n; i++) {   printf("%d %s\n", d[i].key, d[i].val); } }

Автор: borisbn 20.5.2011, 15:59

Цитата(MemphisMayFire @  20.5.2011,  15:38 ) Я не могу найти, где бы нормально был описан алгоритм не знаю, как ты искал... http://lmgtfy.com/?q=%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0+%D1%85%D0%BE%D0%B0%D1%80%D0%B0+%D0%A1%D0%B8&l=1 первая ссылка

Автор: MemphisMayFire 20.5.2011, 16:09

а from и to что такое? Добавлено через 4 минуты и 15 секунд а, вроде понял, все. Добавлено через 6 минут и 33 секунды только вот придется, наверное, писать функцию поиска минимального/максимального элемента массива, так как числа определяются пользователем и могут быть, например, 2 4 5 8.

Автор: borisbn 20.5.2011, 16:16

изначально индекс первого и последнего элемента массива. в твоём случае 0 и n-1. Затем они изменяются в соответствии с алгоритмом

Автор: MemphisMayFire 20.5.2011, 16:20

а, это номера. спасибо!

Автор: borisbn 20.5.2011, 16:35

учти, что в том алгоритме сортируется массив целых чисел, а тебе нужно Цитата(MemphisMayFire @  20.5.2011,  15:38 ) Сортировать нужно по ключу (d[i].val) т.е. вместо простого сравнения Код while ( A[i] < x ) i ++; while ( A[j] > x ) j --; нужно делать как-то так Код while ( strcmp(A[i].val, x.val) < 0 ) i ++; while ( strcmp(A[j].val, x.val) > 0 ) j --; не уверен, что именно так - нужно проверять

Автор: MemphisMayFire 20.5.2011, 16:45

вроде нужно вот так Код while (d[i].val < 0 ) i ++;

Автор: borisbn 20.5.2011, 16:47

Цитата(MemphisMayFire @  20.5.2011,  16:45 ) while (d[i].val < 0 ) i ++;    val - массив символов. как он м.б. < 0 ???

Автор: MemphisMayFire 20.5.2011, 16:51

ну ты обращаешься к элементу массива как a[i], а тут у тебя массив структур и тебе нужно обратиться к элементам одного поля(key в моем случае, тк сортировка идет по ключам), то есть d[i].key. Добавлено через 57 секунд случаенно val вместо key написал Добавлено через 9 минут и 1 секунду Код #include <stdio.h> typedef struct {   char val[256];   int key; } elem; void sort(elem *d, int from, int to) { int x, i, j, temp; if (from >= to) {   return; } i = from; j = to; x = d[(from+to)/2].key; while (i <= j) {   while (d[i].key < x) {     i++;   }   while (d[j].key > x)      j --;   }   if (i <= j) {     temp = d[i].key;      d[i].key = d[j].key;     d[j].key = temp;     i++;     j--;   } } sort(d, from, j); sort(d, i, to); } int main() { int n, i = 0, j = 0; scanf("%d", &n); elem d[n]; for (i = 0; i < n; i++) {   scanf("%d ", &d[i].key);   scanf("%[^\n]", d[i].val); }  sort(d, 0, n-1); for (i = 0; i < n; i++) {   printf("%d %s", d[i].key, d[i].val); } } фэйлы какие-то непонятные(

Автор: borisbn 20.5.2011, 17:03

так, как ты сделал - неправильно, т.к. у тебя сортируется не массив целиком, а только поля key, при этом val остаются на своих местах Цитата(MemphisMayFire @  20.5.2011,  16:51 ) фэйлы какие-то непонятные( наверное, что-то где-то не работает

Автор: MemphisMayFire 20.5.2011, 17:05

а, ну да, будет только одно сортироваться. походу придется указатели сделать.

Автор: borisbn 20.5.2011, 17:06

подсказка: x и temp должны быть не типа int, а типа elem

Автор: MemphisMayFire 20.5.2011, 17:12

о, точно, спасибо!

Автор: borisbn 20.5.2011, 17:14

выкладывай. проверю, да и мож кому сгодится

Автор: MemphisMayFire 20.5.2011, 17:17

только фэйлы выдает при передаче val >>incompatible types when assigning to type ‘char[256]’ from type ‘char *’ Код x.val = d[(from+to)/2].val; temp.val = d[i].val; ... что не так?

Автор: borisbn 20.5.2011, 17:25

Цитата(MemphisMayFire @  20.5.2011,  17:17 ) temp.val = d[i].val; так низя. копируй целиком Код x = d[(from+to)/2]; temp = d[i] а если уж хочешь копировать массивы (а val - это массив), то нужно так Код memcpy( temp.val, d[i].val, sizeof( temp.val ) ); но лучше первый вариант

Автор: MemphisMayFire 20.5.2011, 17:25

Код #include <stdio.h> typedef struct {   char val[256];   int key; } elem; void sort(elem *d, int from, int to) { int i, j; elem x, temp; if (from >= to) {   return; } i = from; j = to; x = d[(from+to)/2]; temp = d[i]; while (i <= j) {   while (d[i].key < x.key) {     i++;   }   while (d[j].key > x.key)      j--;   }   if (i <= j) {     temp = d[i];      d[i] = d[j];     d[j] = temp;     i++;     j--;   } } sort(d, from, j); sort(d, i, to); } int main() { int n, i = 0, j = 0; scanf("%d", &n); elem d[n]; for (i = 0; i < n; i++) {   scanf("%d ", &d[i].key);   scanf("%[^\n]", d[i].val); }  sort(d, 0, n-1); for (i = 0; i < n; i++) {   printf("%d %s\n", d[i].key, d[i].val); } } а код вот *поправил присвоение, но фэйлы какие-то остались

Автор: borisbn 20.5.2011, 17:27

а у тебя задание железно на Си сделать или можно на Си++ ?

Автор: MemphisMayFire 20.5.2011, 17:31

не, у меня железно на Си. это часть курсача. Добавлено через 2 минуты и 6 секунд Код sort(d, from, j); sort(d, i, to); проблема тут, не хочет рекурсивно функцию запускать

Автор: MemphisMayFire 20.5.2011, 18:06

рабочий код Код #include <stdio.h> typedef struct {   char val[256];   int key; } elem; void sortHoar(elem *d, int from, int to) { int i, j; elem x, temp; if (from >= to) {   return; } i = from; j = to; x = d[(from+to)/2]; temp = d[i]; while (i <= j) {   while (d[i].key < x.key) {     i++;   }   while (d[j].key > x.key) {     j--;   }   if (i <= j) {     temp = d[i];      d[i] = d[j];     d[j] = temp;     i++;     j--;   } } sortHoar(d, from, j); sortHoar(d, i, to); } int main() { int n, i = 0, j = 0; scanf("%d", &n); elem d[n]; for (i = 0; i < n; i++) {   scanf("%d ", &d[i].key);   scanf("%[^\n]", d[i].val); }  sortHoar(d, 0, n-1); for (i = 0; i < n; i++) {   printf("%d %s\n", d[i].key, d[i].val); } }

Автор: borisbn 20.5.2011, 20:55

Отлично! Я в тебя верил пару моментов: 1. Отдай дань автору - переименуй sort -> sortHoar 2. На нескольких форумах видел такое правило: если ответ получен, то результат вставляют в самое первое сообщение - чтобы те, кто ищет то же самое, что нужно было тебе, не скроллировали до правильного решения 3. Пометь тему как решённую. По какой-то загадочной причине модераторы требуют/просят этого от всех

Автор: MemphisMayFire 20.5.2011, 22:16

хорошо, сейчас все сделаю. большое спасибо за помощь!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)