Множества

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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