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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.92
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
#1

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

23.02.2010, 14:45. Просмотров 9449. Ответов 19
Метки нет (Все метки)

Здравствуйте! Не могли бы вы выложить примеры или кинуть ссылочку на интересную статью по сортировке массива структур. Имеется массив структур, каждая структура из 5 полей, где 1 - символьное, а остальные - вещественные числа. Необходимо организовать сортировку данного массива структур по каждому из полю. Как сортировать обычные массивы я знаю, а вот массивы структур не получается. Например, сортировка строк с помощью qsort подходит только для двумерных массивов, здесь же не робит(
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5761 / 3410 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
5761 / 3410 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
5761 / 3410 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
5761 / 3410 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
5761 / 3410 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,911
Завершенные тесты: 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
5761 / 3410 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,911
Завершенные тесты: 1
23.02.2010, 16:05     Сортировка массива структур... #15
Если у тебя есть массив A размером N, то индекс I - это массив целых чисел того же размера. Изначально ты заносишь туда последовательные значения от 1 до N - это номера. А потом сортируешь уже сам индекс так, чтобы порядок номеров в нём определял порядок сортировки. То есть, значения в A как были неупорядочены, так и идут, но если ты идёшь по индексу последовательно, то выбранные соответствующие значения (A[I[i]]) будут упорядочены. Преимущество в том, что для одного массива структур ты можешь иметь несколько индексов, которые указывают порядок сортировки по разным полям.
Nameless One
Эксперт С++
 Аватар для Nameless One
5761 / 3410 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,911
Завершенные тесты: 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
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,911
Завершенные тесты: 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++ Сортировка массива структур
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     Сортировка массива структур...
Ответ Создать тему
Опции темы

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