Концепция типа данных. Фундаментальные структуры данных

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

На сегодняшнем занятии мы обсудим основные методы организации данных используемых в компьютерных программах. Для многих задач выбор подходящей структуры данных является самым главным решением принимаемым в процессе их реализации: как только выбор сделан, требуется только применять очень простые алгоритмы. Для одних и тех же данных, разные структуры требуют большие или меньшие объемы памяти чем другие. Некоторые структуры данных ведут к более эффективным алгоритмам, а некоторые к менее. Этот вопрос будет часто появляться на свет в ходе изучения данного курса, так как выбор алгоритмов и структур данных очень тесно связаны друг с другом, и мы будем постоянно искать способы экономии места или времени пытаясь сделать наиболее подходящий выбор.

Структура данных это не пассивный объект: мы должны также продумать множество операций выполняемых над ней (и алгоритмы используемые в этих операциях). Эта концепция формализуется концепцией абстрактного типа данных, который мы обсудим в конце этого занятия. Но нашим островным интересом является конкретная реализация, и поэтому мы сфокусируем наше внимание главным образом на некоторыми специфичными представлениями этих структур и их манипулированием.

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

Тип данных определяет:

1. Формат представления в памяти компьютера

2. Множество допустимых значений, которые может принимать принадлежащая к выбранному типу переменная или константа

3. Множество допустимых операций, применимых к этому типу.

Основные (интересующие нас) типы данных в BP:

1. Простые типы

1. Целочисленные типы

2. Логический тип

3. Символьный тип

4. Перечисляемый тип

5. Интервальный тип

6. Вещественный тип

2. Структурированные типы

1. Массив

2. Множество

3. Запись

Простые типы

Поиск по сайту: