Выделение участка динамической памяти

Лабораторная работа № 16

Обработка списков

 

 

Цель работы

1.1 Получение навыков программирования с использованием структуры данных - список.

1.2 Получение навыков размещения данных в динамической памяти.

 

Техническое обеспечение

2.1 Персональная ЭВМ IBM PC/286 и более поздних моделей.

2.2 Клавиатура.

2.3 Дисплей.

2.4 Печатающее устройство.

Программное обеспечение

3.1 Операционная система MS DOS версия 5.0 и более поздние версии.

3.2 Система программирования Borland C++ версия 3.1 и более поздние версии.

Постановка задачи

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

 

Содержание отчета

5.1. Тема и цель работы.

5.2. Текст программы.

5.3. Результаты выполнения программы.

 

Общие сведения

Любая программа предназначена для обработки данных, от способа организации которых зависят алгоритмы работы, поэтому выбор структур данных должен предшествовать созданию алгоритмов. Выше были рассмотрены стандартные способы организации данных, предоставляемые языком C++, — основные и со­ставные типы. Наиболее часто в программах используются массивы, структуры и их сочетания, например, массивы структур, полями которых являются массивы и структуры.

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

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

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

Элемент любой динамической структуры данных представляет собой структуру (в смысле struct, содержащую по крайней мере два поля: для хранения данных и для указателя. Полей данных и указателей может быть несколько. Поля дан­ных могут быть любого типа: основного, составного или типа указатель. Описа­ние простейшего элемента (компоненты, узла) выглядит следующим образом:

struct Node{

Data d; // тип данных Data должен быть определен ранее

Node *p;

};

 

Выделение участка динамической памяти

С помощью операции new:

int* p = new int; II 1

int* m = new int (10); // 2

int* q = new int [10]; // 3

C помощью функции malloc():

int* u = (int *)malloc(sizeof(1nt)); // 4

В.операторе 1 операция new выполняет выделение достаточного для размещения величины типа int участка динамической памяти и записывает адрес начала это­го участка в переменную p. Память под саму переменную p (размера, достаточно­го для размещения указателя) выделяется на этапе компиляции.

В операторе 2, кроме описанных выше действий, производится инициализация выделенной динамической памяти значением 10.

В операторе 3 операция new выполняет выделение памяти под 10 величин типа int (массива из 10 элементов) и записывает адрес начала этого участка в пере­менную q. которая может трактоваться как имя массива. Через имя можно обра­щаться к любому элементу массива.

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

В операторе 4 делается то же самое, что и в операторе 1, но с помощью функции выделения памяти mallос(), унаследованной из библиотеки С. В функцию переда­ется один параметр — количество выделяемой памяти в байтах. Конструкция (int*) используется для приведения типа указателя, возвращаемого функцией, к требуемому типу. Если память выде­лить не удалось, функция возвращает нулевой указатель NULL.

Операцию new использовать предпочтительнее, чем функцию malloc() особенно при работе с объектами.

Освобождение памяти, выделенной с помощью операции new, должно выпол­няться с помощью delete, а памяти, выделенной функцией mallос() - посредством функции free(). При этом переменная-указатель сохраняется и может инициали­зироваться повторно. Приведенные выше динамические переменные уничтожа­ются следующим образом:

delete p; delete m; delete [ ] q; free (u);,

Если память выделялась с помощью new[ ], для освобождения памяти необходимо применять delete [ ]. Размерность массива при этом не указывается. Если квад­ратных скобок нет, то никакого сообщения об ошибке не выдается, но помечен как свободный будет только первый элемент массива, а остальные окажутся не­доступны для дальнейших операций. Такие ячейки памяти называются мусором.

 

Линейные списки

Самый простой способ связать множество элементов — сделать так, чтобы каж­дый элемент содержал ссылку на следующий. Такой список называется однона­правленным (односвязным). Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.

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

Над списками можно выполнять следующие операции:

· начальное формирование списка (создание первого элемента);

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

· чтение элемента с заданным ключом;

· вставка элемента в заданное место списка (до или после элемента с заданным
ключом);

· удаление элемента с заданным ключом;

· упорядочивание списка по ключу.

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

struct Node {

int d;

Node *next;

Node *prev;

};

Ниже приведена программа, которая формирует список из 5 чисел, добавляет число в список, удаляет число из списка и выводит список на экран. Указатель на начало списка обозначен pbeg, на конец списка - pend, вспомогательные указатели - pv и pkey.

#include <iostream.h>

struct Node {

int d;

Node *next;

Node *prev;

};

//-------------------------------------------------------------------

Node * first (int d);

void add(Node **pend, int d);

Node * find(Node * const pbeg, int i);

bool remove(Node **pbeg, Node **pend, int key);

Node * insert(Node * const pbeg, Node **pend, int key, int d);

//-------------------------------------------------------------------

 

int main()

{

Node *pbeg = first (1); // Формирование первого элемента списка

Node *pend = pbeg; // Список заканчивается, едва начавшись

// Добавление в, конец списка четырех элементов 2, 3, 4, и 5:

for (int i = 2; i<6; i++) add(&pend, i);

// Вставка элемента 200 после элемента 2:

insert(pbeg, &pend, 2, 200);

// Удаление элемента 5:

if(!remove (&pbeg. Spend. 5)) cout << "не найден";

Node *pv = pbeg;

while (pv) { // вывод списка на экран

cout << pv->d << ' ';

pv = pv->next;

}

return 0;

}

//--------------------------------------------------------------------------

// Формирование первого элемента

Node * first (int d) {

Node *pv = new Node;

pv->d = d; pv->next = 0; pv->prev = 0;

return pv;

}

//--------------------------------------------------------------------------

// Добавление в конец списка

void add (Node **pend, int d) {

Node *pv = new Node;

pv->d = d; pv->next = 0; pv->prev = *pend;

(*pend)->next - pv;

*pend = pv;

}

//--------------------------------------------------------------------------

// Поиск элемента по ключу

Node * find (Node * const pbeg. int d){

Node *pv - pbeg;

while (pv) {

if(pv->d == d) break;

pv = pv->next;

}

return pv;

}

//-------------------------------------------------------------------------

// Удаление элемента

bool remove (Node **pbeg. Node **pend, int key) {

if(Node *pkey = find(*pbeg, key)) { // 1

if (pkey == *pbeg) { // 2

*pbeg ■ (*pbeg)->next;

(*pbeg)->prev = 0; }

else if (pkey == *pend) { // 3

*pend = (*pend)->prev:

(*pend)->next = 0; }

else{ // 4

(pkey->prev)->next - pkey->next;

(pkey->next)->prev - pkey->prev; }

delete pkey:

return true; //5

}

return false; // 6

}

//------------------------------------------------------------------------

// Вставка элемента

Node * insert(Node * const pbeg, Node **pend, int key, int d) {

if(Node *pkey = find(pbeg, key)) {

Node *pv = new Node;

pv->d = d;

// 1 - установление связи нового узла с последующим:

pv->next = pkey->next;

// 2 - установление связи нового узла с предыдущим:

pv->prev = pkey;

//3- установление связи предыдущего узла с новым:

pkey->next = pv;

// 4 - установление связи последующего узла с новым:

if(pkey!= *pend) (pv->next)->prev - pv;

// Обновление указателя на конец списка,

// если узел вставляется в конец:

else *pend = pv:

return pv;

}

return 0;

}

Результат работы программы:

1 2 200 3 4

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

Рассмотрим подробнее функцию удаления элемента из списка remove. Ее парамет­рами являются указатели на начало и конец списка и ключ элемента, подлежаще­го удалению. В строке 1 выделяется память под локальный указатель pkey, ко­торому присваивается результат выполнения функции нахождения элемента по ключу find. Эта функция возвращает указатель на элемент в случае успешного поиска и 0, если элемента с таким ключом в списке нет. Если pkey получает нену­левое значение, условие в операторе if становится истинным (элемент существу­ет), и управление передается оператору 2, если нет — выполняется возврат из функции со значением false (оператор 6).

Удаление из списка происходит по-разному в зависимости от того, находится элемент в начале списка, в середине или в конце. В операторе 2 проверяется, на­ходится ли удаляемый элемент в начале списка — в этом случае следует скоррек­тировать указатель pbeg на начало списка так, чтобы он указывал на следующий элемент в списке, адрес которого находится в поле next первого элемента. Новый начальный элемент списка должен иметь в своем поле указателя на предыдущий элемент значение 0.

Если удаляемый элемент находится в конце списка (оператор 3), требуется сме­стить указатель pend конца списка на предыдущий элемент, адрес которого мож­но получить из поля prev последнего элемента. Кроме того, нужно обнулить для нового последнего элемента указатель на следующий элемент. Если удаление происходит из середины списка, то единственное, что надо сделать, — обеспечить двустороннюю связь предыдущего и последующего элементов. После корректи­ровки указателей память из-под элемента освобождается, и функция возвращает значение true.

Работа функции вставки элемента в список проиллюстрирована на рисунке 1. Но­мера около стрелок соответствуют номерам операторов в комментариях.

Сортировка связанного списка заключается в изменении связей между элемента­ми. Алгоритм состоит в том, что исходный список просматривается, и каждый эле­мент вставляется в новый список на место, определяемое значением его ключа.

Рисунок 1 - Вставка элемента в список

 

Ниже приведена функция формирования упорядоченного списка (предполагается, что первый элемент существует):

void add_sort (Node **pbeg, Node **pend, int d) {

Node *pv = new Node; // добавляемый элемент

pv->d = d;

Node * pt = *pbeg;

while (pt) { // просмотр списка

if (d < pt->d) { // занести перед текущим элементом (pt)

pv->next = pt;

if (pt == *pbeg) { // в начало списка

pv->prev = 0;

*pbeg – pv; }

else { // в середину списка

(pt->prev)->next = pv;

pv->prev = pt->prev; }

pt->prev = pv;

return;

}

pt = pt->next;

}

pv->next = 0; //в конец списка

pv->prev = *pend;

(*pend)->next - pv;

*pend = pv;

}

 

 

Варианты заданий

1) Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке

Сведения о каждом автобусе содержат:

· номер автобуса;

· фамилию и инициалы водителя

· номер маршрута.

Программа должна обеспечивать:

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

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

· при въезде каждого автобуса в парк вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся на мар­шруте, и записывает эти данные в список автобусов, находящихся в парке;

· по запросу выдаются сведения об автобусах, находящихся, в парке, или об автобусах, находящихся на маршруте.

 

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

Каждая заявка содержит:

· пункт назначения;

· номер рейса;

· фамилию и инициалы пассажира;

· желаемую дату вылета.

Программа должна обеспечивать:

· хранение всех заявок в виде списка;

· добавление заявок в список;

· удаление заявок;

· вывод заявок по заданному номеру рейса и дате вылета;

· вывод всех заявок.

 

3) Составить программу, которая содержит текущую информацию о книгах в биб­лиотеке.

Сведения о книгах содержат:

· номер УДК;

· фамилию и инициалы автора;

· название;

· год издания;

· количество экземпляров данной книги в библиотеке.

Программа должна обеспечивать:

начальное формирование данных о всех книгах в библиотеке в виде списка;

· при взятии каждой книги вводится номер УДК, и программа уменьшает значение количества книг на единицу или выдает сообщение о том, что требуемой книги в библиотеке нет, или требуемая книга находится на руках;

· при возвращении каждой книги вводится номер УДК, и программа увеличи­вает значение количества книг на единицу;

· по запросу выдаются сведения о наличии книг в библиотеке.

 

4) Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке.

Сведения о каждом автобусе содержат:

· номер автобуса;

· фамилию и инициалы водителя;

· номер маршрута;

· признак того, где находится автобус — на маршруте или в парке.

Программа должна обеспечивать:

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

· при выезде каждого автобуса из парка вводится номер автобуса, и программа
устанавливает значение признака «автобус на маршруте»;

· при въезде каждого автобуса в парк вводится номер автобуса, и программа
устанавливает значение признака «автобус в парке»;

· по запросу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.

 

5) В файловой системе каталог файлов организован как линейный список. Для каждого файла в каталоге содержатся следующие сведения:

· имя файла;

· дата создания;

· количество обращений к файлу.

Составить программу, которая обеспечивает:

· начальное формирование каталога файлов;

· вывод каталога файлов;

· удаление файлов, дата создания которых меньше заданной;

выборку файла с наибольшим количеством обращений.

Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

 

6) Предметный указатель организован как линейный список.

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

Составить программу, которая обеспечивает:

· начальное формирование предметного указателя;

· вывод предметного указателя;

· вывод номеров страниц для заданного слова.

Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

 

7) Картотека в бюро обмена квартир организована как линейный список. Сведения о каждой квартире содержат:

· количество комнат;

· этаж;

· площадь;

· адрес.

Составить программу, которая обеспечивает: Q начальное формирование картотеки;

· ввод заявки на обмен;

· поиск в картотеке подходящего варианта: при равенстве количества комнат
и этажа и различии площадей в пределах 10% выводится соответствующая
карточка и удаляется из списка, в противном случае поступившая заявка
включается в список;

· вывод всего списка.

Программа должна обеспечивать диалог с помощью меню и контроль ошибок
при вводе., -

 

8) Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке

Сведения о каждом автобусе содержат:

· номер автобуса;

· фамилию и инициалы водителя

· номер маршрута.

Программа должна обеспечивать:

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

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

· при въезде каждого автобуса в парк вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся на маршруте, и записывает эти данные в список автобусов, находящихся в парке;

· по запросу выдаются сведения об автобусах, находящихся, в парке, или об автобусах, находящихся на маршруте.

 

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

Каждая заявка содержит:

· пункт назначения;

· номер рейса;

· фамилию и инициалы пассажира;

· желаемую дату вылета.

Программа должна обеспечивать:

· хранение всех заявок в виде списка;

· добавление заявок в список;

· удаление заявок;

· вывод заявок по заданному номеру рейса и дате вылета;

· вывод всех заявок.

 

10) Составить программу, которая содержит текущую информацию о книгах в биб­лиотеке.

Сведения о книгах содержат:

· номер УДК;

· фамилию и инициалы автора;

· название;

· год издания;

· количество экземпляров данной книги в библиотеке.

Программа должна обеспечивать:

начальное формирование данных о всех книгах в библиотеке в виде списка;

· при взятии каждой книги вводится номер УДК, и программа уменьшает значение количества книг на единицу или выдает сообщение о том, что требуемой книги в библиотеке нет, или требуемая книга находится на руках;

· при возвращении каждой книги вводится номер УДК, и программа увеличи­вает значение количества книг на единицу;

· по запросу выдаются сведения о наличии книг в библиотеке.

 

11) Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке.

Сведения о каждом автобусе содержат:

· номер автобуса;

· фамилию и инициалы водителя;

· номер маршрута;

· признак того, где находится автобус — на маршруте или в парке.

Программа должна обеспечивать:

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

· при выезде каждого автобуса из парка вводится номер автобуса, и программа
устанавливает значение признака «автобус на маршруте»;

· при въезде каждого автобуса в парк вводится номер автобуса, и программа
устанавливает значение признака «автобус в парке»;

· по запросу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.

 

12) В файловой системе каталог файлов организован как линейный список. Для каждого файла в каталоге содержатся следующие сведения:

· имя файла;

· дата создания;

· количество обращений к файлу.

Составить программу, которая обеспечивает:

· начальное формирование каталога файлов;

· вывод каталога файлов;

· удаление файлов, дата создания которых меньше заданной;

выборку файла с наибольшим количеством обращений.

Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

 

13) Предметный указатель организован как линейный список.

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

Составить программу, которая обеспечивает:

· начальное формирование предметного указателя;

· вывод предметного указателя;

· вывод номеров страниц для заданного слова.

Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

 

14) Картотека в бюро обмена квартир организована как линейный список. Сведения о каждой квартире содержат:

· количество комнат;

· этаж;

· площадь;

· адрес.

Составить программу, которая обеспечивает: Q начальное формирование картотеки;

· ввод заявки на обмен;

· поиск в картотеке подходящего варианта: при равенстве количества комнат
и этажа и различии площадей в пределах 10% выводится соответствующая
карточка и удаляется из списка, в противном случае поступившая заявка
включается в список;

· вывод всего списка.