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

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

Лабораторная работа № 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 [ ]. Размерность массива при всем этом не указывается. Если Выделение участка динамической памяти квад­ратных скобок нет, то никакого сообщения об ошибке не выдается, но помечен как свободный будет только 1-ый элемент массива, а другие окажутся не­доступны для последующих операций. Такие ячейки памяти именуются мусором.

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

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

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

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

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

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

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

· вставка элемента в данное место перечня Выделение участка динамической памяти (до либо после элемента с данным
ключом);

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

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

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

struct Node {

int d;

Node *next;

Node *prev;

};

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

#include

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; // Перечень завершается, чуть начавшись

// Добавление в, конец перечня 4 частей 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 = 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 - Вставка элемента в перечень

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

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

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

pv->d = d;

Node * pt = *pbeg;

while (pt) { // просмотр перечня

if (d 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) Предметный указатель организован как линейный перечень.

Любая компонента указателя содержит слово и номера страничек, на которых это слово встречается. Количество номеров страничек, относящихся к одному слову, от 1-го до 10.

Составить программку, которая обеспечивает Выделение участка динамической памяти:

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

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

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

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

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

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

· этаж;

· площадь;

· адресок.

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

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

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

· вывод всего перечня.

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

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

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

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

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

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

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

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

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

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

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

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

Любая заявка содержит:

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

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

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

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

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

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

· добавление заявок в перечень;

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

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

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

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

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

· номер УДК;

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

· заглавие;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· название файла;

· дата сотворения;

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

Составить программку, которая обеспечивает Выделение участка динамической памяти:

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

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

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

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

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

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

Любая компонента указателя содержит слово и номера страничек, на которых это слово встречается Выделение участка динамической памяти. Количество номеров страничек, относящихся к одному слову, от 1-го до 10.

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

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

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

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

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

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

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

· этаж;

· площадь;

· адресок.

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

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

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

· вывод всего перечня.


vidi-dejstvij-v-soobsheniyah.html
vidi-dekorativnogo-tvorchestva.html
vidi-deneg-dejstvitelnie-i-znaki-stoimosti.html