Структуры данных презентация

Содержание

Слайд 2

Структуры данных

Структуры данных

Составитель курса лекций:
Спиричева Наталия Рахматулловна,
ст. преподаватель каф. Информационных технологий

Структуры данных Структуры данных Составитель курса лекций: Спиричева Наталия Рахматулловна, ст. преподаватель каф. Информационных технологий

Слайд 3

Структуры данных

Структуры данных

Динамические структуры данных

Структуры данных Структуры данных Динамические структуры данных

Слайд 4

Структуры данных

Структуры данных и алгоритмы

Основные темы лекции:
Связное представление данных в памяти
Стек
Очередь
Дек
Многосвязные списки

Структуры данных Структуры данных и алгоритмы Основные темы лекции: Связное представление данных в

Слайд 5

Структуры данных

Структуры данных

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

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

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

Слайд 6

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 1:
Связное представление данных в памяти

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 1: Связное представление данных в памяти

Слайд 7

Структуры данных

Связное представление данных в памяти

Динамические структуры, по определению, характеризуются отсутствием физической

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

Структуры данных Связное представление данных в памяти Динамические структуры, по определению, характеризуются отсутствием

Слайд 8

Структуры данных

Связное представление данных в памяти

Поскольку элементы динамической структуры располагаются по непредсказуемым

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

Структуры данных Связное представление данных в памяти Поскольку элементы динамической структуры располагаются по

Слайд 9

Структуры данных

Связное представление данных в памяти

Элемент динамической структуры состоит из двух полей:


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

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

Слайд 10

Структуры данных

Связное представление данных в памяти

В простейшем случае элемент имеет вид:
В

данном случае информационная часть состоит из одного поля, которое используется для хранения одного целого числа, указатель - из указателя на один элемент.

Структуры данных Связное представление данных в памяти В простейшем случае элемент имеет вид:

Слайд 11

Структуры данных

Связное представление данных в памяти

Достоинства связного представления данных - в возможности

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

Структуры данных Связное представление данных в памяти Достоинства связного представления данных - в

Слайд 12

Структуры данных

Связное представление данных в памяти

Вместе с тем связное представление не лишено

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

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

Слайд 13

Структуры данных

Списком называется линейно – упорядоченная последовательность элементов данных Е.(1), Е(2), ..., Е(п),

n > О, причем каждый элемент характеризуется одним и тем же набором попей.

Структуры данных Списком называется линейно – упорядоченная последовательность элементов данных Е.(1), Е(2), ...,

Слайд 14

Структуры данных

Операции, которые имеем право выполнять с линейными списками

Структуры данных Операции, которые имеем право выполнять с линейными списками

Слайд 15

Структуры данных

Стек – линейный список, в котором все включения и исключения (и обычно

всякий доступ) делаются в одном конце списка.
Очередь – линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце.
Дек (очередь с двумя концами) – линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка.

Структуры данных Стек – линейный список, в котором все включения и исключения (и

Слайд 16

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 2:
Стеки

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 2: Стеки

Слайд 17

Структуры данных

Стеки
Стек - такой последовательный список с переменной длиной, включение и исключение элементов

из которого выполняются только с одной стороны списка, называемого вершиной стека.
LIFO (Last In - First Out - "последним пришел - первым исключился").

Структуры данных Стеки Стек - такой последовательный список с переменной длиной, включение и

Слайд 18

Структуры данных

Стеки

Структуры данных Стеки

Слайд 19

Структуры данных

Стеки
Основные операции над стеком:
включение нового элемента
исключение элемента из стека
Вспомогательные операции:
определение текущего

числа элементов в стеке;
очистка стека;
неразрушающее чтение элемента из вершины стека, которое может быть реализовано как комбинация основных операций:
x:=pop(stack); push(stack,x).

Структуры данных Стеки Основные операции над стеком: включение нового элемента исключение элемента из

Слайд 20

Структуры данных

Стеки

Состояния стека:
а) пустой;
б-г) после последовательного включения в него элементов 'A', 'B', 'C';
д,

е) после последовательного удаления из стека элементов 'C' и 'B';
ж) после включения в стек элемента 'D'.

Структуры данных Стеки Состояния стека: а) пустой; б-г) после последовательного включения в него

Слайд 21

Структуры данных

Машинное представление стека и реализация операций
При представлении стека в статической памяти для

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

Структуры данных Машинное представление стека и реализация операций При представлении стека в статической

Слайд 22

Структуры данных

Стеки

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

которое указывает указатель стека. После выборки слот, в котором размещался выбранный элемент, считается свободным.

Структуры данных Стеки Операция исключения элемента состоит в модификации указателя стека и выборке

Слайд 23

Структуры данных

Стеки

Операция очистки стека сводится к записи в указатель стека начального значения -

адреса начала выделенной области памяти.

Структуры данных Стеки Операция очистки стека сводится к записи в указатель стека начального

Слайд 24

Структуры данных

Стеки

Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса

начала области.

Структуры данных Стеки Определение размера стека сводится к вычислению разности указателей: указателя стека

Слайд 25

Структуры данных

Стеки

Стеки в вычислительных системах
Стек является чрезвычайно удобной структурой данных для многих задач

вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов функций.

Структуры данных Стеки Стеки в вычислительных системах Стек является чрезвычайно удобной структурой данных

Слайд 26

Структуры данных

Стеки

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

не использующий скобок. В привычной нам записи знак операции записывается между аргументами, например, сумма чисел 2 и 3 записывается как 2 + 3. Ян Лукашевич предложил две другие формы записи: префиксная форма, в которой знак операции записывается перед аргументами, и постфиксная форма, в которой знак операции записывается после аргументов. В префиксной форме сумма чисел 2 и 3 записывается как + 2 3, в постфиксной — как 2 3 +. В честь Яна Лукашевича эти формы записи называют прямой и обратной польской записью.

Структуры данных Стеки В 1920 г. польский математик Ян Лукашевич предложил способ записи

Слайд 27

Структуры данных

Стеки

В польской записи скобки не нужны. Например, выражение
(2+3)*(15-7)
записывается в прямой польской

записи как
* + 2 3 - 15 7,
в обратной польской записи — как
2 3 + 15 7 - *.
Если прямая польская запись не получила большого распространения, то обратная оказалась чрезвычайно полезной. Неформально преимущество обратной записи перед прямой польской записью или обычной записью можно объяснить тем, что гораздо удобнее выполнять некоторое действие, когда объекты, над которыми оно должно быть совершено, уже даны.

Структуры данных Стеки В польской записи скобки не нужны. Например, выражение (2+3)*(15-7) записывается

Слайд 28

Структуры данных

Стеки

Обратная польская запись формулы позволяет вычислять выражение любой сложности, используя стек как

запоминающее устройство для хранения промежуточных результатов. Такой стековый калькулятор был впервые выпущен фирмой Hewlett Packard. Обычные модели калькуляторов не позволяют вычислять сложные формулы без использования бумаги и ручки для записи промежуточных результатов. В некоторых моделях есть скобки с одним или двумя уровнями вложенности, но более сложные выражения вычислять невозможно. Также в обычных калькуляторах трудно понять, как результат и аргументы перемещаются в процессе ввода и вычисления между регистрами калькулятора. Калькулятор обычно имеет регистры X, Y и регистр памяти, промежуточные результаты каким-то образом перемещаются по регистрам, каким именно — запомнить невозможно.

Структуры данных Стеки Обратная польская запись формулы позволяет вычислять выражение любой сложности, используя

Слайд 29

Структуры данных

Стеки

Для вычисления выражения надо сначала преобразовать его в обратную польскую запись (при

некотором навыке это легко сделать в уме). В приведенном выше примере выражение (2+3)*(15-7) преобразуется к
2 3 + 15 7 - *
Затем обратная польская запись просматривается последовательно слева направо. Если мы видим число, то просто вводим его в калькулятор, т.е. добавляем его в стек. Если мы видим знак операции, то нажимаем соответствующую клавишу калькулятора, выполняя таким образом операцию с числами на вершине стека.

Структуры данных Стеки Для вычисления выражения надо сначала преобразовать его в обратную польскую

Слайд 30

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 3:
Очереди FIFO

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 3: Очереди FIFO

Слайд 31

Структуры данных

Очереди FIFO

Логическая структура очереди
Очередью FIFO (First In - First Out - "первым

пришел - первым исключается") называется такой последовательный список переменной длины, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди).
Очереди в магазинах являются типичным бытовым примером очереди FIFO.

Структуры данных Очереди FIFO Логическая структура очереди Очередью FIFO (First In - First

Слайд 32

Структуры данных

Очереди FIFO
Из динамических элементов формируется цепочка. Динамический элемент хранит адрес следующего динамического

элемента.
Очередь работает по тому же принципу, что и очередь в магазине: "первым пришел, первым ушел". Элементы добавляются в конец очереди, а берутся из начала. Для работы необходимо знать начало и конец очереди.
Указатель у последнего элемента в очереди хранит нулевое значение

Структуры данных Очереди FIFO Из динамических элементов формируется цепочка. Динамический элемент хранит адрес

Слайд 33

Структуры данных

Очереди FIFO

Основные операции над очередью - те же, что и над стеком:


включение
исключение
определение размера
очистка,
неразрушающее чтение.

Структуры данных Очереди FIFO Основные операции над очередью - те же, что и

Слайд 34

Структуры данных

Очереди FIFO

Машинное представление очереди FIFO и реализация операций
При представлении очереди вектором в

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

Структуры данных Очереди FIFO Машинное представление очереди FIFO и реализация операций При представлении

Слайд 35

Структуры данных

Очереди FIFO

Возможны, конечно, и другие варианты организации очередей: например, всякий раз, когда

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

Структуры данных Очереди FIFO Возможны, конечно, и другие варианты организации очередей: например, всякий

Слайд 36

Структуры данных

Очереди FIFO

Очереди с приоритетами
В реальных задачах иногда возникает необходимость в формировании очередей,

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

Структуры данных Очереди FIFO Очереди с приоритетами В реальных задачах иногда возникает необходимость

Слайд 37

Структуры данных

Очереди FIFO

Очереди с приоритетами могут быть реализованы на линейных списковых структурах -

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

Структуры данных Очереди FIFO Очереди с приоритетами могут быть реализованы на линейных списковых

Слайд 38

Структуры данных

Очереди FIFO

Очереди в вычислительных системах
Идеальным примером кольцевой очереди в вычислительной системы является

буфер клавиатуры в Базовой системе ввода-вывода ПЭВМ IBM PC. Буфер клавиатуры занимает последовательность байтов памяти по адресам от 40:1E до 40:2D включительно. По адресам 40:1A и 40:1C располагаются указатели на начало и конец очереди соответственно. При нажатии на любую клавишу генерируется прерывание 9. Обработчик этого прерывания читает код нажатой клавиши и помещает его в буфер клавиатуры - в конец очереди. Коды нажатых клавиш могут накапливаться в буфере клавиатуры, прежде чем они будут прочитаны программой. Программа при вводе данных с клавиатуры обращается к прерыванию 16H. Обработчик этого прерывания выбирает код клавиши из буфера - из начала очереди - и передает в программу.

Структуры данных Очереди FIFO Очереди в вычислительных системах Идеальным примером кольцевой очереди в

Слайд 39

Структуры данных

Очереди FIFO

Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows

NT, Unix, OS/2, ЕС и др.). Ресурсы вычислительной системы (процессор, оперативная память, внешние устройства и т.п.) используются всеми задачами, которые одновременно выполняются в среде такой операционной системы. Поскольку многие виды ресурсов реально не допускают одновременного их использования разными задачами, такие ресурсы предоставляются задачам поочередно. Таким образом, задачи, претендующие на использование того или иного ресурса, выстраиваются в очередь к этому ресурсу. Эти очереди обычно приоритетные, однако, довольно часто применяются и FIFO-очереди, так как это единственная логическая организация очереди, которая гарантированно не допускает постоянного вытеснения задачи более приоритетными. LIFO-очереди обычно используются операционными системами для учета свободных ресурсов.

Структуры данных Очереди FIFO Очередь является одним из ключевых понятий в многозадачных операционных

Слайд 40

Структуры данных

Очереди FIFO

Также в современных операционных системах одним из средств взаимодействия между параллельно

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

Структуры данных Очереди FIFO Также в современных операционных системах одним из средств взаимодействия

Слайд 41

Структуры данных

Очереди FIFO

Логическая структура очереди
FIFO (First In - First Out - "первым пришел

- первым исключается")
последовательный список переменной длины, в котором включение элементов выполняется только с одной стороны списка,а исключение - с другой стороны.
Основные операции над очередью:
включение
исключение
определение размера
очистка
неразрушающее чтение

Структуры данных Очереди FIFO Логическая структура очереди FIFO (First In - First Out

Слайд 42

Структуры данных

Очереди FIFO

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

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

Структуры данных Очереди FIFO Очереди с приоритетами Порядок выборки элементов из очередей определяется

Слайд 43

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 4:
Деки

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 4: Деки

Слайд 44

Структуры данных

Деки

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

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

Структуры данных Деки Логическая структура дека Дек особый вид очереди в виде последовательного

Слайд 45

Структуры данных

Деки

Состояния дека в процессе изменения

Структуры данных Деки Состояния дека в процессе изменения

Слайд 46

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 5:
Связные линейные списки

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 5: Связные линейные списки

Слайд 47

Структуры данных

Связные линейные списки

Машинное представление связных линейных списков
Поле INF - информационное поле,

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

Структуры данных Связные линейные списки Машинное представление связных линейных списков Поле INF -

Слайд 48

Структуры данных

Связные линейные списки

Обработка односвязного списка не всегда удобна, так как отсутствует

возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка.
поле NEXT- указатель на следующий элемент, поле PREV- указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать NULL.

Структуры данных Связные линейные списки Обработка односвязного списка не всегда удобна, так как

Слайд 49

Структуры данных

Связные линейные списки

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

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

Структуры данных Связные линейные списки Разновидностью рассмотренных видов линейных списков является кольцевой список.

Слайд 50

Структуры данных

Связные линейные списки

Реализация операций над связными линейными списками
Перебор элементов списка. Осуществляется

последовательный доступ к элементам списка - ко всем до конца списка или до нахождения искомого элемента.
void LookSll( link head )
{ link curr = head;
while( curr )
{ curr = curr->next;
}
}

Структуры данных Связные линейные списки Реализация операций над связными линейными списками Перебор элементов

Слайд 51

Структуры данных

Связные линейные списки

В двухсвязном списке возможен перебор как в прямом направлении,

так и в обратном. В последнем случае параметром процедуры должен быть tail - указатель на конец списка, и переход к следующему элементу должен осуществляться по указателю назад:
curr = curr->prev;

Структуры данных Связные линейные списки В двухсвязном списке возможен перебор как в прямом

Слайд 52

Структуры данных

Связные линейные списки

В кольцевом списке окончание перебора должно происходить не по

признаку последнего элемента - такой признак отсутствует, а по достижению элемента, с которого начался перебор.

Структуры данных Связные линейные списки В кольцевом списке окончание перебора должно происходить не

Слайд 53

Структуры данных

Связные линейные списки

Вставка элемента в список.
void InsertSll( link& prev, data

inf )
{ if( prev )
{ link curr = new SllNode;
curr->inf = inf;
curr->next = prev->next;
prev->next = curr;
}
}

Вставка элемента в середину 1-связного списка

Структуры данных Связные линейные списки Вставка элемента в список. void InsertSll( link& prev,

Слайд 54

Структуры данных

Связные линейные списки

Вставка элемента в середину 2-связного списка

Структуры данных Связные линейные списки Вставка элемента в середину 2-связного списка

Слайд 55

Структуры данных

Связные линейные списки

Вставка элемента в начало 1-связного списка

Структуры данных Связные линейные списки Вставка элемента в начало 1-связного списка

Слайд 56

Структуры данных

Связные линейные списки
void DeleteSll( link& head, link del )
{ if( head ==

NULL ) return;
if( del == head )
{ head = del->next;
}
else
{ link prev = head;
while( prev->next && prev->next != del ) prev = prev->next;
if( prev->next == del )
{prev->next = del->next;
}
}
if( del ) delete del;
}

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

Удаление элемента из списка

Структуры данных Связные линейные списки void DeleteSll( link& head, link del ) {

Слайд 57

Структуры данных

Связные линейные списки
Удаление элемента из 2-связного списка

Структуры данных Связные линейные списки Удаление элемента из 2-связного списка

Слайд 58

Структуры данных

Связные линейные списки

Перестановка элементов списка
void ExchangeSll( link& prev )
{ if(

prev && prev->next && prev->next->next )
{ link p1 = prev->next;
link p2 = p1->next;
p1->next = p2->next;
P2->next = p1;
prev->next = p2;
}
}

Структуры данных Связные линейные списки Перестановка элементов списка void ExchangeSll( link& prev )

Слайд 59

Структуры данных

Связные линейные списки

Перестановка соседних элементов 2-связного списка

Структуры данных Связные линейные списки Перестановка соседних элементов 2-связного списка

Слайд 60

Структуры данных

Связные линейные списки

Копирование части списка
При копировании старый список сохраняется в памяти

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

Структуры данных Связные линейные списки Копирование части списка При копировании старый список сохраняется

Слайд 61

Структуры данных

Связные линейные списки

Алгоритм копирования
части списка:

link CopyList( link head, int

num )
{ if( head == NULL ) return NULL;
link first = NULL, last = NULL;
while( head && num>0 )
{ link curr = new SllNode;
curr->next = NULL;
curr->inf = head->inf;
if( first == NULL )
{ first = curr;
last = first; }
else
{ last->next = curr;
last = curr; }
head = head->next;
num--; }
last->next = NULL;
return first;}

Структуры данных Связные линейные списки Алгоритм копирования части списка: link CopyList( link head,

Слайд 62

Структуры данных

Связные линейные списки

Слияние двух списков
Операция слияния заключается в формировании из двух

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

void Unit( link& Head1, link Head2 )
{ if( Head2 )
{ if(Head1 == NULL ) Head1 = Head2;
else
{ link curr = Head1;
while( curr->next ) curr = curr->next;
curr->next = Head2; }
Head2 = NULL; } }

Структуры данных Связные линейные списки Слияние двух списков Операция слияния заключается в формировании

Слайд 63

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 6:
Мультисписки

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 6: Мультисписки

Слайд 64

Структуры данных

Мультисписки

Пример мультисписка

Структуры данных Мультисписки Пример мультисписка

Слайд 65

Структуры данных

Мультисписки

Для того чтобы при выборке каждого подмножества не выполнять полный просмотр

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

Структуры данных Мультисписки Для того чтобы при выборке каждого подмножества не выполнять полный

Слайд 66

Структуры данных

Мультисписки
Специфика мультисписка проявляется только в операции исключения элемента из списка. Исключение

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

Структуры данных Мультисписки Специфика мультисписка проявляется только в операции исключения элемента из списка.

Слайд 67

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 7:
Нелинейные разветвленные списки

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 7: Нелинейные разветвленные списки

Слайд 68

Структуры данных

Нелинейные разветвленные списки

Основные понятия
Нелинейным разветвленным списком является список, элементами которого могут

быть тоже списки.
Если один из указателей каждого элемента списка задает порядок, обратный к порядку, устанавливаемому другим указателем, то такой двусвязный список будет линейным
Если же один из указателей задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому другим указателем, то такой список будет нелинейным.

Структуры данных Нелинейные разветвленные списки Основные понятия Нелинейным разветвленным списком является список, элементами

Слайд 69

Структуры данных

Нелинейные разветвленные списки

Схематичное представление разветвленного списка

Структуры данных Нелинейные разветвленные списки Схематичное представление разветвленного списка

Слайд 70

Структуры данных

Нелинейные разветвленные списки

Разветвленные списки описываются тремя характеристиками:
порядком
глубиной
длиной.

Структуры данных Нелинейные разветвленные списки Разветвленные списки описываются тремя характеристиками: порядком глубиной длиной.

Слайд 71

Структуры данных

Нелинейные разветвленные списки

Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью,

в которой элементы появляются внутри списка. В списке (x,y,z) атом x предшествует y, а y предшествует z. При этом подразумевается, что x предшествует z.
Данный список не эквивалентен списку (y,z,x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент из которого исходит стрелка, предшествует элементу, на который она указывает.

Структуры данных Нелинейные разветвленные списки Порядок. Над элементами списка задано транзитивное отношение, определяемое

Слайд 72

Структуры данных

Нелинейные разветвленные списки

Глубина. Это максимальный уровень, приписываемый элементам внутри списка или

внутри любого подсписка в списке. Уровень элемента предписывается вложенностью подсписков внутри списка, т.е. числом пар круглых скобок, окаймляющих элемент
Длина - число элементов уровня 1 в списке.

Структуры данных Нелинейные разветвленные списки Глубина. Это максимальный уровень, приписываемый элементам внутри списка

Слайд 73

Структуры данных

Нелинейные разветвленные списки

Выражение:
(a+b)*(c-(d/e))+f
будет вычисляться в следующем порядке:
a+b
d/e

c-(d/e)
(a+b)*(c-d/e)
(a+b)*(c-d/e)+f
Глубина этого списка равна 4,
длина - 3.

Структуры данных Нелинейные разветвленные списки Выражение: (a+b)*(c-(d/e))+f будет вычисляться в следующем порядке: a+b

Слайд 74

Структуры данных

Нелинейные разветвленные списки

Представление списковых структур в памяти
Элементы списка могут быть двух

видов: атомы, содержащие данные и узлы, и содержащие указатели на подсписки. В атомах не используется поле down элемента списка, а в узлах - поле data. Поэтому логичным является совмещение этих двух полей в одно:

Структуры данных Нелинейные разветвленные списки Представление списковых структур в памяти Элементы списка могут

Слайд 75

Структуры данных

Нелинейные разветвленные списки

Поле type содержат признак атом/узел, оно может быть 1-битовым.

Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла:

Структуры данных Нелинейные разветвленные списки Поле type содержат признак атом/узел, оно может быть

Слайд 76

Структуры данных

Нелинейные разветвленные списки

Операции обработки списков
Базовыми операциями при обработке списков являются операции

(функции):
car,
cdr,
cons
atom.

Структуры данных Нелинейные разветвленные списки Операции обработки списков Базовыми операциями при обработке списков

Слайд 77

Структуры данных

Нелинейные разветвленные списки

Операция car в качестве аргумента получает список (указатель на

начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент). Например:
если X - список (2,6,4,7), то car(X) - атом 2;
если X - список ((1,2),6), то car(X) - список (1,2);
если X - атом то car(X) не имеет смысла и в действительности не определено.

Структуры данных Нелинейные разветвленные списки Операция car в качестве аргумента получает список (указатель

Слайд 78

Структуры данных

Нелинейные разветвленные списки

Операция cdr в качестве аргумента также получает список. Ее

возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:
если X - (2,6,4), то cdr(X) - (6,4);
если X - ((1,2),6,5), то cdr(X) - (6,5);
если список X содержит один элемент, то cdr(X) равно nil.

Структуры данных Нелинейные разветвленные списки Операция cdr в качестве аргумента также получает список.

Слайд 79

Структуры данных

Нелинейные разветвленные списки

Операция cons имеет два аргумента: указатель на элемент списка

и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список. Например:
если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7);
если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).

Структуры данных Нелинейные разветвленные списки Операция cons имеет два аргумента: указатель на элемент

Слайд 80

Структуры данных

Нелинейные разветвленные списки

Операция atom выполняет проверку типа элемента списка. Она должна

возвращать логическое значение: true - если ее аргумент является атомом, или false - если ее аргумент является подсписком.

Структуры данных Нелинейные разветвленные списки Операция atom выполняет проверку типа элемента списка. Она

Слайд 81

Структуры данных

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Тема 8:
Управление динамически выделяемой памятью

Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 8: Управление динамически выделяемой памятью

Слайд 82

Структуры данных

Управление динамически выделяемой памятью

Динамические структуры по определению характеризуются непостоянством и непредсказуемостью

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

Структуры данных Управление динамически выделяемой памятью Динамические структуры по определению характеризуются непостоянством и

Слайд 83

Структуры данных

Управление динамически выделяемой памятью

В общем случае при распределении памяти должны быть

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

Структуры данных Управление динамически выделяемой памятью В общем случае при распределении памяти должны

Слайд 84

Структуры данных

Управление динамически выделяемой памятью

Память выделяется блоками.
Блоки могут быть фиксированной или

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

Структуры данных Управление динамически выделяемой памятью Память выделяется блоками. Блоки могут быть фиксированной

Слайд 85

Структуры данных

Управление динамически выделяемой памятью

Одной из проблем, которые должны приниматься во внимание

при управлении памятью, является проблема фрагментации (дробления) памяти. Она заключается в возникновении "дыр" - участков памяти, которые не могут быть использованы. Различаются дыры внутренние и внешние.
Внутренняя дыра - неиспользуемая часть выделенного блока, она возникает, если размер выделенного блока больше запрошенного. Внутренние дыры характерны для выделения памяти блоками фиксированной длины.
Внешняя дыра - свободный блок, который в принципе мог бы быть выделен, но размер его слишком мал для удовлетворения запроса. Внешние дыры характерны для выделения блоками переменной длины.

Структуры данных Управление динамически выделяемой памятью Одной из проблем, которые должны приниматься во

Слайд 86

Структуры данных

1.Каковы особенности динамических структур данных?
2. Перечислите основные динамические структуры?
3. Какие основные операции

выполняются над динамическими структурами?

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

Структуры данных 1.Каковы особенности динамических структур данных? 2. Перечислите основные динамические структуры? 3.

Имя файла: Структуры-данных.pptx
Количество просмотров: 80
Количество скачиваний: 0