Практическая работа 4
Структуры и массивы структур
Цель работы
Целью лабораторной работы является получение практических навыков в работе с интегрированными типами данных - структурами и массивами структур языка C++.
Темы для предварительной проработки
џ Типы данных языка C++.
џ Массивы.
џ Структуры.
Задания для выполнения
Составить программу, в которой будут вводиться 7 - 10 строк таблицы и выводится на экран таблица - сразу же после ввода и после сортировки ее по значениям в первом столбце.
Варианты индивидуальных заданий
5. Пример решения задачи (вариант 30)
Разработка алгоритма решения.
Алгоритм решения, приведенный на рисунке ниже, является типовым алгоритмом обработки массива, элементами которого являются описания монастырей.
Алгоритм начинается с ввода значений элементов этого массива. Ввод происходит в цикле со счетчиком n, который изменяется от 0 до 9 (блок 2), но как мы увидим ниже, выход из цикла может происходить и до того, как счетчик достигнет последнего значения. В каждой итерации циклу выводится приглашение (блок 3) и вводятся значения составных частей описания монастыря (блоки 4, 6, 7, 8). Но сразу же после ввода первой составляющей - названия - проверяется ее значения (блок 5). Если введено название "***", то дальнейшего ввода не происходит, а сразу выполняется выход из цикла. В любом случае после выхода в переменной n остается количество введенных элементов. Таким образом, программа может обрабатывать массив из 10 или меньше элементов - сколько их было введено. Признаком конца ввода является название "***".
Далее печатаем заголовок таблицы (блок 9) и в цикле (блоки 10, 11) - строки таблицы с данными. Поскольку параметр этого цикла изменяется от 0 до n-1, будет напечатано n строк.
Следующий сложный цикл реализует сортировку таблицы по алгоритму простой обменной выборки. Сортировка выполняется с помощью вложенного цикла (блок 12). В первой итерации внешнего цикла выполняется поиск элемента массива с минимальным значением поля name. Для этого сначала минимальным элементом считается первый элемент (блок 13). Потом в цикле (блок 14) пересматриваются остальные элементы массива, и каждый сравнивается с минимальным (блок 15). Если поле name очередного элемента меньше, чем минимального, то теперь этот элемент считается минимальным (блок 16). Индекс минимального элемента записывается в переменную m. После выхода из внутреннего цикла, если найденный минимальный элемент не первый (блок 17), то он меняется местами с первым (блок 18). Таким образом, минимальный элемент массива становится на свое место. В следующей итерации внешнего цикла выполняется поиск минимума среди элементов массива, начиная со второго, в третьей - начиная с третьего и т.д. После выхода из внешнего цикла массив оказывается отсортированным.
Вывод отсортированного массива (блоки 19 - 21) происходит точно так же, как и вывод начального массива (блоки 9 - 11).
5.2. Определение переменных программы
Как мы отметили, элементом массива является описание объекта. Поскольку описание состоит из нескольких составных частей разного типа, для него используем структуру языка C. Описание этой структуры будет иметь вид:
struct mon {
char name[15]; /* название */
char sc; /* школа */
int cnt; /* количество монахов */
float sq; /* площадь */
};
Тут мы резервируем для названия больше символов, предвидя возможность появления более длинных названий, а также даем тип int полю cnt, допуская, что его значения может быть больше, чем 255.
Нам нужно будет иметь массив элементов указанного типа, следовательно, объявляем:
struct mon mm[10];
Для выполнения перестановки элементов массива нужна будет еще рабочая область памяти того же типа, что и элементы массива, поэтому вводимо еще:
struct mon x;
Как видно из схемы алгоритма, нужны будут переменные целого типа для: количества введенных элементов n, индексов внешнего (i) и внутреннего (j) циклов и индекса минимального элемента - m. Поэтому объявляем:
int i, j, n, m;
5.3. Разработка текста программы
Текст программы начинаем с включения файла stdio.h.
Поскольку нам придется проводить сравнение (блок 15) поля name в элементах массива, а это поле - символьная строка, включаем также файл string.h, где описаны функции работы с символьными строками. В самом начале программы вводим также описание структуры mon и одновременно - объявление массива mm. Массив будет размещен в статической памяти.
Потом открывается главная функция программы, и в ней объявляются остальные переменные. Объявление:
float sqx;
мы прокомментируем ниже.
Открывается простой цикл со счетчиком n, в каждой итерации цикла выводится приглашение и вводятся значения полей очередного элемента массива. Сравнение поля name с константой "***" - признаком конца ввода выполняется с помощью функции strcmp(). Если введен признак конца, происходит досрочный выход из цикла за оператором break.
Следует, однако, остановиться на вводе значения для поля sq. Тут мы столкнулись (не впервые в нашей практике) с явлением, которое не можем объяснить иначе, чем ошибкой в системе программирования: функция scanf() работает ненадежно при вводе значений типа float и double, если это - значения полей элементов массива структур. Поэтому мы объявили рабочую переменную sqx типа float и значение поля sq сначала вводится в эту переменную, а потом присваивается полю структуры.
Вывод массива состоит из вывода заголовка как нескольких строк-констант и вывода в цикле строк с фактическими данными.
Следующие операторы программы подробно реализуют блоки 12 - 17 схемы алгоритма (для сравнения символьных строк применяется функция strcmp()). Детального рассмотрения требует только реализация блока 18 - перестановка элементов. Во-первых, при перестановке используется рабочая структура x: сначала содержимое i -го элемента пересылается в x, потом содержимое m -го элемента пересылается в i -ый элемент, а потом содержимое x пересылается в m -ый элемент. Во-вторых, операция присваивания, которая обычно применяется для пересылки значений, не может применяться к структуре в целом, так что присваивания происходит для каждого поля отдельно. К тому же, поле name является символьной строкой, а строки тоже не могут присваиваться прямо, а только - через функцию strcpy(). (Впрочем, для присваивания структур можно использовать функцию пересылки в памяти - memcpy().)
Вывод таблицы-результата - такой же, как и начальной таблицы.
Полный текст программы приведен ниже.
/********************************************************/
/* Практическая работа 4 */
/* Структуры и массивы структур */
/* Пример выполнения. Вариант 30. */
/********************************************************/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <iomanip.h>
using namespace std;
/* Описание структуры, которая представляет монастырь */
struct mon {
char name[15]; /* название */
char sc; /* школа */
int cnt; /* количество монахов */
float sq; /* площадь */
} mm[10]; /* определение массива монастырей */
int main(void) {
struct mon x; /* рабочая переменная */
int n; /* количество элементов в массиве */
int i, j; /* текущие индексы в массиве */
int m; /* индекс минимального элемента */
float sqx;/* рабочая переменная */
/* Ввод данных */
for (n=0; n<10; n++){
cout<< n+1 << "Vvedite nazvanie, shkoly, kolichestvo, ploshad >";
cin >> mm[n].name;
if (!strcmp(mm[n].name,"***")) break;
cin >> mm[n].sc;
cin >> mm[n].cnt;
cin >> mm[n].sq;
}
/* Вывод таблицы */
cout << "-----------------------------------------------\n";
cout << "| Byddiskie monastury Yaponii perioda Nara |\n";
cout << "|---------------------------------------------|\n";
cout << "| Nazvanie | Shkola |Kolichestvo| Ploshad |\n";
cout << "| | | monaxov |zemel(ga)|\n";
cout << "|--------------|--------|-----------|---------|\n";
/* вывод строк фактических данных */
for (i=0; i<n; i++)
cout << "|"<< setw(14)<< mm[i].name<<"|"<< setw(8) << mm[i].sc << "|"<< setw(11)<< mm[i].cnt <<"|"<< setw(9) << mm[i].sq << "|\n";
cout << "-----------------------------------------------\n";
/* сортировка массива */
for (i=0; i<n-1; i++) {
m=i; /* минимальный элемент - первый */
for (j=i+1; j<n; j++)
/* если текущий элемент > минимального,
он становится минимальным */
if (strcmp(mm[m].name,mm[j].name)>0) m=j;
if (m>i) {
/* перестановка первого и минимального элементов */
strcpy(x.name,mm[i].name); x.sc=mm[i].sc;
x.cnt=mm[i].cnt; x.sq=mm[i].sq;
strcpy(mm[i].name,mm[m].name); mm[i].sc=mm[m].sc;
mm[i].cnt=mm[m].cnt; mm[i].sq=mm[m].sq;
strcpy(mm[m].name,x.name); mm[m].sc=x.sc;
mm[m].cnt=x.cnt; mm[m].sq=x.sq;
}
}
/* Вывод таблицы */
cout << "-----------------------------------------------\n";
cout << "| Byddiskie monastury Yaponii perioda Nara |\n";
cout << "|---------------------------------------------|\n";
cout << "| Nazvanie | Shkola |Kolichestvo| Ploshad |\n";
cout << "| | | monaxov |zemel(ga)|\n";
cout << "|--------------|--------|-----------|---------|\n";
for (i=0; i<n; i++)
cout << "|"<< setw(14)<< mm[i].name<<"|"<< setw(8) << mm[i].sc << "|"<< setw(11)<< mm[i].cnt <<"|"<< setw(9) << mm[i].sq << "|\n";
cout << "-----------------------------------------------\n";
return 0;
}