Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.99/245: Рейтинг темы: голосов - 245, средняя оценка - 4.99
11 / 11 / 2
Регистрация: 23.02.2010
Сообщений: 120
1

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

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

Author24 — интернет-сервис помощи студентам
Здравствуйте! Не могли бы вы выложить примеры или кинуть ссылочку на интересную статью по сортировке массива структур. Имеется массив структур, каждая структура из 5 полей, где 1 - символьное, а остальные - вещественные числа. Необходимо организовать сортировку данного массива структур по каждому из полю. Как сортировать обычные массивы я знаю, а вот массивы структур не получается. Например, сортировка строк с помощью qsort подходит только для двумерных массивов, здесь же не робит(
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.02.2010, 14:45
Ответы с готовыми решениями:

Сортировка массива структур через сортировку массива указателей
Ошибка возникает в функции void sort(student **ppStud, int k, char ch). Кто видит ошибку -...

Сортировка массива структур
Ругается на использование структуры, соответственно не работает вся программа. Задача:...

Сортировка массива структур
не могу понять почему не работает. Программа должна сортануть массив из 10 елементов типа Struct....

Сортировка массива структур
Имеется структура : struct Data_base { string team_name; string city; int ...

19
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
23.02.2010, 14:53 2
Здесь можно посмотреть алгоритмы сортировки.
Попробуй сортировать массив таким образом:
  1. Сначала отсортируй массив структур по первому полю
  2. Затем уже отсортированный массив отсортируй по второму полю
  3. И т.д.
  4. Отсортируй массив по последнему полю
0
11 / 11 / 2
Регистрация: 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)
Или не так?
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
23.02.2010, 15:07 4
WiDe, нет, не так. Тебе нужно будет передавать в не отдельное поле, а сам массив структур. И нужно будет немного переписать функцию, т.к. обычный массив и массив структур - это не одно и то же
0
11 / 11 / 2
Регистрация: 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 поля, и сортируем мы по первому, то, если выполняется условие, меняются местами оба поля структуры. Или опять не там мыслю?
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
23.02.2010, 15:24 6
У тебя поля структуры меняться местами не могут, у тебя меняются местами сами структуры в массиве. И у тебя будет уже не шаблон функции:
C++
1
void bubbleSort(MyStruct &s[], size_t size);
Добавлено через 1 минуту
И при каждой сортировке ты производишь ее только по одному полю, ты не можешь сравнивать одно поле с другим, ты сравниваешь одинаковые поля разных экземпляров структур
1
11 / 11 / 2
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 15:27  [ТС] 7
Цитата Сообщение от Nameless One Посмотреть сообщение
void bubbleSort(MyStruct &s[], size_t size)
а здесь поподробнее можно? Я так понял тут MyStruct - название самой структуры, а s - объявленный массив типа MyStruct, ну а size это кол-во элементов массива...?
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
23.02.2010, 15:31 8
Да, здесь ты передаешь ссылку на массив структур s типа MyStruct, вторым параметром ты передаешь размер size этого массива
1
11 / 11 / 2
Регистрация: 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.

Хотя нет, из-за &. Убрал, компилятор успокоился...
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
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);
0
11 / 11 / 2
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 15:53  [ТС] 11
Не, тоже не робит... Работает только так:
Код
void bubbleSort(MyStruct s[], size_t size);
Всё, сделал сортировку, получилось!
Спасибо тебе огромное за помощь! Теперь вот как сортировать поля, которые типа char???
0
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
23.02.2010, 15:57 12
А лучше - просто
C++
1
void bubbleSort(MyStruct s[], size_t size);
Так даже будет работать.

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

В общем, открой для себя "прелести" std::sort и индексов. std::sort (подключать <algorithm>) позволяет сортировать что угодно. Надо только написать операцию сравнения "меньше". А индекс - это массив номеров, который используется для доступа.
0
11 / 11 / 2
Регистрация: 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 - это одно из полей из структуры. А как сделать чтобы можно было передавать в функцию это имя, чтобы потом отсортировать другие поля, не создавая функции для каждого из них?
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
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
1
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
23.02.2010, 16:05 15
Если у тебя есть массив A размером N, то индекс I - это массив целых чисел того же размера. Изначально ты заносишь туда последовательные значения от 1 до N - это номера. А потом сортируешь уже сам индекс так, чтобы порядок номеров в нём определял порядок сортировки. То есть, значения в A как были неупорядочены, так и идут, но если ты идёшь по индексу последовательно, то выбранные соответствующие значения (A[I[i]]) будут упорядочены. Преимущество в том, что для одного массива структур ты можешь иметь несколько индексов, которые указывают порядок сортировки по разным полям.
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
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);
1
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
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, благодаря индексам отсортированный двумя разными способами.
1
11 / 11 / 2
Регистрация: 23.02.2010
Сообщений: 120
23.02.2010, 16:23  [ТС] 18
Цитата Сообщение от Nameless One Посмотреть сообщение
double field[4];
Хорошая идея, спасибо!

Добавлено через 2 минуты
Nick Alte, классы ещё не изучал, к сожалению. Точно не знаю, но либо в этот понедельник, либо в следующий их пройдём и тогда попробую "переварить", написанное вами. Спасибо за информацию!
0
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
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;
}
0
11 / 11 / 2
Регистрация: 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;
    }
и всё работает на ура=) Спасибо!
0
23.02.2010, 19:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.02.2010, 19:25
Помогаю со студенческими работами здесь

Сортировка массива структур
Дана структура WORKER и массив из 10 стркутур. Нужно 1)сортировать список 2) вывести на экран...

Сортировка массива структур
Не могу понять как отсортировать массив структур по убыванию, попробовал несколько алгоритмов,но не...

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

Сортировка массива структур
Дана структура с именем MARSH, состоящая из полей: • название начального пункта назначения; • ...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru