ОБЩИЙ ВИД ТАБЛИЦ

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

Каждый элемент таблицы обычно занимает более одного машинного слова. Если элемент занимает K слов памяти и нужно хранить N элементов, то для организации таблицы необходимо иметь K*N слов памяти. Расположить информацию можно двумя способами:

1. Каждый элемент поместить в K последовательных слов и иметь таблицу из K*N слов.

2. Иметь K таблиц, с именами T1, T2,..., Tk из N слов в каждой таблице. Весь i –ый элемент будет при этом находиться в словах T1 _i, T2 _i,..., Tk _i.

Вопрос выбора между этими двумя методами – это только вопрос удобства программирования.

В нашем случае аргументами таблицы являются символы или идентификаторы, а значениями их характеристики (атрибуты). Так как число символов в идентификаторе может быть самым разным, то как уже отмечалось, в аргументе, обычно, вместо самого идентификатора помещают указатель на идентификатор. Это сохраняет фиксированный размер аргумента. Сами же идентификаторы хранятся в специальном списке строк. Число литер в каждом идентификаторе может храниться как часть аргумента или в списке идентификаторов прямо перед ним. На рисунке 3.2 показаны оба эти способа на примере таблицы, содержащей элементы для идентификаторов I, max и J.

Если число элементов в поле значения переменно, то в этом поле таблицы также следует помещать указатель на эту информацию. Формат таблицы лучше оставлять фиксированным.

Рассмотрим существующие способы организации таблиц и оценим время требуемое на поиск элементов и их добавление.

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