Статические структуры данных

Структуры данных

Конспект лекций

Лекция 4 - 5

Статические структуры данных

Научный редактор доц., д-р техн. наук Л.Г. Доросинский

Екатеринбург

Содержание

1. Статические структуры данных 3

2. Векторы 4

3. Массивы 6

3.1. Логическая структура 6

3.2. Физическая структура 6

3.3. Операции 7

3.4. Адресация массивов с помощью векторов Айлиффа 8

3.5. Специальные массивы 9

3.5.1. Массивы с математическим описанием местоположения нефоновых элементов 10

3.5.2. Разреженные массивы со случайным расположением элементов 12

3.5.3. Представление разреженных матриц методом связанных структур 13

4. Множества (в языке Pascal) 15

4.1. Логическая структура 15

4.2. Физическая структура 15

4.3. Числовые множества 15

4.2. Символьные множества 16

4.3. Множество из элементов перечислимого типа 16

4.4. Множество от интервального типа 17

4.5. Операции над множествами 17

5. Записи 19

5.1. Логическое и машинное представление записей 19

5.2. Операции над записями 21

5.3. Записи с вариантами 21

6. Таблицы 25

6.1. Операции логического уровня над статическими структурами. Поиск 26

6.1.1. Последовательный или линейный поиск 27

6.1.2. Бинарный поиск 27

Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурированное множество примитивных, базовых, структур. Например, вектор может быть представлен упорядоченным множеством чисел. Поскольку по определению статические структуры отличаются отсутствием изменчивости, память для них выделяется автоматически - как правило, на этапе компиляции или при выполнении - в момент активизации того программного блока, в котором они описаны. Ряд языков программирования допускают размещение статических структур в памяти на этапе выполнения по явному требованию программиста, но и в этом случае объем выделенной памяти остается неизменным до уничтожения структуры. Выделение памяти на этапе компиляции является столь удобным свойством статических структур, что в ряде задач программисты используют их даже для представления объектов, обладающих изменчивостью. Например, когда размер массива неизвестен заранее, для него резервируется максимально возможный размер.

Каждую структуру данных характеризуют её логическим и физическим представлениями. Очень часто говоря о той или иной структуре данных, имеют в виду её логическое представление. Физическое представление обычно не соответствует логическому и, кроме того, может существенно различаться в разных программных системах. Нередко физической структуре ставится в соответствие дескриптор, или заголовок, который содержит общие сведения о физической структуре. Дескриптор необходим, например, в том случае, когда граничные значения индексов элементов массива неизвестны на этапе компиляции, и, следовательно, выделение памяти для массива может быть выполнено только на этапе выполнения программы. Дескриптор хранится, как и сама физическая структура, в памяти и состоит из полей, характер, число и размеры которых зависят от той структуры, которую он описывает, и от принятых способов ее обработки. В ряде случаев дескриптор является совершенно необходимым, так как выполнение операции доступа к структуре требует обязательного знания каких-то ее параметров, и эти параметры хранятся в дескрипторе. Другие хранимые в дескрипторе параметры не являются совершенно необходимыми, но их использование позволяет сократить время доступа или обеспечить контроль правильности доступа к структуре. Дескриптор структуры данных, поддерживаемый языками программирования, является "невидимым" для программиста; он создается компилятором и компилятор же, формируя объектные коды для доступа к структуре, включает в эти коды команды, обращающиеся к дескриптору. Статические структуры в языках программирования связаны со структурированными типами. Структурированные типы в языках программирования являются теми средствами интеграции, которые позволяют строить структуры данных сколь угодно большой сложности. К таким типам относятся: массивы, записи (в некоторых языках - структуры) и множества (этот тип реализован не во всех языках).

Дата добавления: 2014-01-07