Форум программистов, компьютерный форум CyberForum.ru

Сортировка массива структур... - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.92
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 14:45     Сортировка массива структур... #1
Здравствуйте! Не могли бы вы выложить примеры или кинуть ссылочку на интересную статью по сортировке массива структур. Имеется массив структур, каждая структура из 5 полей, где 1 - символьное, а остальные - вещественные числа. Необходимо организовать сортировку данного массива структур по каждому из полю. Как сортировать обычные массивы я знаю, а вот массивы структур не получается. Например, сортировка строк с помощью qsort подходит только для двумерных массивов, здесь же не робит(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.02.2010, 14:45     Сортировка массива структур...
Посмотрите здесь:

C++ Сортировка массива структур
Сортировка массива структур C++
Сортировка массива структур C++
Сортировка массива структур C++
Сортировка массива структур C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.02.2010, 14:53     Сортировка массива структур... #2
Здесь можно посмотреть алгоритмы сортировки.
Попробуй сортировать массив таким образом:
  1. Сначала отсортируй массив структур по первому полю
  2. Затем уже отсортированный массив отсортируй по второму полю
  3. И т.д.
  4. Отсортируй массив по последнему полю
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 15:00  [ТС]     Сортировка массива структур... #3
Ну эт я примерно понимаю, ток реализовать никак не могу. Возьмём, например, сортировку пузырьком. То вместо:
Код
void bubbleSort(T a[], long size) {
мне надо писать:
Код
void bubbleSort(T moya_structura[].moe_pole, long size) {
И потом вызывать функцию так:
Код
bubbleSort(moya_structura.moe_pole, razmer_massiva)
Или не так?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.02.2010, 15:07     Сортировка массива структур... #4
WiDe, нет, не так. Тебе нужно будет передавать в не отдельное поле, а сам массив структур. И нужно будет немного переписать функцию, т.к. обычный массив и массив структур - это не одно и то же
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 15:15  [ТС]     Сортировка массива структур... #5
Код
template<class T>
void bubbleSort(T a[], long size) {
  long i, j;
  T x;

  for( i=0; i < size; i++) {
    for( j = size-1; j > i; j-- ) {
      if ( a[j-1].pole_1 > a[j].pole_1 ) {
      x=a[j-1].pole_1;
      a[j-1].pole=a[j].pole_1;
      a[j].pole_1=x;

      x=a[j-1].pole_2;
      a[j-1].pole=a[j].pole_2;
      a[j].pole_2=x;
    }
  }
}
}
А так? Т.е. типа если у нас в структуре 2 поля, и сортируем мы по первому, то, если выполняется условие, меняются местами оба поля структуры. Или опять не там мыслю?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.02.2010, 15:24     Сортировка массива структур... #6
У тебя поля структуры меняться местами не могут, у тебя меняются местами сами структуры в массиве. И у тебя будет уже не шаблон функции:
C++
1
void bubbleSort(MyStruct &s[], size_t size);
Добавлено через 1 минуту
И при каждой сортировке ты производишь ее только по одному полю, ты не можешь сравнивать одно поле с другим, ты сравниваешь одинаковые поля разных экземпляров структур
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 15:27  [ТС]     Сортировка массива структур... #7
Цитата Сообщение от Nameless One Посмотреть сообщение
void bubbleSort(MyStruct &s[], size_t size)
а здесь поподробнее можно? Я так понял тут MyStruct - название самой структуры, а s - объявленный массив типа MyStruct, ну а size это кол-во элементов массива...?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.02.2010, 15:31     Сортировка массива структур... #8
Да, здесь ты передаешь ссылку на массив структур s типа MyStruct, вторым параметром ты передаешь размер size этого массива
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 15:39  [ТС]     Сортировка массива структур... #9
Спасибо, сейчас попробую...

Добавлено через 7 минут
Не пойму на что ругается:
Код
[C++ Error] Unit1.cpp(27): E2023 Array of references is not allowed
По моему из-за size_t, так как он его жирным не выделил, как слово void, например. Я кодю на Borland C++ Builder.

Хотя нет, из-за &. Убрал, компилятор успокоился...
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.02.2010, 15:45     Сортировка массива структур... #10
Цитата Сообщение от WiDe Посмотреть сообщение
[C++ Error] Unit1.cpp(27): E2023 Array of references is not allowed
Запрещены массивы ссылок


Цитата Сообщение от WiDe Посмотреть сообщение
По моему из-за size_t, так как он его жирным не выделил, как слово void, например. Я кодю на Borland C++ Builder.
Нет, size_t - это стандартный тип (беззнаковое целое)
Попробуй так:
C++
1
void bubbleSort(MyStruct &(*s), size_t size);
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 15:53  [ТС]     Сортировка массива структур... #11
Не, тоже не робит... Работает только так:
Код
void bubbleSort(MyStruct s[], size_t size);
Всё, сделал сортировку, получилось!
Спасибо тебе огромное за помощь! Теперь вот как сортировать поля, которые типа char???
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
23.02.2010, 15:57     Сортировка массива структур... #12
А лучше - просто
C++
1
void bubbleSort(MyStruct s[], size_t size);
Так даже будет работать.

хм... опоздал...

В общем, открой для себя "прелести" std::sort и индексов. std::sort (подключать <algorithm>) позволяет сортировать что угодно. Надо только написать операцию сравнения "меньше". А индекс - это массив номеров, который используется для доступа.
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 16:00  [ТС]     Сортировка массива структур... #13
Код
void bubbleSort(line temp[], size_t size) {
  long i, j;
  line x;

  for( i=0; i < size; i++) {            // i - íîìåð ïðîõîäà
    for( j = size-1; j > i; j-- ) {     // âíóòðåííèé öèêë ïðîõîäà
      if ( temp[j-1].kkal > temp[j].kkal ) {
      x=temp[j-1]; temp[j-1]=temp[j]; temp[j]=x;
    }
  }
}
}
Здесь kkal - это одно из полей из структуры. А как сделать чтобы можно было передавать в функцию это имя, чтобы потом отсортировать другие поля, не создавая функции для каждого из них?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.02.2010, 16:03     Сортировка массива структур... #14
WiDe,
Nick Alte, чего-то я намудрил

Цитата Сообщение от WiDe Посмотреть сообщение
Спасибо тебе огромное за помощь! Теперь вот как сортировать поля, которые типа char???
Функция strcmp

Добавлено через 2 минуты
Код
int strcmp(
   const char *string1,
   const char *string2 
);
Return Value
The return value for each of these functions indicates the lexicographic relation of string1 to string2.

Value
 Relationship of string1 to string2
 
< 0
 string1 less than string2
 
0
 string1 identical to string2
 
> 0
 string1 greater than string2
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
23.02.2010, 16:05     Сортировка массива структур... #15
Если у тебя есть массив A размером N, то индекс I - это массив целых чисел того же размера. Изначально ты заносишь туда последовательные значения от 1 до N - это номера. А потом сортируешь уже сам индекс так, чтобы порядок номеров в нём определял порядок сортировки. То есть, значения в A как были неупорядочены, так и идут, но если ты идёшь по индексу последовательно, то выбранные соответствующие значения (A[I[i]]) будут упорядочены. Преимущество в том, что для одного массива структур ты можешь иметь несколько индексов, которые указывают порядок сортировки по разным полям.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.02.2010, 16:07     Сортировка массива структур... #16
Цитата Сообщение от WiDe Посмотреть сообщение
Здесь kkal - это одно из полей из структуры. А как сделать чтобы можно было передавать в функцию это имя, чтобы потом отсортировать другие поля, не создавая функции для каждого из них?
Попробуй объявить структуру так:
C++
1
2
3
4
5
MyStruct 
{
char name[256];
double field[4];//Здесь у тебя будут храниться четыре вещественных поля
};
И передавай в функцию сортировки индекс того поля, по которому ты хочешь сортировать структуру

Добавлено через 1 минуту
Тогда прототип функции будет у тебя выглядеть так:
C++
1
void bubbleSort(MyStruct s[], size_t size, size_t f_index);
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
23.02.2010, 16:20     Сортировка массива структур... #17
Теперь о сортировке std::sort. Для неё надо определить операцию сравнения. Чтобы сортировать индекс, надо показать sort, что сравнивать надо не сами элементы индекса, а соответствующие им элементы основного массива. Хотя перемещаются при этом именно элементы индекса. Для этого надо написать класс с операцией вызова, в которой заложено нужное сравнение, и передать его в sort.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct MyStruct {double x, y;};
MyStruct A[10];  // Будем считать, что массив где-то заполняется
int IndexX[10], IndexY[10];
 
void DoSort()
{
    for(int i=0; i<10; ++i)
        IndexY[i] = IndexX[i] = i;   // Начальные значения для индексов
    // Определим класс для сравнения MyStruct.x
    class CompareX {
    public:
        CompareX(const MyStruct *Array): arr(Array) {}  // Сравниватель должен знать, с каким именно массивом работает
        bool operator () (const int& i1, const int& i2)  const   // А это сама операция сравнения
        {
            return arr[i1].x < arr[i2].x;
        }
    private:
        const MyStruct* const arr;
    } ;
    // Определим класс для сравнения MyStruct.y
    class CompareY {
    public:
        CompareY(MyStruct *Array): arr(Array) {}  // Сравниватель должен знать, с каким именно массивом работает
        bool operator () (const int& i1, const int& i2)  const   // А это сама операция сравнения
        {
            return arr[i1].y < arr[i2].y;
        }
    private:
        const MyStruct* const arr;
    } ;
// А теперь просто отсортируем индексы
    std::sort(IndexX, IndexX+10, CompareX(A));
    std::sort(IndexY, IndexY+10, CompareY(A));
// А теперь напечатаем отсортированные последовательности:
    for(int i=0; i<10; ++i)
        cout << "A[" << IndexX[i] << "].x = " << A[IndexX[i]].x << endl;
    for(int i=0; i<10; ++i)
        cout << "A[" << IndexY[i] << "].y = " << A[IndexY[i]].y << endl;
}
Вот, таким образом у тебя имеется один и тот же массив A, благодаря индексам отсортированный двумя разными способами.
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 16:23  [ТС]     Сортировка массива структур... #18
Цитата Сообщение от Nameless One Посмотреть сообщение
double field[4];
Хорошая идея, спасибо!

Добавлено через 2 минуты
Nick Alte, классы ещё не изучал, к сожалению. Точно не знаю, но либо в этот понедельник, либо в следующий их пройдём и тогда попробую "переварить", написанное вами. Спасибо за информацию!
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 1
23.02.2010, 17:44     Сортировка массива структур... #19
В принципе, можно и функциями, но тогда придётся задействовать глобальные переменные, а это нехорошо. Классами аккуратнее. Но тем не менее для повышения понятности вот как то же самое будет выглядеть:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct MyStruct {double x, y;};
MyStruct A[10];  // Будем считать, что массив где-то заполняется
int IndexX[10], IndexY[10];
 
    // Определим функцию для сравнения MyStruct.x
bool CompareX(const int& i1, const int& i2) 
{
    return A[i1].x < A[i2].x;
}
 
    // Определим функцию для сравнения MyStruct.y
bool CompareY (const int& i1, const int& i2)
{
    return A[i1].y < A[i2].y;
}
 
void DoSort()
{
    for(int i=0; i<10; ++i)
        IndexY[i] = IndexX[i] = i;   // Начальные значения для индексов
// А теперь просто отсортируем индексы
    std::sort(IndexX, IndexX+10, CompareX);
    std::sort(IndexY, IndexY+10, CompareY);
// А теперь напечатаем отсортированные последовательности:
    for(int i=0; i<10; ++i)
        cout << "A[" << IndexX[i] << "].x = " << A[IndexX[i]].x << endl;
    for(int i=0; i<10; ++i)
        cout << "A[" << IndexY[i] << "].y = " << A[IndexY[i]].y << endl;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2010, 19:25     Сортировка массива структур...
Еще ссылки по теме:

C++ сортировка структур массива
Сортировка массива структур C++
Сортировка массива структур через сортировку массива указателей C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 19:25  [ТС]     Сортировка массива структур... #20
Цитата Сообщение от Nameless One Посмотреть сообщение
Функция strcmp
Сделал так:
Код
if ( strcmp(temp[j-1].name, temp[j].name)>0 ) {
      x=temp[j-1]; temp[j-1]=temp[j]; temp[j]=x;
    }
и всё работает на ура=) Спасибо!
Yandex
Объявления
23.02.2010, 19:25     Сортировка массива структур...
Ответ Создать тему
Опции темы

Текущее время: 08:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru