Элементарные структуры данных Лекция 1

Множество Множество это фундаментальное понятие как в математике, так и в теории вычислительных машин. Если математические множества остаются неизменными, множества, которые обрабатываются в ходе выполнения алгоритмов, могут с течением времени разрастаться, уменьшаться или подвергаться другим изменениям. Назовем такие множества динамическими (dinamic). 2

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

Элементы динамического множества В типичных реализациях динамического множества каждый его элемент представлен некоторым объектом; если в нашем распоряжении имеется указатель на объект, то можно проверять и изменять значения его полей. В динамических множествах некоторых типов предполагается, что одно из полей объекта идентифицируется как ключевое (key field). Если все ключи различны, то динамическое множество представимо в виде набора ключевых значений. Иногда объекты содержат сопутствующие данные (satellite data), которые находятся в других его полях, но не используются реализацией множества. Кроме того, объект может содержать поля, доступные для манипуляции во время выполнения операций над множеством; иногда в этих полях хранятся данные или указатели на другие объекты множества. 4

Операции в динамических множествах Операции динамического множества можно разбить на две категории: запросы (queries), которые просто возвращают информацию о множестве, и модифицирующие операции (modifying operations), изменяющие множество. Search(S,k) Insert(S, х) Delete(S,x) Мinimum(S) Мaximum(S) Successor(S, x) Predecessor(S,х) 5

Search(S,k) Запрос, который возвращает указатель на элемент х заданного множества S, для которого кеу [х] = к, или значение NIL, если в множестве S такой элемент отсутствует. Insert(S, х) Модифицирующая операция, которая пополняет заданное множество S одним элементом, на который указывает х. Обычно предполагается, что вы­полнена предварительная инициализация всех полей элемента х, необходи­мых для реализации множества. Delete(S,x) Модифицирующая операция, удаляющая из заданного множества S элемент, на который указывает х. (Обратите внимание, что в этой операции исполь­зуется указатель на элемент, а не его ключевое значение.) Мinimum(S) Запрос к полностью упорядоченному множеству S, который возвращает указатель на элемент этого множества с наименьшим ключом. Мaximum(S) Запрос к полностью упорядоченному множеству S, который возвращает указатель на элемент этого множества с наибольшим ключом. 6

Successor(S, x) Запрос к полностью упорядоченному множеству S, который возвращает указатель на элемент множества S, ключ которого является ближайшим соседом ключа элемента х и превышает его. Если же х- максимальный элемент множества S, то возвращается значение NIL. Predecessor(S,х) Запрос к полностью упорядоченному множеству S, который возвращает ука­затель на элемент множества S, ключ которого является ближайшим мень­шим по значению соседом ключа элемента х. Если же х- минимальный элемент множества S, то возвращается значение NIL. 7

Запросы Successor и Predecessor часто обобщаются на множества, в которых не все ключи различаются. Для множества, состоящего из n элементов, обычно принимается допущение, что вызов операции Мinimum, после которой n 1 раз вызывается операция Successor, позволяет пронумеровать элементы множества в порядке сортировки. Время, необходимое для выполнения операций множества, обычно измеряется в единицах, связанных с размером множества, который указывается в качестве одного из аргументов. 8

Стеки и очереди Стеки и очереди это динамические множества, элементы из которых удаляются с помощью предварительно определенной операции Delete. Первым из стека (stack) удаляется элемент, который был помещен туда последним: в стеке реали­зуется стратегия "последним вошел первым вышел" (last-in first-out LIFO). Аналогично, в очереди (queue) всегда удаляется элемент, который содержится в множестве дольше других: в очереди реализуется стратегия "первым вошел первым вышел" (first-in first-out FIFO). Существует несколько эффективных способов реализации стеков и очередей в компьютере. 9

Стеки Операция вставки применительно к стекам часто называется Рush (запись в стек), а операция удаления Рор (снятие со стека). Cтек, способный вместить не более n элементов, можно реализовать с помощью массива S [1..n]. Этот массив обладает атрибутом tор[S], представляющим собой индекс последнего помешенного в стек элемента. Стек состоит из элементов S[1..tор[|S]], где S [1] - элемент на дне стека, а S [tор[S]] элемент на его вершине. Если tор[S] = 0, то стек не содержит ни одного элемента и является пустым. (empty). Протестировать стек на наличие в нем элементов можно с помощью операции-запроса Stack_Еmpty. 10

Если элемент снимается с пустого стека, говорят, что он опустошается (underflow), что обычно приводит к ошибке. Если значение top [S] больше n, то стек переполняется (overflow). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.) 11

Каждую операцию над стеком можно легко реализовать несколькими строками кода: Stack_Еmpty(S) 1 if top[S] = 0 2 then return TRUE 3 else return FALSE Рush(S, x) 1 top[S] top[S] S[top[S] x Рop(S) 1 if Stack_Еmpty(S) 2 then error "underflow" 3 еlsе top[S] top[S] return S[tор[S] + 1] 12

Очереди Применительно к очередям операция вставки называется Enqueue (поместить в очередь), а операция удаления Dequeue (вывести из очереди). Подобно стековой операции Pop, операция Dequeue не требует передачи элемента массива в виде аргумента. Благодаря свойству FIFO очередь подобна, например, живой очереди к врачу в поликлинике. У нее имеется голова (head) и хвост (tail). Когда элемент ставится в очередь, он занимает место в ее хвосте, точно так же, как человек занимает очередь последним, чтобы попасть на прием к врачу. Из очереди всегда выводится элемент, который находится в ее головной части аналогично тому, как в кабинет врача всегда заходит больной, который ждал дольше всех. 13

Способ, который позволяет с помощью массива Q[1..n] реализовать очередь, состоящую не более чем из n 1 элементов. Эта очередь обладает атрибутом head [Q], который является индексом головного элемента или указателем на него; атрибут tail[Q] индексирует местоположение, куда будет добавлен новый элемент. Элементы очереди расположены в ячейках head[Q], head[Q}+1, …, tail[Q] – 1, которые циклически замкнуты в том смыс­ле, что ячейка 1 следует сразу же после ячейки n в циклическом порядке. 14

При выполнении условия head[Q] = tail[Q] очередь пуста. Изначально выполняется соотношение head[Q] = tail[Q] = 1. Если очередь пустая, то при попытке удалить из нее элемент происходит ошибка опустошения. Если head[Q] = tail[Q] +1, то очередь заполнена, и попытка добавить в нее элемент приводит к ее переполнению. В наших процедурах Enqueue и Dequeue проверка ошибок опустошения и переполнения не производится. 15

Реализация методов Enqueue(Q, х) 1 Q[tail[Q]] х 2 if tail[Q] = length[Q] 3 then tail[Q] 1 4 else tail[Q] tail[Q]+ 1 Dequeue(Q, х) 1 х Q[head[Q]] 2 if head[Q] = length[Q] 3 then head[Q] 1 4 else head[Q] head[Q]+ 1 5 return x 16

Работа процедур Еnqueue и Dequeue. Элементы очереди содержатся только в светло-серых ячейках. В части A рисунка изображена оче­редь, состоящая из пяти элементов, расположенных в ячейках Q[7..11]. В части Б показана эта же очередь после вызова процедур Еnqueue (Q, 17), Еnqueue (Q, 3) и Еnqueue (Q, 5), а в части B конфигурация очереди после вызова процедуры Dequeue (Q), возвращающей значение ключа 15, которое до этого находилось в голове очереди. Значение ключа новой головы очереди равно 6. 17

Связанные списки Связанный список (linked list) это структура данных, в которой объекты расположены в линейном порядке. Однако, в отличие от массива, в котором этот порядок определяется индексами, порядок в связанном списке определяется указателями на каждый объект. Связанные списки обеспечивают простое и гибкое представление динамических множеств и поддерживают все операции (возможно. недостаточно эффективно), перечисленные ранее. 18

Каждый элемент дважды связанного списка (double linked list) L это объект с одним полем ключа key и двумя полями-указателями: next (следующий) и prev (предыдущий). Этот объект может также содержать другие сопутствующие данные. Для заданного элемента списка x указатель next [х] указывает на следующий элемент связанного списка, а указатель prev [х] на предыдущий. Если prev [х] = NIL, у элемента x нет предшественника, и, следовательно, он является первым, т.е. головным в списке. Если next[х] = NIL то у элемента х нет последующего, поэтому он является последним, т.е. хвостовым в списке. Атрибут head[L] указывает на первый элемент списка. Если hеаd [L] = NIL то список пуст. 19

Список может быть однократно или дважды связанным, отсортированным или неотсортированным, кольцевым или не кольцевым. Если список однократно связанный {однонаправленный) (singly linked), то указатель prev в его элементах отсутствует. Если список отсортирован (sorted), то его линейный порядок соответствует линейному порядку его ключей; в этом случае минимальный элемент находится в голове списка, а максимальный в его хвосте. Если же список не отсортирован, то его элементы могут располагаться в произвольном порядке. Если список кольцевой (circular list), то указатель prev его головного элемента указывает на его хвост, а указатель next хвостового элемента на головной элемент. Такой список можно рассматривать как замкнутый в виде кольца набор элементов. 20

Поиск в связанном списке Процедура List_Search(L, к) позволяет найти в списке L первый элемент с ключом k; путем линейного поиска, и возвращает указатель на найденный элемент. Если элемент с ключом k в списке отсутствует, возвращается значе­ние NIL. Процедура List_Search(L, 4), вызванная для связанного списка, возвращает указатель на третий элемент, а процедура List_Search(L, 7) значение NIL: List_Search(L, к) 1 хhеаd[L] 2 while x NIL and кеу[х] k 3 do х next[х] 4 return x 21

Вставка в связанный список Если имеется элемент x, полю key которого предварительно присвоено значение, то процедура List_Insert вставляет элемент x в переднюю часть списка : List_Insert (L, х) 1 next[x] head[L] 2 if head[L] NIL 3 then prev[head[L]] x 4 head[L] x 5 prev[х] NIL 22

Удаление из связанного списка Представленная ниже процедура List_Delete удаляет элемент х из связанного списка L. В процедуру необходимо передать указатель на элемент х. после чего она удаляет х из списка путем обновления указателей. Чтобы удалить элемент с заданным ключом, необходимо сначала вызвать процедуру List_Search для получения указателя на элемент List_Delete(L,х) 1 if prev[L] NIL 2 then next[prev[х]] nехt[х] 3 еlsе head[L] nехt[х] 4 if nехt[х] NIL 5 then prev[next[х]] prev[х] 23

Ограничители Код процедуры List_Delete мог бы быть проще, если бы можно было игнорировать граничные условия в голове и хвосте списка: List_Delete(L,х) 1 nехt([рrеv[x]] nехt[х] 2 рrеv[next[х]] рrеv[х] Ограничитель (sentinel) - это фиктивный объект, упрощающий учет граничных условий. Например, предположим, что в списке L предусмотрен объект nil[L], представляющий значение NIL, но при этом содержащий все поля, которые имеются у других элементов. 24

Когда в коде происходит обращение к значению NIL, оно заменяется обращением к ограничителю nil[L]. Наличие ограничителя преобразует обычный дважды связанный список в циклический дважды связанный список с ограничителем (circular, doubly linked list with sentinel). В таком списке ограничитель nil[L] расположен между головой и хвостом. Поле next[nil[L]] указывает на голову списка, а поле prev[nil[L]] на его хвост. 25

Аналогично, поле next хвостового элемента и поле рrеv головного элемен­та указывают на элемент nil [L]. Поскольку поле next[nil[L]] указывает на голову списка, можно упразднить атрибут head[L], заменив ссылки на него ссылками на поле пехt[nil[L]]. Пустой список содержит только ограничитель, поскольку и полю пехt[nil[L]], и полю рrеv[nil[L]] можно присвоить значение nil[L]. Код процедуры List_Search остается тем же, что и раньше, однако ссылки на значения NIL и head[L] заменяются : List_Search(L,k) 1 х nехt[nil[х]] 2 while x nil[L] and кеу[х] k 3 do х next[х] 4 return x 26

Удаление элемента из списка производится с помощью уже описанной процедуры List_Delete, состоящей всего из двух строк. Для вставки элемента в список используется приведенная ниже процедура: List_Insert (L, х) 1 next[x] next[nil[L]] 2 prev[next[nil[L]]] x 3 next[nil[L]] x 4 prev[х] nil[L] Действие процедур List_Insert и List_Delete проиллюстрировано на пред. Слайде. В части а этого рисунка приведен пустой список. В части б изображен связанный список, уже знакомый нам, в голове которого находится ключ 9, а в хвосте ключ 1. В части в изображен этот же список после выполнения процедуры List_Insert (L, х), где key[х| =

Новый объект становится в голову списка. В части г рассматриваемый список представлен после удаления в нем объекта с ключом 1. Новым хвостовым объектом становится объект с ключом 4. Применение ограничителей редко приводит к улучшению асимптотической зависимости времени обработки структур данных, однако оно может уменьшить величину постоянных множителей. Благодаря использованию ограничителей в циклах обычно не столько увеличивается скорость работы кода, сколько повышается его ясность. Например, представленный выше код, предназначенный для обработки связанного списка, упрощается в результате применения ограничителей, но сэкономленное в процедурах List_Insert и List_Delete время равно всего лишь 0(1). Однако в других ситуациях применение ограничителей позволяет сделать код в циклах компактнее, а иногда даже уменьшить время работы в n или n 2 раз. 28

Реализация указателей и объектов Как реализовать указатели и объекты в таких языках, как Fortran, где их просто нет? Объекты и указатели будут созданы на основе массивов и индексов. Представление объектов с помощью нескольких массивов Набор объектов с одинаковыми полями можно представить с помощью массивов. Каждому полю в таком представлении будет соответствовать свой массив. В качестве примера рассмотрим рис. на след.слайде, где проиллюстрирована реализация с помощью трех массивов связанного списка. В каждом столбце элементов на рисунке представлен отдельный объект. В массиве кеу содержатся значения ключей элементов, входящих в данный момент в динамическое множество, а указатели хранятся в массивах nехt и prev. 29

. Для заданного индекса массива х элементы кеу [х], пехt [х] и рrеv[х] представляют объект в свя­занном списке. В такой интерпретации указатель х это просто общий индекс в массивах кеу, nехt и рrеv. Указатели при таком способе хранения представляют собой просто индексы объектов, на которые они указывают. Объект с ключом 4 в связанном списке следует после объекта с ключом 16. Соответственно, ключ 4 является значением элемента кеу [2], а ключ 16 значением элемента kеу[5]. 30

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

Показано, как можно реализовать связанный список, с помощью одного массива А. Объект занимает подмассив смежных элементов А [j..к]. Каждое поле объекта соответствует смещению, величина которого принимает значения от 0 до к - j, а указателем на объект является индекс j. Каждый элемент списка это объект, занимающий по три расположенных рядом элемента массива. Указатель на объект это индекс его первого элемента. Объекты, в которых содержатся элементы списка, на рисунке отмечены светло-серым цветом. Cдвиги, отвечающие полям кеу, nехt и prev, равны 0, 1 и 2 соответственно. 32

Чтобы считать значение поля prev [i] для данного указателя i, к значению указателя добавляется величина сдвига 2, в результате чего получается А[i + 2]. Представление в виде единственного массива можно считать более гибким в том плане, что с его помощью в одном и том же массиве можно хранить объекты различной длины. Задача управления такими неоднородными наборами объектов сложнее, чем аналогичная задача для однородного набора объектов, где все объекты состоят из одинаковых полей. Поскольку большинство структур данных, которое нам предстоит рассмотреть, состоит из однородных элементов, для наших целей достаточно использовать представление объектов с помощью нескольких массивов. 33

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

Предположим, что в таком представлении используются массивы длиной m, и что в какой-то момент динамическое множество содержит n<m элементов. В этом случае n объектов представляют элементы, которые находятся в данный момент времени в динамическом множестве, а m - n элементов свободны. Их можно использовать для представления элементов, которые будут вставляться в динамическое множество в будущем. Свободные объекты хранятся в однократно связанном списке, который мы назовем списком свободных позиций (free list). Список свободных позиций ис­пользует только массив next, в котором хранятся указатели next списка. Головной элемент списка свободных позиций находится в глобальной переменной free. Когда динамическое множество, представленное связанным списком L, не является пустым, список свободных позиций используется вместе со списком L, как показано на рис. Заметим, что каждый объект в таком представлении находится либо в списке L, либо в списке свободных позиций, но не в обоих списках одновременно. 35

Список свободных позиций это стек: очередной выделяемый объект является последним освобожденным. Таким образом, реализовать процедуры выделения и освобождения памяти для объектов можно с помощью стековых операций Рush и Рop. Глобальная переменная frее, использующаяся в приведенных ниже процедурах, указывает на первый элемент списка свободных позиций: 36

Аllосате_Оbjеct() 1 if frее = NIL 2 then error "Нехватка памяти" 3 еlsе х frее 4 frее пехt[х] 5 return х Free_Object(х) 1 nехt[х] frее 2frее х В начальный момент список свободных позиций содержит все n объектов, для ко­торых не выделено место. Когда в списке свободных позиций больше не остается элементов, процедура Аllocate_Оbject выдает сообщение об ошибке. 37

На рис показано, как изменяется исходный список свободных позиций (а) при вызове процедуры Аllocate_Оbject (), которая возвращает индекс 4, и вставке в эту позицию нового элемента (6), а также после вызова List_Delete(L,5) с последующим вызовом Free_Оbjесt(5) (в). Часто один список свободных позиций обслуживает несколько связанных списков. Время выполнения обеих процедур равно О (1), что делает их весьма практичными. Эти процедуры можно модифицировать так, чтобы они работали с любым набором однородных объектов, лишь бы одно из полей объектов работало бы в качестве поля next списка свободных позиций. 38