Форма отчета по лабораторной работе. Отчет должен содержать: титульный лист; цель работы; условие задачи; текст программы с комментариями; результаты работы программы с контрольным примером

Отчет должен содержать: титульный лист; цель работы; условие задачи; текст программы с комментариями; результаты работы программы с контрольным примером небольшой размерности и ручной расчет контрольного примера для проверки правильности работы алгоритмов; выводы по работе.

Вопросы для самоконтроля

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;

}