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

Шаблон функции сортировки массива структур по разным типам полей - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
don_keyhot
 Аватар для don_keyhot
4 / 4 / 2
Регистрация: 02.04.2014
Сообщений: 60
04.04.2014, 13:35     Шаблон функции сортировки массива структур по разным типам полей #1
Делаю лабу.
Вот текст задания.
Считайте все записи из файла "1.dat".
Для чтения каждой отдельной записи осуществите динамический захват памяти.
Предполагается, что к-во записей в файле заранее неизвестно.

Выполните сортировку записей по различным ключам:
· по фамилии (по возрастанию);
· по дате рождения (по возрастанию);
· по окладу (по убыванию).

Для каждого ключа используйте различные алгоритмы сортировки:
· сортировка выбором,
· сортировка вставками,
· сортировка Шелла,
· быстрая сортировка.

Всего сортировка будет выполнена 12 раз, каждый раз сортируется массив в первоначальном состоянии.
Для каждого случая подсчитайте к-во сравнений и перестановок.
Оцените скорость, естественность и устойчивость каждого алгоритма.
Оптимальную организацию функций продумайте самостоятельно.

Неделю уже ломаю голову не могу придумать "Оптимальную организацию" шаблонов функций сортировки (

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
struct note
{
    char fam[20];   // фамилия
    char name[20];  // имя
    char phone[10]; // телефон
    int  data_r[3]; // дата рождения, массив из трех чисел: год, месяц, день
    int  oklad;     // оклад
};
 
// шаблон сравнения элементов структуры
template <class item> 
void compare_swap (item &a, item &b)
{
    if (b < a) 
        swap(a, b);
}
 
// шаблон обмена элементов структуры
template <class item>
void swap(item&a, item&b)
{
    item temp;
    temp = a;
    a = b;
    b = temp;
}
 
// шаблон сортировки массива структур методом выбора
// вот тут моя наглая попытка передачи сортируемого поля структуры в параметр [B]key[/B], увы НЕ катит (
// а так хотелось передавать сюда по очереди нужные поля: fam, oklad, data_r[3] !
//
template <class T, class item> 
void selection_sort(T a[], [B]item key[/B], int left, int right)
{ 
    for (int i = left+1; i <= right; i++)
        for (int j = i; j > left; j--) 
            compare_swap(a[j-1][B][COLOR="Red"]->key[/COLOR][/B], a[j][B][COLOR="Red"]->.key[/COLOR][/B]);
}
Неужели придется писать отдельную функцию сортировки для каждого поля?
Но это же ужас, на каждое сортируемое поле (3 поля) писать 4 вида функций сортировки, итого 3 * 4 = 12 !!!
Есть ли из моего тупика другой выход?

P.S. Классы, string, перегрузку операторов, алгоритмы из STL и прочие новомодные навороты НЕ предлагать - этого мы еше НЕ проходили.

Добавлено через 2 часа 0 минут
наверное выход есть?
штудирую счас указатели на функции и что-то смутное у меня вырисовывается
типа как работает стандартная функцией qsort()
у нее есть параметр на функцию сравнения, возможно это выход для меня, написать три перегруженные функции сравнения:

C++
1
2
3
int compare_name(note a[], char* name);
int compare_oklad(note a[], int oklad);
int compare_date(note a[], int data_r[3]);
и тогда в функцию сортировки подставлять указатель на конкретную функцию
типа так:
C++
1
compare_swap(a[j-1], a[j], compare_name);
Это будет правильный подход?

Подумал еще и, блин, опять засада:
а что подставить на место параметров функции *(pf_compare)(note a[], ?..) в шаблоне?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// шаблон сравнения элементов структуры
template <class item> 
void compare_swap (item &a, item &b, int *(pf_compare)(note a[], ?..))
{
    if (pf_compare(a, b) < 0) 
        swap(a, b);
}
 
// шаблон обмена элементов структуры
template <class item>
void swap(item&a, item&b)
{
    item temp;
    temp = a;
    a = b;
    b = temp;
}
голова кругом от этих засад!
как жить с такими проблемами!!!
думаю дальше, думаю...............

Добавлено через 4 минуты
у меня пока с указателями БЕДА! каша полная в голове )
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2014, 13:35     Шаблон функции сортировки массива структур по разным типам полей
Посмотрите здесь:

Шаблон функции с разным возвращаемым типом C++
C++ Как оформить операцию создания (формирования) массива структур из 5 полей (фамилия, имя, улица, дом, квартира) в виде функции?
C++ Написать шаблон функции для сортировки массивов действительных и целых чисел
Реализовать шаблон сортировки массива методом слияния C++
C++ Структура "экзамен". Сортировка массива структур по одному из полей
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
04.04.2014, 13:42     Шаблон функции сортировки массива структур по разным типам полей #2
Цитата Сообщение от don_keyhot Посмотреть сообщение
Выполните сортировку записей по различным ключам:
· по фамилии (по возрастанию);
· по дате рождения (по возрастанию);
· по окладу (по убыванию).
Для каждого ключа используйте различные алгоритмы сортировки:
· сортировка выбором,
· сортировка вставками,
· сортировка Шелла,
· быстрая сортировка.
Цитата Сообщение от don_keyhot Посмотреть сообщение
у меня пока с указателями БЕДА! каша полная в голове )
Посмотрите здесь:
определенный интеграл на указанном пользователем промежутке
Там самый последний код. Вкратце - имеются 4 формулы (в Вашем случае - 3 ключа) и 3 метода (в Вашем случае - 4 метода сортировки), юзер выбирает формулу и метод, программа использует указатели и выдает результат. Удачи.
DrOffset
6426 / 3800 / 880
Регистрация: 30.01.2014
Сообщений: 6,594
04.04.2014, 14:27     Шаблон функции сортировки массива структур по разным типам полей #3
Цитата Сообщение от don_keyhot Посмотреть сообщение
прочие новомодные навороты
Я думаю этим "новомодным наворотам" уже наверное больше лет, чем тебе

Цитата Сообщение от don_keyhot Посмотреть сообщение
а что подставить на место параметров функции *(pf_compare)(note a[], ?..) в шаблоне?
Так параметры свои и подставляй
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int compare_name(note & a, note & b);  //реализация сравнения по имени
int compare_oklad(note & a, note & b); //реализация сравнения по окладу
int compare_date(note & a, note & b);  //реализация сравнения по дате
 
 
// шаблон сравнения элементов структуры
template <class item>
void compare_swap(item &a, item &b, int (*pf_compare)(item & a, item & b))
{
    if (pf_compare(a, b) < 0)
        swap(a, b);
}
 
//.....
 
compare_swap(a, b, &compare_name);
don_keyhot
 Аватар для don_keyhot
4 / 4 / 2
Регистрация: 02.04.2014
Сообщений: 60
04.04.2014, 17:20  [ТС]     Шаблон функции сортировки массива структур по разным типам полей #4
DrOffset,
пошел по твоему пути
Цитата Сообщение от DrOffset Посмотреть сообщение
2
int compare_name(note & a, note & b); //реализация сравнения по имени
но по-моему здесь параметр должен быть не структура note целиком, а поле структуры типа char *name, int oklad?
крутил я в параметрах и note и конкретные поля и нифига не идет (
блин, котелок уже не варит!
запутался я
увы, знаний пока маловато

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

Кликните здесь для просмотра всего текста

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include <iostream>
#include <locale>
#include <fstream>
#include <string.h> // для strcmp()
#include <iomanip>  // для setw
 
using namespace std;
 
// Объявляем структуру note из Лабораторной работы №2
struct note
{
    char fam[20];   // фамилия
    char name[20];  // имя
    char phone[10]; // телефон
    int  data_r[3]; // дата рождения, массив из трех чисел: год, месяц, день
    int  oklad;     // оклад
};
 
// Прототип шаблона функции вывода
template <class T> // или typename Т 
void print(T arr[], int size, char* message);
 
// Прототип шаблона функции вывода
template <class T>
void print_record(T &record);
 
 
// 
int compare_name(char *a, char *b);  //реализация сравнения по имени
int compare_oklad(int a, int b); //реализация сравнения по окладу
int compare_date(int date_a[], int date_b[]);  //реализация сравнения по дате
 
// Прототип шаблона функции обмена двух элементов
template <class item>
void swap(item &a, item &b);
 
// шаблон сравнения элементов структуры
template <class item>
void compare_swap(item &a, item &b, int(*pf_compare)(item &a, item &b));
 
// сортировка выбором
template <class T, class item>
void selection_sort(T a[], int left, int right, int (*pfun_compare)(item &a, item &b));
 
 
 
//------------------------------------------------------------------------------
 
int main(int argc, char *argv[]) 
{
    // русификация
    setlocale(LC_CTYPE, "Russian");
    // ----------------------------
 
 
    note *a_student;                     // указатель на массив студентов
    int  kol_student;                    // количество студентов в файле
    char filename[] = "1.dat";           // имя файла данных
 
    fstream file_in;                                  // объявляем входной файл
    file_in.open(filename, ios::in | ios::binary);    // открываем файл для чтения из него
    if (!file_in.is_open())                           // если файл не удалось открыть
    {
        cout << "Не могу открыть файл " << filename;  // сообщаем об ошибке
        return 1;                                     // и завершаем программу с ошибкой
    }
 
    // вычислим количество студентов в файле
    file_in.seekg(0, ios::end);           // передвинем указатель в конец файла
    int end_pos = file_in.tellg();        // получаем размер файла в байтах = позиции указателя в конце
    kol_student = end_pos / sizeof(note); // количество записей = размер файла / размер записи
    file_in.seekg(0, ios::beg);           // передвинем опять указатель в начало файла
 
    a_student = new note[kol_student];    // выделяем память для num_records студентов
 
    // можно читать данные из файла по одному студенту за раз
    // цикл пока не конец файла
    // функция file_in.eof() возвращает истину если достигнут конец
    //for (int i = 0; i < num_records && !file_in.eof(); i++)
    //  file_in.read((char *)a_student, sizeof(note));
 
    // но лучше прочитать все сразу!
    file_in.read((char*)a_student, sizeof(note) * kol_student);
 
    file_in.close();  // закрываем файл
 
    // создаем динамический вспомогательный массив по количеству студентов
    note *pa_student = new note[kol_student];
 
    char* message; // для передачи сообщений в функции вывода
    // выводим полученный список студентов
    message = "Исходный Список студентов";
    print(a_student, kol_student, message);
 
    // заполняем вспомогательный массив указателями на студентов
    for (int i = 0; i < kol_student; i++)
        pa_student[i] = a_student[i];
    
    
    system("pause"); // пауза перед очисткой экрана
    system("cls");   // очистка экрана
 
 
    message = "Список студентов 2";
    print(pa_student, kol_student, message);
 
    selection_sort(pa_student, 0, kol_student, compare_name);
 
 
    // освобождаем выделенную память перед выходом
    //for (int i = 0; i < num_records; i++)
    //  delete [] a_student[i];
    delete [] a_student;
    delete [] pa_student;
 
 
    // ----------------------------
    // пауза перед выходом
    cout << endl << endl;
    system("pause");
 
    return 0;
 
} // конец main
 
 
// -------------------------------------------------------------------
// Шаблон функции вывода списка студентов
//
template <class T>
void print(T arr[], int arr_size, char* message)
{
    cout << setw(40) << message << endl;
    cout << "---------------------------------------------------------------------\n";
    cout << "Фамилия           Имя         Телефон  Дата рожд.  Оклад   Ссылка  \n";
    cout << "---------------------------------------------------------------------\n";
 
    for (int i = 0; i < arr_size; i++) // цикл по количеству студентов
        print_record(arr[i], i);       // вывод одного студента
 
    cout << endl;
}
 
// -------------------------------------------------------------------
// Шаблон функции вывода одного студента
//
template <class T>
void print_record(T &student, int i)
{
    cout << setw(2) << i+1 << ") "
        << setfill(' ') << left 
        << setw(13) 
        << student.fam       << " " 
        << setw(10) 
        << student.name      << " " 
        << right 
        << setw( 8) << student.phone     << "  " 
        << setfill('0') << setw( 2) << student.data_r[2] << "/" 
        << setfill('0') << setw( 2) << student.data_r[1] << "/" 
        << student.data_r[0] << " " 
        << setfill(' ') 
        << setw( 4) << student.oklad     << " руб "
        << &student // адрес
    << endl;
}
 
 
// сортировка массива структур методом выбора
//
template <class T, class item>
void selection_sort(T a[], int left, int right, int(*pf_compare)(item &a, item &b))
{
    for (int i = left + 1; i <= right; i++)
        for (int j = i; j > left; j--)
            compare_swap( a[j - 1], a[j], pf_compare(a[j - 1], a[j]) );
}
 
// сравнение элементов структуры
template <class item>
void compare_swap( item &a, item &b, int(*pf_compare)(item &a, item &b) )
{
    if (pf_compare(a, b) < 0)
        swap(a, b);
}
 
 
//------------------------------------------------------------------------------
// обмен двух элементов
template <class T>
void swap(T &a, T &b)
{
    T temp;
    temp = a;
    a = b;
    b = temp;
}
 
 
// сравнение по имени
int compare_name(char *a, char *b)
{
    int i = -1;
    
    return i;
}
 
// сравнение по окладу
int compare_oklad(int a, int b)
{
    int i = 0;
    if (a < b)
        i = -1;
    else if (a > b)
        i = 1;
 
    return i;
}
 
// сравнение по дате
int compare_date(int date_a[], int date_b[])
{
    int i = -1;
    
    return i;
}


Добавлено через 11 минут
в 107 строке компилятор (VS 2013) ругается так
e:\anton\vs\vc++\семестр 2\5\1\1.cpp(135): error C2784: void selection_sort(T [],int,int,int (__cdecl *)(item &,item &)): не удалось вывести аргумент шаблон для "перегруженный тип функции" из "перегруженный тип функции"

Добавлено через 45 секунд
перемудрил я что-то (
DrOffset
6426 / 3800 / 880
Регистрация: 30.01.2014
Сообщений: 6,594
04.04.2014, 17:28     Шаблон функции сортировки массива структур по разным типам полей #5
Цитата Сообщение от don_keyhot Посмотреть сообщение
но по-моему здесь параметр должен быть не структура note целиком
Именно структура Note целиком. Иначе логика рассыпается. А внутри функции уже выбираешь нужное поле и его сравниваешь. Зачем ты сам себя закапываешь?
don_keyhot
 Аватар для don_keyhot
4 / 4 / 2
Регистрация: 02.04.2014
Сообщений: 60
04.04.2014, 17:35  [ТС]     Шаблон функции сортировки массива структур по разным типам полей #6
вот всплывающая подсказка компилятора на ошибку
Миниатюры
Шаблон функции сортировки массива структур по разным типам полей  
don_keyhot
 Аватар для don_keyhot
4 / 4 / 2
Регистрация: 02.04.2014
Сообщений: 60
04.04.2014, 17:36  [ТС]     Шаблон функции сортировки массива структур по разным типам полей #7
я уже сегодня не соображаю )
DrOffset
6426 / 3800 / 880
Регистрация: 30.01.2014
Сообщений: 6,594
04.04.2014, 17:38     Шаблон функции сортировки массива структур по разным типам полей #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот поправил, но не компилировал и не проверял. Если что - спрашивай.
Кликните здесь для просмотра всего текста
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include <iostream>
#include <locale>
#include <fstream>
#include <string.h> // для strcmp()
#include <iomanip>  // для setw
 
//using namespace std;
 
// Объявляем структуру note из Лабораторной работы №2
struct note
{
    char fam[20];   // фамилия
    char name[20];  // имя
    char phone[10]; // телефон
    int  data_r[3]; // дата рождения, массив из трех чисел: год, месяц, день
    int  oklad;     // оклад
};
 
// Прототип шаблона функции вывода
template <class T> // или typename Т
void print(T arr[], int size, char const * message);
 
// Прототип шаблона функции вывода
template <class T>
void print_record(T &record);
 
 
//
int compare_name(note & a, note & b);  //реализация сравнения по имени
int compare_oklad(note & a, note & b); //реализация сравнения по окладу
int compare_date(note & a, note & b);  //реализация сравнения по дате
 
// Прототип шаблона функции обмена двух элементов
template <class item>
void swap(item &a, item &b);
 
// шаблон сравнения элементов структуры
template <class item>
void compare_swap(item &a, item &b, int(*pf_compare)(item &a, item &b));
 
// сортировка выбором
template <class T>
void selection_sort(T * a, int left, int right, int (*pfun_compare)(T &a, T &b));
 
 
 
//------------------------------------------------------------------------------
 
int main(int argc, char *argv[])
{
    // русификация
    setlocale(LC_CTYPE, "Russian");
    // ----------------------------
 
 
    note *a_student;                     // указатель на массив студентов
    int  kol_student;                    // количество студентов в файле
    char filename[] = "1.dat";           // имя файла данных
 
    std::fstream file_in;                                  // объявляем входной файл
    file_in.open(filename, std::ios::in | std::ios::binary);    // открываем файл для чтения из него
    if (!file_in.is_open())                           // если файл не удалось открыть
    {
        std::cout << "Не могу открыть файл " << filename;  // сообщаем об ошибке
        return 1;                                     // и завершаем программу с ошибкой
    }
 
    // вычислим количество студентов в файле
    file_in.seekg(0, std::ios::end);           // передвинем указатель в конец файла
    int end_pos = file_in.tellg();        // получаем размер файла в байтах = позиции указателя в конце
    kol_student = end_pos / sizeof(note); // количество записей = размер файла / размер записи
    file_in.seekg(0, std::ios::beg);           // передвинем опять указатель в начало файла
 
    a_student = new note[kol_student];    // выделяем память для num_records студентов
 
    // можно читать данные из файла по одному студенту за раз
    // цикл пока не конец файла
    // функция file_in.eof() возвращает истину если достигнут конец
    //for (int i = 0; i < num_records && !file_in.eof(); i++)
    //  file_in.read((char *)a_student, sizeof(note));
 
    // но лучше прочитать все сразу!
    file_in.read((char*)a_student, sizeof(note) * kol_student);
 
    file_in.close();  // закрываем файл
 
    // создаем динамический вспомогательный массив по количеству студентов
    note * pa_student = new note[kol_student];
 
    char const * message; // для передачи сообщений в функции вывода
    // выводим полученный список студентов
    message = "Исходный Список студентов";
    print(a_student, kol_student, message);
 
    // заполняем вспомогательный массив указателями на студентов
    for (int i = 0; i < kol_student; i++)
        pa_student[i] = a_student[i];
 
 
    system("pause"); // пауза перед очисткой экрана
    system("cls");   // очистка экрана
 
 
    message = "Список студентов 2";
    print(pa_student, kol_student, message);
 
    selection_sort(pa_student, 0, kol_student, compare_name);
 
 
    // освобождаем выделенную память перед выходом
    //for (int i = 0; i < num_records; i++)
    //  delete [] a_student[i];
    delete [] a_student;
    delete [] pa_student;
 
 
    // ----------------------------
    // пауза перед выходом
    std::cout << std::endl << std::endl;
    system("pause");
 
    return 0;
 
} // конец main
 
 
// -------------------------------------------------------------------
// Шаблон функции вывода списка студентов
//
template <class T>
void print(T arr[], int arr_size, char const * message)
{
    std::cout << std::setw(40) << message << std::endl;
    std::cout << "---------------------------------------------------------------------\n";
    std::cout << "Фамилия           Имя         Телефон  Дата рожд.  Оклад   Ссылка  \n";
    std::cout << "---------------------------------------------------------------------\n";
 
    for (int i = 0; i < arr_size; i++) // цикл по количеству студентов
        print_record(arr[i], i);       // вывод одного студента
 
    std::cout << std::endl;
}
 
// -------------------------------------------------------------------
// Шаблон функции вывода одного студента
//
template <class T>
void print_record(T &student, int i)
{
    std::cout << std::setw(2) << i+1 << ") "
        << std::setfill(' ') << std::left
        << std::setw(13)
        << student.fam       << " "
        << std::setw(10)
        << student.name      << " "
        << std::right
        << std::setw( 8) << student.phone     << "  "
        << std::setfill('0') << std::setw( 2) << student.data_r[2] << "/"
        << std::setfill('0') << std::setw( 2) << student.data_r[1] << "/"
        << student.data_r[0] << " "
        << std::setfill(' ')
        << std::setw( 4) << student.oklad     << " руб "
        << &student // адрес
    << std::endl;
}
 
 
// сортировка массива структур методом выбора
//
template <class T>
void selection_sort(T * a, int left, int right, int(*pf_compare)(T &a, T &b))
{
    for (int i = left + 1; i <= right; i++)
        for (int j = i; j > left; j--)
            compare_swap( a[j - 1], a[j], pf_compare);
}
 
// сравнение элементов структуры
template <class item>
void compare_swap( item &a, item &b, int(*pf_compare)(item &a, item &b) )
{
    if (pf_compare(a, b) < 0)
        swap(a, b);
}
 
 
//------------------------------------------------------------------------------
// обмен двух элементов
template <class T>
void swap(T &a, T &b)
{
    T temp;
    temp = a;
    a = b;
    b = temp;
}
 
 
// сравнение по имени
int compare_name(note & a, note & b)
{
    int i = -1;
 
    return i;
}
 
// сравнение по окладу
int compare_oklad(note & a, note & b)
{
    int i = 0;
    if (a.oklad < b.oklad)
        i = -1;
    else if (a.oklad > b.oklad)
        i = 1;
 
    return i;
}
 
// сравнение по дате
int compare_date(note & a, note & b)
{
    int i = -1;
 
    return i;
}


Добавлено через 1 минуту
Цитата Сообщение от don_keyhot Посмотреть сообщение
вот всплывающая подсказка компилятора на ошибку
У тебя там ошибок была тьма.
don_keyhot
 Аватар для don_keyhot
4 / 4 / 2
Регистрация: 02.04.2014
Сообщений: 60
04.04.2014, 17:58  [ТС]     Шаблон функции сортировки массива структур по разным типам полей #9
большое спасибо, счас проверю, хех, энергия появляется, усталость уходит )

Добавлено через 18 минут
DrOffset,
Цитата Сообщение от DrOffset Посмотреть сообщение
Вот поправил, но не компилировал и не проверял
код компилируется, ура!
да уж, сколько у меня там было ошибок! спасибо!

ну правда после сортировки, уже на выходе выскакивает ошибка, но мы с этим уже сами справимся, надеюсь )
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.04.2014, 15:47     Шаблон функции сортировки массива структур по разным типам полей
Еще ссылки по теме:

C++ Написать функцию sort() для сортировки массива структур
Написать структуру Book и функции сортировки массива таких структур C++
C++ Функции сортировки структур

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

Или воспользуйтесь поиском по форуму:
don_keyhot
 Аватар для don_keyhot
4 / 4 / 2
Регистрация: 02.04.2014
Сообщений: 60
15.04.2014, 15:47  [ТС]     Шаблон функции сортировки массива структур по разным типам полей #10
вот черновик пока для одного типа сортировки:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
// -----------------------------------------------------------------------------
// Лабораторная работа №5
// Задание 1
//
//Считайте все записи из файла "1.dat" (Лаб.раб.2. Задание 3). 
//Для чтения каждой отдельной записи осуществите динамический захват памяти. 
//Предполагается, что к-во записей в файле заранее неизвестно.
//
//Выполните сортировку записей по различным ключам:
// по фамилии (по возрастанию); 
// по дате рождения (по возрастанию); 
// по окладу (по убыванию). 
//
//Для каждого ключа используйте различные алгоритмы сортировки: 
// сортировка выбором,  
// сортировка вставками,  
// сортировка Шелла,  
// быстрая сортировка.  
//
//Всего сортировка будет выполнена 12 раз, каждый раз сортируется массив в первоначальном состоянии.
//Для каждого случая подсчитайте к-во сравнений и перестановок.
//Оцените скорость, естественность и устойчивость каждого алгоритма.
//Оптимальную организацию функций продумайте самостоятельно.
//
// Вариант 1.
// студента группы 107213 Абрамчука Антона Алексеевича
// -----------------------------------------------------------------------------
 
#include <iostream>
#include <locale>
#include <fstream>
#include <string.h> // для strcmp()
#include <iomanip>  // для setw
 
//using namespace std;
 
// Объявляем структуру note из Лабораторной работы №2
struct note
{
    char first_name[20]; // фамилия
    char name[20];       // имя
    char phone[10];      // телефон
    int  birth_date[3];  // дата рождения, массив из трех чисел: год, месяц, день
    int  oklad;          // оклад
};
 
// Прототип шаблона функции вывода всего массива структур
template <class T> // или typename Т
void print(T arr[], int size, char const * message);
 
// Прототип шаблона функции вывода одной структуры из массива структур 
template <class T>
void print_record(T &record);
 
 
// Прототипы функций сравнения по конкретным полям структуры
int compare_name(note & a, note & b);  // реализация сравнения по имени
int compare_oklad(note & a, note & b); // реализация сравнения по окладу
int compare_date(note & a, note & b);  // реализация сравнения по дате
 
// Прототип шаблона функции обмена двух элементов
template <class item>
void swap(item &a, item &b);
 
// Прототип шаблона сравнения и обмена элементов структуры
template <class item>
void compare_swap(item &a, item &b, int(*pf_compare)(item &a, item &b));
 
// Прототип шаблона функции сортировки выбором
template <class T>
void selection_sort(T *a[], int left, int right, int(*pfun_compare)(T &a, T &b));
 
// Инициализация массива указателей, сброс в первоначальное состояние
// для последующей его сортировки другими видом: выбор, вставка, Шелла, быстрая
void init_array(note **pa_student, note *a_student, int kol_student);
 
 
//------------------------------------------------------------------------------
 
int main(int argc, char *argv[])
{
    // русификация
    setlocale(LC_CTYPE, "Russian");
    // ----------------------------
 
 
    note *a_student;                     // указатель на массив студентов
    int  kol_student;                    // количество студентов в файле
    char filename[] = "1.dat";           // имя файла данных
 
    std::fstream file_in;                                  // объявляем входной файл
    file_in.open(filename, std::ios::in | std::ios::binary);    // открываем файл для чтения из него
    //if (!file_in.is_open())                           // если файл не удалось открыть
    if (!file_in)                           // если файл не удалось открыть
    {
        std::cout << "Не могу открыть файл " << filename;  // сообщаем об ошибке
        return 1;                                     // и завершаем программу с ошибкой
    }
 
    // вычислим количество студентов в файле
    file_in.seekg(0, std::ios::end);           // передвинем указатель в конец файла
    int end_pos = file_in.tellg();        // получаем размер файла в байтах = позиции указателя в конце
    kol_student = end_pos / sizeof(note); // количество записей = размер файла / размер записи
    file_in.seekg(0, std::ios::beg);           // передвинем опять указатель в начало файла
 
    a_student = new note[kol_student];    // выделяем память для num_records студентов
 
    // можно читать данные из файла по одному студенту за раз
    // цикл пока не конец файла
    // функция file_in.eof() возвращает истину если достигнут конец
    //for (int i = 0; i < num_records && !file_in.eof(); i++)
    //  file_in.read((char *)a_student, sizeof(note));
 
    // но лучше прочитать все сразу!
    file_in.read((char*)a_student, sizeof(note)* kol_student);
 
    file_in.close();  // закрываем файл
 
    // создаем динамический вспомогательный массив по количеству студентов
    note ** pa_student = new note*[kol_student];
 
    char const * message; // для передачи сообщений в функции вывода
    // выводим полученный список студентов
    message = "Исходный Список студентов";
    print(a_student, kol_student, message);
 
    system("pause"); // пауза перед очисткой экрана
    system("cls");   // очистка экрана
 
    // заполняем вспомогательный массив указателями на студентов
    init_array(pa_student, a_student, kol_student);
    //for (int i = 0; i < kol_student; i++)
    //  pa_student[i] = &a_student[i];
 
    //----------------------------------------------------------------------------------
    // По Фамилии
    message = "Список студентов отсортированный по фамилии";
    selection_sort(pa_student, 0, kol_student, compare_name);
    print(*pa_student, kol_student, message);
 
    system("pause"); // пауза перед очисткой экрана
    //system("cls");   // очистка экрана
 
    // По Окладу
    // перезаполняем массив указателей на студентов
    init_array(pa_student, a_student, kol_student);
    //for (int i = 0; i < kol_student; i++)
    //  pa_student[i] = &a_student[i];
 
    message = "Список студентов отсортированный по окладу";
    selection_sort(pa_student, 0, kol_student, compare_oklad);
    print(*pa_student, kol_student, message);
 
    system("pause"); // пауза перед очисткой экрана
    //system("cls");   // очистка экрана
 
    // По Дате рождения
    // перезаполняем массив указателей на студентов
    init_array(pa_student, a_student, kol_student);
    //for (int i = 0; i < kol_student; i++)
    //  pa_student[i] = a_student[i];
 
    message = "Список студентов отсортированный по дате рождения";
    selection_sort(pa_student, 0, kol_student, compare_date);
    print(*pa_student, kol_student, message);
 
    //system("pause"); // пауза перед очисткой экрана
    ////system("cls");   // очистка экрана
 
    //----------------------------------------------------------------------------------
 
    // освобождаем выделенную память перед выходом
    //for (int i = 0; i < num_records; i++)
    //  delete [] a_student[i];
    delete[] a_student;
    delete[] pa_student;
    a_student  = 0;
    pa_student = 0;
 
 
    // ----------------------------
    // пауза перед выходом
    std::cout << std::endl << std::endl;
    system("pause");
 
    return 0;
 
} // конец main
 
 
void init_array(note **pa_student, note *a_student, int kol_student)
{
    for (int i = 0; i < kol_student; i++)
        pa_student[i] = &a_student[i];
}
 
// -------------------------------------------------------------------
// Шаблон функции вывода списка студентов
//
template <class T>
void print(T arr[], int arr_size, char const * message)
{
    std::cout << std::endl;
    std::cout << std::setw(40) << message << std::endl;
    std::cout << "---------------------------------------------------------------------\n";
    std::cout << "Фамилия           Имя         Телефон  Дата рожд.  Оклад   Ссылка  \n";
    std::cout << "---------------------------------------------------------------------\n";
 
    for (int i = 0; i < arr_size; i++) // цикл по количеству студентов
        print_record(arr[i], i);       // вывод одного студента
 
    std::cout << std::endl;
}
 
// -------------------------------------------------------------------
// Шаблон функции вывода одного студента
//
template <class T>
void print_record(T &student, int i)
{
    std::cout << std::setw(2) << i + 1 << ") "
        << std::setfill(' ') << std::left
        << std::setw(13)
        << student.first_name << " "
        << std::setw(10)
        << student.name << " "
        << std::right
        << std::setw(8) << student.phone << "  "
        << std::setfill('0') << std::setw(2) << student.birth_date[2] << "/"
        << std::setfill('0') << std::setw(2) << student.birth_date[1] << "/"
        << student.birth_date[0] << " "
        << std::setfill(' ')
        << std::setw(4) << student.oklad << " руб "
        << &student // адрес указателя
        << std::endl;
}
 
 
//------------------------------------------------------------------------------
// Сортировка массива структур методом выбора
//
//  Сначала отыскивается наименьший элемент массива, 
//  затем он меняется местами с элементом, стоящим первым в сортируемом массиве.
//  Далее, находится второй наименьший элемент и меняется местами с элементом, стоящим вторым в исходном массиве. 
//  Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.
//
// Параметры:
//  1) T *a[]    - указатель на массив структур
//  2) int left  - левый индекс в массиве, с него начинаем поиск
//  3) int right - правый индекс в массиве, до которого продолжаем поиск
//  4) int(*pf_compare)(T &a, T &b) - указатель на функцию сравнения двух структур по конкретному полю
//
template <class T>
void selection_sort(T *a[], int left, int right, int(*pf_compare)(T &a, T &b))
{
    // внешний цикл начинаем со следующего индекса от левой границы (со второго)
    for (int i = left + 1; i < right; i++)
    {
        // во внутреннем цикле сравниваем текущий элемент с элементами слева от текущего
        for (int j = i; j > left; j--)
        {
            // сравниваем элементы
            compare_swap(*(a[j - 1]), *(a[j]), pf_compare);
        }
    }
}
 
// Сравнение и, если нужно обмен элементов структуры
// Параметры:
//  1) item &a  - ссылка на 1-ю структуру
//  2) item &b  - ссылка на 2-ю структуру
//  3) int(*pf_compare)(T &a, T &b) - указатель на функцию сравнения двух структур по конкретному полю
//
template <class item>
void compare_swap(item &a, item &b, int(*pf_compare)(item &a, item &b))
{
    // сравниваем две структуры
    if (pf_compare(a, b) > 0)
    {
        // если результат сравнения положителен, меняем в массиве элементы местами
        swap(a, b);
    }
}
 
 
// обмен двух элементов
// Параметры:
//  1) item &a  - ссылка на 1-ю структуру
//  2) item &b  - ссылка на 2-ю структуру
//
template <class item>
void swap(item &a, item &b)
{
    item temp;
    temp = a;
    a = b;
    b = temp;
}
 
 
// сравнение по имени
int compare_name(note & a, note & b)
{
    //int i = 0;
    //if (a.first_name[0] < b.first_name[0])
    //  i = -1;
    //else if (a.first_name[0] > b.first_name[0])
    //  i = 1;
 
    //return i;
 
    return strcmp(a.first_name, b.first_name);
}
 
// сравнение по окладу
int compare_oklad(note & a, note & b)
{
    int i = 0;
    if (a.oklad < b.oklad)
        i = -1;
    else if (a.oklad > b.oklad)
        i = 1;
 
    return i;
}
 
// сравнение по дате
int compare_date(note & a, note & b)
{
    int i = 0;
    //if (a.birth_date[0] < b.birth_date[0])
    //  i = -1;
    //else if (a.birth_date[0] > b.birth_date[0])
    //  i = 1;
 
    //return i;
 
    //сравниваем год
    if (a.birth_date[0] < b.birth_date[0]) 
        i = -1;
    else if (a.birth_date[0] > b.birth_date[0]) 
        i = 1;
    else if (a.birth_date[0] == b.birth_date[0])
    {
        //сравниваем месяц
        if (a.birth_date[1] < b.birth_date[1]) 
            i = -1;
        else if (a.birth_date[1] > b.birth_date[1]) 
            i = 1;
        else if (a.birth_date[1] == b.birth_date[1])
        {
            // сравниваем день
            if (a.birth_date[2] < b.birth_date[2])
                i = -1;
            else i = 1;
        }
    }
    return i;
}
я смотрю в правильном направлении ?..
Yandex
Объявления
15.04.2014, 15:47     Шаблон функции сортировки массива структур по разным типам полей
Ответ Создать тему
Опции темы

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