13.Таблица

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

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

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

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

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

Способы хранения таблицы.

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

По мере роста таблицы А после того как выделенный под нее блок памяти окажется заполненным для таблица А выделяется новый блок памяти он связывается указателем с первым блоком. После заполнения таблицы В под нее также выделяется новый блок памяти, такие таблицы могут расти как угодно долго.

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

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