АТД и структура данных

Assert

Assert- заголовочный файл стандартной библиотеки языка программирования С#, в котором объявляется макрос препроцессора языка С assert (). Данный макрос реализует исключение, которое может использоваться для проверки сделанных программой вычислений.

- инструмент отладки: -взаимодействует с пользователем

-проверка отсутствует в «продуктовом коде»

-дополнительное документирование кода.

- проверяет исходное выражение, если false- кид. исключение

- контроль внутренних деталей реализации

- может дублировать исключения

Девид. Assert (bool_expr, message)

Ассоциативный массив и варианты реализации

- абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающее операции дополнения пары, а также поиска и удаления пары по ключу:

(«быстрый» поиск значения по ключу)

Insert (ключ, значение)

Find (ключ)

Remove (ключ)

Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами.

- Операции: создание, уничтожение, добавление элемента, удаление элемента, поверка на пустоту, получение значения по ключу

- Реализация: дерево, хеш-таблица, динамический массив(его размеры могут меняться) (сортированный), список (сортированный)

3.Абстрактный Тип Данных «множество» и варианты реализации

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

- Данные типа «множество» позволяют хранить ограниченное число значений определенного типа без определенного порядка.

-динамическая структура данных

- набор уникальных элементов

- «быстрая» проверка наличия значения

- Операторы: объединение, пересечение, заполнение, разность и др.

-Операции: создание, уничтожение, добавление элемента, удаление элемента, проверка на пустоту, проверка элемента на вхождение, получение размера

- Реализация: дерево, хеш-таблица, битовый массив, динамический массив (сортированный), список (сортированный)

4. АТД “cтек” и варианты реализации

- динамическая структура данных

-упорядоченный набор элементов

- LIFO (last in first out) -добавление и удаление элементов с одного конца, называется вершиной стека

-Операции: создание, уничтожение, добавление элемента, удаление элемента, проверка на пустоту, получение значения верхнего элемента.

- Стек реализации: Динамический массив, Линейный список

- Стек (динамический массив): - физический и логический размер

- добавление в «конец»

- удаление из «конца»

- проверка логического размера

- доступ к последнему элементу

- Стек (линейный список): - добавление в «голову»

- удаление из «головы»

- проверка наличия элементов

- доступ к голове

5.АТД «динамический массив» и варианты реализации Размеры этого массива может меняться.Массив- доступ к элементу по его индексуОперации: -создание, -уничтожение, -присваивание, -получение доступа к элементу по индексу, -получение размера -изменение размера 6.АТД «дэк» и варианты реализации, двусвязная очередь Добавление и извлечение элементов возможно с обоих концов

PushBack, popBack, pushFront, popFront

Реализация: -динамический массив(вставка и извлечение с концов)

-динамический массив (подвижные концы)

- список

7.АТД “массив фиксированного размера” и варианты реализации

Массив-тип данных для хранения других типов, хранилище для данных

- Имеется размер (типа хранимых данных, один тип) - получение размера

[ i ]-обращение к элементу

0,1,2..(size-1) size-размер

-Массив ---> фиксированный размер-нельзя изменить

---> динамический, можно менять размер

-Метод RESIZE меняет количество элементов, которые хранятся в массиве.

- Массивы фиксированного размера- встроенные

-Элементы массива в памяти расположены последовательно, что позволяет производить быстрый поиск по индексу

8.АТД “матрица” и варианты реализации Матрица- математический объект, допускающий запись и хранение однотипных данных /чисел и допускающий алгебраические операции (сложение, вычитание, умножение) между ними и другими подобными объектами.

-Операции: -создание,

-уничтожение,

-получение доступа к элементу по индексу (i,j),

-получение размера по измерению

- Алгебраические операции: -умножение на число

-сложение двух матриц

-умножение двух матриц

- Дополнительные операции: -изменение размера по измерению

-транспонирование

-вставка/удаление столбца/строки

-перестановка двух строк/столбцов

-умножение на число строки/столбца

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

-размеры

-массив элементов (i,j)->i*nCol + j

- массив строк столбцов

9.АТД “очередь с приоритетом” и варианты реализации

-пара <ключ, данные>

-порядок извлечения элементов определяется ключом, а не порядком добавления элемента в очередь

-реализация: -список (сортировка при вставке)

- дерево (сортирующее)

-массив (сортировка при вставке)

10.АТД “очередь” и варианты реализации

-динамическая структура данных

-упорядоченный набор элементов

- FIFO (first in first out)-добавление элементов с одного конца (хвоста) и удаления из другого (головы)

- Операции: -создание,

-уничтожение,

-добавление элемента

-удаление элемента

-проверка на пустоту

-получение значения верхнего элемента

11.АТД “полином” и варианты реализации

F(x)=a₀*x⁰+a₁*x¹+…+a_nxⁿ

а_i-коэффициент

i- показатель степени (неотрицательное число)

х- переменная

- Степень многочлена-максимальный показатель степени (для 0 не определен)

- Операции:- создание (одночлен)

- уничтожение

- сложение полиномов

- умножение полиномов

-получение коэффициентов при заданном показателе степени

-вычисление значения

- Представление полинома: -массив a_n, n=0, N

-массив пар {n, a_n}

-список пар {n, a_n}

- Оптимизация: - выбор способа хранения в зависимости от разреженности и размерности

- для разреженных – хранение в упорядоченном виде (поддержание упорядочения при вставке членов)

12.АТД “число” и варианты реализации

Число – простейший и самый распространённый в программировании тип данных, представляет собой целочисленное значение (integer). Различают числа без знака и со знаком (+ или -). Количество чисел в машинном изображении множества целых чисел зависит от длины машинного слова, обычно выражаемой в битах. Например, при длине машинного слова 1 байт (8 бит) диапазон представимых целых чисел со знаком от -128 до 127. В беззнаковом формате байтововое представление числа будет от 0 до 255 (28 - 1). Если используется 32-разрядное машинное слово, то целое со знаком будет представлять значения от −2 147 483 648 (-231) до 2 147 483 647 (231−1); всего 1 0000 000016 (4 294 967 29610) возможных значений.-создание

-уничтожение

-Операции: 1.присваивание

2.сравнение = =;!=, <, <=, >=, >

3. арифметические операции -,+,/,*,-=,+=,/=,*=

4. Ввод и вывод:

-Встроенные типы: 1.Целые

2.Вещественные

-Классы: 1.Комплексные

2.Рациональные

3.«Длинная арифметика»

АТД и структура данных

-Абстрактный тип данных: -создание/уничтожение

-набор операций

-Структура данных: -реализация АТД

-способы организации в памяти

-Структура данных: массив, список, дерево, графа

14.базовые принципы ООП Для поддержки принципов объектно-ориентированного программирования все ООП-языки, включая C#, имеют три характерных черты: инкапсуляцию, полиморфизм и наследование.

-Абстракция

-Инкапсуляция: -сокрытие

-пользовательские типы данных

-Наследование

-Полиморфизм: -перегрузка функций

- «шаблонный» код (generics, templates)

-виртуальный вызов

-Инкапсуляция - свойство системы, позволяющее объединить данные и методы, работающие с ними в классе, и скрыть детали реализации от пользователя

-Наследование – свойство системы, позволяющее описать новый класс на основе уже существующего с частично или полностью заимствующейся функциональностью. Класс, от которого производится наследование, называется базовым или родительским, новый класс-потомком, наследником или производным классом.

-Полиморфизм-свойство системы использовать объекты с одинаковым интерфейсом без информации о типе и внутренней структуре объекта (перегрузка, шаблонный виртуальный вызов)

Встроенные типы -> способ хранения

-> способ интерпретации

-> допустимые операции

Простые -> порядковые-целочисленный, логический, символьный

-> вещественные

-> строковые