ПРОГРАММИРОВАНИЕ/ ЯЗЫКИ ПРОГРАММИРОВАНИЯ Лекция 6 Структуры данных с ограниченным режимом доступа (весенний семестр 2012 г.) Доцент Кафедры вычислительных систем, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Структуры с ограниченным доступом к элементам 2 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1. Предназначены для хранения наборов однотипных значений. 2. В отличие от массивов и списков, не допускают обращения к произвольному элементу. 3. Предоставляют лишь ограниченный набор допустимых операций. В рамках данного курса будут рассматриваться структуры, в которых набор допустимых сводится к двум операциям: 1) включение нового элемента в структуру; 2) исключение существующего элемента из структуры.

Ограничение доступа к программным и аппаратурным объектам 3 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Причины ограничения доступа могут быть различными, наиболее распространенными вариантами являются: 1. Безопасность. Например, ограничение доступа к внутренним данным аппаратурных компонентов или сетевых узлов. 2. Универсальность (переносимость). Изменения в ограниченном наборе операций с объектом проще учесть в программе, которая с ним работает. 3. Интерфейс. Если набор операций работы с некоторым объектом жестко зафиксирован, он называется интерфейсом. Обычно интерфейс остается неизменным, несмотря на самые серьезные изменения в модуле.

СТЕК 4 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Стек (англ. stack – стопка) – структура данных с методом доступа к элементам LIFO (Last In – First Out, последним пришел первым вышел). Чаше всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала снять верхнюю. Доступ к элементам стека осуществляется через две операции: 1) push (англ. вталкивание) – добавление нового элемента в стек, которое возможно только в вершину стека (добавленный элемент становится первым сверху) 2) pop (англ. выстрелить) – извлечение элемента из вершины стека, при этом второй сверху элемент становится верхним.

Реализация стека (динамически-расширяемый массив) 5 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct stack { struct darray da; }; int stack_init(struct stack *s) { return dinit(&(s->da)); }

Реализация стека (динамически-расширяемый массив) 6 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int push(struct stack *s, elem){ if( dexpand(&(s->da), 1) != 0) return -1; // ошибка выделения памяти dptr(&(s->da))[ dcount(&(s->da))- 1 ] = elem; return 0; } int pop(struct stack *s, *elem){ if( dcount( &(s->da) ) == 0) // если стек пуст return -1; *elem = dptr(&(s->da))[ dcount(&(s->da))- 1 ]; return dreduce(&(s->da), 1); }

Реализация стека (списки) 7 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct stack { struct list *l; }; int stack_init(struct stack *s) { return s->l = linit(); }

Реализация стека (списки) 8 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int push(struct stack *s, elem){ return linsfirst(s->l,elem); } int pop(struct stack *s, *elem){ struct list *ptr = lfirst(s->l); if( ptr != NULL){ *elem = ptr->val; return ldel( lfirst(s->l) ); } return -1; }

СТЕК (Заключение) 9 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Были рассмотрены различные реализации структуры данных "стек", основанные на: 1) динамически-расширяемых массивах; 2) списках. При этом был выдержан единый интерфейс, что обеспечивает следующие свойства: int push(struct stack *s, elem); int pop(struct stack *s, *elem); Возможна прозрачная замена базовой структуры данных, лежащей в основе очереди.

ОЧЕРЕДЬ 10 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Очередь структура данных с дисциплиной доступа к элементам «первый пришёл - первый вышел» (FIFO, First In - First Out). Доступ к элементам стека осуществляется через две операции: 1) enqueue (включить в очередь) – добавление элемента в конец очереди; 2) dequeue (исключить из очереди) – извлечение элемента из начала очереди.

Реализация очереди на базе динамически-расширяемых массивов 11 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Реализация очереди (динамически-расширяемый массив) 12 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» При реализации очереди на базе динамически- расширяемого массива возникает следующая проблема: в отличие от стека, в очереди удаляется первый элемент. В случае массива это требует сдвига ВСЕХ элементов массива вправо на одну позицию. Если очередь состоит из большого числа элементов это может приводить к чрезвычайно высоким накладным расходам. Далее будет рассмотрен подход, позволяющий более эффективно работать с массивом.

Реализация очереди (динамически-расширяемый массив) 13 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct queue { struct darray da; int s, e; }; int queue_init(struct queue *s) { int ret = dinit(&q->da); ret += dexpand( dsize(&q->da) ); q->s = q->e = 0; }

Получение размера, доступ к элементам и освобождение динамически-расширяемого массива 14 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int *dcount(struct darray *da) { return da->used; } int *dsize(struct darray *da) { return da->size; }

Операция enqueue 15 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Изменение размера динамического массива только в случае, когда очередь переполнена, т.е.: (e+1) % dsize == s

Операция enqueue (2) 16 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» s = 0 e = 0 s == e => пуста 1) s = 0 e = 1 (e+1)%2 == s => полн. 2) s = 0 e = 2 не полн., не пустая. 3) s = 0 e = 3 (e+1)%4 == s => полн. 4)

Операция enqueue (3) 17 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» s = 1 e = 3 не полн., не пустая 5) s = 1 e = 0 (e+1)%4 == s => полн. 6) s = 2 e = 0 не полн., не пустая. 7) s = 2 e = 1 (e+1)%4 == s => полн. 8)

Операция enqueue (4) 18 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» s = 2 e = 1 (e+1)%4 == s => полн. e < s 8) 9.1) 9.2) s = 2 e = 6 не полн., не пуст.

Операция enqueue (5) 19 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» s == 3, e == 2, size = 4 q[size] = q[0]; ( q[4] = q[0] ) q[size+1] = q[1]; ( q[5] = q[1] ) e = e + size; ( e = 6 )

Операция enqueue (реализация на языке СИ) 20 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int enqueue(struct queue *q, elem){ int cursize = dcount(&q->da); if( (q->e + 1)%cursize == q->s ){ // в очереди имеется только один свободный элемент // 1. Изменить размер массива if( dexpand( dsize(&q->da) ) ) return -1; // 2. Перенести элементы, если необходимо if( e < s ){ *ptr = dptr(&q->da); for(i=0;ie += cursize; } return insert(q,elem); }

Операция insert (реализация на языке СИ) 21 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int insert(struct queue *q, elem) { *ptr = dptr(&q->da); ptr[q->e] = elem; q->e = (q->e + 1) % dsize(&q->da); return 0; }

Размер очереди (динамически-расширяемый массив) 22 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int qsize(struct queue *q){ if( q->s e ){ return (q->e – q->s); } else { return ( (dsize(&q->da) – q->s) + q->e ); }

Операция dequeue (динамически-расширяемый массив) 23 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int dequeue(struct queue *q, *elem){ *ptr = dptr(&q->da); if( q->s == q->e ){ return -1; // очередь пуста } *elem = ptr[q->s]; q->s = (q->s + 1) % dsize(&q->da); // Уменьшение размера, если qsize(q)*4 da)... }

Реализация очередей на базе списков 24 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Реализация очередей (списки) 25 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Реализация очередей на базе списков отличается сравнительной простотой по сравнению с реализацией на базе динамически-расширяемых массивов. Это связано с тем, что списки допускают эффективную реализацию операции извлечения элемента из начала списка.

Реализация очередей (списки) 26 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Реализация очереди (списки) 27 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct queue{ struct list *l; int size; }; int stack_init(struct stack *s) { size = 0; return s->l = linit(); }

Операции enqueue и dequeue (списки) 28 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int enqueue(struct queue *q, elem){ int ret = linslast(s->l,elem); if( ret == 0 ){ q->size++; } return ret; } int dequeue(struct queue *q, *elem){ struct list *ptr = lfirst(s->l); int ret = -1; if( ptr != NULL){ *elem = ptr->val; ret = ldel( lfirst(s->l) ); q->size--; } return ret; }

Размер очереди (динамически-расширяемый массив) 29 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int qsize(struct queue *q){ return q->size; }

ОЧЕРЕДЬ (Заключение) 30 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Были рассмотрены различные реализации структуры данных "очередь", основанные на: 1) динамически-расширяемых массивах; 2) списках. При этом был выдержан единый интерфейс, что обеспечивает следующие свойства: int enqueue(struct queue *q, elem); int dequeue(struct queue *q, *elem); int qsize(struct queue *q); Возможна прозрачная замена базовой структуры данных, лежащей в основе очереди.

ПИРАМИДА 31 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пирамида (куча) (англ. heap) – структура данных, которая имеет следующие характеристики: 1) вычислительная сложность определения максимального или минимального элемента O(1); 2) вычислительная сложность операций вставки нового элемента и удаления минимального элемента O(log 2 N), где N – количество элементов в пирамиде. Пирамиды также называют очередями с приоритетами. Для кучи определен следующий набор операций: 1) enqueue_h – включение элемента в пирамиду; 2) dequeue_h – исключение максимального (минимального) элемента из пирамиды.

Организация пирамиды 32 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пирамида может быть представлена в виде последовательности a элементов, удовлетворяющей "свойству пирамиды". Свойство пирамиды подразумевает наличие древовидной структуры: каждый элемент имеет не более двух потомков. Пусть последовательность a = {a i | i = 0, …, N-1} хранящая элементы пирамиды, состоит из N элементов. Тогда для элемента a i потомки определяются следующим образом: Если 2i+2 < N, то a i имеет двух потомков: a 2i+2, a 2i+1. Иначе, если 2i+1 < N, то a i имеет одного потомка: a 2i+1. Иначе a i не имеет потомков.

Организация пирамиды (3) 33 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть последовательность a = {a i | i = 0, …, N-1} хранящая элементы пирамиды, состоит из N элементов. Тогда индекс k предка элемента a i определяются следующим образом: k = (i – 1) div 2

Свойство пирамиды 34 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть последовательность a = {a i | i = 0, …, N-1} хранящая элементы пирамиды, состоит из N элементов. Тогда индекс k предка элемента a i определяются следующим образом: Для всех элементов a i должно выполняться неравенство: a i a 2i+1 a i a 2i+2

Включение элемента в пирамиду 35 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть последовательность a = {a i | i = 0, …, N-1} хранящая элементы пирамиды, состоит из N элементов. Тогда включение элемента E в пирамиду выполняется следующим образом: 1) вставка элемента последним в пирамиду: i = N, a i = E, N = N + 1; 2) вычисляется индекс предка: k = (i – 1) div 2; 3) ЕСЛИ a i > a k ТО t = a i, a i = a k, a k = t. Перейти на ШАГ 4. ИНАЧЕ перейти на шаг 5. 4) ЕСЛИ k = 0 ТО перейти на ШАГ 5. ИНАЧЕ i = k, перейти на ШАГ 2. 5) Завершить алгоритм.

Включение элемента в пирамиду (пример) 36 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Исключение максимального элемента из пирамиды 37 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть последовательность a = {a i | i = 0, …, N-1} хранящая элементы пирамиды, состоит из N элементов. Алгоритм исключение элемента из а выглядит следующим образом: 1) x = a 0 ; 2) a 0 = a N – 1, N = N 1; 3) номер текущего элемента i = 0; 4) ЕСЛИ (2i+2 a 2i+1 ) AND и (a i < a 2i+2 ) ТО t = a i, a i = a 2i+2, a 2i+2 = t, i = 2i+2, перейти на ШАГ 5. ИНАЧЕ – перейти на ШАГ 5. 5) ЕСЛИ (2i+1 < n AND a i < a 2i+1 ) ТО t = a i, a i = a 2i+1, a 2i+1 = t, i = 2i+1, перейти на ШАГ 4. ИНАЧЕ: перейти ШАГ 6. 6) Возвратить значение x, алгоритм завершен.

Исключение максимального элемента из пирамиды (пример) 38 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Выбор базовой структуры для реализации пирамиды 39 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пирамида – это последовательность a = {a i | i = 0, …, N1}, элементов. Операции вставки и исключения элемента: 1) эффективны (вычислительная сложность O(log 2 N); 2) требуют доступа к элементам, расположенным не последовательно: а) к предку элемента a i с индексом (i 1) div 2. б) к потомкам элемента a i с индексами 2i+1 и 2i+2. В связи с п. 2 применение списков в качестве базовой структуры является неэффективным. Динамически-расширяемые массивы позволяют хранить произвольное число элементов, а также обеспечить эффективность основных операций.

Реализация пирамиды 40 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct heap { struct darray da; }; int hinit(struct heap *h) { return dinit(&(h->da)); } int enqueue_h(struct heap *h, elem){ dexpand(&h->da,1); dptr(&h->da)[dcount(&h->da)-1] = elem; percolate_up(h); } int dequeue_h(struct heap *h, *elem){ *elem = dptr(&h->da)[0]; dptr(&h->da)[0] = dptr(&h->da)[dcount(&h->da)-1]; dreduce(&h->da,1); percolate_down(h); }

ПИРАМИДА (Заключение) 41 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Была рассмотрена реализация структуры данных "пирамида" на базе динамически-расширяемых массивов При этом был выдержан единый интерфейс: int enqueue_h(struct queue *q, elem); int dequeue_h(struct queue *q, *elem); Реализация допускает прозрачную замену базовой структуры данных, лежащей в основе пирамиды.

ЛАБОРАТОРНАЯ РАБОТА 4 Сетевой ввод-вывод данных 42 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

43 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ЛАБОРАТОРНАЯ РАБОТА 4 Сетевой ввод-вывод данных (2)

ЛАБОРАТОРНАЯ РАБОТА 4 дисковый ввод-вывод данных 44 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Дисковый ввод-вывод данных (схема модели) 45 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Входные потоки ("2", 10, 3, 1, 1) ("1", 1, 3, 0, 1)("3", 6, 3, 0, 1) Noop Scheduler FIFOКЭШ

Дисковый ввод-вывод данных ( I цикл формирования запросов ) 46 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Noop Scheduler Входные потоки ("2", 10, 3, 1, 1)("1", 1, 3, 0, 1)("3", 6, 3, 0, 1) FIFOКЭШ 10

Дисковый ввод-вывод данных ( I цикл обработки запросов) 47 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Noop Scheduler Входные потоки ("2", 10, 3, 1, 1)("2", 1, 3, 0, 1)("3", 6, 3, 0, 1) FIFOКЭШ 10 c = 0, n = 1 T = T + f(n c) c = 0, n = 1 T = T + f(n c)

Дисковый ввод-вывод данных ( II цикл формирования запросов ) 48 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Noop Scheduler Входные потоки ("2", 10, 3, 1, 1)("2", 1, 3, 0, 1)("3", 6, 3, 0, 1) FIFOКЭШ

Дисковый ввод-вывод данных ( II цикл обработки запросов ) 49 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Noop Scheduler Входные потоки ("2", 10, 3, 1, 1)("2", 1, 3, 0, 1)("3", 6, 3, 0, 1) FIFOКЭШ c = 2, n = 10 T = T + f(n c) c = 2, n = 10 T = T + f(n c)

Дисковый ввод-вывод данных ( III цикл формирования запросов ) 50 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Noop Scheduler Входные потоки ("2", 10, 3, 1, 1)("2", 1, 3, 0, 1)("3", 6, 3, 0, 1) 6 6 FIFOКЭШ

Литература 51 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ, М.:МЦНМО, 2002, 960 с. 2.Кнут, Д.Э. Искусство программирования. Том 1. Основные алгоритмы. – Вильямс, – (Серия: Искусство программирования). – ISBN