Лабораторная работа № 8. Программирование с использованием динамической памяти

Цель работы: изучение средств языка и приемов работы со списками, размещенными в динамической памяти

Объем работы: 6 часов

Теоретическая часть

Динамическими принято называть структуры данных, которые создаются в процессе выполнения программы. Понятие ≪создаются≫ можно интерпретировать по-разному:

· создаются – в смысле ≪получают память и начинают реально существовать≫;

· создаются – в смысле ≪организуются, строятся из некоторых элементов≫.

К первому типу относятся динамические массивы, строки и структуры, память под которые выделяется во время выполнения программы. К структурам второго типа относятся списки.

Список – структура, при организации которой использованы указатели, содержащие адреса следующих элементов. Элемент списка состоит из двух частей: информационной и адресной. Информационная часть содержит поля данных. Адресная – включает от одного до n указателей, содержащих адреса других элементов. Количество связей, между соседними элементами списка определяет его связность: односвязные, двусвязные, n-связные.

По структуре списки бывают линейными, древовидными и сетевыми. На линейных списках обычно реализуют разные дисциплины обслуживания:

· очередь – дисциплина обработки элементов данных, в которой добавление элементов выполняется в конец, а удаление – из начала;

· стек – дисциплина обработки элементов данных, в которой добавление и удаление элементов осуществляется с одной стороны;

· дек – дисциплина обработки элементов данных, в которой добавление и удаление элементов может выполняться с двух сторон.

Линейные односвязные списки используют чаще других списковых структур, так как они сравнительно просты, но одновременно в отличие от одномерных массивов позволяют:

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

· осуществлять вставку и удаление записей, не перемещая остальных элементов последовательности.

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

Рассмотрим более подробно, как выполняются основные операции с линейными односвязными списками.

Исходные установки. В начале программы необходимо описать элемент и его тип:

Элемент односвязного списка:

struct element // тип элемента

{

char name[16]; // информационное поле 1

char telefon[7]; // информационное поле 2

element *p; // адрес следующего элемента

};

Элемент двусвязного списка:

struct element // тип элемента

{

char name[16]; // информационное поле 1

char telefon[7]; // информационное поле 2

element *prev; // адресное поле ≪предыдущий≫

element *next; // адресное поле ≪следующий≫

};

В статической памяти описываем переменную-указатель списка и несколько переменных-указателей, используемых при выполнении операций со списком:

element * first, // адрес первого элемента

*n,*f,*q; // вспомогательные указатели

Исходное состояние «список пуст»:

first=NULL;

Обработку списков рассмотрим на примере добавления нового элемента к списку.

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

В общем случае при добавлении элемента к списку возможны следующие варианты:

· список пуст, добавляемый элемент станет единственным элементом списка;

· элемент необходимо вставить перед первым элементом списка;

· элемент необходимо вставить перед заданным (не первым) элементом списка;

· элемент необходимо дописать в конец списка.

Добавление элемента к пустому списку состоит из записи адреса элемента в указатель списка, причем в поле «адрес следующего» добавляемого элемента необходимо поместить NULL:

first=new element; // запросили память под элемент

first->num=5; // занесли данные в информационное поле

first->p=NULL; // записали признак конца списка NULL

На рис. 14 показана последовательность операций при добавлении элемента к пустому списку.

Рисунок 14 – Последовательность операций при добавлении элемента к пустому списку: исходное состояние (а), запрос памяти под элемент (б), заполнение элемента (в), занесение nil в поле адреса следующего элемента (г)

Добавление элемента перед первым элементом списка. При выполнении этой операции необходимо в поле «адрес следующего» переписать адрес первого элемента списка, а в указатель списка занести адрес добавляемого элемента (рис. 15):

q=new element; // запросили память под элемент

q->num=4; // занесли данные в информационное поле

q->p=first; // записали в новый элемент адрес первого

first=q; // записали в качестве первого адрес нового элемента

Рисунок 15 – Последовательность операций при добавлении элемента перед первым: исходное состояние (а), запрос памяти под элемент (б), заполнение элемента (в), шаги включения элемента в список (г, д)

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

q=new element; // запросили память под элемент

q->num=4; // занесли данные в информационное поле

q->p=n; // в поле «адрес следующего» нового элемента переписываем адрес следующего элемента

first->p=q; // в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента записали признак конца списка NULL

Рисунок 16 – Добавление элемента перед заданным (не первым): исходное состояние (а), запрос памяти под элемент (б), заполнение элемента (в), шаги включение элемента в список (г, д)

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

q=new element; // запросили память под элемент

q->num=4; // занесли данные в информационное поле

q->p=NULL; // записали признак конца списка NULL

first->p=q; // записали признак конца списка NULL

Рисунок 17 – Добавление элемента в конец списка: исходное состояние (а), запрос памяти под элемент (б), заполнение элемента (в), включение элемента в список (г, д)

Более подробно особенности выполнения операций со списками рассмотрены в [1].

Порядок выполнения работы

1. Прочитать и проанализировать задание в соответствии со своим вариантом.

2. Разработать схему алгоритма решения задачи.

3. Написать программу.

4. Вызвать среду программирования Turbo Delphi, создать новый проект консольного приложения и ввести текст программы в среду программирования.

5. Подобрать тестовые данные (не менее 3-х вариантов).

6. Отладить программу на выбранных тестовых данных.

7. Продемонстрировать работу программы преподавателю.

8. Составить отчет по лабораторной работе.

9. Защитить лабораторную работу преподавателю.

Требования к отчету

Отчет должен быть выполнен на бумаге формата А4 или А5 в том числе в тетрадях или на тетрадных листах. Если отчет выполняется на отдельных тетрадных листах, то они должны быть аккуратно обрезаны по линии подшивки и скреплены. Неаккуратно выполненные, оборванные или грязные отчеты не принимаются.

Все записи в отчете должны быть либо напечатаны на принтере, либо разборчиво выполнены от руки синей или черной ручкой (карандаш – не допускается). Схемы также должны быть напечатаны при помощи компьютера или нарисованы с использованием чертежных инструментов в том числе карандаша.

Каждый отчет должен иметь титульный лист, на котором указывается:

а) наименование факультета и кафедры;

б) название дисциплины;

в) номер и тема лабораторной работы;

г) фамилия преподавателя, ведущего занятия;

д) фамилия, имя и номер группы студента;

е) номер варианта задания.

Кроме того отчет по лабораторной работе должен содержать:

1) схему алгоритма, выполненную вручную или в соответствующем пакете;

2) текст программы;

3) результаты тестирования, которые должны быть оформлены в виде таблицы вида:

Исходные данные	Ожидаемый результат	Полученный результат

4) выводы.

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

1. Что такое «список» в программировании? В каких случаях используется эта конструкция?

2. Какие типы списковых структур вы знаете?

3. Что такое указатели и как опи объявляются?

4. Как описывается элемент списка?

5. Какие варианты возможны для добавления элемента к списку?

6. Как отлаживают программы, содержащие обработку списков?