Внутренняя структура записи

Логическая запись состоит из отдельных элементов, связанных опре­деленными отношениями, и имеет многоуровневую структуру.

Элементами первого, самого нижнего, уровня являются элементар­ные данные: числа, символы, логические данные, знаки. Элементарные данные читаются программой целиком, доступ к их частям невозможен. Эти данные не являются непосредственным объектом информационного поиска, но в ряде случаев к ним должен быть обеспечен доступ. Так, на­пример, в процессе поиска может возникнуть необходимость сравнения отдельных символов.

Элементарные данные каждого типа имеют определенную форму представления в ОП, для их хранения выделяется строго определенный объем памяти.

Элементом второго уровня является поле записи. Это последова­тельность элементарных данных, имеющая определенный смысл, но не имеющая смысловой завершенности. Данные, образующие отдельное поле записи, описывают соответствующий признак объекта.

Каждый признак объекта имеет наименование и значение. Так, например, для студентов, записи о которых хранятся в АИС, в качестве признаков могут использоваться номер студенческого билета, фамилия, средний балл успеваемости.

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

В записи могут предусматриваться дополнительные поля для хране­ния служебной информации: меток, ссылок, различных указателей.

Поля записи объединяются в группу данных (агрегат данных, груп­повое данное). Группа данных — элемент третьего уровня внутренней структуры записи — представляет собой поименованную совокупность элементов данных, рассматриваемую как единое целое.

Логическая запись — это поименованная совокупность полей или групп данных. Запись является отдельной логической единицей и имеет смысловую завершенность. Каждая запись описывает индивидуальный объект или класс объектов. Логическая запись является непосредствен­ным предметом информационного поиска, основной единицей обработки информации.

Перечень полей, последовательность их расположения и взаимосвязь между ними составляют внутреннюю структуру записи, которая в конеч­ном итоге определяет тип записи. Отдельные логические записи, описывающие определенный класс объектов, группируются в информационный массив. Массивы, хранящи­еся на ВЗУ, называют файлами. Файл имеет имя и рассматривается как единое целое. Так, например, совокупность записей всех студентов учеб­ной группы может рассматриваться как отдельный файл.

ТИПЫСТРУКТУР ДАННЫХ

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

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

Для добавления, удаления или корректировки, для обработки информации, содержащейся в определенной записи, необходимо прежде всего найти нужную запись или место ее расположения в массиве. Поэто­му операции поиска являются традиционными для СОХИ. Поиск записи должен осуществляться как можно быстрее, так как время поиска в зна­чительной мере определяет общее время обработки информации.

Структуры данных делятся на линейные и нелинейные структуры. В нелинейных структурах в отличие от линейных связь между элемента­ми структуры (записями) определяется отношениями подчинения или какими-либо логическими условиями. К линейным структурам данных относятся массив, стек, очередь, таблица. К нелинейным структурам при­надлежат деревья, графы, многосвязные списки и списковые структуры.

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

Различные структуры данных предоставляют и различный доступ к своим элементам: в одних структурах доступ возможен к любому элементу, в других - к строго определенному. Ограничение в доступе сопровождается увеличением времени поиска нужных записей.

Структуры данных могут быть однородными и неоднородными. В однородных структурах все элементы представлены записями одного типа. В неоднородных структурах элементами одной структуры могут являться записи разных типов.

 

 

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.

Массивы

Массив — это линейная структура данных фиксированного размера, реализуемая с использованием последовательного представления дан­ных. Понятие массива как структуры данных не тождественно понятию информационного массива, определяющему совокупность данных, обра­батываемых АИС.

Каждый элемент массива идентифицируется одним или несколькими индексами. Индекс — это целое число, значение которого определяет позицию соответствующего элемента в массиве и используется для осу­ществления доступа к этому элементу. Отдельные элементы массива могут изменяться (т.е. записи могут модифицироваться), но общее число элементов массива всегда остается неизменным; следовательно, для массивов нет операций добавления и удаления.

В зависимости от числа индексов, идентифицирующих каждый эле­мент массива, различают одномерные и многомерные массивы.

Одномерный массив называется вектором. Вектор А = {А (1)А (2)... A(I)..A(N) } — это последовательность элементов (записей), размещен­ных в смежных ячейках памяти. Единственный индекс вектора указы­вает позицию каждого элемента в последовательности.

Адрес первого байта, выделенного для первого элемента вектора, называется адресом базы вектора. Вектор в целом определяется адресом базы, размером элементов и их числом или размером элементов и диапа­зоном изменения индекса (рис. 8.1). Если L₀ — адрес первого байта в блоке памяти, выделенном для хранения вектора, с — число байтов, выделенное для хранения каждого элемента, то адрес любого i-го элемен­та будет

1ос(Аi.) =L₀ +с(i-1)

Двумерный массив называется матрицей. Каждый элемент матрицы определен двумя индексами. В общем случае массив может иметь любую размерность, т.е. являться многомерным. Многомерный массив может быть представлен эквивалентным одномерным массивом. Например, матрицу можно рассматривать как вектор, элементы которого, в свою очередь, являются векторами. При этом матрица может рассматриваться и храниться в памяти ЭВМ как "строка строк" и как "строка столбцов". Хранение элементов матрицы в такой последовательности называют раз­мещением по строкам

При размещении по строкам адрес матричного элемента А (i, j) опре­деляется выражением

loc(Aij) =L₀+ cm(i - 1) + с (j - 1) где m — число столбцов.

В общем случае массив может иметь любую размерность. Для n-мер­ного массива указывается число размерностей, а также верхняя и ниж­няя границы диапазона изменения индексов.

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

Из одномерных неоднородных массивов могут быть организованы многомерные неоднородные массивы, например массив, описывающий всех студентов группы.

 

СТЕКИ

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

Особенность стековой структуры в том, что доступ к элементам, включение и исключение элементов возможны только с одного конца структуры — с вершины стека. Поэтому первым будет прочитан или выбран тот элемент, который включался в стек последним. Информация в такой структуре обрабатывается по принципу " последним пришел, первым ушел ". Структуру стека иногда называют структурой типа LIFO.

Структура стека явля­ется структурой данных с ограниченным доступом, так как доступ разрешается только к элементу, находя­щемуся в вершине стека. Этот элемент называется те­кущим. Информацию о пози­ции текущего элемента стека хранит указатель вершины стека (УВС), размещаемый обычно в головной ячейке стека.

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

Доступ к стеку может быть организован так, чтобы значение ука­зателя вершины оставалось неизменным в течение всего времени сущест­вования стека. В этом случае доступ осуществляется всегда к одной и той же ячейке блока памяти, зарезервированного под стек. На эту ячейку

устанавливается указа­тель вершины, в ней хра­нится текущий (верхний) элемент стека. При вклю­чении или исключении элемента все остальные элементы стека переме­щаются вниз или вверх соответственно внутри блока памяти (рис. 8.3). В этом случае операцию включения иногда называют проталкиванием, а операцию исключе­ния "выталкиванием".

Недостаток последовательного представления стека состоит в том, что всегда остается опасность переполнения стека; в противном случае часть зарезервированной памяти остается неиспользованной.

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

Структура стека удобна в тех случаях, когда требуется быстрое выполнение операций включения и исключения без оценки содержательного смыс­ла данных. Алгоритм, управляющий включением осво­бодившихся ячеек в стек свободной памяти, часто называют "сборщи­ком мусора". Стековые структуры широко применяются в трансляторах при реализации вложенных подпрограмм и многоуровневых прерываний, а также при решении задач, алгоритмы которых лучше всего описываются рекурсивным методом.

 

Очередь

Очередь - это линейная структура переменного размера. Исключение элементов из очереди допускается с одного конца - с начала очереди. Включение элементов возможно лишь в противоположный конец — в конец очереди. Данные в такой структуре обрабатываются в порядке их поступления по принципу: "первым пришел, первым ушел". В литерату­ре структуру очереди называют структурой типа FIFO

Доступ к элементам очереди осуществляется по указателям начала и конца. Указатель начала указывает на элемент очереди, который пер­вым будет исключаться или читаться. Указатель конца устанавливается на свободную ячейку памяти, следующую за последней записью в очере­ди. Именно в эту ячейку разместится вновь пришедшая запись, т.е. новый элемент очереди.

Для реализации структуры очереди в памяти ЭВМ используется как последовательное, так и связанное представление данных. При последо­вательном представлении под очередь, так же как и под стек, резерви­руется блок памяти, внутри которого очередь может расти и сокра­щаться включением каждого нового элемента указатель конца изме­няется на единицу. Когда в результате включения новых элементов указатель конца очереди достигает конца зарезервированного блока па­мяти, он перебрасывается на начало блока. Если указатель конца дого­няет указатель начала, то это означает, что блок памяти переполнен.

При исключении элемента указатель начала изменяется на единицу. Если указатель начала совпадает с указателем конца, то очередь пуста.

При связанном представлении очереди предварительного резервиро­вания памяти не требуется. Записи, образующие очередь, размещаются в любых свободных ячейках памяти и связываются между собой указа­телями (рис. 8.6). Такая очередь может расти неограниченно. При вклю­чении и исключении элементов изменяются лишь значения указателей начала и конца очереди и значения указателей связи (АС).

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

 

Таблица

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

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

Обычно записи таблицы упорядочивают по какому-либо принципу (например, по возрастанию значения ключа или по частоте обращения к записям) и хранят в виде упорядоченного последовательного списка. В этом случае поиск может быть ускорен за счет использо­вания специальных методов. Однако ведение упорядоченного последова­тельного списка усложняется и сопровождается рядом дополнительных процедур. Так, например, для включения в последовательный упорядо­ченный список новой табличной записи необходимо определить место, которое должна занять в списке новая запись в соответствии со значе­нием своего ключа. Соответствующая ячейка памяти должна быть осво­бождена, для чего все записи передвигаются на одну ячейку, т.е. часть массива перезаписывается.

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

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

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

Для хранения таблиц часто используется способ размещения в памя­ти, обеспечивающий прямой доступ к каждой записи таблицы.

Если все N записей таблицы имеют разные значения ключей Ki и най­дена функция f{Ki), такая, что для любого 0 < i < N f(Ki) принимает целое значение от 0 до т, то значение f(Ki) можно рассматривать как адрес ячейки памяти, в которой размещена запись с ключом Ki. Функция f(Ki) называется функцией преобразования или, иначе, функцией расста­новки. Доступ к любой записи осуществляется путем непосредственного вычисления по значению ключа адреса хранения этой записи. Время поиска в таких таблицах минимально и определяется в основном време­нем вычисления f(Ki).