44. Структура данных динамический вектор. Операции над структурой данных динамический вектор.

Динамическая матрица – структура, у которой:

~ индекс строки от одного до числа элементов. Число элементов меняется динамически.

Операции: добавление\удаление элемента.

45. Структура данных динамическая матрица. Операции над структурой данных динамическая матрица.

Динамическая матрица – структура, у которой:

~ индекс строки от одного до числа строк матрицы

~ индекс столбцов от одного до числа столбцов матрицы

~ число строк меняется динамически

~ число столбцов меняется динамически

Операции: добавление\удаление строки\столбца.

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

47. Структура данных двусвязный список. Кольцевой двусвязный список.В тех случаях, когда при работе со списками их приходиться просматривать в двух направлениях, структура односвязного списка становится непригодной, а при использовании кольцевого односвязного списка требуется слишком много времени для поиска … в списке. Каждый элемент двусвязного списка содержит два указателя.Линейность двусвязного списка вытекает из того, что каждый из 2-х указателей в любом элементе списка (кроме крайних, в которых один из указателей пуст) задает линейный порядок элементов, обратный по отношению к порядку, устанавливаемому другим указателем.

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

48. Операция включения элемента в односвязный список.Считаем, что включаемый элемент уже взят из списка свободных мест и сформирован соответствующим образом, т.е. 1)Нам известен адрес его хранения, заданный указателем на новый элемент.2)Формат полей включаемого элемента соответствует формату полей нашего списка.Операция включения в список за работающим указателем выполняется следующим образом:Шаг 1: в указательное поле включаемого элемента заносится содержимое указанного поля элемента, на который указывает рабочий указатель. Этим устанавливается связь включаемого элемента со следующим за ним элементом списка.Шаг 2: в указательное поле элемента, на который указывает рабочий указатель заносится значение указателя нового элемента *(т.е. его адрес). В результате этого устанавливается связь нового элемента с предыдущим в списке элементов. Шаги следует выполнять именно в таком порядке, иначе если сначала выполнять шаг 2, то потеряется связь включаемого элемента со следующим за ним в списке элементом.

49.Операция исключения элемента из односвязного списка.Предположим, что исключению подлежит элемент, следующий за элементом, на который указывает рабочий указатель.Предположим также, что элемент, подлежащий исключению, действительно есть в списке, т.е. рабочий указатель указывает не на последний элемент списка.После исключения элемента, память, отводимая под него, должна быть возвращена в список свободных областей памяти. Для этого нужно заполнить адрес этой памяти специальным указателем указателя исключенного элемента.Операция исключения элемента за рабочим указателем выполняется следующим образом:Шаг 1: вспомогательному указателю указателя исключенного элемента присваивается содержимое указанного поля, адресуемого рабочему указателю, тем самым мы запоминаем адрес памяти, которую нужно освободить.Шаг 2: в указательное поле элемента, адресуемого в рабочий указатель, присваивается содержимое указанного поля исключаемого элемента. Этим мы исключаем элемент из списка.Шаг 3: помещаем отрезок памяти адресом указанного исключенного элемента в список свободных областей памяти.

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

Считаем, что нам дан список, каждый элемент которого состоит из 3 полей.Поле 1 – указательное поле для хранения адреса следующего элемента списка.Поле 2 – поле данных.Поле 3 – указательное поле для хранения адреса предыдущего элемента списка.Шаг 1: необходимо захватить память под включаемый элемент. Структура захваченной памяти должна соответствовать структуре элемента списка. Шаг 2: присвоить полю 1 включаемого элемента значение поля 1 элемента перед текущим указателем.Шаг 3: присвоить полю 1 элемента до текущего указателя значение указателя включаемого элемента.Шаги 2 и 3 добавляют включаемый элемент в список в прямом направлении. Шаг 4: присвоить полю 3 включаемого элемента значение поля 3 элемента, на который указывает рабочий указатель. Шаг 5: присвоить полю 3 элемента, на который указывает рабочий указатель, значение указанного включаемого элемента.Шаг 4 и 5 добавляют включаемый элемент в список в обратном направлении.Следует обратить внимание на добавление первого и последнего элемента списка, т.к :1)при добавлении 1-го элемента необходимо изменить значение указателя начала списка.2)При добавлении последнего элемента необходимо изменить значение указателя конца списка.

51. Операция исключения элемента из двусвязного списка.Рассмотрим, как выполняется операция исключения элемента в двусвязный список до рабочего указателя.Имеется список с форматом полей поле 1, поле 2, поле 3.Шаг 1: запоминаем адрес исключаемого элемента в указатель исключенного элемента.Шаг 2: удаляем исключаемый элемент в прямом направлении. Для этого в поле 1 элемента, расположенного перед удаляемым, помещается содержимое поля 1 исключаемого элемента.Шаг 3: удаляем исключаемый элемент из списка в обратном направлении. Для этого в поле 3 адресуемого рабочего указателя помещается содержимое поля 3 исключаемого элемента. Шаг 4: помещаем отрезок памяти, адресуемый указателю исключенного элемента, в список свободных мест. Следует обратить внимание на удаление первого и последнего элемента, т.к.:1)при удалении 1-го элемента необходимо изменить значение указателя начала списка.2)при удалении последнего элемента необходимо изменить значение указателя начала списка.

52. Нелинейные связные структуры. Включение и исключение элементов.Односвязный список всегда линейный, двусвязный может быть и нелинейным, если 2-й указатель каждого элемента задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому в 1-ом указателе. Каждый элемент такого списка содержится одновременно в двух разных односвязных списках. Каждый из этих списков имеет свой указатель начала. В общем случае каждый элемент связного списка может содержать произвольное конечное количество элементов отношений, одинаковое или разное в различных элементах. В результате такого обобщения получается многосвязный список, каждый элемент которого одновременно входит во столько разных односвязных списков, сколько имеется связок в соответствующем элементе, при этом необязательно, чтобы каждый элемент непременно всходил во все односвязные списки. Такой многосвязный список как бы прошит в разных направлениях многими связками, поэтому многосвязные списки иногда называют прошитыми списками или плексами.

53. Многосвязные списки. Включение и исключение элементов.Используются для представления сложных структур данных. И выполнение операций в многосвязных списках достаточно сложный процесс, т.к. каждый элемент входит в несколько односвязных списков. И выполнение операции над элементом списка многосвязного списка приводит к изменению всех односвязных элементов, в которых он содержится. И алгоритмы выполнения таких списков самые сложные.

54. Кольцевые списки.Часто используются в алгоритмах, в которых не так важно какой из элементов является первым или последним.Преимущество этих структур состоит в том, что указатель начала списка может быть установлен на любой элемент списка. При этом список не нарушается. Алгоритмы обработки кольцевых списков аналогичны алгоритмам обработки простых линейных списков, отличающиеся лишь обнаружением последнего элемента списка, т.к. ни одно указательное поле не равно 0. Также некоторые трудности могут возникнуть, когда список пуст.

55. Понятие списка свободных мест.В реальности ОП поддерживает в рабочем состоянии хотя бы один список, который называют списком свободных мест памяти и для того, чтобы различать списки, в которых хранится информация для программ, их называют функциональными списками. Каждый элемент свободного списка имеет такой же формат полей, как и элемент функционального списка. При этом содержимое поля свободного списка не определено.Одновременно в системе может существовать несколько функциональных списков. Если элементы всех функциональных списков имеют одну и ту же структуру и размер, то на всю группу этих списков достаточно иметь один свободный список, в противном случае создается и поддерживается столько свободных списков, сколько имеется свободных структур элементов функциональных списков. В начале работы программы все незанятые области памяти помещаются в список свободных областей. Когда возникает необходимость добавить новый элемент в некоторый функциональный список, из списка свободных областей извлекается один из элементов и используется для размещения нового элемента функционального списка. При исключении того или иного элемента из функционального списка, та часть памяти, в которой он хранился, теряется. Если не принять специальных мер для ее повторного использования. Это означает, что освобожденный отрезок памяти ОП система должна поместить в список свободных мест памяти. Это может происходить с помощью одного из способов:1. При исключении элемента из некоторого функционального списка освободившаяся область сразу помещается во все списки свободных областей. 2. Способ, носящий название «сбор мусора». При этом способе всякий раз когда список свободных областей становится пустым, проводится проверка всех функциональных списков. Любой элемент, который не входит ни в один функциональный список, считается ненужным и соответствующая область памяти отмечается.Функции захвата памяти работают со списком свободных мест. Когда он становится пусты, они возвращают нулевой указатель.

56. Реализация ЛСД в структуры хранения. Непрерывная реализация ЛСД на базе вектора.При непрерывной реализации элементы ЛСД размещаются в векторе друг за другом непрерывным отрезком. А порядок элементов в структуре, если он есть, определяется порядком их следования в векторе.Рассмотрим на примерах:1)Непрерывная реализация стека на базе вектора. В этом случае совмещаем дно стека с 1-м элементом вектора. В качестве элемента стека выступает один элемент вектора. Может иметь столько элементов в стеке, сколько имеет вектор. Выполнение операций над стеком сводится к выполнению операций над элементами вектора.2) Непрерывная реализация односвязного списка на базе вектора.Связи между элементами становятся невырожденными и определяются неявно порядком следования элементов. Трудно выполнять операции «удалить(добавить) элемент», приводит к массовому сдвигу структуры. Это неудобно и связано с тем, что при непрерывной реализации на базе вектора, сам вектор выполняет 2 функции: он хранит значения элементов структур и хранит связи элементов. Такая реализация подходит для ЛСД, которой не важен порядок элементов (например множество) или порядок элементов не меняется (стек, дек, очередь). Для структур, в которых элемент связан с другими явным образом, такая реализация подходит плохо. Для устранения массовых операций сдвига используется второй способ реализации на базе вектора, а именно ссылочная реализация.

57. Реализация ЛСД в структуры хранения. Ссылочная реализация ЛСД на базе вектора.Основная идея этого метода – отдельное хранение полей данных и полей отношений ЛСД. Для этого требуется 2 вектора:1й - вектор значения элементов;2й – вектор ссылок или связей элементов.В векторе значений хранятся значения элементов. В векторе ссылок хранятся: 1) место положений1-й элемент вектора ссылок хранит значение 1-го элемента структуры данных в векторе значений. 2) связь элемента со следующимДля этого считается, что значение элемента вектора ссылок с индексом равным индексу элемента ЛСД векторе значений является индекс индекс следующего элемента ЛСД в векторе значений. 3) информация о том, какие элементы вектора значений свободны, т.е. список свободных мест в векторе значений. Начало это списка хранится во 2-ом элементе вектора ссылок => Первые два не используются, а заняты. Содержание: