Таблицы. В данном разделе рассмотрены плоские таблицы с фиксированным числом столбцов
В данном разделе рассмотрены плоские таблицы с фиксированным числом столбцов. Примером такой таблицы может служить телефонный справочник:
Улица | Дом | Кв. | Фамилия И.О. | Телефон |
Коммуны | Петров П.П. | |||
Советская | Сидоров.С.С. |
Таблицу идентификаторов строит любой компилятор:
Идентификатор | Тип | Длина | Адрес |
Alpha | int | 0xEA45345 |
Мы не рассматриваем таблиц с двумя входами типа таблицы умножения (рис.30), в которых искомая величина лежит на перекрестии строки и столбца. Строку таблицы называют также записью или кортежем. Столбец также называют полем или атрибутом. Поле или группа полей, по которым выполняется поиск данных в таблице, называется ключом. Если в таблице не может существовать более одной записи с данным значением ключа, то такой ключ называют первичным. Другие ключи называют непервичными или вторичными. В телефонном справочнике роль первичного ключа может играть, например, номер телефона. Фамилия не может быть первичным ключом, так как возможно существование однофамильцев. Все операции в таблице задаются по отношению к ключу, а выполняются над всей записью. К типичным операциям над таблицей относятся:
- включение: дана пара ключ - данные. Требуется включить запись в таблицу так, что впоследствии ее можно было найти по ключу.
- поиск. Дан ключ, требуется найти запись.
- модификация: дан ключ, и новые значения изменяемых полей. Требуется найти запись и изменить данные.
- удаление. Дан ключ, требуется найти и удалить запись.
Как видно, во всех случаях, прежде чем выполнить операцию, требуется сначала найти запись. Это относится и к операции включения, так как для того, чтобы добавить запись в таблицу, требуется найти место вставки. Следует различать удачный и неудачный поиск (поиск того, чего в таблице нет), а также поиск единственной записи (по первичному ключу) и поиск многих записей, удовлетворяющих критерию поиска. Эффективность этих операций, как правило, различается. Мы будем рассматривать четыре основных способа организации таблиц:
- последовательные
- сортированные
- древовидные
- рассеянные (они же рандомизированные или hash – таблицы)
Дата добавления: 2014-12-02; просмотров: 890;