рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Логическое и машинное представление записей

Реферат Курсовая Конспект

Выберите учебное заведение

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

Логическое и машинное представление записей - раздел Образование, СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Запись - Конечное Упорядоченное Множество Полей, Характери- Зующихся...

Запись - конечное упорядоченное множество полей, характери-

зующихся различным типом данных. Записи являются чрезвычайно

удобным средством для представления программных моделей реальных

объектов предметной области, ибо, как правило, каждый такой объ-

ект обладает набором свойств, характеризуемых данными различных

типов.

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

Объект "студент" обладает свойствами:

"личный номер" - характеризуется целым положительным числом,

"фамилия-имя-отчество" - характеризуется строкой символов и т.д.

Пример: var

rec:record

num :byte; { личный номер студента }

name :string[20]; { Ф.И.О. }

fac, group:string[7]; { факультет, группа }

math,comp,lang :byte; {оценки по математике, выч.тех-}

end; {нике, ин. языку }

В памяти эта структура может быть представлена в одном из

двух видов :

а) в виде последовательности полей, занимающих непрерывную

область памяти (рис. 3.10). При такой организации достаточно

иметь один указатель на начало области и смещение относительно

начала. Это дает экономию памяти, но лишнюю трату времени на вы-

числение адресов полей записи.

@rec│+0 │+1 │+21 │+29 │+37 │+38 │+39 │

├───────┼───────────────┼──────┼──────┼─────┼─────┼─────┤

│ 24 │ Иванов В.И. │ АП │ 54 │ 4 │ 5 │ 5 │

└───────┴───────────────┴──────┴──────┴─────┴─────┴─────┘

Рис. 3.10. Представление в памяти переменной типа record

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

б) в виде связного списка с указателями на значения полей

записи. При такой организации имеет место быстрое обращение к

элементам, но очень неэкономичный расход памяти для хранения.

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

менты приведена на рис. 3.11.

Дескриптор записи

┌───────┬────────────┬────┐

│ rec │ student │ 7 │

├───────┼────┬───────┼────┤ ─┐

│ byte │ 1 │ num │ ──┼────> │

├───────┼────┼───────┼────┤ │

│ string│ 21 │ name │ ──┼────> │

├───────┼────┼───────┼────┤ │

│ string│ 8 │ fac │ ──┼────> │

├───────┼────┼───────┼────┤ │ Указатели значений

│ string│ 8 │ group │ ──┼────> ├─ полей записи

├───────┼────┼───────┼────┤ │

│ byte │ 1 │ math │ ──┼────> │

├───────┼────┼───────┼────┤ │

│ byte │ 1 │ comp │ ──┼────> │

├───────┼────┼───────┼────┤ │

│ byte │ 1 │ lang │ ──┼────> │

└───────┴────┴───────┴────┘ ┘

Рис. 3.11. Представление в памяти переменной типа record

в виде связного списка.

Примечание: для экономии объема памяти, отводимой под за-

пись, значения некоторых ее полей хранятся в самом дескрипторе,

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

ветствующие признаки.

В соответствии с общим подходом языка C дескриптор записи (в

этом языке записи называются структурами) не сохраняется до вы-

полнения программы. Поля структуры просто располагаются в смежных

слотах памяти, обращения к отдельным полям заменяются на их адре-

са еще на этапе компиляции.

Полем записи может быть в свою очередь интегрированная

структура данных - вектор, массив или другая запись. В некоторых

языках программирования (COBOL, PL/1) при описании вложенных за-

писей указывается уровень вложенности, в других (PASCAL, C) -

уровень вложенности определяется автоматически.

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

такая же. Это связано прежде всего с тем, что компилятор должен

выделить для размещения записи память. Предположим, описана за-

пись вида:

type rec = record

f1 : integer;

f2 : char[2];

f3 : rec; end;

Как компилятор будет выделять память для такой записи? Для

поля f1 будет выделено 2 байта, для поля f2 - 2 байта, а поле f3

- запись, которая в свою очередь состоит из f1 (2 байта), f2 (2

байта) и f3, которое... и т.д. Недаром компилятор C, встретив по-

добное описание, выдает сообщение о нехватке памяти.

Однако, полем записи вполне может быть указатель на другую

такую же запись: размер памяти, занимаемой указателем известен и

проблем с выделением памяти не возникает. Этот прием широко ис-

пользуется в программировании для установления связей между одно-

типными записями (см. главу 5).

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

Массивы Логическая структура фиксированным набором элементов... Операции... Важнейшая операция физического уровня над массивом доступ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Логическое и машинное представление записей

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурирован- ное множество примитивных, базовых, структур. Например, в

Векторы
ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа ти- па. Каждый элемент вектора имеет уникальный в рамках

Логическая структура
Массив - такая структура данных, которая характеризуется: - фиксированным набором элементов одного и того же типа; - каждый элемент имеет уникальный набор значений индексов;

Физическая структура
Физическая структура - это размещение элементов массива в памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая структура предс-

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

Специальные массивы
На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших раз

МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ
ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, мо- гут быть математически описаны,

ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОГО
РАЗМЕЩЕНИЯ. Один из основных способов хранения подобных разрежен- ных матриц заключается в запоминании ненулевых элементов в одно- мерном массиве и идентификации

ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
Методы последовательного размещения для представления разреженных матриц обычно позволяют быстрее выполнять операции над матрицами и более эффективно использовать память, чем мето

Множества
ЛОГИЧЕСКАЯ СТРУКТУРА. Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все зн

Числовые множества
Стандартный числовой тип, который может быть базовым для формирования множества - тип byte. Множество хранится в памяти как показано в таблице 3.3. Таблица 3.3 &

Множество из элементов перечислимого типа
Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит

Множество от интервального типа
Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит

Таблицы
Когда речь шла о записях, было отмечено, что полями записи могут быть интегрированные структуры данных - векторы, массивы, другие записи. Аналогично и элементами векторов и массив

Структурами. Поиск
В этом и следующих разделах представлен ряд алгоритмов поис- ка данных и сортировок, выполняемых на статических структурах данных, так как это характерные операции логического уро

Последовательный или линейный поиск
Простейшим методом поиска элемента, находящегося в неупоря- доченном наборе данных, по значению его ключа является последова- тельный просмотр каждого элемента набора, который про

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

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

Сортировки выборкой
СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практи- чески "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки

Еще одна модификация пузырьковой сортировки носит название
шейкер-сортировки. Суть ее состоит в том, что направления прос- мотров чередуются: за просмотром от начала к концу следует прос- мотр от конца к началу входного м

Сортировки включением
СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реа- лизации стратегии включения. Порядок алгоритма сортировки просты- ми вставками - O(N^2), ес

Сортировки распределением.
ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА.Алгоритм требует представ- ления ключей сортируемой последовательности в виде чисел в неко- торой системе счисления P. Число прохо

Таблицы прямого доступа
Простейшей организацией таблицы, обеспечивающей идеально быстрый поиск, вляется таблица прямого доступа. В такой таблице ключ является адресом записи в таблице или может быть прео

Таблицы со справочниками
Одним из способов устранения этого недостатка является метод справочников. Основная таблица содержит записи в произвольном по- рядке. В дополнение к основной строится справочная и

Хешированные таблицы и функции хеширования
Как отмечалось выше, в каждой реальной таблице фактическое множество ключей является лишь небольшим подмножеством множества всех теоретически возможных ключей. Поскольку память яв