Форма отчета по лабораторной работе. Отчет должен содержать: титульный лист; цель работы; условие задачи; текст программы с комментариями; результаты работы программы с контрольным примером
Отчет должен содержать: титульный лист; цель работы; условие задачи; текст программы с комментариями; результаты работы программы с контрольным примером небольшой размерности и ручной расчет контрольного примера для проверки правильности работы алгоритмов; выводы по работе.
Вопросы для самоконтроля
1. Назначение функций в языке Си.
2. Определение, описание и вызов функции.
3. Передача в функцию массивов.
4. Способы передачи параметров в функцию.
5. Вызов функции как «функции» и вызов функции как «процедуры».
Лабораторная работа № 6. Изучение динамических структур данных. Списки
Цель и задачи работы, требования к результатам ее выполнения
Цель работы состоит в овладении навыками разработки программ на языке Си, использующих линейные списки, при работе с данными, имеющими динамическую структуру. Для достижения цели необходимо выполнить следующие задачи:
- изучить учебный материал, посвященный линейным спискам [3, 4];
- разработать программу на языке Си для решения заданного варианта задания;
- отладить программу;
- подготовить отчет по лабораторной работе.
Краткая характеристика объекта изучения
Статические структуры данных (обычные переменные, массивы, структуры, объединения и т.п.) имеют, раз навсегда, заданные для них объем памяти и соответственно диапазон возможных значений.
Множество задач требуют хранения данных с более сложной структурой, в процессы вычисления должны меняться не только значения переменных, но и их структура и соответственно размер выделяемой памяти. Такие данные называются данными с динамической структурой. Иногда их называют данными с рекурсивной структурой [4].
Пример генеалогическое дерево определяется как имя человека + 2 дерева его родителей, такое определение ведет к бесконечной структуре, реальные деревья всегда конечны.
Особенность рекурсивных структур – способность изменять размер. Для этого используется метод динамического распределения памяти, т.е. память под отдельные компоненты выделяется в тот момент, когда они начинают существовать. Это можно реализовать с помощью указателей.
Простейшая динамическая структура данных – линейный односвязный список. Каждый элемент списка содержит информационное поле, и указатель на следующий элемент списка, в последнем элементе этот указатель обычно равен 0. Для работы со списком достаточно хранить в оперативной памяти в отдельной переменной указатель на первый элемент списка. Схема линейного односвязного списка представлена на рисунке 7.
| Информационное поле Указатель на след. элемент |
| Информационное поле Указатель на след. элемент |
| Информационное поле NULL |
| Указатель на 1-ый элемент |
Рисунок 7 – Схема линейного односвязного списка
Структура, описывающая линейный односвязный список:
struct Inform { ... }; // Информационная структура (задает информационное поле)
struct List1
{
Inform Inf;
List1 *pNext;
};
Для работы с таким списком необходимо знать указатель на первый элемент списка (признак последнего элемента pNext==NULL), иногда удобно хранить указатель на последний элемент для ускорения доступа к последнему элементу, например, чтобы добавить элемент в конец списка. Более подробно с теоретическими основами для работы со списками можно ознакомиться в [3, 4].
Задачи и порядок выполнения работы
В лабораторной работе необходимо организовать список объектов и сортировку списка. Данные списка вводятся с клавиатуры, после каждого элемента идет запрос на ввод следующего элемента или завершение ввода (число элементов заранее неизвестно). При сортировке элементы списка остаются в оперативной памяти на «своих местах», меняются только значения указателей, связывающие элементы. Вывести на экран список до сортировки и после сортировки.
Пример выполнения работы
Условие задачи:
Объект списка- сотрудник (поля: ФИО, дата приема на работу, должность, базовый оклад). Сортировка по полю «оклад» методом прямого выбора.
Для решения задачи в среде Microsoft Visual Studio 2013 было создано стандартное консольное приложение (проект типа Win32 Console Application) с установленным свойством «пустой проект» (Empty project). В проект добавлен файл с расширением .cpp, исходный код которого приведен ниже.
Листинг программы с комментариями:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct Sotr // Сотрудник
{
char fio[64]; // ФИО
char date[16]; // Дата рождения
char dolg[32]; // Должность
double okl; // Оклад
};
struct List // Список
{
Sotr sotr; // Инф поле
List *pNext; // Указательна следующий элемент
};
// Функция добавления элемента в начало списка
void addFirst(List *& pF, // Указатель на начало списка
List* p) // Указатель на добавляемый элемент
{
p->pNext = pF;
pF = p;
}
// Удаление элемента из начала списка
List * delFirst(List *&pF) // Функция возвращает указатель на удаляемый элемент
{
if (pF == 0) return 0;
List *p = pF;
pF = pF->pNext;
return p;
}
// Добавление элемента перед заданным
bool add(List *&pF, List * pZad, List *p)
{
// Функция возвращает true при нормальном завершении и false в случае ошибки
if (pZad == pF) // Элемент будет первым
{
p->pNext = pF;
pF = p;
return true;
}
List *pPred = pF; // Указатель на предыдущий элемент перед pZad
while (pPred->pNext != pZad && pPred->pNext)
pPred = pPred->pNext;
if (pPred->pNext == 0) return false; // Элемента pZad нет в списке
p->pNext = pZad;
pPred->pNext = p;
return true;
}
// Удаление любого элемента p из списка
List * del(List*& pF, List *p) // Функция возвращает указатель на удаленный элемент
{
if (pF == 0) return 0;
if (pF == p) // Удаляем первый элемент
{
pF = pF->pNext;
return p;
}
else
{
List *pPred = pF; // Указатель на предыдущий элемент перед p
while (pPred->pNext != p && pPred->pNext)
pPred = pPred->pNext;
if (pPred->pNext == 0) return 0; // Элемента p нет в списке
pPred->pNext = p->pNext;
return p;
}
while (delFirst(pF)); // Очистка списка
}
int main(int argc, char* argv[])
{
List *pF = 0; // Список пуст
List *p;
// Ввод списка
char Ch; // Переменная для ввода условия продолжения ввода
do
{
p = (List *)malloc(sizeof(List)); // Выделяем память под элемент
printf("\nFIO: ");
fflush(stdin); gets_s(p->sotr.fio, 63);
printf("Date: ");
fflush(stdin); gets_s(p->sotr.date, 15);
printf("Dolg: ");
fflush(stdin); gets_s(p->sotr.dolg, 31);
printf("Okl=");
fflush(stdin); scanf_s("%lf", &p->sotr.okl);
addFirst(pF, p); // Добавляем элемент в начало списка
printf("For continue press Y or y else any key! ");
Ch = _getche(); // Чтение кода клавиши с печатью символа
} while (Ch == 'Y' || Ch == 'y');
// Вывод спика
for (List *pi = pF; pi; pi = pi->pNext) // Просмотр списка
printf("\n%s %s %s oklad=%.2f", pi->sotr.fio, pi->sotr.date,
pi->sotr.dolg, pi->sotr.okl);
// Сортировка списка
for (List *pi = pF; pi->pNext;)
{
// Ищем минимальный элемент в списке
double min = pi->sotr.okl;
List *pmin = pi;
for (List *pj = pi->pNext; pj; pj = pj->pNext)
if (pj->sotr.okl<min)
{
min = pj->sotr.okl;
pmin = pj;
}
if (pi != pmin) // Минимальный элемент делаем первым, он будет перед pi
{
del(pF, pmin);
add(pF, pi, pmin);
}
else pi = pi->pNext;
}
// Печать списка после сортировки
printf("\nSrting:");
for (List *pi = pF; pi; pi = pi->pNext) // Просмотр списка
printf("\n%s %s %s oklad=%.2f", pi->sotr.fio, pi->sotr.date,
pi->sotr.dolg, pi->sotr.okl);
printf("\nFor exit press any key ");
system("pause"); // Останавливаем программу, ждем нажатия любой клавиши
return 0;
}