Таблицы - раздел Образование, СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Когда Речь Шла О Записях, Было Отмечено, Что Полями Записи
Могут Быт...
Когда речь шла о записях, было отмечено, что полями записи
могут быть интегрированные структуры данных - векторы, массивы,
другие записи. Аналогично и элементами векторов и массивов могут
быть также интегрированные структуры. Одна из таких сложных
структур - таблица. С физической точки зрения таблица представля-
ет собой вектор, элементами которого являются записи. Характерной
логической особенностью таблиц, которая и определила их рассмот-
рение в отдельном разделе, является то, что доступ к элементам
таблицы производится не по номеру (индексу), а по ключу - по зна-
чению одного из свойств объекта, описываемого записью-элементом
таблицы. Ключ - это свойство, идентифицирующее данную запись во
множестве однотипных записей. Как правило, к ключу предъявляется
требование уникальности в данной таблице. Ключ может включаться в
состав записи и быть одним из ее полей, но может и не включаться
в запись, а вычисляться по положению записи. Таблица может иметь
один или несколько ключей. Например, при интеграции в таблицу за-
писей о студентах (описание записи приведено в п.3.5.1) выборка
может производиться как по личному номеру студента, так и по фа-
милии.
Основной операцией при работе с таблицами является операция
доступа к записи по ключу. Она реализуется процедурой поиска.
Поскольку поиск может быть значительно более эффективным в табли-
цах, упорядоченных по значениям ключей, довольно часто над табли-
цами необходимо выполнять операции сортировки. Эти операции расс-
матриваются в следующих разделах данной главы.
Иногда различают таблицы с фиксированной и с переменной дли-
ной записи. Очевидно, что таблицы, объединяющие записи совершенно
идентичных типов, будут иметь фиксированные длины записей. Необ-
ходимость в переменной длине может возникнуть в задачах, подобных
тем, которые рассматривались для записей с вариантами. Как прави-
ло таблицы для таких задач и составляются из записей с варианта-
ми, т.е. сводятся к фиксированной (максимальной) длине записи.
Значительно реже встречаются таблицы с действительно переменной
длиной записи. Хотя в таких таблицах и экономится память, но воз-
можности работы с такими таблицами ограничены, так как по номеру
записи невозможно определить ее адрес. Таблицы с записями пере-
менной длины обрабатываются только последовательно - в порядке
возрастания номеров записей. Доступ к элементу такой таблицы
обычно осуществляется в два шага. На первом шаге выбирается пос-
тоянная часть записи, в которой содержится - в явном или неявном
виде - длина записи. На втором шаге выбирается переменная часть
записи в соответствии с ее длиной. Прибавив к адресу текущей за-
писи ее длину, получают адрес следующей записи.
Так таблица с записями переменной длины может, например,
рассматриваться в некоторых задачах программируемых в машинных
кодах. Каждая машинная команда - запись, состоит из одного или
нескольких байт. Первый байт - всегда код операции, количество и
формат остальных байтов определяется типом команды. Процессор вы-
бирает байт по адресу, задаваемому программным счетчиком, и опре-
деляет тип команды. По типу команды процессор определяет ее длину
и выбирает остальные ее байты. Содержимое программного счетчика
увеличивается на длину команды.
записи в соответствии с ее длиной. Прибавив к адресу текущей за-
писи ее длину, получают адрес следующей записи.
Так таблица с записями переменной длины может, например,
рассматриваться в некоторых задачах программируемых в машинных
кодах. Каждая машинная команда - запись, состоит из одного или
нескольких байт. Первый байт - всегда код операции, количество и
формат остальных байтов определяется типом команды. Процессор вы-
бирает байт по адресу, задаваемому программным счетчиком, и опре-
деляет тип команды. По типу команды процессор определяет ее длину
и выбирает остальные ее байты. Содержимое программного счетчика
увеличивается на длину команды.
Все темы данного раздела:
СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Статические структуры относятся к разряду непримитивных
структур, которые, фактически, представляют собой структурирован-
ное множество примитивных, базовых, структур. Например, в
Векторы
ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура
данных с фиксированным числом элементов одного и того же типа ти-
па. Каждый элемент вектора имеет уникальный в рамках
Логическая структура
Массив - такая структура данных, которая характеризуется:
- фиксированным набором элементов одного и того же типа;
- каждый элемент имеет уникальный набор значений индексов;
Физическая структура
Физическая структура - это размещение элементов массива в
памяти ЭВМ. Для случая двумерного массива, состоящего из
(k1-n1+1) строк и (k2-n2+1) столбцов физическая структура предс-
Адресация элементов с помощью векторов Айлиффа
Из выше приведенных формул видно, что вычисление адреса эле-
мента многомерного массива может потребовать много времени, пос-
кольку при этом должны выполняться операции сложения
Специальные массивы
На практике встречаются массивы, которые в силу определенных
причин могут записываться в память не полностью, а частично. Это
особенно актуально для массивов настолько больших раз
МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ
ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых
местоположения элементов со значениями отличными от фонового, мо-
гут быть математически описаны,
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОГО
РАЗМЕЩЕНИЯ. Один из основных способов хранения подобных разрежен-
ных матриц заключается в запоминании ненулевых элементов в одно-
мерном массиве и идентификации
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
Методы последовательного размещения для представления разреженных
матриц обычно позволяют быстрее выполнять операции над матрицами
и более эффективно использовать память, чем мето
Множества
ЛОГИЧЕСКАЯ СТРУКТУРА. Множество - такая структура, которая
представляет собой набор неповторяющихся данных одного и того же
типа. Множество может принимать все зн
Числовые множества
Стандартный числовой тип, который может быть базовым для
формирования множества - тип byte.
Множество хранится в памяти как показано в таблице 3.3.
Таблица 3.3
&
Множество из элементов перечислимого типа
Множество, базовым типом которого есть перечислимый тип,
хранится также, как множество, базовым типом которого является
тип byte. Однако, в памяти занимает место, которое зависит
Множество от интервального типа
Множество, базовым типом которого есть интервальный тип,
хранится также, как множество, базовым типом которого является
тип byte. Однако, в памяти занимает место, которое зависит
Логическое и машинное представление записей
Запись - конечное упорядоченное множество полей, характери-
зующихся различным типом данных. Записи являются чрезвычайно
удобным средством для представления программных моделей ре
Структурами. Поиск
В этом и следующих разделах представлен ряд алгоритмов поис-
ка данных и сортировок, выполняемых на статических структурах
данных, так как это характерные операции логического уро
Последовательный или линейный поиск
Простейшим методом поиска элемента, находящегося в неупоря-
доченном наборе данных, по значению его ключа является последова-
тельный просмотр каждого элемента набора, который про
Бинарный поиск
Другим относительно простым методом доступа к элементу явля-
ется метод бинарного (дихотомического, двоичного) поиска, который
выполняется в заведомо упорядоченной последовательно
Структурами. Сортировка
Для самого общего случая сформулируем задачу сортировки та-
ким образом: имеется некоторое неупорядоченное входное множество
ключей и должны получить выходное множество тех же клю
Сортировки выборкой
СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практи-
чески "дословно" сформулированную выше стратегию выборки. Порядок
алгоритма простой выборки
Еще одна модификация пузырьковой сортировки носит название
шейкер-сортировки. Суть ее состоит в том, что направления прос-
мотров чередуются: за просмотром от начала к концу следует прос-
мотр от конца к началу входного м
Сортировки включением
СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реа-
лизации стратегии включения. Порядок алгоритма сортировки просты-
ми вставками - O(N^2), ес
Сортировки распределением.
ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА.Алгоритм требует представ-
ления ключей сортируемой последовательности в виде чисел в неко-
торой системе счисления P. Число прохо
Таблицы прямого доступа
Простейшей организацией таблицы, обеспечивающей идеально
быстрый поиск, вляется таблица прямого доступа. В такой таблице
ключ является адресом записи в таблице или может быть прео
Таблицы со справочниками
Одним из способов устранения этого недостатка является метод
справочников. Основная таблица содержит записи в произвольном по-
рядке. В дополнение к основной строится справочная и
Хешированные таблицы и функции хеширования
Как отмечалось выше, в каждой реальной таблице фактическое
множество ключей является лишь небольшим подмножеством множества
всех теоретически возможных ключей. Поскольку память яв
Новости и инфо для студентов