Лекция 1.6 (Структуры, рекурсия). Структуры и алгоритмы обработки данных Понятие структуры данных (окончание). Рекурсивный алгоритм (начало)

• Название: Структуры и алгоритмы обработки данных Понятие структуры данных (окончание). Рекурсивный алгоритм (начало)
• Дата: 26.05.2022
• Размер: 5.49 Mb.
• Имя файла: Лекция 1.6 (Структуры, рекурсия).pptx
• Тип: Документы; #551032

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

7. Понятие структуры данных (окончание).

8. Рекурсивный алгоритм (начало).

Рысин М.Л.

7. Понятие структуры данных

Структура данных (data structure)

Это именованная совокупность логически связанных значений в памяти ЭВМ в соответствии с определённым макетом
Макет задаёт:

Логические (причинно-следственные) связи между элементами
Способ доступа к значениям (прямой или последовательный);

Один и тот же макет может быть эффективен для одних операций и неэффективен для других (нет универсальной структуры)
Изображение структур часто – в виде графа. →

Виды структур данных

По характеру связи:

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

Графовые – дерево, лес, граф
Теоретико-множественные – реляционные.


Пример – структура доменов в DNS.

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

Статические (определены в коде на этапе компиляции)
Динамические (создаются на этапе исполнения кода).

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

Векторные (вектор, массив) →
Списочные – связанные линейные списки:

Однонаправленный список
Двунаправленный список.

Сеть.

Вектор –

Это линейная структура хранения для многоэлементных структур данных
Состоит из нескольких последовательно расположенных ячеек в памяти ЭВМ
Ячейка хранит только значение без ссылочных связей с другими ячейками
Если все значения (элементы данных) одного типа, то все ячейки одинакового размера
Дескриптор вектора – управляющая информация
В однородном векторе А доступ к элементу с индексом i по адресу Аi: Аi=A0+(i-m)*l
Реализация в ЯВУ – массив.

Линейные списочные структуры данных –

Списки →
Стеки (LIFO)
Очереди (FIFO)
Деки.

Связные линейные списки (1/2)

Структура хранения предназначена для многоэлементных структур данных
Ячейка (элемент списка, узел) хранит значение и связь (ссылку) с другими ячейками списка
В зависимости от количества связей в элементе различают:

однонаправленные (или односвязные)
двунаправленные (двухсвязные) списки.

Для организации таких структур в ЯВУ используются указатели
Не существует понятия позиции (индекса) узла.

Линейные связные списки (2/2)

Однонаправленный список

Двунаправленный список

Пример использования: линейный односвязный список

Это вырожденный вариант древовидной структуры – цепь элементов данных (информационных записей)
Каждый элемент в списке содержит как полезные данные, так и служебную информацию – ссылку на следующий элемент в списке
Chain (англ.) - цепь.

Транзакция в БД

Транзакция – это неделимая (атомарная) совокупность коротких операций над данными, переводящая БД из одного целостного состояния в другое
Транзакция считается достоверной, когда проверены формат записи о ней и её подпись (ЭЦП)
Транзакция завершена, когда запись о ней внесена в реестр (журнал) транзакций. →

Реестр транзакций

Реестр (регистр) – это совокупность записей о транзакциях – записи можно только добавлять, изменять их нельзя
Т.о. реестр – это БД об операциях над элементами другой (возможно, распределённой) БД
Нет возможности редактирования реестра, только добавление
Реестр транзакций может быть также распределённым.

Блок

Реестр транзакций может быть организован как линейный связный список (цепь) блоков записей о транзакциях
Блок содержит:

Заголовок:

хеш новых транзакций, хеш предыдущего блока, служебная информация

Записи о новых транзакциях

Внутри блока используется древовидное хеширование транзакций.

Блокчейн

Блокчейн – это технология реализации децентрализованной сетевой службы на основе БД по определенной предметной области
Реестр транзакций – это реплицированная распределенная БД записей о транзакциях над предметной БД
Реестр транзакций – цепь (линейный связный список) блоков записей о транзакциях над предметной БД
Блоки упорядочены в цепь по хешам предыдущих блоков в своих заголовках.

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

Создать структуру или новый элемент структуры;
Вставить или добавить элемент в структуру;
Найти нужный элемент в структуре;
Удалить элемент из структуры.

Пример реализации линейного однонаправленного списка на С++

Последовательность действий:

структура узла; →
конструктор списка с указателями на первый (и последний) узлы;
функция проверки наличия узлов в списке (список не пуст);
функция добавления элемента в конец списка;
функция печати списка;
функция поиска узла в списке по ключу;
функция удаления узла по ключу.

Узел однонаправленного списка (С++)

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

list l;

Реализация однонаправленного списка на С++ (1/6)

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

Реализация однонаправленного списка на С++ (2/6)

В первом случае используем функцию проверки наличия узлов:
Если список пуст, указатели на первый и последний узел направляем на единственный новый узел
Иначе указываем, что новый узел стоит после последнего, после чего обновляем значение указателя last:

Реализация однонаправленного списка на С++ (3/6)

В структуре list в функции печати всего списка (если список не пуст) направляем указатель p на первый узел и выводим значения узлов, пока p не пуст
При каждой итерации перенаправляем p на следующий узел:

Реализация однонаправленного списка на С++ (4/6)

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

Реализация однонаправленного списка на С++ (5/6)

Добавим в структуру list функцию удаления узла из списка по заданному ключу. Если список не пуст, то возможны три случая:
узел с искомым значением – первый в списке;
узел с искомым значением – последний;
не первый и не второй случаи.
Первый случай: сравниваем значение первого узла с ключом, если значения совпадают, тогда вызываем функцию удаления первого узла.
Второй случай: сравниваем значение последнего узла с ключом, если значения совпадают, тогда вызываем функцию удаления последнего узла.
Третий случай:
Создаются указатели slow на первый узел, и fast – на следующий после первого. Затем, пока fast не пустой и пока значение текущего узла fast не равно ключу, при каждой итерации перенаправляем slow и fast на следующий после них узел. Если указатель fast пустой, то сообщаем об ошибке, иначе просто удаляем узел fast. →

Реализация однонаправленного списка на С++ (6/6)

Пример работы со стеком на С++

Нелинейные структуры данных (1/2)

Позволяют выражать более сложные отношения между элементами
Множество предметных областей описываются нелинейно
Графовые:

Деревья и лес
Граф, сеть;

Теоретико-множественные:

Реляционные.

Нелинейные структуры данных (2/2)

Примеры:

Оглавление книги
Организационная структура предприятия
Файловая система
Пространство имён DNS
Сеть автодорог
Логистические схемы
Компьютерная сеть (топология)
Топология микросхем
Химические структуры;

Способы представления структур:

Встроенные типы данных (массивы)
Пользовательские типы (на основе указателей).

8. Рекурсивный алгоритм

Определение рекурсии

Рекурсивным называется объект, частично состоящий из самого себя или определяемый с помощью себя
Примеры:

1. Определение натурального числа:

1 есть натуральное число

Целое число, следующее за натуральным, есть натуральное число.

2. Алгоритм вычисления n!:

.

Примеры рекурсивных определений

3. Вычисление НОД двух натуральных чисел по алгоритму Евклида: если а≠0 и b ≠0 то НОД(a,b) = НОД(b,r) где r = a % b

НОД(18,4)=НОД(4,2)=НОД(2,0)=2

4. Метод Гаусса—Жордана решения систем линейных алгебраических уравнений

5. Геометрические фракталы задаются в форме бесконечной рекурсии (например, треугольник Серпинского)

6. Функция Аккермана

7. Узел однонаправленного списка:

struct node {

Titem info;

node *next; }

8. Метод декомпозиции – разделяй и властвуй

Парадигма, лежащая в основе метода:

1. Разделение задачи на несколько подзадач

2. Рекурсивное решение этих подзадач, когда объем подзадачи достаточно мал, выделенные подзадачи решаются непосредственно (получаем простейшее решение)

3. Комбинирование решения исходной задачи из решений вспомогательных подзадач.

Рекуррентное соотношение (recurrence) —

Это уравнение или неравенство, описывающее функцию с использованием её самой
Определяет природу рекурсивного алгоритма:
Рекурсивный алгоритм для вычисления значения реализуемой задачи использует на каждом шаге ранее вычисленные значения, начиная с наименьшего.

Рекурсивный процесс – через рекуррентное соотношение (1/2)

1. Вычисление xn сводится к умножению n раз, т. е. xn =x*xn-1:

2. Вычисление суммы s = 1+2+3+4+5+6+7+8+9+10:

Рекурсивный процесс – через рекуррентное соотношение (2/2)

3. Целочисленное деление a на b (где b≠0):

4. Числа Фибоначчи:

f1=1, f2=1, fn=fn-1+fn-2

 

Рекурсивный алгоритм –

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