- •1. Архитектура машинной памяти
- •2. Адресация памяти
- •3. Три уровня представления данных
- •4.Внутренняя структура записи
- •5. Типы структур данных
- •7. Массивы
- •8. Стеки
- •9.Очередь
- •10. Таблица
- •11. Способы размещения, основанные
- •12.Сортировка. Метод выбора
- •13. Метод обмена (пузырька)
- •14. Метод вставок
- •15. Метод подсчета
- •16. Метод Шелла
- •17.Внешняя сортировка
- •18. Последовательный поиск
- •19. Ускоренные методы поиска. Двоичный поиск. Блочный поиск
- •20.Поиск по двоичному дереву
4.Внутренняя структура записи
Логическая запись состоит из отдельных элементов, связанных определенными отношениями, и имеет многоуровневую структуру.
Элементами первого, самого нижнего, уровня являются элементарные данные: числа, символы, логические данные, знаки. Элементарные данные читаются программой целиком, доступ к их частям невозможен. Эти данные не являются непосредственным объектом информационного поиска, но в ряде случаев к ним должен быть обеспечен доступ. Так, например, в процессе поиска может возникнуть необходимость сравнения отдельных символов.
Элементарные данные каждого типа имеют определенную форму представления в ОП, для их хранения выделяется строго определенный объем памяти.
Элементом второго уровня является поле записи. Это последовательность элементарных данных, имеющая определенный смысл, но не имеющая смысловой завершенности. Данные, образующие отдельное поле записи, описывают соответствующий признак объекта.
Каждый признак объекта имеет наименование и значение. Так, например, для студентов, записи о которых хранятся в АИС, в качестве признаков могут использоваться номер студенческого билета, фамилия, средний балл успеваемости.
Используемый для идентификации записи в процессе обработки или поиска признак называется ключевым или ключом записи. Поле записи, содержащее ключ, называется ключевым полем. Если каждое из возможных значений ключа идентифицирует единственную запись, то такой ключ называют уникальным. Так, номер студенческого билета является уникальным ключом каждой записи массива, хранящего сведения о студентах данного вуза.
В записи могут предусматриваться дополнительные поля для хранения служебной информации: меток, ссылок, различных указателей.
Поля записи объединяются в группу данных (агрегат данных, групповое данное). Группа данных — элемент третьего уровня внутренней структуры записи — представляет собой поименованную совокупность элементов данных, рассматриваемую как единое целое.
Логическая запись — это поименованная совокупность полей или групп данных. Запись является отдельной логической единицей и имеет смысловую завершенность. Каждая запись описывает индивидуальный объект или класс объектов. Логическая запись является непосредственным предметом информационного поиска, основной единицей обработки информации.
Перечень полей, последовательность их расположения и взаимосвязь между ними составляют внутреннюю структуру записи, которая в конечном итоге определяет тип записи. Отдельные логические записи, описывающие определенный класс объектов, группируются в информационный массив. Массивы, хранящиеся на ВЗУ, называют файлами. Файл имеет имя и рассматривается как единое целое. Так, например, совокупность записей всех студентов учебной группы может рассматриваться как отдельный файл.
5. Типы структур данных
В процессе функционирования АИС записи и массивы претерпевают изменения. В массивы добавляются новые записи и удаляются ставшие ненужными. Процесс поддержания информационного массива в актуальном состоянии, заключающийся в добавлении (включении) и удалении (исключении) записей, называется ведением.
Отдельные характеристики объектов со временем могут изменяться, поэтому в записи необходимо вносить соответствующие изменения. Процесс внесения изменений в записи называют корректировкой или модификацией.
Для добавления, удаления или корректировки, для обработки информации, содержащейся в определенной записи, необходимо прежде всего найти нужную запись или место ее расположения в массиве. Поэтому операции поиска являются традиционными для СОХИ. Поиск записи должен осуществляться как можно быстрее, так как время поиска в значительной мере определяет общее время обработки информации.
Структуры данных делятся на линейные и нелинейные структуры. В нелинейных структурах в отличие от линейных связь между элементами структуры (записями) определяется отношениями подчинения или какими-либо логическими условиями. К линейным структурам данных относятся массив, стек, очередь, таблица. К нелинейным структурам принадлежат деревья, графы, многосвязные списки и списковые структуры.
Ряд структур данных после создания не позволяет включать или исключать записи, а допускает лишь их корректировку. Это структуры фиксированного размера. Структуры переменного размера позволяют включать и исключать записи, предоставляя информационному массиву возможность динамически изменяться.
Различные структуры данных предоставляют и различный доступ к своим элементам: в одних структурах доступ возможен к любому элементу, в других - к строго определенному. Ограничение в доступе сопровождается увеличением времени поиска нужных записей.
Структуры данных могут быть однородными и неоднородными. В однородных структурах все элементы представлены записями одного типа. В неоднородных структурах элементами одной структуры могут являться записи разных типов.
6. ПОСЛЕДОВАТЕЛЬНОЕ И СВЯЗАННОЕ ПРЕДСТАВЛЕНИЯ ДАННЫХ В ПАМЯТИ ЭВМ
При последовательном представлении данные в памяти машины размещаются в соседних последовательно расположенных ячейках. При этом физический порядок следования записей полностью соответствует логическому порядку, определяемому логической структурой, т.е. логическая структура поддерживается физическим порядком следования данных. Совокупность записей, размещенных в последовательно расположенных ячейках памяти, называют последовательным списком.
Для хранения информационного массива в виде последовательного списка в памяти выделяется блок свободных ячеек под максимальный размер массива. Записи, имеющие следующий логический порядок: Зап. В, Зап. А, Зап. F, Зап. С, 3an.7V, - разместятся в памяти машины так, как это показано на рис. 7.1, д. Вновь появившиеся записи размещаются в конце блока на свободном участке памяти. Если количество новых записей окажется больше, чем число свободных ячеек в зарезервированном блоке, то эти записи не удастся разместить в памяти. Если же записей окажется меньше, чем предполагалось, то память останется неиспользованной.
На рис. 7.1,6 добавлена запись (N +1) -я и удалены две записи: Зап. А и Зап. F. Ячейки 102 и 103 оказались свободными. Список, в котором содержатся свободные ячейки памяти, будет неплотным. Со временем значительное число ячеек может оказаться свободным. Для того чтобы эти участки памяти не пустовали, время от времени весь массив данных перезаписывается, при этом все записи передвигаются так, как это показано на рис. 7.1,в. Перезапись массива требует дополнительных затрат машинного времени.
Последовательное представление данных обычно используют для реализации линейных структур данных в тех случаях, когда предельный размер массива можно предсказать.
При связанном представлении в каждой записи предусматривается дополнительное поле, в котором размещается указатель (ссылка). Физический порядок следования записей в этом случае может не соответствовать логическому порядку. В машинной памяти записи располагаются в любых свободных ячейках и связываются между собой указателями, указывающими на место расположения записи, логически следующей за данной записью. Указатель часто интерпретируют как адрес ячейки памяти, в которой хранится следующая запись.
Структуры хранения, основанные на связанном представлении данных, называют связанными списками. Если каждая запись содержит лишь один указатель, то список односвязный, при большем числе указателей список многосвязный.
Пусть структура данных отображает следующую логическую последовательность записей: Зап. А, Зап. В, Зап. С, Зап. F. Записи размещены в ячейках памяти с адресами 01, 03, 05, 10. В поле указателя каждой записи размещается адрес связи (АС), определяющий адрес ячейки с логически следующей записью. Структура хранения массива представлена на рис. 7.2, д. На рисунке стрелками показан порядок чтения записей.
Одна из ячеек - головная — содержит указатель на ячейку с первой записью списка. В соответствии с указателями первым будет прочитано содержимое ячейки 01 (Зап. А), затем содержимое ячеек 05 (Зап. В), 03 (Зап. 0, 10 (Зап. F). Символ ©, помещенный в поле указателя последней записи списка, означает конец списка. Вместо символа 0 может быть использован любой другой элемент данных, который не воспримется системой как указатель.
Связанное представление обеспечивает широкие возможности для манипулирования данными и большую гибкость структуры хранения. Удаление и добавление новых записей в процессе ведения связанного списка не требует перезаписи элементов массива, а производится заменой соответствующих указателей так, чтобы логический порядок следования записей не нарушался.
При выполнении операции удаления исключаемая запись удаляется из массива вместе со всеми своими полями, в том числе и с полем указателя. При этом цепочка указателей разрывается и доступ к следующим записям списка становится невозможным. Указатель записи, логически предшествующей исключаемой, называют "висящим", так как он указывает на несуществующую запись и цепочка записей списка на нем обрывается. Чтобы логическая цепочка следования записей не разрушилась, перед исключением записи следует произвести замену указателей. При этом значение указателя исключаемой записи заносится в поле указателя логически предшествующей записи.
Возможен и другой способ удаления записей, когда исключаемая запись помечается специальным символом исключения, физически оставаясь в списке. В этом случае возможен доступ к полю указателя, цепочка записей не разрушается и замена указателей не требуется.
Односвязный список можно организовать в виде замкнутого кольца рис. 7.3) . В этом случае указателем последней записи будет адрес первой. Такой список называют еще циклическим. Просмотр циклического списка можно начинать с любой ячейки. Условием окончания просмотра может быть либо совпадение числа просмотренных записей с общим числом записей в списке, либо совпадение указателя с адресом первой прочитанной ячейки. В последнем случае адрес первой прочитанной ячейки должен запоминаться и каждый раз при чтении очередной записи сравниваться с ее указателем.
Связанное представление данных используется для хранения нелинейных структур данных, а также для реализации линейных структур в тех случаях, когда заранее не известен предельный размер информационного массива (следовательно, непредсказуемы требования на размер памяти); информационный массив часто подвергается изменениям, над данными выполняются многочисленные операции добавления и удаления.
Связанное представление приводит к дополнительному расходу машинной памяти под указатели.
В ряде задач необходимо иметь возможность продвижения по связанному списку в обоих направлениях. Для этого в каждый элемент списка вводится дополнительный указатель, задающий продвижение по списку в обратном направлении. Такой список называется двунаправленным. В поле указателя заносится адрес ячейки с записью, логически предшествующей данной записи (рис. 7.4,д). Головная ячейка содержит в этом случае указатели на первую и последнюю ячейки списка. Поиск в двунаправленном списке возможен как с начала, так и с конца списка.
Для реализации связанного представления данных язык программирования должен располагать определенными средствами, а именно иметь данные типа "указатель".
Пусть структура данных определена как массив М(1). Для определения порядка чтения элементов массива, не совпадающего с физическим порядком их следования, можно организовать вспомогательный вектор указателей N(J), элементы которого — целые числа — определяют порядковые но-
мера (индексы) записей основного массива. На рис. 7.5 изображены два одномерных массива: массив указателей N(J) и основной массив записей М(Г), а также моделируемый список. Процедура чтения основного массива организуется с учетом того, что / = N(J). Таким образом, вектор Л^(/) при изменении значения J от 1 до 4 задает следующий порядок чтения записей основного массива: Зап. А, Зап. В, Зап. С, Зап. D.