Слайд 2
![Понятие Структура данных – это класс однородных математических объектов, ориентированный](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-1.jpg)
Понятие
Структура данных –
это класс однородных математических объектов, ориентированный на эффективное представление
данных в некотором классе задач.
это систематизированный способ организации данных и доступа к ним.
Слайд 3
![Классификация Простые Статические Полустатические Динамические Файловые](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-2.jpg)
Классификация
Простые
Статические
Полустатические
Динамические
Файловые
Слайд 4
![Простые структуры данных Числовые Символьные Логические Перечисление Интервал Указатели](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-3.jpg)
Простые структуры данных
Числовые
Символьные
Логические
Перечисление
Интервал
Указатели
Слайд 5
![Статические структуры данных Вектор Массивы Множества Записи Таблицы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-4.jpg)
Статические структуры данных
Вектор
Массивы
Множества
Записи
Таблицы
Слайд 6
![Полустатические структуры данных Стеки Очереди Деки Строки](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-5.jpg)
Полустатические структуры данных
Стеки
Очереди
Деки
Строки
Слайд 7
![Динамические структуры данных Связные списки Графы Деревья](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-6.jpg)
Динамические структуры данных
Связные списки
Графы
Деревья
Слайд 8
![Файловые структуры Последовательные Прямого доступа Комбинированного доступа](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-7.jpg)
Файловые структуры
Последовательные
Прямого доступа
Комбинированного доступа
Слайд 9
![Требования, предъявляемые к структурам данных: Эффективность представления Экономное расходование памяти Быстрый доступ к элементам структуры.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-8.jpg)
Требования, предъявляемые к структурам данных:
Эффективность представления
Экономное расходование памяти
Быстрый доступ к элементам
структуры.
Слайд 10
![Массив Массив – структура данных для представления множества элементов, однотипных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-9.jpg)
Массив
Массив – структура данных для представления множества элементов, однотипных по структуре
и способу использования.
Массивы относятся к структурам данных со случайным доступом : для выделения некоторой компоненты к имен массива добавляется индекс (значение специального типа), который можно вычислить, потому элементы массива иногда называют переменным с индексами
Слайд 11
![Базовые операции поиск элемента, равного x В произвольном массиве T(n)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-10.jpg)
Базовые операции
поиск элемента, равного x
В произвольном массиве T(n) = Θ(n).
В отсортированном массиве T(n) = Θ(log n)
поиск максимального (минимального) элемента.
В произвольном массиве T(n) = Θ(n).
В отсортированном массиве T(n) = Θ(1).
Слайд 12
![Базовые операции Обычный прием работы с массивами – это поиск](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-11.jpg)
Базовые операции
Обычный прием работы с массивами – это
поиск
выборочное изменение отдельных компонент
массива.
Основные операции над массивами не предполагают включения новых элементов или исключения элементов.
Однако на практике часто необходимо выполнять процедуры включения и исключения отдельных элементов, что приводит к необходимости разработки структур данных, поддерживающих эти операции.
Слайд 13
![Линейный список Список – упорядоченная последовательность данных, характеризующих однородные объекты,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-12.jpg)
Линейный список
Список
– упорядоченная последовательность данных, характеризующих однородные объекты, отличающиеся
значениями своих признаков.
– конечная последовательность элементов, порядок которых определяется с помощью ссылок.
Линейный список – конечная последовательность элементов (множество), структурные свойства которой ограничиваются лишь линейным (одномерным) относительным порядком элементов.
Слайд 14
![Базовые операции формирование списка (T(n) = Θ(n)) просмотр списка (T(n)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-13.jpg)
Базовые операции
формирование списка (T(n) = Θ(n))
просмотр списка (T(n) = Θ(n))
поиск некоторого
заданного элемента с ключом х (T(n) = Θ(n))
поиск максимального (минимального) элемента (T(n) = Θ(n))
включение элемента с ключом x (T(n) = Θ(1))
исключение элемента (T(n) = Θ(1))
Слайд 15
![Виды списков Однонаправленный список – список, в котором предусмотрен жесткий](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-14.jpg)
Виды списков
Однонаправленный список – список, в котором предусмотрен жесткий порядок перебора
элементов – от первого к последнему.
Двунаправленный список – список, структура которого предусматривает возможность перебора элементов как в прямом, так и в обратном порядке.
Способы представления одно- и двунаправленного списков аналогичны.
Слайд 16
![Способы реализации В виде двух массивов А и В: Пусть](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-15.jpg)
Способы реализации
В виде двух массивов А и В:
Пусть i -
индекс элемента в списке, тогда
А[i] - сам элемент,
В[i] - индекс следующего элемента в списке А. В[k] = 0, где k - индекс последнего элемента в списке.
Две переменные:
nz -индекс начала занятых компонент,
ns - индекс начала свободных компонент.
Слайд 17
![Способы реализации Список: 8, 13, 5 A: B: nz = 1, ns = 4](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-16.jpg)
Способы реализации
Список: 8, 13, 5
A:
B:
nz = 1, ns = 4
Слайд 18
![Способы реализации 2. С использованием последовательности связанных компонент (линейный список):](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-17.jpg)
Способы реализации
2. С использованием последовательности связанных компонент (линейный список): Каждая компонента
списка состоит из двух ячеек памяти (первая содержит сам элемент либо указатель на его местоположение, а вторая – указатель на следующий элемент)
Слайд 19
![Способы реализации Список: 8, 13, 5](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-18.jpg)
Способы реализации
Список: 8, 13, 5
Слайд 20
![Включение элемента в начало (конец) списка до (после) элемента, на который указывает заданная ссылка p](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-19.jpg)
Включение элемента
в начало (конец) списка
до (после) элемента, на который указывает
заданная ссылка p
Слайд 21
![Включение элемента](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-20.jpg)
Слайд 22
![Формирование списка Начиная с пустого списка последовательно включаем элементы в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-21.jpg)
Формирование списка
Начиная с пустого списка последовательно включаем элементы в начало списка.
не
надо обрабатывать отдельно ситуацию, когда включается элемент в пустой список
порядок следования элементов в списке обратен порядку их включения
Включаем элементы в конец списка.
порядок следования элементов совпадает с порядком их включения
необходимо ввести указатель на последний поступивший элемент (tail)
первый включаемый элемент обрабатывается иначе, чем остальные элементы.
Слайд 23
![Исключение элемента из списка стоящего после элемента, на который указывает](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-22.jpg)
Исключение элемента из списка
стоящего после элемента, на который указывает заданная ссылка
p.
на который указывает заданная ссылка p
р – указатель не на последний элемент
р – указатель на последний элемент.
Слайд 24
![Поиск элемента x в неупорядоченном списке Осуществляется последовательным просмотром элементов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-23.jpg)
Поиск элемента x в неупорядоченном списке
Осуществляется последовательным просмотром элементов
заканчивается либо при
обнаружении требуемого элемента, либо при достижении конца списка
чтобы оптимизировать условие окончания просмотра, будем использовать технику барьера (s.key ← x)
переменная head указывает на начало списка
для того, чтобы процедура отработала правильно в случае когда список пустой, необходимо при формировании списка выполнить оператор: head ← s.
Слайд 25
![Поиск элемента x в упорядоченном списке можно заканчивать при обнаружении](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-24.jpg)
Поиск элемента x в упорядоченном списке
можно заканчивать при обнаружении первого ключа,
со значением большем x.
упорядоченность списка достигается путем включения нового элемента в подходящее для него место, что позволяет полностью использовать гибкость списковой структуры.
Однако, даже упорядоченные линейные списки не позволяют организовать ничего подобного на двоичный поиск в массивах.
Слайд 26
![Операции работы со списками Конкатенация (сцепление) двух списков. В результате](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-25.jpg)
Операции работы со списками
Конкатенация (сцепление) двух списков. В результате образуется единый
список.
T = Θ(1), если имеются адреса первого и последнего элементов списков.
Если известны только начальные адреса, то Т = Θ(n+ m), где n, m – количество элементов в сцепляемых списках. Или Т = O(max{n, m})
Расцепление списка.
T = Θ(1), если известен указатель на элемент непосредственно предшествующий месту расцепления.
Слайд 27
![Стек Стек – линейный однонаправленный список, в котором все включения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-26.jpg)
Стек
Стек – линейный однонаправленный список, в котором все включения и исключения
элементов (и обычно всякий доступ) делаются в одном конце списка.
Реализуется принцип “последний вошел – первый вышел” (last-in, first-out – LIFO).
Слайд 28
![Представление стека Если заранее известно максимальное количество элементов, одновременно хранящихся](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-27.jpg)
Представление стека
Если заранее известно максимальное количество элементов, одновременно хранящихся в стеке,
то целесообразно моделировать стек на массиве постоянной длины.
Переменная top содержит индекс последнего включенного стек элемента (первоначально top = 0).
В случае, когда количество элементов заранее неизвестно, стек может быть реализован виде списковой структуры.
Переменная top содержит адрес последнего включенного в стек элемента (первоначально top = null).
Слайд 29
![Базовые операции Операция добавления элемента в стек часто обозначается Push,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-28.jpg)
Базовые операции
Операция добавления элемента в стек часто обозначается Push, а операция
удаления – Pop.
Трудоемкость процедур включения и исключения элемента из стека есть Θ(1).
Слайд 30
![Очередь Очередь – линейный список, в котором все включения элементов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-29.jpg)
Очередь
Очередь – линейный список, в котором все включения элементов производятся
в одном конце списка, а все исключения (и обычно всякий доступ) делаются в другом его конце.
Реализуется принцип “первый вошел первый вышел” (first-in, first-out – FIFO).
Слайд 31
![Очередь Если максимальное количество элементов, одновременно хранящихся в очереди не](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-30.jpg)
Очередь
Если максимальное количество элементов, одновременно хранящихся в очереди не превосходит
l, то можно смоделировать очередь на массиве постоянной длины l.
Переменные head и tail, определяют индексы первого и последнего элементов очереди (первоначально head= 1 и tail =0);
В случае циклической очереди необходима переменная булевского типа empty, которая равна true в случае, когда очередь пуста.
Слайд 32
![Очередь Если количество элементов очереди заранее не известно, то для](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/266529/slide-31.jpg)
Очередь
Если количество элементов очереди заранее не известно, то для реализации очереди
используются списковые структуры.
Переменная head содержит адрес первого элемента очереди, а tail – адрес последнего элементов очереди (первоначально head, tail = null).
Трудоемкость процедур включения и исключения элемента из очереди есть Θ(1).