Таблицы. В данном разделе рассмотрены плоские таблицы с фиксированным числом столбцов

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

 

Улица Дом Кв. Фамилия И.О. Телефон
Коммуны Петров П.П.
Советская Сидоров.С.С.

 

Таблицу идентификаторов строит любой компилятор:

Идентификатор Тип Длина Адрес
Alpha int 0xEA45345

 

Мы не рассматриваем таблиц с двумя входами типа таблицы умножения (рис.30), в которых искомая величина лежит на перекрестии строки и столбца. Строку таблицы называют также записью или кортежем. Столбец также называют полем или атрибутом. Поле или группа полей, по которым выполняется поиск данных в таблице, называется ключом. Если в таблице не может суще­ство­вать более одной записи с данным значением ключа, то такой ключ называют первичным. Другие ключи называют непервичными или вторичными. В телефонном справочнике роль первичного ключа может играть, например, номер телефона. Фамилия не может быть первичным ключом, так как возможно существование одно­фамильцев. Все операции в таблице задаются по отношению к ключу, а выполняются над всей записью. К типичным операциям над таблицей относятся:

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

- поиск. Дан ключ, требуется найти запись.

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

- удаление. Дан ключ, требуется найти и удалить запись.

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

- последовательные

- сортированные

- древовидные

- рассеянные (они же рандомизированные или hash – таблицы)








Дата добавления: 2014-12-02; просмотров: 898;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.