- •Типы и структуры данных. Опредления, классифиация.
- •Простые типы данных, операции над ними. Сильная и слабая типизация.
- •Массивы. Операции, способы предсавления, сложность операций.
- •Записи. Операции над ними, способы представления, сложность операций.
- •Объединения. Операции, представление. Сложность операций.
- •Множества. Операции, способы представления, сложность операций.
- •Последовательности вкратце
- •Линейные списки
- •Очереди.
- •Линейный список, сложность операции o(1)
- •Динамические струкутуры данных. Работа динамической памяти в c.
- •Деревья. Определения, классификация, способы представления.
- •Двоичные деревья, операции.
- •Дерево поиска. Основные операции, вычисление средней длины пути.
- •Виды сбалансированных деревьев, достоинства и недостатки.
- •Дерево оптимального поиска
- •Красно-черные деревья.
- •Splay-деревья.
- •Асоциативные массивы и хэши
Типы и структуры данных. Опредления, классифиация.
Тип данных — фундаментальное понятие теории программирования. Тип данных определяет множество значений, набор операций, которые можно применять к таким значениям и, возможно, способ реализации хранения значений и выполнения операций. Любые данные, которыми оперируют программы, относятся к определённым типам.
Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных. Структура данных поддерживает определенный порядок доступа к ним. Структуру данных можно рассматривать как своего рода склад или библиотеку.
Основные принципы концепции типа:
Любой тип данных определяет множество значений, к которым может относиться некоторая константа, которое может принимать переменная, или выражение и которое может формироваться операцией или функцией;
Тип любой величины, обозначаемой константой, переменной или выражением, может быть введен по ее виду или по ее описанию, для этого нет необходимости проводить какие-либо вычисления;
Каждая операция или функция требует аргументов определенного типа и дает результат также фиксированного типа. Если операция допускает аргументы нескольких типов, то тип результата регламентируется вполне определенными правилами языка.
Типы данных – простые типы (не содержат внутри себя никаких других типов).
Предопределенные (integer, character, boolean, float) – типы, имеющиеся (строенные) на большинстве выч. машин. Все, кроме вещественного, упорядочены.
Перечисляемый – новый, простейший тип, определяющийся простым перечислением входящих в него различных значений (enum color {red, blue, green};
Диапазонный – используется, когда переменной присваивается значение некоторого типа, лежащее только внутри определенного интервала значений (type index = 1..10).
Структуры данных – составные типы (определяются с помощью простых типов, их значения обычно представляют собой совокупности значений компонент, относящихся к составляющим их типам; если составляющий тип один, то он называется базовым).
Статические (массивы, строки, записи (структуры), объединения, множества, последовательности) – память под них выделяется во время компиляции и сохраняется в течение всей работы программы.
Динамические - память под величины отводится во время выполнения программы, а в процессе вычислений изменяются не только значения переменных, но и структура.
Нерекурсивные (массивы);
Рекурсивные (линейные списки, стеки, очереди, деревья, графы) – с применением рекурсии для описания и обработки данных.
Преимущества от использования типов данных:
Надёжность. Типы данных защищают от трёх видов ошибок:
Некорректное присваивание. Пусть переменная объявлена как имеющая числовой тип. Тогда попытка присвоить ей символьное или какое-либо другое значение в случае статической типизации приведёт к ошибке компиляции и не даст такой программе запуститься. В случае динамической типизации код программы перед выполнением потенциально опасного действия сравнит типы данных переменной и значения и также выдаст ошибку. Всё это позволяет избежать неправильной работы и «падения» программы.
Некорректная операция. Позволяет избежать попыток применения выражений вида «Hello world» + 1. Поскольку, как уже говорилось, все переменные в памяти хранятся как наборы битов, то при отсутствии типов подобная операция была выполнима (и могла дать результат вроде «ello worldǼ»). С использованием типов (см. далее «Контроль типов») такие ошибки отсекаются опять же на этапе компиляции.
Некорректная передача параметров. Если функция «синус» ожидает, что ей будет передан числовой аргумент, то передача ей в качестве параметра строки «Hello world» может иметь непредсказуемые последствия. При помощи контроля типов такие ошибки также отсекаются на этапе компиляции.
Стандартизация.