Задания для лабораторной работы:

Для заданной прикладной области разработать описание объектов этой области. Разработать процедуры, реализующие базовые операции над этими объектами, в том числе:

текстовый ввод-вывод (консольный и файловый);

присваивание;

задание константных значений;

сравнение (не менее 2-х типов).

Процедуры и описания данных должны составлять отдельный модуль (модуль типа данных). Используя процедуры и описания модуля типа данных, разработать программу, обеспечивающую ввод исходных данных из первого файла данных в память и хранение их в памяти в виде связного списка, сортировку списка по алфавитному и по числовому параметру.

Для каждой области перечислены параметры объекта. Среди параметров обязательно есть ключевое алфавитное поле (например, фамилия), которое идентифицирует объект, у каждого объекта имеется также одно или несколько числовых полей, по которым вероятны обращения к объекту.

1 Отдел кадров фамилия сотрудника, имя, отчество, должность, стаж работы, оклад

2 Красная книга вид животного, род, семейство, место обитания, численность популяции

3 Производство обозначение изделия, группа к которой оно относится, год выпуска, объем выпуска, расход металла

4 Персональные ЭВМ фирма-изготовитель, тип процессора, тактовая частота, емкость ОЗУ, емкость жесткого диска

5 Библиотека автор книги, название, год издания, код УДК, цена, количество в библиотеке

6 Спутники планет название, название планеты-хозяина, год открытия, диаметр, период обращения

7 Радиодетали обозначение, тип, номинал, количество на схеме, обозначение возможного заменителя

8 Текстовые редакторы наименование, фирма-изготовитель, количество окон, количество шрифтов, стоимость

9 Телефонная станция номер абонента, фамилия, адрес, наличие блокиратора, задолженность

10 Быт студентов фамилия студента, имя, отчество, факультет, размер стипендии, число членов семьи

11 Спортивные соревнования фамилия спортсмена, имя, команда, вид спорта, зачетный результат, штрафные очки

12 Соревнование факультетов по успеваемости факультет,количество студентов, средний балл по факультету, число отличников, число двоечников

13 С/х работы фамилия студента, имя, отчество, факультет, вид работ, заработок

14 Сельхозработы наименование с/х предприятия, вид собственности, число работающих, основной вид продукции, прибыль

15 Сведения о семье фамилия студента, имя, отчество, факультет, специальность отца, специальность матери, количество братьев и сестер

16 Скотоводство вид животных, количество особей в стаде в возрасте до 1 года, количество особей 1 - 3 лет, свыше 3 лет, смертность в каждой группе, рождаемость

17 Микросхемы памяти обозначение, разрядность, емкость, время доступа, количество на схеме, стоимость

18 Описание изображения тип фигуры (квадрат, окружность и т.п.), координаты на плоскости, числовые характеристики (длина строрны, радиус и т.п.).

19 Лесное хозяйство наименование зеленого массива, площадь, основная порода, средний возраст, плотность деревьев на кв.км

20 Городской транспорт вид транспорта, номер маршрута, начальная остановка, конечная остановка, время в пути

21 Университет ФИО и должность преподавателя, названиепредмета, количество часов, тип контроля

22 Оптовая база название товара, количество на складе, стоимость единицы, название поставщика, срок поставки

23 Сеть магазинов номер, название, адрес, телефон магазина, ФИО, адрес, капитал владельцев магазина.

24 Авторемонтные мастерские номер, марка, мощность и цвет автомобиля, ФИО и квалификация механика, тип работ

25 Зоопарк вид животного, кличка, возраст, категория редкости, вес, суточный рацион мяса, овощей, молока

26 Договорная деятельность организации шифр договора, наименование организации, наименование контрагента сроки выполнения, сумма договора, вид договора.

27 Поликлиника ФИО и дата рождения пациента, ФИО, должность и специализация лечащего врача, диагноз

28 Домоуправление номер квартиры, общая площадь, полезная площадь, количество комнат, фамилия квартиросъемщика, количество членов семьи, количество детей в семье, есть ли задолженность по квартплате

29 Аэропорт номер рейса, пункт назначения, день рейса, тип самолета, время вылета, время в пути, является ли маршрут международным,

30 Шахматы ФИО спортсмена, дата рождения, страна, спортивный разряд, участвовал ли в борьбе за звание чемпиона мира, рейтинг,

31 Ипподром кличка лошади, масть, возраст, рейтинг, вид забега, фамилия наездника, занятое место

32 Малые планеты Название, название планеты-хозяина (для спутников), дата открытия, диаметр, период обращения

33 Автотранспортное предприятие номерной знак автомобиля, марка, техническое состояние, грузоподъемность, расход топлива, табельный номер и ФИО закрепленного водителя водителя

34 Мобильные устройства Производитель, цена, ОС, количество ядер, поддержка 4G, цвет.

35 Телевизор Производитель, частота обновления, поддержка SMART TV, стоимость, количество портов USB, диагональ.

Контрольные вопросы

1. Что такое структура?

2. Как задается структурированная переменная?

3. Что такое список?

4. Какие операции над списками можно выполнить?

5. Какой список называется линейным?

Лабораторная работа № 5-6

«Представление в памяти массивов и матриц»

Цель работы: получение практических навыков в использовании массивов и динамических объектов в языке Cи, создание модульных программ и обеспечение инкапсуляции.

Образовательные результаты, заявленные во ФГОС третьего поколения:

Студент должен

уметь:

- осуществлять разработку кода программного модуля на современных языках программирования;

- создавать программу по разработанному алгоритму как отдельный модуль;

знать:

- основные этапы разработки программного обеспечения;

- основные принципы технологии структурного и объектно-ориентированного программирования.

Краткие теоретические и учебно-методические материалы

по теме лабораторной работы

Переменные с двумя и более индексами служат для описания многомерных массивов. Двумерный массив состоит из элементов, образующих прямоугольную таблицу. В этом случае первый индекс обозначает номер строки, а второй индекс – номер столбца таблицы, на пересечении которых и расположен данный элемент.

Экономное использование памяти предусматривает, что для тех элементов матрицы, в которых наверняка содержатся нули, память выделяться не будет. Поскольку при этом нарушается двумерная структура матрицы, она может быть представлена в памяти как одномерный массив, но при обращении к элементам матрицы пользователь имеет возможность обращаться к элементу по двум индексам.

Программное изделие должно быть отдельным модулем, в котором должны размещаться как данные (матрица и вспомогательная информация), так и функции, которые обеспечивают доступ. Внешний доступ к программам и данным модуля возможен только через вызов функций чтения и записи элементов матрицы. Доступные извне элементы программного модуля должны быть описаны в отдельном файле, который может включаться в программу пользователя оператором препроцессора.

Преобразование 2-компонентного адреса элемента матрицы, которую задает пользователь, в 1-компонентную должно выполняться отдельной функцией (так называемой, функцией линеаризации), вызов которой возможен только из функций модуля. Возможны три метода преобразования адреса: при создании матрицы для нее создается также и дескриптор D[N] - отдельный массив, каждый элемент которого соответствует одной строке матрицы; дескриптор заполняется значениями, подобранными так, чтобы: n = D[x] + y, где x, y - координаты пользователя (строка, столбец), n - линейная координата; линейная координата подсчитывается методом итерации як сумма полезных длин всех строк, предшествующих строке x, и к ней прибавляется смещение y-го полезного элемента относительно начала строки; для преобразования подбирается единое арифметическое выражение, которой реализует функцию: n = f(x,y).

Первый вариант обеспечивает быстрейший доступ к элементу матрицы, ибо требует наименьших расчетов при каждом доступе, но плата за это - дополнительные затраты памяти на дескриптор. Второй вариант - наихудший по всем показателям, ибо каждый доступ требует выполнения оператора цикла, а это и медленно, и занимает память. Третий вариант может быть компромиссом, он не требует дополнительной памяти и работает быстрее, чем второй. Но выражение для линеаризации тут будет сложнее, чем первом варианте, следовательно, и вычисляться будет медленнее.

Пример: написать программу, где матрица содержит нули ниже главной диагонали; индексация начинается с 0.

Введем обозначения переменных:

int NN - размерность матрицы;

int SIZE - количество ненулевых элементов в матрице;

int *m_addr - адрес сжатой матрицы в памяти, начальное значение этой переменной - NULL - признак того, что память не выделена;

int L2_RESULT - общий флаг ошибки, если после выполнения любой функции он равен -1, то произошла ошибка.

Переменные SIZE и m_addr описаны вне функций с квалификатором static, это означает, что вони доступны для всех функций в этом модуле, но недоступны для внешних модулей. Переменная L2_RESULT также описана вне всех функций, не без явного квалификатора. Эта переменная доступна не только для этого модуля, но и для всех внешних модулей, если она в них буде описана с квалификатором extern.

Функция creat_matr предназначена для выделения в динамической памяти места для размещения сжатой матрицы. Прототип функции:

int creat_matr ( int N ).

Функция сохраняет значение параметра в собственной статической переменной и подсчитывает необходимый размер памяти для размещения ненулевых элементов матрицы. Для выделения памяти используется библиотечная функция C malloc. Функция возвращает -1, если при выделении произошла ошибка, или 0, если выделение прошло нормально. При этом переменной L2_RESULT также присваивается значение 0 или -1.

Функция close_matr предназначена для освобождения памяти при завершении работы с матрицей, Прототип функции:

int close_matr ( void );

Функция возвращает 0 при успешном освобождении, -1 - при попытке освободить невыделенную память. Если адрес матрицы в памяти имеет значения NULL, это признак того, что память не выделялась, тогда функция возвращает -1, иначе - освобождает память при помощи библиотечной функции free и записывает адрес матрицы - NULL. Соответственно функция также устанавливает глобальный признак ошибки - L2_RESULT.

Функция read_matr предназначена для чтения элемента матрицы. Прототип функции: int read_matr(int x, int y); где x и y - координаты (строка и столбец). Функция возвращает значение соответствующего элемента матрицы. Если после выполнения функции значение переменной L2_RESULT -1, то это указывает на ошибку при обращении. Проверка корректности задания координат выполняется обращением к функции ch_coord, если эта последняя возвращает ненулевое значение, выполнение read_matr на этом и заканчивается. Если же координаты заданы верно, то проверяется попадание заданного элемента в нулевой или ненулевой участок. Элемент находится в нулевом участке, если для него номер строки больше, чем номер столбца. Если элемент в нулевом участке, функция просто возвращает 0, иначе - вызывает функцию линеаризации lin и использует значение, которое возвращает lin, как индекс в массиве m_addr, по которому и выбирает то значения, которое возвращается.

Функция write_matr предназначена для записи элемента в матрицу. Прототип функции: int write_matr(int x, int y, int value); где x и y - координаты (строка и столбец), value - то значение, которое нужно записать. Функция возвращает значение параметра value, или 0 - если была попытка записи в нулевой участок. Если после выполнения функции значение переменной L2_RESULT -1, то это указывает на ошибку при обращении.

Выполнение функции подобно функции read_matr с тем отличием, что, если координаты указывают на ненулевой участок, то функция записывает value в массив m_addr.

Функция ch_coord предназначена для проверки корректности задания координат. Эта функция описана как static и поэтому может вызываться только из этого же модуля. Прототип функции static char ch_coord(int x, int y); где x и y - координаты (строка и столбец). Функция возвращает 0, если координаты верные, -1 - если неверные. Соответственно, функция также устанавливает значение глобальной переменной L2_RESULT.

Выполнение функции собственно состоит из проверки трех условий: адрес матрицы не должен быть NULL, т.е., матрица должна уже находиться в памяти; ни одна из координат не может быть меньше 0; ни одна из координат не может быть больше NN. Если хотя бы одно из этих условий не выполняется, функция устанавливает признак ошибки.

Функция lin предназначена для преобразования двумерных координат в индекс в одномерном массиве. Эта функция описана как static и поэтому может вызываться только из этого же модуля. Прототип функции: static int lin(int x, int y); где x и y - координаты (строка и столбец). Функция возвращает координату в массиве m_addr.

Выражение, значение которого вычисляет и возвращает функция, подобрано вот из каких соображений. Пусть мы имеет такую матрицу, как показано ниже, и нам нужно найти линейную координату элемента, обозначенного буквой A с координатами (x,y):

x x x x x x

0 x x x x x

0 0 x x A x

0 0 0 x x x

0 0 0 0 x x

0 0 0 0 0 x

Координату элемента можно определить как:

n = SIZE - sizeX +offY,

где SIZE - общее количество элементов в матрице (см. creat_matr),

SIZE = NN * (NN - 1) / 2 + NN;

sizeX - количество ненулевых элементов, которые содержатся в строке x и ниже,

sizeX = (NN - x) * (NN - x - 1) / 2 + (NN - x);

offY - смещение нужного элемента от начала строки x, offY = y - x.

Для проверки функционирования нашего модуля создается программный модуль, который имитирует программу пользователя. Этот модуль обращается к функции creat_matr для создания матрицы нужного размера, заполняет ненулевую ее часть последовательно увеличивающимися числами, используя для этого функцию write_matr, и выводит матрицу на экран, используя для выборки ее элементов функцию read_matr. Далее в диалоговом режиме программа вводит запрос на свои действия и читает/пишет элементы матрицы с заданными координатами, обращаясь к функциям read_matr/write_matr. Если пользователь захотел закончить работу, программа вызывает функцию close_matr.

/********************** Файл LAB.H *************************/

/* Описание функций и внешних переменных файла LAB.C */

extern int L2_RESULT; /* Глобальна переменна - флаг ошибки */

/***** Выделение памяти под матрицу */

int creat_matr ( int N );

/***** Чтение элемента матрицы по заданным координатам */

int read_matr ( int x, int y );

/***** Запись элемент в матрицу по заданным координатам */

int write_matr ( int x, int y, int value );

/***** Уничтожение матрицы */

int close_matr ( void );

/************************* Файл LAB.C *************************/

/* В этом файле определены функции и переменные для обработки

матрицы, заполненной нулями ниже главной диагонали */

#include <alloc.h>

static int NN; /* Размерность матрицы */

static int SIZE; /* Размер памяти */

static int *m_addr=NULL; /* Адрес сжатой матрицы */

static int lin(int, int); /* Описание функции линеаризации */

static char ch_coord(int, int); /* Описание функции проверки */

int L2_RESULT; /* Внешняя переменная, флаг ошибки */

/* Выделение памяти под сжатую матрицу */

int creat_matr ( int N ) {

/* N - размер матрицы */

NN=N;

SIZE=N*(N-1)/2+N;

if ((m_addr=(int *)malloc(SIZE*sizeof(int))) == NULL )

return L2_RESULT=-1;

else

return L2_RESULT=0;

/* Возвращает 0, если выделение прошло успешно, иначе -1 */

}

/* Уничтожение матрицы (освобождение памяти) */

int close_matr(void) {

if ( m_addr!=NULL ) {

free(m_addr);

m_addr=NULL;

return L2_RESULT=0;

}

else return L2_RESULT=-1;

/* Возвращает 0, если освобождение пршло успешно, иначе - -1 */

}

/* Чтение элемента матрицы по заданным координатам */

int read_matr(int x, int y) {

/* x, y -координати (строка, столбец) */

if ( ch_coord(x,y) ) return 0;

/* Если координаты попадают в нулевой участок - возвращается

0, иначе - применяется функция линеаризации */

return (x > y) ? 0 : m_addr[lin(x,y)];

/* Проверка успешности чтения - по переменной

L2_RESULT: 0 - без ошибок, -1 - была ошибка */

}

/* Запись элемента матрицы по заданным координатам */

int write_matr(int x, int y, int value) {

/* x, y -координати, value - записываемое значение */

if ( chcoord(x,y) ) return;

/* Если координаты попадают в нулевой участок - записи нет,

иначе - применяется функция линеаризации */

if ( x > y ) return 0;

else return m_addr[lin(x,y)]=value;

/* Проверка успешности записи - по L2_RESULT */

}

/* Преобразование 2-мерних координат в линейную */

/* (вариант 3) */

static int lin(int x, int y) {

int n;

n=NN-x;

return SIZE-n*(n-1)/2-n+y-x;

}

/* Проверка корректности обращения */

static char ch_coord(int x, int y) {

if ( ( m_addr==NULL ) ||

( x>SIZE ) || ( y>SIZE ) || ( x<0 ) || ( y<0 ) )

/* Если матрица не размещена в памяти, или заданные

координаты выходят за пределы матрицы */

return L2_RESULT=-1;

return L2_RESULT=0;

}

/************************ Файл MAIN5.C **************************/

/* "Программа пользователя" */

#include "lab5.h"

main(){

int R; /* размерность */

int i, j; /* номера строки и столбца */

int m; /* значения элемента */

int op; /* операция */

clrscr();

printf('Введите размерность матрицы >'); scanf("%d",R);

/* создание матрицы */

if ( creat_matr (R) ) {

printf("Ошибка создания матрицы\n");

exit(0);

}

/* заполнение матрицы */

for ( m=j=0; j<R; j++)

for ( i=о; i<R; i++)

write_matr(i,j,++m);

while(1) {

/* вывод матрицы на экран */

clrscr();

for (j=0; j<R; j++) {

for (i=0; i<R; i++)

printf("%3d ",read_matr(i,j));

printf("\n");

}

printf("0 - выход\n1 - чтение\n2 - запись\n>")

scanf("%d",&op);

switch(op) {

case 0:

if (close_matr()) printf("Ошибка при уничтожении\n");

else printf("Матрица уничтожена\n");

exit(0);

case 1: case 2:

printf("Введите номер строки >");

scanf("%d",&j);

printf("Введите номер столбца >");

scanf("%d",&i);

if (op==2) {

printf("Введите значение элемента >");

scanf("%d",&m);

write_matr(j,i,m);

if (L2_RESULT<0) pritnf("Ошибка записи\n");

}

else {

m=read_matr(j,i);

if (L2_RESULT<0) pritnf("Ошибка считывания\n");

else printf("Считано: %d\n",m);

}

printf("Нажмите клавишу\n"); getch();

break;

}

}

}