Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика
жүктеу/скачать 3,71 Mb.
|
УМКАлгор и стр данн Инеттен (1)
|
8. Приведите примеры О-оценок роста функций трудоемкости. 9. Приведите примеры Ω-оценок роста функций трудоемкости.
конструкции «ветвление» и «цикл». 11.Напишите формулу определяющую трудоемкость конструкции «цикл» со вложенным циклом. 12.Напишите формулу определяющую трудоемкость конструкции «цикл» с m вложенными циклами. 13.В чем заключаются основные проблемы при переходе от операционных к временным оценкам трудоемкости алгоритмов 14.В чем состоит отличие подходов при переходе к временным оценкам? 15.Проведите анализ трудоемкости алгоритма сортировки вставками. 16.Дайте определение теоретического предела трудоемкости алгоритмов. 17.Можно ли оценить теоретический предел трудоемкости алгоритмов нахождения простых чисел? 18.Дайте определение рекуррентных соотношений, приведите примеры. 19.Приведите примеры оценки трудоемкости рекуррентных алгоритмов с использованием основной теоремы. 46 4. ВВЕДЕНИЕ В СТРУКТУРЫ ДАННЫХ 4.1. МНОЖЕСТВА Множество — это одно из фундаментальных понятий как в математике, так и в работе с программными средствами. Множества, которые в ходе выполнения алгоритмов могут расширяться, уменьшаться или подвергаться другим изменениям, называются динамическими. В алгоритмах обработки множеств, требуется выполнять операции: Вставить/удалить элементы в множество, Проверить принадлежность множеству (поиск). Динамическое множество, поддерживающее перечисленные операции, называется словарем. Более сложные операции: Вставка/извлечение минимального/максимального элемента в неубывающих очередях с приоритетами. Оптимальный способ реализации динамического множества зависит от того, какие операции должны им поддерживаться. В объектно-ориентированных языках программирования объекты могут быть созданы: во время компиляции – статические объекты, во время выполнения программы, путем вызова функций из стандартной библиотеки – динамические объекты. Основная разница этих методов – в их эффективности и гибкости. Использование статических объектов более эффективно, но менее гибко – выделение памяти происходит до выполнения программы, но при этом необходимо заранее указать тип и размер создаваемого объекта (искусство программирования). Задачи, в которых нужно хранить и обрабатывать неизвестное заранее число элементов, требуют динамического выделения памяти.
Отличия между статическим и динамическим выделением памяти: статические объекты обозначаются именованными переменными, действия над объектами производятся напрямую, с использованием их имен;
динамические объекты не имеют собственных имен, действия над ними производятся косвенно, с помощью указателей; выделение и освобождение памяти под статические объекты производится компилятором автоматически, под динамические объекты – программистом. В реализациях динамического множества каждый его элемент представляется некоторым объектом.
47 Указатель – это переменная, хранящая адрес другой переменной или объекта. Если имеется указатель на объект, то можно проверять и изменять значения его полей. Одно из полей объекта – ключевое (key field). Если все ключи различны, то динамическое множество определено набором ключевых значений. Объекты могут содержать сопутствующие данные (satellite data), которые находятся в других его полях, но не используются. Объект может содержать поля, доступные для манипуляции во время выполнения операций над множеством (иногда в этих полях хранятся данные или указатели на другие объекты множества). Ключи могут являться членами полностью упорядоченного множества: множества действительных чисел множества всех слов, которые могут быть расположены в алфавитном порядке. ОПЕРАЦИИ ДЛЯ ДИНАМИЧЕСКИХ МНОЖЕСТВ Запросы (accessor) – возвращают информацию о множестве, Модифицирующие операции (mutator) – изменяющие множество. Список типичных операций: Search(S, k) –запрос (возвращает указатель на элемент множества S с ключом k). Insert(S, x) – модифицирующая операция Delete(S, х) – модифицирующая операция Minimum(S), Maximum(S) – запрос (возвращает указатель на элемент множества S с наименьшим (наибольшим) ключом). Successor(S, x), Predecessor(S, x) –запросы (возвращают указатели на элементы множества S, которые являются соответственно «следующим» и «предшествующим» элементом для элемента х). Время, необходимое для выполнения операций с множеством измеряется в единицах, связанных с размером множества. Например, для двоичного поиска это время Ο(log 2 𝑛).
4.2. СТЕКИ И ОЧЕРЕДИ Первым из стека (stack) удаляется элемент, который был помещен туда последним. В стеке реализуется стратегия "последним вошел – первым вышел" (last in, first out – LIFO). Стеки применяются, например, для отслеживания точек возврата из подпрограмм. Языки программирования высокого уровня также используют стек вызовов для передачи параметров при вызове процедур. Псевдокод операций: 48 1. Проверка стэка на «пустоту» – Stack_Empty(S); 2. Затолкнуть (добавить) элемент в стэк – Push(S, x); 3. Вытолкнуть (извлечь) элемент из стэка – Pop(S).
Каждая операция выполняется в течение времени О(1). Пример использования стэка – алгоритм обращения порядка элементов массива:
1. все элементы последовательно проталкиваются в стек; 2. все элементы выталкиваются из стека в обратном порядке и записываются обратно в массив. В очереди (queue) удаляется элемент, который был помещен туда первым. В очереди реализуется стратегия "первым вошел первым вышел" (first in, first out — FIFO). Очередь имеет «голову» (head) и «хвост» (tail). Когда элемент добавляется в очередь, он занимает место в ее «хвосте». Из очереди всегда выводится элемент, который находится в ее «голове». Псевдокод операций: 1. Добавить элемент в очередь – Enqueue(Q, x); 2. Извлечь элемент из очереди – Dequeue(Q, x). 49 4.3. СПИСКИ Простые списки Если в программе необходим список постоянного размера, его можно создать, используя массив. В этом случае можно при необходимости опрашивать его элементы в цикле For. Многие программы используют списки, которые растут или уменьшаются со временем. Можно создать массив, соответствующий максимально возможному размеру списка, но такое решение не всегда будет оптимальным. Неупорядоченные списки Порядок расположения элементов не важен. Поддерживаются следующие операции: добавление элемента к списку; удаление элемента из списка; определение наличия элемента в списке; операции для всех элементов списка (например, вывод списка на дисплей, принтер или в файл). СВЯЗАННЫЕ СПИСКИ
Связный список (linked list) – базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.
Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком 50 расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями. Связные списки обеспечивают простое и гибкое представление динамических множеств и поддерживают все операции. Линейные связные списки 1. Односвязный список (Однонаправленный связный список). В односвязном списке можно передвигаться только в одну сторону – от начала в конец. Узнать адрес предыдущего элемента, опираясь на содержимое текущего элемента невозможно (рис.3).
Рис.3. Односвязный список 2. Двусвязный список (Двунаправленный связный список) В этом списке можно передвигаться в обоих направлениях, так как каждый узел хранит адреса как следующего, так и предыдущего узла.. Это свойство делает его более гибкой структурой, чем односвязный список (рис.4).
Рис.4. Двусвязный список 3. XOR-связный список – структура, похожая на обычный двусвязный список, однако в каждом элементе хранится только один адрес – результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. A[n]=f(A[n+1]A[n-1]) Чтобы перемещаться по списку, необходимо выполнить операцию А[n]=f(А[n-1]А[n-2]) В сравнении с обычным двусвязным списком, XOR список расходует в два раза меньше памяти для хранения связей между элементами. Используется довольно редко, так как существуют хорошие альтернативы, например, развёрнутый связный список.
Кольцевой связный список Может быть односвязным или двусвязным. Ключевая особенность этих списков в том, что его последний элемент содержит указатель на первый, а первый (в случае двусвязного списка) – на последний.
51 Рис. 5. Кольцевой связный список Развёрнутый связный список Каждый физический элемент содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить расход памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при малом (оптимальном) размере логических элементов и большом их количестве. Например, располагая 10 тысяч 4-байтных целых чисел в виде односвязного списка с 4-байтной адресацией, получим расход памяти 10 000 * 4 (числа) + 4 * 10 000 (адресация) = 80 000 байт. Объединяя числа в 100 массивов по 100 элементов, получим развёрнутый связный список, в котором расход памяти на адреса упадёт до 400 байт, и суммарный расход памяти составит 40400 байт.
Преимущество состоит в том, что в развёрнутый список легко добавлять новые элементы – нет необходимости переписывать весь массив. Однако, при слишком большом размере блока список начинает страдать от тех же проблем, что и обыкновенный массив: долгая вставка элементов в начало или середину, долгое удаление элементов оттуда же, и т.п., при слишком маленьком увеличивается расход памяти. ОПЕРАЦИИ С ДВУСВЯЗНЫМ СПИСКОМ Элемент (узел) списка это объект с полями: • key(ключ) – хранимые данные; • next(следующий) – указатель; • prev(предыдущий) – указатель. 52 Если prev[x] = NULL, то узел x является первым в списке. Если next[x] = NULL, то узел x является последним в списке. Указатель head[L] указывает на первый элемент списка. Если head[L] = NULL, то список пуст. 1) Процедура List_Search(L, k) позволяет найти в списке L первый элемент с ключом k путем линейного поиска, и возвращает указатель на найденный элемент. Если элемент с ключом k в списке отсутствует, возвращается значение NULL. Асимптотическая трудоемкость 𝚯(𝒏). Псевдокод процедуры:
2) Процедура List_Insert(L, x) добавляет элемент х в начало списка. Асимптотическая трудоемкость O(1). Псевдокод процедуры: 53 3) Процедура List_Delete(L, x) удаляет элемент х из связанного списка L. В процедуру необходимо передать указатель на элемент х, после чего он удаляет х из списка путем перенаправления указателей. Асимптотическая трудоемкость удаления элемент с заданным ключом 𝚯(𝒏).Чтобы удалить элемент с заданным ключом, необходимо сначала вызвать процедуру List_Search(L, k) для получения указателя на элемент. Псевдокод процедуры: 4.4. ДЕРЕВЬЯ Дерево – структура данных, представляющая собой связный, ациклический граф.
Связный граф – граф между любой парой вершин которого существует по крайней мере один путь. Ацикличность означает, что между любой парой вершин в дереве существует только один путь. Ориентированное (направленное) дерево – ацикличный орграф, в котором только одна вершина имеет нулевую степень захода, а все остальные вершины имеют степень захода 1. Корень дерева — вершина с нулевой степенью захода. Концевая вершина (лист) – вершина с нулевой степенью исхода. Дерево – конечное множество T со свойствами: существует единственный корень дерева T остальные узлы распределены среди Tiнепересекающихся множеств и каждое из множеств является деревом.
𝑚 𝑚 𝑻 = ⋃ 𝑻𝒊 , 𝑖=1 ⋂ 𝑻𝒊 = ∅. 𝑖=1 Деревья Tiназываются поддеревьями. Основные свойства структуры данных ДЕРЕВО Дерево не имеет кратных рёбер и петель. Любое дерево с n вершинами содержит n − 1 ребро. 54 Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём. Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми вершинами. Для любых трех вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.
Неориентированное дерево – степени вершин не превосходят 3. Ориентированное дерево – исходящие степени вершин не превосходят 2. Бинарное дерево – абстрактная структура данных, на которой основаны: бинарное дерево поиска бинарная куча красно-чёрное дерево АВЛ-дерево, фибоначчиева куча и др. N-арные деревья — деревья с произвольным количеством дочерних элементов. В неориентированном – степени вершин не превосходят N+1. В ориентированном исходящие степени вершин не превосходят N. Каждый узел дерева представляет собой отдельный объект. Как и в связных списках, предполагается, что каждый узел содержит ключевое поле key. Остальные поля – это указатели на другие узлы, и их вид зависит от типа дерева.
4.5. КУЧА Куча – структура данных (типа дерева), которая удовлетворяет основному свойству кучи (рис.9): если B является узлом-потомком узла A, то key(A) ≥ key(B). Элемент с наибольшим ключом всегда является корневым узлом кучи. Бинарная куча, пирамида, или сортирующее дерево – такое двоичное дерево, для которого выполнены три условия: 1. Значение в любой вершине не меньше, чем значения её потомков. 2. Каждый лист имеет глубину (расстояние до корня) либо h либо h-1. Все слои, кроме, быть может, последнего, заполнены полностью. 3. Последний слой заполняется слева направо. Над кучами обычно проводятся следующие операции: найти максимум или найти минимум удалить максимум или удалить минимум увеличить ключ или уменьшить ключ слияние: соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных добавить: добавление нового ключа в кучу Двоичная куча позволяет за время 𝚶(𝐥𝐨𝐠 𝟐 𝒏)добавлять, изменять, извлекать элемент с максимальным приоритетом.
55 Рис.9. Куча Сравнение теоретических оценок сложности вычислений Операция Двоичная Биноминальная Фибоначчиева Спаренная Найтиn) or минимум УдалитьO(log n)*O(log n)*n)n) минимум ДобавитьO(log n)O(1)*n) Уменьшить n)O(log n)*n) ключ
СлияниеO(log n)*O(1)* Таб.1.Сравнение теоретических оценок сложности вычислений Бродал
O(log n)
56 Контрольные вопросы 1. Поясните в чем заключается отличие динамического множества от статического 2. Какие стандартные операции могут совершаться с динамическим множеством? 3. Приведите примеры использования стека. 4. Опишите и поясните основные операции над стеком. 5. Приведите примеры использования очереди. 6. Опишите и поясните основные операции над очередью. 7. Дайте развернутую классификацию списков. 8. Поясните принципы организации связанных списков и приведите их классификацию. 9. Опишите организацию операции поиска элемента в связном списке. 10.Опишите организацию операции вставки элемента в связном списке. 11.Опишите организацию операции удаления элемента в связном списке. 12.Опишите основные свойства структуры данных дерево. 13.Опишите основные свойства структуры данных куча. 57 Лабораторная работа №1 Цель работы: Изучение принципов организации и работы с абстрактной структурой данных ОДНОСВЯЗНЫЙ ЛИНЕЙНЫЙ СПИСОК. Односвязный линейный список — структура данных, где каждый элемент содержит указатель только на следующий элемент. Общий вид элемента (узла) списка: data link data — информационная часть (public) link — указатель (private) Общий вид односвязного линейного списка: head 11 23 38 47 NULL Каждый элемент списка может быть описан как класс (class) или структура (struct). Информационная часть может меняться в зависимости от того, какие данные обрабатываются. Однако, присутствие указателя на следующий элемент обязательно. В простейшем случае, элемент списка можно представить в виде структуры: struct nodeType { int data; nodeType *link; };
nodeType *head, *current; Рассмотримследующийсписок: адрес head 4300 4300 адрес 2400 адрес 3700 11 data 2400 23 data 58 3700 38 data link NULL link link Тогда имеет место таблица: Переменная Значение head head->data head->link head->link->data 4300 11 2400 23 Пусть указатель current будет копией указателя head: current = head; В памяти компьютера это будет выглядеть следующим образом: адрес head 4300 4300 адрес 2400 адрес 3700 11 Data 2400 23 data 3700 link 38 data link NULL link 4300 current Для указателя current имеет место та же самая таблица: Переменная Значение current current->data current->link current->link->data Если теперь 4300 11 2400 23 current = current->link; тов памяти компьютера произойдёт следующее: адрес head 4300 4300 адрес 2400 адрес 3700 11 data 2400 23 data 3700 38 data link NULL link link current 2400 59 В этом случае таблица для указателя current будет выглядеть так: Переменная Значение current current->data current->link current->link->data 2400 23 3700 38 При этом указатель head остаётся без изменеия и «указывает», как и прежде, на первый элемент списка. Доступ к любому элементу списка можно получить с помощью обоих указателей, — head или current, но перемещаться по списку можно лишь в одном направлении — от текущего элемента к следующему слева направо:
Переменная Значение head->link->link head->link->link->data head->link->link->link current->link->link current->link->data current->data current->link 3700 38 NULL NULL 38 23 3700 Имея в своём распоряжении указатель current, можно легко «пройти» по списку от начала до конца. Например, вывести информационную часть жүктеу/скачать 3,71 Mb. Достарыңызбен бөлісу:
|